Dynamic rate control scheduler for ATM networks

Details Dynamic rate control scheduler for ATM networks Dynamic rate control scheduler for ATM networks

1997-09-05

2002-06-18

Nguyen, Chau (Department: 2663)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S468000

Reexamination Certificate

active

06408005

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a control scheduler for an ATM network and, more specifically, to a scheduler which guarantees minimum rate of transmission, while fairly distributes any unused bandwidth.
2. Description of Related Art
High-speed networks based on the Asynchronous Transfer Mode (ATM) are expected to carry services with a wide range of traffic characteristics and quality-of-service (QoS) requirements. For example, in audio transmission a cell is useless to the receiver if it is delayed beyond the specified rate. On the other hand, video transmission is very bursty and, unless shaped at the entry point, may cause temporary congestion and delay other cells. Integrating all services in one network with a uniform transport mechanism can potentially simplify network operation and improve network efficiency. In order to realize these potential benefits, an efficient and fair means of allocating the network resources is essential.
A central problem in allocating the network resources is the manner in which the service to the various users is prioritized. A simple model is to use a First In First Out (FIFO) algorithm. In a simple First-In First-Out (FIFO) scheduler, there is no way of guaranteeing that each stream gets its assigned rate. During some interval of time, a given stream may transmit at a rate higher than its assigned rate M
i
, and thereby steal bandwidth from other streams which are transmitting at or below their assigned rates. This problem led to the development of various mechanisms for shaping the entry to the network, such as the known leaky bucket algorithm. For example, the output stream for each queue can be peak rate shaped to a predetermined rate M
p
.
FIG. 1
shows a static rate control (SRC) scheduler with N-stream queues, SQ1, SQ2 . . . SQN, one queue corresponding to each stream. The SRC scheduler serves a queue i at the constant rate M
i
and the output cell streams are fed to a common bottleneck queue CQ which is served at a given rate C. Service from the common queue CQ corresponds to cell transmission over a link of capacity C.
Rate-shaping transforms the streams into constant rate streams (assuming all queues are continuously backlogged). Considering the relationship
∑
i
=
1
N
⁢
M
i
≤
C
.
(
1
)
(to be developed further below), the bottleneck queue will be stable; in fact, the maximum queue length is N. In fact, strict inequality in (1) will usually hold, implying that the cell delay in the common queue will be small with high probability. Although the service discipline depicted in
FIG. 1
is work-conserving with respect to the stream queues, it is non-work-conserving with respect to the common queue, since it is possible that the common queue may go empty even when at least one of the stream queues is non-empty. This scheduler is similar to a circuit-switched system, except for the asynchronous nature of the cell streams.
If the rates, M
i
, have been computed correctly based on the stream traffic characteristics and QoS requirements, the minimum rate scheduler should succeed in guaranteeing QoS for all of the streams. However, because this scheduler is non-work-conserving with respect to the common queue, bandwidth could be wasted for one of two reasons:
The CAC algorithm was optimistic in its computation of M
i
. It may be the case that a bandwidth of M
i
+&Dgr; over short intervals of time is required to ensure that QoS is met for stream i.
The traffic stream could include low priority cells, with the cell loss priority (CLP) bit set to one.
In the first case, a stream should be allowed to make use of bandwidth beyond its allocated rate, M
i
, if the bandwidth is available. In the second case, the QoS guarantee applies only to cells that conform to the negotiated traffic contract, i.e., cells with cell loss priority (CLP) set to zero. However, if bandwidth is available, a stream should be permitted to transmit nonconforming cells, i.e., cells tagged as CLP=1 cells, over and above the allocated minimum rate for CLP=0 cells. If bandwidth is not available, CLP=1 cells should be dropped before CLP=0 cells; i.e., there should be a lower threshold for dropping CLP=l cells. (As is known in the art, when a source transmits at a rate higher than the negotiated rate, its violating cells are tagged by setting their CLP to 1.)
Clearly, the problem with the minimum rate scheduler, is that streams cannot make use of excess bandwidth even when it is available. In minimum rate scheduling, there is no statistical multiplexing among cells belonging to different streams. (As is known in the art, statistical multiplexing takes into account “economies of scale,” i.e., the bandwidth it takes to transmit all the streams together is less than the sum of the individual bandwidths required to transmit each stream.) A simple way to enhance this scheme is to provide means for serving a cell from a non-empty queue whenever bandwidth is available. During a cell time, if the common queue is empty, the scheduler services a cell from one of the non-empty stream queues.
According to another prior art method, the queue selection is done in a round-robin fashion, and the excess bandwidth i s shared equally among the active streams. A disadvantage of such a scheduler is that queues are served without regard to QoS. That is, the bandwidth is alternated sequentially to the queues without regard to the urgency of transmission, i.e., requested minimum rate, of any specific source. Therefore, this method does not lend itself well for serving different classes having different QoS requirements.
Accordingly, there has been considerable interest in packet scheduling algorithms which are intended to provide weighted shares of the bandwidth on a common link to competing traffic streams, so as to enable service of different classes. With slightly more complexity, the excess bandwidth can be shared using Weighted Round-Robin (WRR) Weighted Fair Queuing (WFQ), and Virtual Clock, and their variants, which attempt to approximate the idealized Generalized Processor Sharing (GPS) scheduling, assuming a fluid model of traffic. For WRR, see M. Katevenis, S. Sidiropoulos, and C. Courcoubetis, Weighted Round-Robin Cell Multiplexing in a General-Purpose ATM Switch, IEEE JSAC, Vol 9, pp. 1265-1279, October 1991. For WFQ, see, A. K. Parekh and R. G. Gallager, A generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: The Single-Node Case, IEEE/ACM Trans. on Networking, vol. 1, pp. 344-357, June 1993. For Virtual Clock, see, L. Zhang, Virtual Clock: A New Traffic Control Algorithm for Packet Switching, ACM Trans. on Computer Systems, vol. 9, pp. 101-124, May 1991. In these schedulers, each stream is assigned a weight corresponding to the QoS requested by a user of the stream. Accordingly, over an interval of time in which the number of active streams is fixed, the bandwidth received by an active stream should be roughly proportional to the assigned weight.
By an appropriate assignment of weights, each stream can be provided with a share of the link bandwidth that is proportional to its weight. Hence, each stream receives a minimum bandwidth guarantee. If a stream cannot make use of all of its guaranteed bandwidth, the excess bandwidth is shared among the active streams in proportion to the weights. However, a stream with a larger weight will not only receive a higher bandwidth guarantee, but also receive larger shares of the available bandwidth than streams with smaller weights. Thus, the weight assigned to a connection determines not only its minimum bandwidth guarantee, but also its share of the available unused bandwidth.
In this specification the term “weighted fair share scheduler” is used generally to refer to a general class of work-conserving schedulers which schedule cells so as to give each stream a share of the link bandwidth which is approximately proportional to a pre-assigned weight. A work-conserving scheduler transmits a cell over the link when

Affiliated with

Also associated with

Rating

Dynamic rate control scheduler 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 Dynamic rate control scheduler for ATM networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic rate control scheduler for ATM networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2975623