Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-08-31
2002-11-05
Jung, Min (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S252000, C370S395210
Reexamination Certificate
active
06477146
ABSTRACT:
TECHNICAL FIELD OF INVENTION
The following invention relates generally to the improved operation of a usage parameter control (UPC) device for asynchronous transfer mode (ATM) communications systems, and in particular, to following wrapping of finite counter and register elements used to keep track of infinitely progressing time.
BACKGROUND OF THE INVENTION
In recent years, ATM communication has become increasingly popular. Prior to this preference for ATM, time division multiplexing (TDM) systems were the preferred mode of communication. In TDM systems, each user was allocated a particular time slot within a standard time interval during which a communication channel would be dedicated to the user. In this system, the time slot would be unavailable to other users regardless of whether the allocated user was actually using it which frequently resulted in wasted bandwidth.
In ATM systems, by contrast, information is transmitted as bandwidth is available without regard to time. In order to keep ATM traffic flowing, each user agrees, by way of a contract with the ATM network operator, to a minimum length of time, t, between transmission of his or her cells. A maximum number of cells which may be transmitted in an interval, T, is also agreed upon. The time, t, determines the user's peak cell rate (PCR) and the interval, T, determines the user's sustained cell rate (SCR). A third parameter, maximum burst size (MBS) which specifies the maximum number of cells which are permitted to be transmitted consecutively at the PCR, is also contracted for. In order to prevent users from exceeding their respective limitations, ATM networks may employ a UPC device which can monitor these and other usage parameters.
In an ATM system, UPC monitoring is typically performed in accordance with standard generic cell rate algorithms (GCRAs). Once such GCRA is a “leaky bucket” algorithm, in which a figurative bucket “fills” proportional to the actual cell rate received from a user and “drains” at a fixed rate proportional to the contracted service rate parameters. If the user exceeds the limits on contracted parameters, such as PCR or SCR, the “bucket” will “overflow” and the user's cells may be either discarded or tagged as having a low priority.
ATM communications may be carried out using a constant bit rate (CBR) or using a variable bit rate (VBR). A CBR connection essentially mimics the old TDM systems. Monitoring of a CBR connection is accomplished using a single leaky bucket. Conformance is characterized by the peak cell rate (PCR) and the corresponding cell delay variation tolerance (CDVT) due to, e.g., head-of-line blocking. The CDVT is defined in relation to the PCR. The capacity of the leaky bucket is 1/PCR (a.k.a. IP)+CDVT specified for the cell flow. The drain rate of the PCR bucket is 1/PCR.
FIG. 1
is a flow chart illustrating the operation of a leaky bucket GCRA used to monitor usage parameters for a CBR connection. In block
102
, a cell arrives at time T
TA
. Thereafter T
TATp
for the particular user is read from memory in block
105
. T
TATp
is the time value at which the “bucket” will have drained to an empty condition in the absence of new cell arrivals. It is calculated during cell arrivals and is adjusted in proportion to the contracted PCR rate for CBR service. In Block
107
a comparison between T
TA
and T
TATp
is performed. If T
TA
is greater than T
TATp
, i.e. the cell arrived after the bucket had completely emptied, then the cell is accepted at block
111
, and, at block
114
, T
TATp
is set to T
TA
+1/PCR. If T
TA
is not greater than T
TATp
, i.e. the bucket is not completely empty, a check is done in block
117
to determine if there is enough room in the partially full bucket to accept the cell based on its maximum capacity of 1/PCR+ CDVT. If not, the cell is discarded at block
120
. If so, the cell is accepted at block
122
, and T
TATp
is updated at block
125
to equal T
TATp
+1/PCR.
In a variable bit rate (VBR) system, a second leaky bucket GCRA is used in addition to the first leaky bucket GCRA described above in order to ensure compliance with the contracted sustained cell rate (SCR) and maximum burst size (MBS). The capacity of this second leaky bucket is 1/SCR+Burst Tolerance (BT)+CDVT. Burst tolerance is calculated from the contracted SCR, PCR, and MBS, and is the additional bucket depth required to hold “MBS-1” more cells arriving at the PCR rate (BT={MBS−1}×{1/SCR−1/PCR}). The sum of BT and CDVT is given the identifier “L”. The drain rate of this bucket is 1/SCR.
FIG. 2
shows the flow diagram for this second GCRA for the case where it is used in conjunction with the GCRA of FIG.
1
. If a cell is accepted in accordance with the GCRA of
FIG. 1
, i.e., either of boxes
128
or
131
of
FIG. 1
are reached, then T
TATs
is retrieved from memory in block
137
. T
TATs
is the time value at which the “bucket” will have drained to an empty condition in the absence of new cell arrivals, and is calculated in increments of 1/SCR which provides enough time for a full bucket to leak enough to provide room for another cell. A comparison between the T
TA
of the cell from box
102
of FIG.
1
and the theoretical arrival time, T
TATs
, is then performed at box
140
.
If the result of the comparison of box
140
is that T
TA
is greater than T
TATs
, then the cell is accepted at box
143
, and T
TATs
is set to T
TA
+1/SCR at box
146
. If the result of box
140
is that T
TA
is not greater than T
TATs
, then the system checks at box
149
to see whether the sum of T
TA
plus the burst tolerance (BT) plus the CDVT is greater than T
TATs
, where BT is a function of the contracted parameters MBS, PCR and SCR. If not, the cell is non-conforming and is discarded at box
152
. If, on the other hand, the condition T
TA
+BT+CDVT>T
TATs
is met, the cell is accepted at box
155
and T
TATs
is set to T
TATs
+1/SCR at box
158
.
A brief example using simple, if not practical, hypothetical figures for SCR, MBS and PCR will better illustrate the operation of the leaky bucket of FIG.
2
. Assuming a VBR service with contracted parameters of SCR=5 cells/sec, a MBS=3 cells, and a PCR of 100 cells/sec and CDVT of 0.02 sec. This results in 1/SCR=IS=0.2 sec/cell, BT=0.38 sec, and L=BT+CDVT=0.4 sec. For the purposes of this example, assume that the criteria of the first leaky bucket check against PCR and CDVT is always favorable and that the initial value of T
TATs
is 0.0. If a first cell is transmitted at 0.01 seconds, i.e., T
TA
=0.01, the result of box
140
is that T
TA
>T
TATs
so that the cell is accepted at box
143
and T
TATs
is set to T
TATs
+1/SCR, i.e., 0.0+0.2=0.2 sec at box
146
. A second cell now arrives at time 0.02 seconds. The result of box
140
is that T
TA
<T
TATs
so that the condition T
TA
+L>T
TATs
is checked at box
149
. We find that this condition is met (0.02+0.4>0.2). The cell is accepted at box
155
and T
TATs
is set to T
TATs
+1/SCR, i.e., 0.2+0.2=0.4 sec at box
158
. Similarly, a third cell arrivals at 0.03 sec, the cell is accepted and T
TATs
is set to 0.6 sec. If a fourth cell arrives at 0.04 sec, T
TA
+L will not be greater than T
TATs
. The fourth cell is therefore discarded at box
152
and T
TATs
remains unchanged at 0.6 sec. The same result occurs for any cell received earlier than time 0.2 seconds. After that time, the condition T
TA
+L>T
TATs
of box
149
is again met. Furthermore, if the fifth cell does not arrive until a time later than 0.6 sec, the bucket will be completely empty and the T
TA
>T
TATs
condition will be met.
Those skilled in the art will appreciate that the above description is a simplified explanation of ATM systems, the role of UPC devices and leaky buckets generally. With respect to ATM systems, detailed explanations of the operation of such systems may be found in Us
Bottiglieri Michael P.
Samori Michael J.
Fujitsu Network Communications, Inc.
Jung Min
LandOfFree
Usage parameter control device for asynchronous transfer... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Usage parameter control device for asynchronous transfer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Usage parameter control device for asynchronous transfer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2926681