Rate-proportional servers: A design methodology for fair queueing algorithms

Generalized processor shoring (GPS) has been considered as an ideal scheduling discipline based on its end-to-end delay bounds and fairness properties. Until recently, emulation of GPS in a packet server has been regarded as the ideal means of designing a packet-level scheduling algorithm to obtain low delay bounds and bounded unfairness. Strict emulation of GPS, as required in the weighted fair queueing (WFQ) scheduler, however, incurs a time-complexity of O(N) where N is the number of sessions sharing the link. Efforts in the past to simplify the implementation of WFQ, such as self-clocked fair queueing (SCFQ), have resulted in degrading its isolation properties, thus affecting the delay bound. In this paper we present a methodology for the design of scheduling algorithms that provide the same end-to-end delay bound as that of WFQ and bounded unfairness without the complexity of GPS emulation. The resulting class of algorithms, called rate-proportional servers (RPS's), are based on isolating scheduler properties that give rise to ideal delay and fairness behaviors. Network designers can use this methodology to construct efficient fair-queueing algorithms, balancing their fairness with implementation complexity. This work is completed in a sequel to this paper, where we present the detailed design and implementation of two novel scheduling algorithms based on the RPS framework.