Method and apparatus for guaranteeing data transfer rates and delays in data packet networks using logarithmic calendar queues

Abstract

The total implementation complexity of packet schedulers which aim at approximating the Generalized Processor Sharing (GPS) policy is the combination of the complexity of their system-potential function and the complexity involved in sorting the timestamps in order to select the packet with minimum timestamp for transmission. Given that several scheduling algorithms which use a system-potential function of O(1) complexity have been introduced (among them, the Minimum-Delay Self-Clocked Fair Queuing (MD-SCFQ) algorithm achieves optimal delay and excellent fairness properties), the major contribution to the total complexity comes from the task of sorting the timestamps every time a packet is transmitted or received, which is common to all GPS-related schedulers. A method and an apparatus, called the Logarithmic Calendar Queue (LCQ), is disclosed which can achieve a dramatic reduction of the implementation complexity of sorting the timestamps in a GPS-related scheduler, at the cost of very small and controllable degradation of the guaranteed delay bounds. This is achieved by using a plurality of calendar subqueues, each subqueue associated with different granularity for the representation of timestamp values.