Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-03-18
2002-05-14
Ton, Dang (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S233000
Reexamination Certificate
active
06389019
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to schedulers for asynchronous transfer mode (ATM) networks and, more specifically, to an architecture and method for scheduling stream queues serving cells with different quality-of-service (QoS) requirements while shaping the transmission rate to avoid congestion at bottlenecks within an ATM switch.
2. Description of Related Art
The function of a scheduler is to determine the order in which cells queued at a port are to be sent out. The simplest scheduling method is a first-in, first-out (FIFO) method. Cells are buffered in a common queue and sent out in the order in which they are received. The problem with FIFO queuing is that there is no isolation between connections or even between traffic classes. A “badly behaving” connection (i.e., it sends cells at a much higher rate than its declared rate) may adversely affect quality of service (QoS) of other “well behaved” connections.
A solution to this problem is to queue cells in separate buffers according to class. One further step is to queue cells on a per connection basis. The function of the scheduler is to decide the order in which cells in the multiple queues should be served. In round-robin (RR) scheduling, the queues are visited in cyclic order and a single cell is served when a visited queue is not empty. However, if all queues are backlogged, the bandwidth is divided equally among the queues. This may not be desirable, however, because queues may be allocated different portions of the common link bandwidth.
In weighted round-robin (WRR) scheduling, which was described in a paper by Manolis Katevenis, et al., entitled, “Weighted Round-Robin Cell Multiplexing in a General Purpose ATM Switch Chip,” IEEE Journal on Selected Areas in Communications, Vol. 9, No. 8, pp. 1265-1279, October 1991, each queue (connection or class queue) is assigned a weight. WRR aims to serve the backlogged queues in proportion to the assigned weights. WRR is implemented using counters, one for each queue. The counters are initialized with the assigned weights. A queue is eligible to be served if it is not empty and has a positive counter value. Whenever a queue is served, its counter is decreased by one (to a minimum of zero). Counters are reset with the initial weights when all other queues are either empty or have zero counter value. One problem with this counter-based approach is that the rate granularity depends on the choice of frame size (i.e., the sum of weights).
Another method, weighted fair queuing (WFQ), also known as packet-by-packet generalized sharing (PGPS), was described in a paper by Alan Demers, et al., entitled, “Analysis and Simulation of a Fair Queuing Algorithm,” Proc. SIGCOMM'89, pp. 1-12, Austin, Tex., September 1989, and a paper by S. Jamaloddin Golestani, entitled, “A Self-clocked Fair Queuing Scheme for Broadband Applications,” IEEE, 0743-166X/94, 1994, pp. 5c.1.1-5c.1.11. This method is a scheduling algorithm based on approximating generalized processor sharing (GPS). In the GPS model, the traffic is assumed to be a fluid, such that the server can drain fluid from all queues simultaneously at rates proportional to their assigned weights. A timestamp is computed when each cell arrives. The value of the timestamp represents the finishing time of the cell in the fluid model. The WFQ method schedules by selecting the cell with the smallest timestamp value.
All the methods described above are work-conserving with respect to the local link bottleneck, in the sense that if there are cells in the buffer(s), one cell will be served during a cell time. In contrast, another cell scheduling scheme, dynamic rate control (DRC), which was developed in co-pending application Ser. No. 08/924,820, is in general, non-work conserving. A cell may be held back if it could cause congestion downstream. DRC scheduling uses timestamps, as in WFQ, but the timestamps represent absolute time values. Thus, DRC may hold back a cell, if necessary, to alleviate congestion at a later switch bottleneck. This feature cannot be achieved with WFQ or WRR. One feature of DRC is that it does not require sorting of the timestamps, since the timestamps are compared to an absolute time clock. Also, traffic shaping can easily be incorporated into the DRC scheduler.
SUMMARY OF THE INVENTION
The present invention is a flexible and scalable architecture and method that implements DRC scheduling. Details on the algorithms and principles underlying DRC scheduling, are described in co-pending application Ser. No. 08/924,820. A key component of the DRC scheduler is a traffic shaper that shapes multiple traffic streams based on dynamically computed rates. The rates are computed based on congestion information observed at switch bottlenecks. Alternatively, the rates can be computed based only on the congestion observed at the local bottleneck. The modular design of the scheduler allows it to be used in a variety of switch configurations. In particular, the DRC scheduler architecture and method of the present invention can be applied to the input-output buffered switch architecture discussed in co-pending application Ser. No. 08/923,978 now U.S. Pat. No. 6,324,165.
The traffic shaper can shape a large number of streams with a wide range of associated rate values. With current technology, the architecture is able to support per VC queuing with up to 64 K virtual channels (VCs) with bit rates ranging from 4 Kbps to 622 Mbps. Scalability with respect to the number of streams that can be supported is achieved by scheduling streams to be served using a timewheel data structure, also known as a calendar queue. Calendar queues are well known. See for example, an article by R. Brown entitled, “Calendar Queues: A Fast 0(1) Priority Queue Implementation for the Simulation Event Set Problem,” Communications of the ACM, Vol. Oct. 31, 1988, which is incorporated herein by reference.
To handle a large range of bit rates, a plurality of timewheels are employed with different time granularities. The timewheel concept and the partitioning of rates into ranges are also well known. See for example, an article by J. Rexford, et al. entitled, “Scalable Architecture for Traffic Shaping in High Speed Networks, IEEE INFOCOM '97, (Kobe), April 1997, which is incorporated herein by reference. The shaper architecture of the present invention differs from the one described in the Rexford article in that it supports priority levels for arbitrating among streams which are simultaneously eligible to transmit. The highest priority level is assigned dynamically to provide short time-scale minimum rate guarantees in DRC scheduling. The remaining priority levels provide coarse QoS differentiation for defining traffic classes. Also in this architecture, the assignment of streams to timewheels is dynamic, depending on the current rate value computed for the stream.
A primary object of the invention is to provide an architecture and method capable of scheduling stream queues serving cells with different QoS requirements while shaping the transmission rate to avoid congestion at bottlenecks in an ATM switch.
Another object of the invention is to provide a scheduler architecture that can be used to implement available bit rate (ABR) service virtual source (VS)/virtual destination (VD) protocols as outlined in “Traffic Management Specification, Version 4.0,” The ATM Forum, March 1996).
Another object of the invention is to provide a scheduler architecture that performs both scheduling and dual leaky bucket usage parameter control (UPC) shaping as also outlined in “Traffic Management Specification, Version 4.0.” UPC shaping is used to force a traffic stream to conform to UPC parameters in order to avoid cell tagging or discarding at the interface to another subnetwork through which the stream passes.
Herein, the principles of the present invention will be schematically described in consideration of the above to facilitate the present invention.
Briefly, the gist of the present invention resides in the fact that a dynamic rat
Fan Ruixue
Ishii Alexander T.
Mark Brian L.
Ramamurthy Gopalakrishan
NEC USA Inc.
Sughrue & Mion, PLLC
Ton Dang
LandOfFree
Time-based scheduler architecture and method for ATM networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Time-based scheduler architecture and method for ATM networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Time-based scheduler architecture and method for ATM networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2837538