DRR-Based Algorithm | QoS and Fairness in WiMAX

DRR is a scheduling algorithm that approximates less strictly the fairness performance of GPS, but with a low computational complexity, which is O(1) processing work per packet. It uses round-robin service with a quantum of service assigned to each queue. Differently from traditional round-robin scheme, if a queue was not able to send a packet in a given round because of its large packet size, the remainder of the quantum (deficit) is added to the quantum for the next round. The use of the deficit variable makes DRR suitable to the management of queues with different packet sizes.

DRR maintains for each queue q_i (i = 1, …, 3) a deficit counter DC_i and a quantum Q_i measured in bytes. At the beginning, all DC_i variables are set to zero. The algorithm works serving queues in turn; each time a queue is selected, its DC_i is incremented by the Q_i value; then packets are sent out if their size (in bytes) is less than DC_i. Each time a packet is extracted from queue, DC_i is decremented by the packet size. To avoid examining empty queues, the scheduler keeps an auxiliary list, active list, which includes the indices of queues that contain at least one packet. The round-robin selector points to the head of the active list. Whenever a packet arrives to a previously empty queue, the index of that queue is inserted into the active list.