I found a bug in a backoff counting mechanism in 802_11 MAC protocol.  It is counted in a non discrete manner.

According to 802.11 standard (section 9.2.5.2- Backoff procedure):
"A STA performing the backoff procedure shall use the CS mechanism (see 9.2.1) to determine whether there is activity during each backoff slot. If no medium activity is indicated for the duration of a particular backoff slot, then the backoff procedure shall decrement its backoff time by aSlotTime.
If the medium is determined to be busy at any time during a backoff slot, then the backoff procedure is suspended; that is, the backoff timer shall not decrement for that slot. The medium shall be determined to be idle for the duration of a DIFS period or EIFS, as appropriate (see 9.2.3), before the backoff procedure is allowed to resume. Transmission shall commence when the Backoff Timer reaches zero."

That is - backoff should be counted in discrete slots. Moreover, if the backoff should be suspended during some slot, this slot should not be counted.

In SWANS, the backoff is generally counted in discrete slot. However, in case the medium is determined to be busy at any time during a backoff slot, current SWANS implementation simply stops the backoff timer in the middle of this slot. Later, this timer will be resumed from the point it stopped. This means that SWANS decrements the backoff timer for part of the slot, while it should not decrement this slot at all. As a result, SWANS implementation tends to create an unslotted backoff counting, as opposed to the standard, which aims in slotted counting. This resulted in more collisions and in reduced throughput, basically since unslotted medium access (Unslotted Aloha) has lower throughput than a slotted one (Slotted Aloha).

This bug is originated from the following method (this is the original code): file Mac802_11.java:

private void pauseBackoff()
{
        bo -= JistAPI.getTime() - boStart; // bo now is what is left to backoff
        Util.assertion(bo>=0);
}

The fix is:

private void pauseBackoff()
{
        long alreadyPassedSlots = (long)(Math.floor( ((JistAPI.getTime()-boStart)/SLOT_TIME) ));
        bo -= alreadyPassedSlots * SLOT_TIME;  // bo now is what is left to backoff, but in discrete slots
        Util.assertion(bo>=0);
        Util.assertion( (bo%SLOT_TIME) == 0 );
}

 

The fix mimics the same implementation in NS2 simulator, in which backoff is paused correctly.
For example, see an older (prio to version 2.33) version of NS2, file mac/mac-timers.cc, function BackoffTimer::pause() or the latest version 2.33, file mac/mac-802_11Ext.cc, function void BackoffTimer_t::pause() .

void BackoffTimer_t::pause()
{
        remainingSlots_-=(int)(floor((Scheduler::instance().clock()-startTime)/tSlot));
        if (status()==TIMER_PENDING)
            cancel();
        startTime = -1.0;
}

void BackoffTimer_t::run()
{   
        if (remainingSlots_ ==0) {
            remainingSlots_=-1;
            bkmgr_->handleBackoffTimer();
        } else {
            startTime = Scheduler::instance().clock();
            sched(remainingSlots_*tSlot);
        }
}

 

Gabriel Kliot

09/16/2008