Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-10-30
2002-05-28
Vincent, David R. (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S389000
Reexamination Certificate
active
06396843
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to methods and apparatuses for sorting timestamps in packet networks, and more particularly to a method and an apparatus for sorting timestamps in a system for scheduling packets in a packet network to guarantee data transfer rates to a data source and data transfer delays from a data source to a destination.
BACKGROUND OF THE INVENTION
The implementation of Per-Virtual-Connection (Per-VC) schedulers which aim at approximating the Generalized Processor-Sharing (GPS) policy, as described in A. K. Parekh and R. G. Gallager, “A Generalized Processor-Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case,” IEEE/ACM TRANSACTIONS ON NETWORKING, June 1993, pp. 344-357, which is incorporated herein by reference, is a central issue in next-generation switching systems for broadband packet networks, such as Asynchronous Transfer Mode (ATM) switches and Internet Protocol (IP) routers. In a market arena in which the cost targets are precipitously dropping, it is desirable to minimize the complexity involved in schedulers, and to make the cost differential with respect to systems with less sophisticated scheduling as small as possible.
The total implementation complexity of these GPS-related scheduling algorithms is a combination of the complexity of the function used as the system potential to compute the timestamps for the packets in the system, and the complexity involved in sorting the timestamps in order to select the packet with the minimum timestamp for transmission.
In recent years, several scheduling algorithms have been introduced, which algorithms use a system-potential function of minimal complexity. Examples are Self-Clocked Fair Queuing (SCFQ), as described in S. J. Golestani, “A Self-Clocked Fair Queuing Scheme for Broadband Applications,” PROCEEDINGS OF INFOCOM '94, April 1994, pp. 636-646, which is incorporated herein by reference; Virtual Clock (VC), as described in L. Zhang, “Virtual Clock: A New Traffic Control Algorithm for Packet Switching,” ACM TRANSACTIONS ON COMPUTER SYSTEMS, May 1991, pp. 101-124, which is incorporated herein by reference; Frame-based Fair Queuing (FFQ), as described in D. Stiliadis and A. Varma, “Design and Analysis of Frame-based Fair Queuing: A New Traffic Scheduling Algorithm for Packet-Switched Networks,” PROCEEDING OF SIGMETRICS '96, May 1996, pp. 104-115, which is incorporated herein by reference; and Minimum-Delay Self-Clocked Fair Queuing (MD-SCFQ), as described in F. M. Chiussi and A. Francini, “Minimum-Delay Self-Clocked Fair Queuing Algorithm for Packet-Switched Networks,” PROCEEDINGS OF INFOCOM '98, March 1998, which is incorporated herein by reference. In particular, among these algorithms, MD-SCFQ achieves both optimal delay properties and excellent fairness properties.
Given that scheduling algorithms achieving the desired performance with a system-potential function of minimal complexity are available, the major contribution to the total complexity comes from the sorting of timestamps to select which packet to serve, an operation that is common to all GPS-related schedulers and one that has to be performed every time a packet is transmitted or received.
The number of timestamps that have to be sorted is equal to the number of connections V supported by the scheduler. As an example, typical values of V in current ATM switches are in the tens of thousands of connections. The range of possible values that the timestamps can assume at any given time depends on the ratio between the maximum and minimum service rates that the scheduler is required to provide to the connections, and is typically very wide. Given the complexity of sorting a large number of timestamps over a wide range of possible values at the high speeds of interest in broadband packet networks, data structures that are specifically devised to be efficiently mapped into silicon must be used to make hardware implementation affordable. One popular technique to implement the sorting structure is the so-called calendar queue, which consists of an ordered collection of bins, one bin for each possible value of timestamp. The sorting of the timestamps occurs by physically separating the timestamps in the corresponding bins, and visiting the bins in order. The calendar queue uses a direct relation between position in memory and value of the timestamps to simplify the data structure required to perform the sorting. In the particular case of ATM networks, the granularity of interest to represent the timestamps is the timeslot, equal to the duration of transmission of a cell on a link. Accordingly, the calendar queue, to accurately implement the sorting in a GPS-related scheduler, should provide one bin per timeslot, and have as many bins as necessary to cover the possible range of values of the timestamps at any given time; again, with what is typical in current ATM switches, the required size of the calendar queue is very large and, consequently, the scheduler is still expensive. Similar considerations apply to data packet networks based on other technologies, such as IP networks.
To reduce the cost of the scheduler, approximations can be introduced to simplify the sorting task. Such approximations may negatively affect the delay properties of the initial scheduler. The challenge, of course, is to devise techniques that are simple to implement and introduce minimal degradation. A possible approach, as described in J. L. Rexford, A. G. Greenberg, and F. G. Bonomi, “Hardware-Efficient Fair Queuing Architectures for High-Speed Networks,” PROCEEDINGS OF INFOCOM '96, pp. 120-128, which is incorporated herein by reference, is to increase the granularity with which timestamps are represented and thus reduce the number of bins in the calendar queue accordingly. In a scheme such as SCFQ, which achieves delay bounds that are far from optimal, especially for connections with high service rate, the degradation introduced by the increased granularity is, after all, not that noticeable. In case of schemes such as FFQ and MD-SCFQ, which achieve optimal delay bounds and are therefore more desirable, such a technique would basically compromise those delay bounds, and in particular heavily penalize the high-rate connections.
The present invention relates to a method and an apparatus for sorting timestamps in a system for scheduling the transmission of data packets in a packet-switched network, which guarantees data transfer rates to data sources and data transfer delays from data sources to destinations and is cost-efficient to implement.
SUMMARY OF THE INVENTION
The present invention provides a technique to reduce the implementation cost of the sorting mechanism, which technique we have called the Logarithmic Calendar Queue (LCQ). The LCQ consists of a small ordered set of short calendar subqueues, in which the subqueues use bins of progressively increasing granularity. The name chosen for the technique comes from the fact that the set of subqueues can be viewed as a single calendar queue in which the granularity of the bins used to sort the timestamps increases logarithmically with the distance of the timestamps from the system potential at the time when they are computed. The LCQ increases the granularity in an optimal way, so that the relative degradation in delay bounds is very small and is the same for any connection, regardless of its service rate. Using the LCQ, the reduction in memory requirements, and consequently in cost, to implement the calendar queue is dramatic (e.g., three orders of magnitude in a typical scenario of a scheduler for a 622 Mbps link in a current ATM switch).
REFERENCES:
patent: 5471631 (1995-11-01), Beardsley et al.
patent: 5689506 (1997-11-01), Chiussi et al.
patent: 5859835 (1999-01-01), Varma et al.
patent: 6021116 (2000-02-01), Chiussi et al.
patent: 6064650 (2000-05-01), Kappler et al.
patent: 6075791 (2000-06-01), Chiussi et al.
patent: 6134217 (2000-10-01), Stiliadis et al.
Chiussi Fabio Massimo
Francini Andrea
Kneuer Joseph George
Agere Systems Guardian Corp.
Mayer Fortkort & Williams PC
Mayer, Esq. Stuart H.
Vincent David R.
LandOfFree
Method and apparatus for guaranteeing data transfer rates... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for guaranteeing data transfer rates..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for guaranteeing data transfer rates... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2816805