Packet scheduling is the process of deciding which packet to forward next into the communication link of a network node. Packet scheduling is often realized by annotating packets with time stamps (also referred to as ‘tags’, in this document) and subsequently sorting these packets according to their annotated time stamp values. While a number of approaches have been proposed that address the calculation of packet tags in scheduling algorithms, little work has been done addressing the complexity associated with sorting tagged packets. Existing approaches make a number of restrictive assumptions about packet sizes and allocated rates characterizing scheduled sessions or suffer from significant latency, space requirement, or processing power requirement. Existing approaches to sorting can be grouped into three categories: the first category includes schemes that use general purpose data structures for sorting packets and for extracting the packet with a minimum tag. These approaches make no assumptions about the incoming sessions. The most representative of these schemes are: (i) the binomial heaps; (ii) the Fibonacci heaps; (iii) the Van Emde Boas trees; (iv) the tree of comparators; and (v) the calendar queue. While these approaches demonstrate good asymptotic complexity for extracting the minimum tag packet (e.g., Fibonacci heaps are associated with θ(1) complexity) these algorithms are usually inefficient to implement due to the fact that their complexity functions involve large constants.
A second category of algorithms makes assumptions about sessions. These approaches usually group sessions according to their packet sizes and allocated rates. These approaches reduce the overall complexity of the enqueuing process from sorting tags across sessions to sorting tags across groups. Such approaches include: (i) the approximate sorting approach; (ii) the sorting bins scheme from AT&T; and (iii) the connection grouping scheme from Carnegie Mellon University (CMU).
FIG. 1 illustrates a prior art sorting scheme using a tree of comparators 100. The tree of comparators 100, divides the number of sessions into groups. For each group, a comparator algorithm selects a head-of-line packet with a minimum tag. The tagged packets selected from a first stage of comparators 110 are further divided into groups and passed into a second stage of comparators 130. The second stage of comparators 130 further reduces the number of candidate packets which may be annotated with a minimum tag. The process is continued until only one packet remains at the final stages of comparators 150. When a new head-of-line packet enters the system, comparisons do not need to be made across all sessions but only within a small number of groups, equal to the height of the tree. This approach is associated with logarithmic complexity (i.e., O(log N)) as a function of the number of sessions in the system N.
FIG. 2 illustrates a prior art sorting scheme using a calendar queue 200. The calendar queue 200 maintains an array of pointers 210 to packets, where each entry in the array is indexed by a separate time stamp value. Time stamp values may be consecutive. Packets are ideally inserted in O(1) time in a queue 220 during the enqueuing process and a scheduler 230 selects the next packet for transmission in a single step, at best case. The main drawback of the calendar queue 200 is its memory storage requirement. Memory explosion may be caused by the need to store a separate entry in the array for every distinct time stamp value a packet may be associated with. If the range of time stamp values is large, then the calendar queue 200 may require a significant amount of storage space.
FIG. 3 illustrates a prior art sorting scheme using approximate sorting 300. In this approach, the range of time stamp values is divided into smaller ranges and queues 320 are created for storing packets. Packets annotated with time stamp values in the same range are stored in the same queue 320. Inside, the queue packets are stored in a FIFO order. The scheduler prioritizes queues but not packets within queues. This approach is called “approximate sorting” since packets are coarsely classified into groups of different time stamp ranges. This approach has the benefit of simplifying both the enqueuing and the dequeuing processes at the expense of the level of fairness characterizing the scheduler. A scheduling algorithm that uses approximate sorting is not fair over a short time scale because the correct transmission order of packets (i.e., the transmission order according to Generalized Processor Sharing (GPS)) is violated.
Other schemes have been proposed that impose a number of restrictive assumptions on the size of packets and range of rates allocated to sessions. For example, ATM networks carry packets of fixed sizes and hence ATM network solutions can be thought of as simplifying the enqueuing and dequeuing process significantly.