Fair Queuing Algorithms to Acheive QoS
EION Inc. White Paper Series
October 10, 2005
Providing fair and stable service to competing best-effort flows over a bottleneck router/link pair is a major challenge in providing quality of service in today’s Internet. Numerous scheduling algorithms have been proposed to provide isolation and bandwidth guarantees to the competing flows. In this paper, 4 algorithms: WFQ, SPFQ, DRR, QLWFQ are introduced and their performance especially on fairness and flow isolation are analyzed both theoretically and by simulation. A novel scheduling algorithm: sorted-priority based deficit round robin is then developed in this paper to improve the performance of DRR. Theoretical analysis and simulation results are given to show the improvement. The new algorithm has a O(logN) complexity and provides the best fairness bound and a comparable delay bound with WFQ and SPFQ. The QLWFQ is an ATM scheduler. To extend its usage to the generic packet switching networks, the scheduler is modified in this paper to adapt to packets with different lengths. Theoretical analysis shows the revised algorithm has similar performance to DRR.
To obtain a copy of this white paper, please contact: firstname.lastname@example.org .