Thursday, December 2, 2010

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.


Add a note hereDRR maintains for each queue qi (i = 1, , 3) a deficit counter DCi and a quantum Qi measured in bytes. At the beginning, all DCi variables are set to zero. The algorithm works serving queues in turn; each time a queue is selected, its DCi is incremented by the Qi value; then packets are sent out if their size (in bytes) is less than DCi. Each time a packet is extracted from queue, DCi 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.
Add a note here
Related Posts with Thumbnails