Opportunistic scheduling

The half-duplex nature of IEEE 802.11 devices requires the the sender to wait for an ACK signal after transmitting each frame. If the transmitting station does not receive the ACK it reschedules the transmission like if a collision occurred. If a node sustains repeated unsuccessful transmission it may degrade its transmission bit-rate in order to employ more robust but less efficient modulation schemes.

As a result, since the CSMA/CA algorithm gives to each node the same channel access probability, nodes transmitting at low bit-rates will capture the wireless channel for long periods of time at the expenses of the nodes transmitting at higher bit-rates. Such behavior combined with the FCFS scheduling policy implemented in most commercial AP lead to the well known IEEE 802.11 performance anomaly.

Our scheme aims at providing intra-cell airtime fairness as opposed to the bandwidth fairness provided by traditional scheduling policy, i.e. Fair Queuing or, in case of equally sized data packets, Round-Robin. The proposed Airtime Deficit Round Robin (ADRR) scheduler serves packets at the head of each nonempty queue which deficit counter greater than the expected frame transmission time.

A frame whose transmission time exceed the counter is held back until the next visit of the scheduler and the deficit counter is increased by the quantum value. The deficit counter is decreased by the expected transmission time of each frame being served. The building blocks the scheduler and their relationships are sketched in the next figure.

Incoming frames are first classified according to the destination address and then fed to a suitable buffer queue. The A-DRR scheduler exploits the ETX metric in order to estimate the channel time spent serving each nonempty queue.

Here follows the pseudo-code of the enqueue process:

1: for each incoming packet p do
2:   i = p.NextHop()
3:   if i not in QueueP ool then
4:     QueuePool.PushBack(i)
5:   end if
6:   QueuePool(i).Enqueue(p)
7: end for

and the pseudo-code of the dequeue process:

1: while true do
2:   if QueuP ool is not empty then
3:     i = QueueP ool.PullFront()
4:     DC(i) = DC(i) + Q
5:     while (DC(i) > 0) and i is not empty do
6:       airtime = ComputeTxAirtime(Head(i))
7:       if airtime < DC(i) then
8:         DC(i) = DC(i) - airtime
9:         p = QueueP ool(i).Dequeue()
10:        Send(p)
11:      else
12:        Break
13:      end if
14:    end while
15:    if i is not empty then
16:      QueueP ool.PushBack(i)
17:    end if
18:  end if
19: end while

Variables and data structure exploited by both algorithms are the following:

• QueuePool, Array containing currently backlogged queues
• Q, Quantum value
• DCi, Deficit counter for queue i

The ADRR scheduler presented in this section is implemented as part of our QoS Provisioning framework.

R. Riggio, Daniele Miorandi, and I. Chlamtac
Airtime Deficit Round Robin (ADRR) Packet Scheduling Algorithm (meshtech2008.pdf)
in Proc. of MeshTech 2008, Atlanta, Georgia, USA.