Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-11-15
2004-10-26
Qureshi, Afsar (Department: 2667)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S395410, C370S395430, C370S412000, C370S468000
Reexamination Certificate
active
06810012
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of computer networking. In particular the present invention discloses a cell scheduling system for an Asynchronous Transfer Mode (ATM) network.
BACKGROUND OF THE INVENTION
Asynchronous Transfer Mode (ATM) is a digital communication standard for transmitting information. In the Asynchronous Transfer Mode system, the information to be transmitted is divided into fifty-three byte units known as “cells.” The fifty-three byte cells of information are transmitted from a source node to a destination node through an ATM network constructed of communication lines and ATM switches.
In an ATM system, information is communicated from a source node to a destination node through a defined path known as a “virtual circuit”. The virtual circuit is set up when a connection is needed and later torn down when the connection is no longer needed. Each virtual circuit is defined by several parameters such as Quality of Service (QOS) parameters and traffic parameters, the latter of which may include a required bandwidth. Once a virtual circuit has been established, all cells will travel along the same set of intermediary nodes between the source node and the destination node until the virtual circuit is torn down. However, when a subsequent virtual circuit is established between the same source node and destination node, the subsequent virtual circuit may not consist of the same intermediary nodes.
Within each ATM node, the ATM node must switch ATM cells from incoming communication lines to outgoing communication lines. Since a virtual circuit may have a defined required bandwidth amount, the ATM node must carefully schedule cell servicing such that the virtual circuit receives its required bandwidth and QOS requirements. To perform this function, a cell scheduler is implemented for each outgoing communication line. The cell scheduler allocates the bandwidth of its associated communication line to the virtual circuits or groups of virtual circuits that are assigned to use that communication line. Then the cell scheduler must schedule cells from queues associated with each virtual circuit or virtual circuit group such that each receives its allocated bandwidth.
SUMMARY OF THE INVENTION
In the interval based cell scheduler of the present invention, each cell queue is assigned an ideal service interval time. The ideal service interval time of each cell queue is the reciprocal of the bandwidth assigned to that cell queue. The scheduler is then initialized by setting a time reference to zero and setting a next service time for each queue to the queue's ideal service interval. The cell scheduler then enters a repeating loop. During each iteration of the loop, the first nonempty cell queue having the smallest next service time value is selected. The selected queue is serviced and its next service time is updated by adding its ideal service interval. The time reference value is also updated. If all the queues are empty, then an idle time slot is allowed to pass. The cell queues may consists of queue groups. For example, several queues can be gathered into a queue group that is assigned a single ideal service time. Within this queue group, each queue may be serviced equally using a fair queuing system.
Other features and advantages of present invention will be apparent from the accompanying drawings and from the following detailed description that follows below:
REFERENCES:
patent: 4979165 (1990-12-01), Dighe et al.
patent: 5268900 (1993-12-01), Hluchyj et al.
patent: 5463620 (1995-10-01), Sriram
patent: 5500858 (1996-03-01), McKeown
patent: 5533020 (1996-07-01), Byrn et al.
patent: 5577035 (1996-11-01), Hayter et al.
patent: 5629928 (1997-05-01), Calvignac et al.
patent: 5640389 (1997-06-01), Masaki et al.
patent: 5742765 (1998-04-01), Wong et al.
patent: 5793747 (1998-08-01), Kline
patent: 5896511 (1999-04-01), Manning et al.
patent: 6002667 (1999-12-01), Manning et al.
patent: 6014367 (2000-01-01), Joffe
patent: 6018527 (2000-01-01), Yin et al.
patent: 6061330 (2000-05-01), Johansson
patent: 6064677 (2000-05-01), Kappler et al.
patent: 6076112 (2000-06-01), Hauser et al.
patent: 6088734 (2000-07-01), Marin
patent: 6088736 (2000-07-01), Manning et al.
patent: 6115748 (2000-09-01), Hauser et al.
patent: 6167452 (2000-12-01), Manning et al.
patent: 6256674 (2001-07-01), Manning et al.
patent: 6272109 (2001-08-01), Pei
patent: 6408005 (2002-06-01), Fan
“Hardware-Efficient Fair Queueing Architectures for High-Speed Networks,” Rexford et al., IEEE Infocom'96, Mar. 24-28, 1996, pps 638-646.
“Real-Time Scheduling With Quality of Service Constraints,” Hyman et al., IEEE Jornal on Selected Areas in Communications, Sep., 1991, vol. 9, No. 7, pps. 1052-1063.
“Multiplexing Spacer Outputs on Cell Emissions,” Mercankosk et al., IEEE Infocom'95, Boston, Apr. 1995, pps. 49-55.
Borden Marty
Hluchyj Michael
Li Shiping
Yin Nanying
Blakely , Sokoloff, Taylor & Zafman LLP
Qureshi Afsar
LandOfFree
Queue service interval based cell schedular with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Queue service interval based cell schedular with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Queue service interval based cell schedular with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3304389