Efficient fair queueing algorithms for packet-switched networks

Abstract

Abslmcl-Although wcightcd fair queueing (WFQ) has been re- gnrdcd ns an ideal scheduling algorithm in terms of its combined dclny bound and proportional fairness properties, its asymp- totic time complexity increases linearly with the number of sessions scrviccd by the scheduler, thus limiting its use in high- speed networks. An algorithm that combines the delay and fairness bounds of WFQ with O(1) timestamp computations had rcmnincd clusivc so far. In this paper we present two novel scheduling nlgorithms that have O( 1) complexity for timestamp computations and provide the same bounds on end-to-end delay nnd buffer rcquircmcnts as those of WFQ. The first algorithm, flrrrrtc-based fair qucueing VE'Q), uses a framing mechanism to pcriodicnlly recalibrate a global variable tracking the progress oP work in the system, limiting any short-term unfairness to within n frnme period. The second algorithm, starring potential- bnsc~ij2ir qrrerrcirtg (SPFQ), performs the recalibration at packet boundaries, resulting in improved fairness while still maintaining the 0(l) timcstnmp computations. Both algorithms are based on the general framework of rate-proportional servers (RPS's) lntroduccd in (ll). The algorithms may be used in both general pnckct networks with variable packet sizes and in asynchronous transfer mode (ATM) networks.