Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-09-10
2002-11-05
Nguyen, Chau (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S395400, C370S412000, C370S468000
Reexamination Certificate
active
06477144
ABSTRACT:
FIELD OF INVENTION
The invention generally resides in flow control mechanisms of telecommunications network. In particular, it is directed to scheduling of traffic classes at a node of an ATM network and more specifically to the traffic scheduling which is based on the rates allocated to each class of the traffic.
BACKGROUND OF INVENTION
ATM networks are multimedia networks which handle a mixture of traffic classes with diverse connection requirements. The networks-employ a variety of traffic control and/or network management techniques to ensure that the networks meet the connection requirements. In
FIG. 1
, a number of traffic classes a to d are buffered in separate queues
10
and a controller
12
(or scheduler) accesses the queues for outputting in a certain order so that an output link
14
of fixed capacity is shared by the traffic classes. Throughout the specification, “class” or “traffic class” is used to indicate a category of traffic in accordance with a certain descriptor. A class therefore may represent the traffic of one connection or may contain different connections, all having a common descriptor, i.e. all the cells in a class are buffered in the same queue. Therefore, there are as many queues as there are classes and the scheduler may be described as a queue controller. The classes may share the link according to one of many policies, such as strict priority, a fixed-rate per class, a guaranteed minimum rate per class, etc. In any of these policies, the maximum number of cells that a queue may transfer to the link in a single transaction may be limited to a predetermined bound. These control mechanisms are sometimes called scheduling mechanisms. In the priority based scheduling mechanism, one class of traffic will always be served before the other as long as there are cells to send. Satisfying the delay and loss requirements of the lower priority class may not be possible due to the traffic behaviour in the high priority class. When more priorities are added, satisfying delay and loss guarantees of each class becomes progressively more difficult. For example,
FIG. 2
shows the priority scheduler
20
in which there are four queues
22
for four priority classes, a to d in the descending order. Relative arrival
24
of cells for each class is also shown in the figure. Cells are stored in respective queues when they arrive and the priority scheduler serves the queues according to the degree of priority.
FIG. 3
is a series of charts showing conditions of the queues and a selection of a cell for output by a priority scheduler at each successive output timeslot (cell interval). At timeslot
1
, cell a
1
is selected because of its highest priority. At timeslot
2
, however, cell b
1
is selected because cell a
3
is yet to arrive and b
1
is the highest priority cell among cells stored in the queues. The sequence continues in a similar fashion. The output traffic
30
on the link would consists of a series of ATM cell as shown at the bottom of the figure. As seen in the figure, class d therefore must wait until the first three classes are empty before being allowed to send traffic.
A rate scheduler selects queues according to criteria based on the preset bandwidth allocation to each class, i.e. the link bandwidth is divided among different classes of traffic based on the respective rate of traffic for each class. For example in
FIG. 4
, classes a to c are given ¼ (in other words, one in every four cells at the most) of the total capacity of the link and class d has ⅕ of the capacity. This gives each class a number of dedicated opportunities to send cells and limits the impact of higher priority classes. In other words, with a rate scheduler, no queue has “priority” over another. Interference (competition or contention) comes from all queues now, not just from higher priority ones. However the interference is lessened by the rate limits of the queues, and changing the assigned rates offers a way to manage the interference, thus improving isolation. Similar to
FIG. 3
,
FIG. 5
shows a series of chart showing conditions of queues and selection of a cell for outputting at each successive output timeslot. In this example, cell arrival is the same as that shown in FIG.
2
. At timeslots
1
and
2
, cells a
1
and b
1
are selected. At timeslot
3
, however, although the highest priority queue contains cell a
3
, the scheduler cannot send the cell out because class a has used up its allocated bandwidth when it sent out cell a
1
two timeslots earlier. In other words, queue a must wait for at least three timeslots before it is allowed to send a cell. The output traffic profile on the link is therefore as shown at the bottom of the figure. Improved isolation of classes allows a better chance at meeting delay and loss guarantees for each class. This leads to simpler call admission control algorithms and higher link utilization. A programmable rate mechanism allows the scheduler to track the changing traffic profile of the link. This could be controlled by software and updated every time a connection is created/destroyed. While the rate based scheduling mechanism operates in principle as described above, there are different schemes for implementing the general concept. The invention is concerned with efficient allocation of a specified bandwidth to each traffic class.
OBJECTS OF INVENTION
It is therefore an object of the invention to provide a method of and apparatus for scheduling packet traffic onto an output link.
It is another object of the invention to provide a method of and apparatus for scheduling packet traffic in which the scheduling is based upon the bandwidth allocation among various classes of traffic.
It is still an object of the invention to provide a method of and apparatus for scheduling packet traffic in which the scheduling is based on indexing a scheduling table which indicates the next class of traffic to be serviced and updating the table according to the bandwidth allocation of the class.
It is yet another object of the invention to provide a method of and apparatus for scheduling packet traffic in which the classes in the same timeslot are linked in the table.
It is a further object of the invention to provide a method of and apparatus for scheduling ATM traffic onto an output link.
SUMMARY OF INVENTION
Briefly stated, the invention resides in a packet network in which a node receives a plurality of traffic classes and outputs them to an output link. According to one aspect, the invention is directed to a method of scheduling the traffic classes. The method comprises steps of buffering cells of each traffic class in a respective queue, assigning reference numbers, Tnext, to traffic classes buffered in the queues and creating one or more linked lists of traffic classes, each of which has traffic classes with a similar scheduled departure time determined from Tnext. The method includes further steps of outputting cells to the output link from the queues according to the scheduled departure time of the linked list of traffic classes and updating the Tnext according to the bandwidth allocated to each class.
According to another aspect, the invention is directed to an apparatus for scheduling the traffic classes in a packet network in which a node receives a plurality of traffic classes and outputs them to an output link. The apparatus comprises a plurality of queues, each queue for buffering cells of each traffic class and a class data structure containing reference numbers, Tnext, assigned to traffic classes and one or more linked lists of traffic classes, each list having traffic classes with a similar scheduled departure time determined from Tnext. The apparatus further includes a reference counter for indexing the linked lists of traffic classes according to their scheduled departure times and selecting one linked list for outputting cells to the output link according to its scheduled departure time , and a link/parser for updating the Tnext according to the bandwidth allocated to each class and for linking classes into the link
Lyon Norman A.
Morris Todd D.
Nichols Stacy W.
Toplis Blake S.
Mehra Inder Pal
Millard Allan P.
Nguyen Chau
Nortel Networks Limited
LandOfFree
Time linked scheduling of cell-based traffic 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 linked scheduling of cell-based traffic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Time linked scheduling of cell-based traffic will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2922120