Dynamic rate control scheduler for ATM networks
First Claim
1. A method of rate-based cell scheduling of a plurality of cells arriving at an ATM switch having a plurality of queues, comprising:
- directing each one of said plurality of cells to a respective queue;
assigning a respective minimum rate guarantee for each of said queues;
assigning a respective excess rate share for each of said queues;
estimating excess bandwidth on a downstream link;
transmitting said cell from said queues according to the respective minimum rate guarantee, while distributing the excess bandwidth to said queues according to said excess rate share.
4 Assignments
0 Petitions
Accused Products
Abstract
A Dynamic Rate Control (DRC) scheduler for scheduling cells for service in a generic Asynchronous Transfer Mode (ATM) switch is disclosed. According to the inventive DRC, each traffic stream associated with an internal switch queue is rate-shaped according to a rate which consists of a minimum guaranteed rate and a dynamic component computed based on congestion information within the switch. While achieving high utilization, DRC guarantees a minimum throughput for each stream and fairly distributes unused bandwidth. The distribution of unused bandwidth in DRC can be assigned flexibly, i.e., the unused bandwidth need not be shared in proportion to the minimum throughput guarantees, as in weighted fair share schedulers. Moreover, an effective closed-loop QoS control can be built into DRC by dynamically updating a set of weights based on observed QoS. Another salient feature of DRC is its ability to control congestion internal congestion at bottleneck points within a multistage switch. DRC can also be extended beyond the local switch in a hop-by-hop fashion.
-
Citations
15 Claims
-
1. A method of rate-based cell scheduling of a plurality of cells arriving at an ATM switch having a plurality of queues, comprising:
-
directing each one of said plurality of cells to a respective queue;
assigning a respective minimum rate guarantee for each of said queues;
assigning a respective excess rate share for each of said queues;
estimating excess bandwidth on a downstream link;
transmitting said cell from said queues according to the respective minimum rate guarantee, while distributing the excess bandwidth to said queues according to said excess rate share.
-
-
2. A method of rate-based scheduling at an ATM switch having a plurality of input queues, comprising the steps of:
-
assigning a minimum guaranteed rate for each of said queues;
computing a dynamic rate for each of said queues;
shaping each stream arriving at each of said queues according to the respective minimum guaranteed rate and the respective dynamic rate. - View Dependent Claims (3)
monitoring the level of each of said buffers and, when one of said buffers reaches a predetermined level, generating a shape signal identifying said one buffer;
scheduling said queues according to a rate composed of the minimum guaranteed rate plus the dynamic rate when said shape signal is not generated and scheduling said queues according to said minimum rate when said shape signal is generated.
-
-
4. A method of rate-based cell scheduling of a plurality of cell streams, comprising the steps of:
-
assigning a minimum rate for each of said plurality of cell streams;
calculating a dynamic rate for each of said cell streams, said dynamic rate comprising a product of an assigned weight and an estimated excess bandwidth at a downstream bottleneck; and
adding each dynamic rate to a corresponding minimum rate. - View Dependent Claims (5, 6, 7)
-
-
8. A method for queuing a plurality of virtual channels in an ATM switch having a plurality of input buffers, comprising the steps of:
-
assigning an input buffer for each of said virtual channels;
assigning a minimum guaranteed rate for each of said buffers;
assigning a weight for each of said buffers;
calculating a dynamic rate for each of said buffers, said dynamic rate comprising the minimum guaranteed rate plus a portion of an unused bandwidth of said switch, said portion being proportional to the assigned weight; and
shaping transmissions from said buffers according to the dynamic rate. - View Dependent Claims (9, 10, 11, 12)
distributing the dynamic rate of each buffer to its respective active virtual channels.
-
-
11. The method of claim 10, wherein said dynamic rate is distributed evenly among the respective active virtual channels.
-
12. The method of claim 10, wherein each of said virtual channels is assigned a secondary weight and wherein the dynamic rate is distributed to the respective virtual channels according to the respective secondary weight.
-
13. A method for controlling overload in a buffer comprising:
-
monitoring a load level in said buffer;
when said load level reaches a first threshold, generating a shape signal to cause input to said buffer to be reduced to a minimum level;
when said load level reaches a second threshold, generating a stop signal to halt any input to said buffer;
estimating an unused bandwidth available on said buffer; and
generating a signal indicating said estimate.
-
-
14. A method of rate-based scheduling of a plurality of data packets arriving at a switch having a plurality of queues, comprising:
-
directing each one of said plurality of packets to a respective queue;
assigning a respective minimum rate guarantee for each of said queues;
assigning a respective excess rate share for each of said queues;
estimating excess bandwidth on a downstream link;
transmitting said packet from said queues according to the respective minimum rate guarantee, while distributing the excess bandwidth to said queues according to said excess rate share.
-
-
15. A method of rate-based scheduling at a switch having a plurality of input queues, comprising the steps of:
-
assigning a minimum guaranteed rate for each of said queues;
computing a dynamic rate for each of said queues;
shaping each packet stream arriving at each of said queues according to the respective minimum guaranteed rate and the respective dynamic rate.
-
Specification