Scheduling circuitry and methods

Details Scheduling circuitry and methods Scheduling circuitry and methods

1999-05-05

2004-10-26

Ton, Dang (Department: 2666)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395400, C370S395710

Reexamination Certificate

active

06810043

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to scheduling circuitry and methods for use, for example, in scheduling cell transmission operations in an asynchronous transfer mode (ATM) communications network.
2. Description of the Related Art
In an ATM communications network a plurality of so-called “virtual channels” (VCs) are used to transmit user data and control information between different network units. Such user data and control information is transmitted in the form of ATM cells, each cell having a header portion, containing control and addressing information for the cell, and a payload portion containing the user data or other control information.
A given network unit may have a plurality of such virtual channels connecting it to one or more other units of the network. It is therefore necessary to provide, in each network unit, a traffic manager that manages the times at which cells are caused to be applied to the different virtual channels concerned.
The task of the traffic manager is complicated by the fact that different virtual channels may be used to transmit different types of traffic, including traffic types having different so-called priorities. For example, the following types of traffic may occur in ATM networks:
i) Constant bit rate (CBR) traffic. This is typically used for high-priority data which should not be subject to delays, for example video signals.
ii) Variable bit rate (VBR) traffic. This type of traffic also has a relatively high priority (but lower than CBR traffic). It is used where some tolerance to delay is available, for example compressed video (e.g. Motion Picture Expert Group MPEG2) traffic or voice traffic.
iii) Available bit rate (ABR) traffic. A virtual channel used to transmit ABR traffic has traffic parameters that are agreed between the user of the channel and the network operator. Within the limitations imposed by the agreed parameters, the ABR channel is permitted to vary its transmission rate so as to take advantage of spare capacity in the network. ABR traffic has a low priority (lower than CBR and VBR traffic). ABR channels may be used, for example, for file and data transfers.
iv) Unspecified bit rate (UBR) traffic, for example e-mail and some types of data/file transfers.
FIG. 1
of the accompanying drawings is a schematic block diagram for use in explaining a “calendar” scheduling method proposed previously for managing the cell transmission times from an ATM network unit.
In
FIG. 1
, a calendar
1
is made up of a list of storage locations
2
corresponding respectively to a succession of time slots. The duration of each time slot is equal to the time taken to transmit a single ATM cell at the maximum required data rate of the ATM network.
Each storage location
2
is capable of storing one or more entries, each such entry denoting that a specified virtual channel is to be serviced by the traffic manager in the time slot to which the storage location corresponds. For example, a storage location
2
A
in the calendar
1
has a single entry denoting that the virtual channel VCw is to be serviced by the traffic manager in the time slot corresponding to the storage location
2
A
.
It is possible for more than one VC to be entered into the same storage location. For example, a storage location
2
B
in the calendar
1
has three virtual channels VCx, VCy and VCz entered therein, denoting that each of these channels is to be serviced in the time slot corresponding to the storage location
2
B
. The three entries in the storage location
2
B
are made in the form of a linked list, so as to avoid reserving large amounts of memory per time slot to attempt to accommodate the largest possible number of VCs which could accumulate at a particular storage location.
The traffic manager uses two pointers
3
and
4
to process the calendar
1
. The first of these pointers
3
is a current time pointer (T) which represents real time. The current time pointer T is always incremented after each cell interval. The second pointer
4
is an activity pointer (A) which is always attempting to catch up with the T pointer
3
, without ever being incremented past it.
At each storage location
2
in the calendar
1
, if no VCs are entered, the A pointer is simply incremented to the next storage location, so that in this case the A pointer will tend to catch up to the T pointer. If, on the other hand, one or more VCs is entered at a storage location pointed to by the A pointer, the pointer is not incremented until all the VCs have been processed (in this case the T pointer will be incremented more than once during the time required to process all the VCs concerned, so that the A pointer will tend to fall further behind the T pointer).
The traffic manager services the entries in the calendar as follows. Firstly, a cell for the VC specified in the entry is transmitted. Secondly, if necessary, a new inter-cell interval for the channel is calculated (CBR channels always have the same inter-cell interval but for VBR, ABR and UBR channels the cell interval can vary in use of the channel and so must be recalculated from time to time). The next cell transmission for the specified VC is then rescheduled by making a new entry for the VC in a different storage location
2
of the calendar
1
.
For example, if VCx has 33% of the available transmission capacity from the ATM network unit concerned, when it is serviced at location
2
B
it will be rescheduled at storage location
2
C
, three cell time slots ahead of the current time pointer T.
Incidentally, in this example, it can be seen that the A pointer, which at this time is pointing to the storage location
2
B
, is five storage locations behind the T pointer. Some catching up of the A pointer to the T pointer will be possible because of the empty storage locations between the two pointers but there are also three virtual channels VCy, VCz and VCw to service between the A and T pointers. This means that in practice it will be more than three cell periods before VCx will be encountered again for further processing.
One problem with the calendar scheduling method shown in
FIG. 1
is that it is necessary to be able to cope with channels having very different transmission rates. Each cell period in an ATM network having a maximum data rate of 155 Mbps is 2.726 &mgr;s. However, some types of VC can have very low cell rates. For example, ABR channels use resource management (RM) cells for control purposes and the cell rates for such RM cells may be only 10 cells per second. This would require the calendar
1
in
FIG. 1
to have 35000 entries (i.e. 35000×2.726 &mgr;s=0.1 s). This is impractical, as the calendar
1
requires a storage location
2
for each time slot.
One solution to this problem, proposed previously, is to include a counter with each VC, which counter is set initially to a certain positive value and then decremented on each pass around the calendar as each VC entry is examined by the traffic manager. The VC is only serviced (i.e. a cell transmitted and the next cell transmission scheduled) when its counter reaches 0. In this way, it is possible to reduce the size of the calendar to (say) 1000 storage locations, using a six-bit counter per VC. VCs whose cell rates are greater than 370 cells per second (an inter-cell period of 2.7 milliseconds at 155 Mbps) are always “hit” in the calendar, i.e. the counter for each such VC is permanently 0.
Although the solution outlined above is partially effective in reducing the calendar size, it is wasteful of traffic manager resources in that, even though a particular VC is encountered on each pass through the calendar, this does not necessarily mean that it should be serviced on each encounter. Often, therefore, entries are read by the traffic manager which do not require any servicing on this particular pass of the calendar.
A further disadvantage is associated with the need for each entry in the calendar to have a backward pointer (to the previous entry in the linked list) as well as a forward pointer. Beca

Affiliated with

Also associated with

Rating

Scheduling circuitry and methods does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Scheduling circuitry and methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling circuitry and methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3264873