12/01/1995 09:00 AM
Computer Engineering
Weighted Fair Queueing is considered as the ideal traffic scheduling algorithm in terms of its delay and fairness properties. Timestamp computations in a Weighted Fair Queueing scheduler serving N sessions have a time complexity of 0(N) per packet-transmission time, making its implementation difficult. Efforts in the past to simplify the implementation of Weighted Fair Queueing, such as Self-Clocked Fair Queueing, have resulted in degrading its isolation properties, thus affecting the delay bound. In this paper we present a class of scheduling algorithms - called Rate-Proportional Servers (RPS) - with bounds on end-to-end delays, buffer requirements and internal traffic burstiness equal to those of Weighted Fair Queueing. This class of algorithms is based on the notion of the potential associated with each connection sharing the same outgoing link, as well as, the system potential that tracks the progress of work in the system. We show that, depending on the implementation, different algorithms in the RPS class may have significantly different fairness properties. Network designers can use this methodology to implement efficient fair- queueing algorithms, balancing their fairness with implementation complexity. This work is completed in the sequel of this paper, where we present detailed implementations of two novel traffic scheduling algorithms with 0(1) timestamp computations, that exhibit the same delay and fairness properties as those of Weighted Fair Queueing.
