EFFICIENT FAIR QUEUING ALGORITHMS FOR PACKET-SWITCHED NETWORKS

Although weighted fair queueing (WFQ) has been regarded as an ideal sc heduling algorithm in terms of its combined delay bound and proportion al fairness properties, its asymptotic time complexity increases linea rly with the number of sessions serviced by the scheduler, thus limiti ng its use in highspeed networks. An algorithm that combines the delay and fairness bounds of WFQ with O(1) timestamp computations had remai ned elusive so far. In this paper we present two novel scheduling algo rithms that have O(1) complexity for timestamp computations and provid e the same bounds on end-to-end delay and buffer requirements as those of WFQ. The first algorithm, frame-based fair queueing (FFQ), uses a framing mechanism to periodically recalibrate a global variable tracki ng the progress of work in the system, limiting any short-term unfairn ess to within a frame period. The second algorithm, starting potential -based fair queueing (SPFQ), performs the recalibration at packet boun daries, resulting in improved fairness while still maintaining the O(1 ) timestamp computations. Both algorithms are based on the general fra mework of rate-proportional servers (RPS's) introduced in [11], The al gorithms may be used in both general packet networks with variable pac ket sizes and in asynchronous transfer mode (ATM) networks.