Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-11-24
2003-09-23
Yao, Kwang Bin (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S395400
Reexamination Certificate
active
06625122
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to networks, and more particularly to selecting data for transmission in networks.
Data transmission in networks may be subjected to some bandwidth (i.e., bits-per-second) requirements. For example, on a voice channel, data may have to be transmitted at exactly 64 Kbps. In another example, a network user may have contracted with a network service provider for a minimum and maximum bandwidth parameters. The network provider must limit the user's data rates to these bandwidth parameters.
FIG. 1
illustrates a scheduler that selects (schedules) data for transmission in accordance with predefined bandwidth parameters. The scheduler is used in an asynchronous transfer mode (ATM) switch. The scheduler schedules data transmission on virtual connections (VCs)
120
which share an output port
130
. Each VC is to be given some bandwidth which is a portion of the total bandwidth of port
130
. The bandwidth of each VC is defined by a parameter &Dgr; (a separate parameter for each VC). &Dgr; is the number of cell times in which a single ATM cell must be transmitted on the VC. &Dgr; can be thought of as the time between transmission of consecutive cells on the VC.
The scheduling method can be conceptually represented using a time wheel
140
. The time wheel has a number of time slots
150
.
0
,
150
.
1
,
150
.
2
,
150
.
3
. . . Each of these time slots
150
is associated with a queue
160
of virtual connections
120
which should transmit a cell at the same time in order to meet their respective bandwidth parameters &Dgr;. However, only one VC can transmit on port
130
at any given time.
Each cell time, the time wheel rotates clockwise by one time slot. Hence, the queue
160
of slot
150
.
2
moves to slot
150
.
1
, the queue
160
of slot
150
.
3
moves to slot
150
.
2
, and so on. When a queue
160
reaches slot
150
.
0
, its VCs are added to active queue
160
.
0
. The active queue contains VCs that should transmit in the current cell time. One VC is dequeued from the head of the active queue. This VC is shown at
120
.
0
in
FIG. 1. A
cell is transmitted from this VC to port
130
. Then the VC
120
.
0
is moved to the queue
160
in time wheel slot &Dgr; (i.e., slot
150
.&Dgr;) where &Dgr; is the bandwidth parameter of the VC
120
.
0
. This means the VC will return to the active queue in &Dgr; cell times, which is when the next cell on the VC should be transmitted.
When a VC
120
is added to active queue
160
.
0
, the VC may have to wait for other VCs ahead in the queue before a cell from the VC is transmitted. If VC
120
.
0
has waited for “d” cell times, the VC is moved to queue &Dgr;−d (i.e., queue of slot &Dgr;−d) rather than &Dgr;. Therefore, the VC will re-enter the active queue
160
.
0
“d”cell times earlier.
In one implementation, a Current_Time counter keeps the current time, measured in cell times. Each VC
120
is associated with a time stamp register TS storing the time when the next cell should be transmitted on the VC. When a cell is transmitted on the VC, the corresponding TS is incremented by &Dgr;. Then the VC is moved to queue Q_Id=TS−Current_Time. Since TS and &Dgr; can be fractional numbers, Q_Id is actually computed as int (TS)−Current_Time, where “int” is a function equal to the largest integer not exceeding the argument TS. See European patent application EP 0 874 531“ATM Cell Scheduling Method” filed by MMC Networks, Inc. (published Oct. 28, 1998). See also “AF5500 Chip Set User Guide” (MMC Networks, Inc. of Sunnyvale, Calif. July 1998), pages 8-1 through 8-40.
Improvements on this scheme are desirable.
SUMMARY
The inventor has observed that if the total bandwidth of port
130
is high but the minimal supportable bandwidth for an individual VC is allowed to be low, the cell scheduling method of
FIG. 1
can require a large number of queues
160
. The number of queues required is determined by the maximum value of the &Dgr; parameters. This is because when a cell is transmitted on a VC, the VC can be returned to the queue number &Dgr; to allow the next cell transmission in &Dgr; time slots. It can be shown that the maximum value of &Dgr; is the ratio TB/mb, where TB is the total bandwidth of port
130
and mb is the minimum bandwidth supported by the ATM switch (here the bandwidth is measured in bits per second). For example, if port
130
is an optical carrier OC-192 port (9953.280 Mbps) and “mb” represents a DSO voice channel (64 Kbps), the number of queues required is 9953280/64=155520. This large number of queues requires a large memory. The large memory increases the size, cost and power dissipation of the switch.
In one scheduler of the present invention, the number of queues required is reduced exponentially to about log (max &Dgr;) where “log” is a logarithm base
2
and “max &Dgr;” is the maximum value of &Dgr;. The scheduler works as follows. Let the non-active queues be denoted as Q
1
, Q
2
, . . . QN, where N is the number of queues. N is ┌log (max &Dgr;)┐, i.e., log (max &Dgr;) rounded up to an integer. VCs are transferred from queue Q
1
to the active queue every second cell time, from queue Q
2
to the active queue every fourth cell time, from queue Q
3
to the active queue every eighth cell time, and so on. VCs are transferred from queue Qi to the active queue every 2
i
th cell time.
As in
FIG. 1
, one VC is selected from the active queue for transmission every cell time. A cell is transmitted on the VC and the VC is moved to the queue Qi, where the queue number i=log &Dgr;, rounded to an integer. If the VC has waited in the active queue for “d” cell times, then i=log (&Dgr;−d), rounded to an integer.
The invention is not limited to the embodiments described above. Queues Qi and the active queue can be replaced with non-queue data structures. The invention can be applied to non-ATM networks. The invention can be applied to data flows other than VCs. Other embodiments and variations are within the scope of the invention, as defined by the appended claims.
REFERENCES:
patent: 5231633 (1993-07-01), Hluchyj et al.
patent: 5533009 (1996-07-01), Chen
patent: 5535201 (1996-07-01), Zheng
patent: 5633859 (1997-05-01), Jain et al.
patent: 5771234 (1998-06-01), Wu et al.
patent: 5793747 (1998-08-01), Kline
patent: 5982771 (1999-11-01), Caldara et al.
patent: 6359861 (2002-03-01), Sui et al.
patent: 6408005 (2002-06-01), Fan et al.
patent: 6438134 (2002-08-01), Chow et al.
patent: 0 710 046 (1996-05-01), None
patent: 0 874 531 (1998-10-01), None
patent: 0 874 532 (1998-10-01), None
MMC Networks, Inc.,AF5500 Chip Set User Guide, Jul. 1998, pp. 8-1 through 8-40.
Applied Micro Circuits Corporation
MacPherson Kwok & Chen & Heid LLP
Shenker Michael
Yao Kwang Bin
LandOfFree
Selection of data for network transmission does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Selection of data for network transmission, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Selection of data for network transmission will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3107230