SYSTEME DE GESTION DYNAMIQUE DE TAMPON POUR SELECTEURS MTA

DYNAMIC BUFFER MANAGEMENT SCHEME FOR ATM SWITCHES

Abrégé français

L'invention concerne un système de gestion de tampon pour une mémoire partagée d'un sélecteur MTA, qui fixe des seuils dynamiques différents (18) pour différentes connexions virtuelles Vcs (10), conformément à la formule: Tsub I(U) = Tsub Fsub i + gamma sub i . (B-U), B représentant la capacité totale du tampon partagé et U la capacité de la partie utilisée du tampon. Selon l'invention, Tsub i(U) représente le seuil (en nombre de cellules) pour la i?ième¿ connexion lorsque la partie utilisée du tampon est U, Tsub Fsub i représente l'attribution de tampon requise (en nombre de cellules) pour le i?ième¿ tampon de connexion lorsque le tampon est plein et gamma sub i représente une puissance de deux pour la i?ième¿ connexion au moment où la connexion est établie. Tsub Fsub i et gamma sub i sont choisis en fonction de la catégorie de la connexion (12). En outre, le système de gestion de tampon fixe les capacités minimum et maximum du tampon en fonction de la catégorie de la connexion. De préférence, un tampon minimum est garanti pour les catégories de services au-dessus d'un débit binaire non spécifié UBR. Pour le trafic UBR, le tampon minimum est déterminé par le nombre de connexions accumulées. La capacité maximum de la mémoire tampon pour chaque connexion est fonction de la capacité totale du tampon, B, Tsub Fsub i et gamma sub i.

Abrégé anglais

A buffer management scheme for a shared memory in an ATM switch sets different
dynamic thresholds (18) for different Vcs (10) according to the formula: Tsub
i (U) = Tsub Fsub i + gama sub i . (B - U) where B is the total size of the
shared buffer and U is the size of the used portion of the buffer. According
to the invention, Tsub i (U) is the threshold (in number of cells) for the ith
connection when the used portion of the buffer is U, Tsub Fsub i is the
required buffer allocation (in number of cells) for the ith connection buffer
when the buffer is full and gama sub i is a power of two chosen for the ith
connection at the time the connection is set-up. Both Tsub Fsub i and gama sub
i are chosen based on the service category of the connection (12). In
addition, the buffer management scheme sets minimum and maximum buffer sizes
based on the service category of the connection. Preferably, a minimum buffer
is guaranteed for service categories above UBR (unspecified bit rate). For UBR
traffic, the minimum buffer available is determined by the number of
backlogged connections. The maximum buffer size for each connection is a
function of the total buffer size B, Tsub Fsub i and gama sub i.

Revendications

13
Claims:
1. A dynamic buffer management method for managing multiple ATM
queues in a shared buffer, comprising:
a) creating a queue for each virtual connection at the time
the virtual connection is set up;
b) setting a minimum queue threshold for each queue at the
time it is created based on the service category of the virtual
connection for which the queue was created;
c) dynamically adjusting the queue threshold for each queue
based on the minimum queue threshold and the amount of unused
shared buffer space.
2. A method according to claim 1, wherein:
said step of adjusting includes increasing the minimum
queue threshold by a fractional amount of the unused shared
buffer space.
3. A method according to claim 2, wherein:
the fractional amount which is added to the minimum queue
threshold is determined by the service category of the virtual
connection for which the queue was created.
4. A method according to claim 1, further comprising:
d) setting a maximum permitted queue occupancy for each queue
at the time it is created based on the service category of the
virtual connection for which the queue was created.
5. A method according to claim 4, wherein:
the maximum permitted queue occupancy is a fractional
amount of the dynamically adjusted queue threshold when the
buffer is empty.

14
6. A method according to claim 4, further comprising:
e) setting a minimum queue occupancy for each queue at the
time it is created based on the service category of the virtual
connection for which the queue was created.
7. A method according to claim 6, Wherein:
the minimum queue occupancy is based on the number of
active backlogged connections.
8. A dynamic buffer management method for managing multiple ATM
queues in a shared buffer, comprising:
a) creating a queue for each virtual connection at the time
the virtual connection is set up;
b) setting a minimum queue threshold TFi for each ith queue at
the time it is created based on the service category of the
virtual connection for which the queue was created;
c) dynamically adjusting the queue threshold for each queue
based on the formula
Ti(U) = TFi + .gamma.i ~ (B-U)
where B is the total size of the shared buffer, U is the size of
the currently used portion of the buffer, .gamma.1 is a fraction based
on the service category of the virtual connection for which the
queue was created, and Ti(U) is the dynamically adjusted
threshold (in number of cells) for the ith connection when the
used portion of the buffer is U.
9. A method according to claim 8, wherein:
.gamma.i = 2y where y is chosen based on the service category of
the connection.
10. A method according to claim 9, further comprising:
d) setting a maximum permitted queue occupancy Qmax for each
queue at the time it is created based on the formula
<IMG>

15
11. A method according to claim 10, wherein:
for CBR service and for VBR-rt service y = <IMG> and
T p = ~PCR .PCR;
F xR
for VBR-nrt service y=-4 and T F=b e.
for ABR service y=-4 and T F=TBE; and
for UBR service y=0 and T F=0.
12. An apparatus for dynamically managing multiple ATM queues
in a shared buffer, comprising:
a) means for creating a queue for each virtual connection at
the time the virtual connection is set up;
b) means of setting a minimum queue threshold for each queue
at the time it is created based on the service category of the
virtual connection for which the queue was created:
c) means for dynamically adjusting the queue threshold for
each queue based on the minimum queue threshold and the amount
of unused shared buffer space.
13. An apparatus according to claim 12, wherein:
said means for dynamically adjusting includes means for
increasing the minimum queue threshold by a fractional amount of
the unused shared buffer space.
14. An apparatus according to claim 13, wherein:
said means for dynamically adjusting includes means for
determining the fractional amount which is added to the minimum
queue threshold based upon the service category of the virtual
connection for which the queue was created.
15. An apparatus according to claim 12, further comprising:
d) means for setting a maximum permitted queue occupancy for
each queue at the time it is created based on the service
category of the virtual connection for which the queue was
created.

16
16. An apparatus according to claim 15, further comprising:
e) means for setting a minimum queue occupancy for each queue
at the time it is created based on the service category of the
virtual connection for which the queue was created.

Description

CA 02338218 2001-O1-19
WO 00/05656 PCT/US99/16477
i
DYNAMIC BUFFER MANAGEMENT SCHEME FOR ATM SWITCHES
This application claims the benefit of provisional
application Serial Number 60/093,681 filed July 22, 1998.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates broadly to the field of
telecommunications. More particularly, the present invention
relates to the management of shared memory buffers in an
asynchronous transfer mode (ATM) switch or node by setting of
queue size and dynamic queue thresholds as functions of overall
buffer occupancy and service category.
2. State of the Art
Perhaps the most awaited, and now fastest growing
technology in the field of telecommunications in the 1990's is
known as Asynchronous Transfer Mode (ATM) technology. ATM is
providing a mechanism for removing performance limitations of
local area networks (LANs) and wide area networks (WANs) and
providing data transfers at a speed of on the order of
gigabits/second. The variable length packets of LAN and WAN
data are being replaced with ATM cells which are relatively
short, fixed length packets. Because ATM cells can carry voice,
video and data across a single backbone network, the ATM
technology provides a unitary mechanism for high speed end-to-
end telecommunications traffic.
Because the data contained in the ATM cells can be
generated from either generally fixed rate communications, or
bursty type communications, it will be appreciated that traffic
accommodation mechanisms have been introduced in order to avoid
situations where ATM switches or nodes are over-taxed, resulting
in loss of cells. In particular, various buffering mechanisms
are well known. Among these include input queues, output
queues, and shared buffers. It is now generally agreed that

CA 02338218 2001-O1-19
WO 00/05656 PCT/US99/16477
2
shared buffers are the preferred mechanism for implementing
either input queues or output queues (or both) in an ATM switch.
The simplest implementation of shared memory buffers sets
up queues for virtual connections (VCs) as needed and sets a
queue length threshold for each queue regardless of the service
category of the VC. This implementation is often referred to as
the "Static Threshold" scheme. Arriving cells are admitted to
the queue only if the queue length is smaller than the threshold
set for the queue. Although the Static Threshold scheme is
simple to implement, it does not adapt to changing traffic
conditions. If one port in the switch (one VC) is very active,
cells from that VC will be lost even if there is shared memory
available to enlarge the queue.
Several "Dynamic Threshold" schemes have been proposed.
These schemes attempt to adjust the queue length thresholds of
all of the queues in shared memory based on the amount of
currently available memory. One scheme for dynamic buffer
management is disclosed in A. K. Choudhury and E. L. Hahne,
Dynamic Oueue Length ThrashnldS in a Shared Memorv ATM Switch,
Proc. IEEE INFOCOM '96 (San Francisco, California) pp. 1-9,
March 1996 (hereinafter "Choudhury"). According to Choudhury, a
control threshold T(t) at time t is set (using notation of the
present invention) equal to a multiple y of the unused buffer
space as shown in equation (1) where B is the total size of the
shared buffer and U is the size of the used portion of the
buffer.
(1)
If any queue reaches a length greater than or equal to the
control threshold T(t), cells destined for that queue will be
discarded. Choudhury states that ( should be a positive,
negative, or zero power of two so that a shifter can be used to
regulate the control threshold. According to Choudhury, y is
adjusted depending on whether the switch is moderately loaded or

CA 02338218 2001-O1-19
WO 00/05656 PCT/US99/16477
3
heavily loaded and whether the load is uniform across all ports
or non-uniform with one port more heavily loaded than others.
The Dynamic Threshold scheme of Choudhury is essentially a
Static Threshold Scheme which is dynamically tuned according to
load conditions in the switch. All VCs are treated equally and
a certain amount of buffer space is intentionally wasted to
accomplish this. The Choudhury scheme excels when there is a
uniform load on the switch but does not provide much improvement
over Static Threshold schemes when only a few ports in the
switch are overloaded. Also, as specifically noted by
Choudhury, the scheme does not address the issue of multiple
service categories.
Current ATM service is offered in different categories
according to a user's needs. Some of these categories include
constant bit rate (CBR), variable bit rate (VBR), unspecified
bit rate (UBR), and available bit rate (ABR). Some categories
are given a higher priority than others when decisions are made
to discard cells. For example, it is desirable that cells
rarely, if ever, be discarded from CBR traffic. It has been
recognized that the category of service should be taken into
account when managing queues in shared memory. However, no
scheme has been proposed for doing so.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide a
dynamic buffer management scheme for ATM switches.
It is also an object of the invention to provide a dynamic
buffer management scheme which allocates shared buffer memory to
VC queues based in part on the service category of the VC.
It is another object of the invention to provide a dynamic
buffer management scheme which adjusts the allocation of shared

CA 02338218 2001-O1-19
WO 00/05656 PCT/US99/16477
4
buffer memory to VC queues based in part on the service category
of the VC and overall congestion in the ATM switch.
In accord with these cbjects which will be discussed in
detail below, the buffer management scheme of the present
invention sets different dynamic thresholds for different VCs
according to the formula expressed in equation (2).
T~(U) = TF, + y~ ~ (B-U) (2)
As in equation (1), B is the total size of the shared buffer and
U is the size of the used portion of the buffer. According to
the invention, Ti(U) is the threshold (in number of cells) for
the ith connection when the used portion of the buffer is U. TFi
is the minimum required buffer threshold allocation (in number
of cells) for the ith connection buffer when the buffer is full
and Yi is preferably a power of two chosen for the ith connection
at the time the connection is set-up. Both TFi and 'yi are chosen
based on the service category of the connection.
In addition, the buffer management scheme of the present
invention sets minimum and maximum buffer sizes based on the
service category of the connection. Preferably, a minimum
buffer is guaranteed for service categories above UBR
(unspecified bit rate). For UBR traffic, the minimum buffer
available is determined by the number of backlogged connections.
The maximum buffer size for each connection is a function of the
total buffer size B, TF;,, and yi.
Additional objects and advantages of the invention will
become apparent to those skilled in the art upon reference to
the detailed description taken in conjunction with the provided
figures.

CA 02338218 2001-O1-19
WO 00/05656 PC'T/US99/16477
J
BRIEF DESCRIPTION OF '.'HE DRAWINGS
Figure 2 is a graph of the relationship between dynamic
threshold and overall buffer occupancy; and
Figure 2 is a flow chart illustrating the operations of an
apparatus according to the invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
As mentioned above, a dynamic trreshold T(U) can be set
such that if the number of cells Q~~ '_n a buffer equals or
exceeds the threshold (Q~~?T(U)), cells arriving at the buffer
are discarded. Referring now to Figure 1, the dynamic threshold
T(U) is shown to be a linear function of the overall buffer
occupancy U. In particular, it will be noted that as the
overall buffer occupancy increases, the dynamic threshold
decreases, i.e. cells will be discarded sooner. Thus, the
linear function has a negative slope. The "y intercept" of the
function, labelled "x" on the y-axis of Figure 1, is the integer
value of the dynamic threshold when the overall buffer occupancy
is empty. Thus, the minimum required buffer threshold
allocation To should be some integer number less than or equal to
x. According to standard practices, puffer thresholds are set
by add/subtract shift operations. Therefore, the slope of the
function is preferably limited to an nteger power of two, i.e.
2y. The intercept and the slope of the function T(U) can be
chosen so that the threshold has some value TF when the buffer is
full as shown in equation (3).
T(B)=TF=x-2''B (3)
Thus, the value of the intercept x can be expressed as shown in
equation (4).
x=T +2''B (4)
F

CA 02338218 2001-O1-19
WO 00/OS656 PCT/US99/16477
6
As mentioned above, the threshold when the buffer is empty
should be less than or equal to x as shown in equation (5).
x z Ta (5)
Substituting equation (4) for x in equation (5) yields equation
( 6) .
TF + 2yB z To (6)
Equation (6) can be rewritten as equation (7).
2 To - TF (~)
B
Therefore, an appropriate algorithm for choosing the value of y
in order to set the slope of the threshold function can be
expressed as equation (8).
(8)
According to one embodiment of the invention, equations (4)
and (8) may be used directly at the time a VC is set up to
determine x and y from B, Ta, and TF. However, in the preferred
embodiment y is selected on a per class basis, i.e. the value of
y depends solely on the service category and the size of the
buffer. TF is also preferably based solely on the service
category.
With the above considerations in mind, the buffer threshold
formula according to the invention can be expressed in
simplified form as equation (9).
T~(U) = TF + y, (B-U) (9)
As shown in equation (9), T1(U) is the threshold for the ith
connection buffer when the overall buffer usage is U. B is the
total shared buffer size, and yi ~.s 2~ where y is chosen for the

CA 02338218 2001-O1-19
WO 00/05656 PCT/US99/16477
7
ith connection at the time the connection is set-up based on
service category and total shared buffer size. The thresholds,
buffer size and buffer usage are given as an integer number of
cells.
According to a preferred embodiment of the invention,
minimum and maximum queue occupancy levels (Q",in and Q",~X) are
also set by the dynamic thresholding scheme for each connection.
Table 1 illustrates the presently preferred recommended dynamic
threshold parameters for five different service categories.

CA 02338218 2001-O1-19
WO 00/05656 PCT/US99/16477
8
Service Y TF Qr~ Qmin
Category
T~ + 2rB
' ' PCR ' PCR
I ~ ~
CBR log ~ (1 +2r) ~R
PCR
T'~ + 2r8
' PCR I ' PCR
2 2
VBR-rt log (l+2r) ~R
4 ~ PCR -
-
+ z-'B
r
VBR-rirt ~ -4 ~ be ~ ~ be
fl+z~)
,
Tp + 2"B
- TBE
~R 4 ~ TBE fl+z-'J
UBR 0 I 0 B
I+N
Table 1
In Table 1, a is a dimensionless coefficient as defined by
ITU I.371, the complete disclosure of which is hereby
incorporated herein by reference. The default value of a is
120. PCR refers to the peak cell rate and ~p~R refers to the cell
delay variation tolerance or CDVT as defined in ITU I.371 for
constant bit rate (CBR) and variable bit rate-real time (VBR-rt)
service categories. As above, B is the size of the shared
buffer in number of cells. be is the effective buffer size as
defined in IEEE Journal on Selected Areas in Communications,
Vol. 13, No. 6, pp. 1115-11127 (1995) and TBE is the transient
buffer exposure as defined in ATM forum Traffic Management
Specification 4.0, April 1996, #af-tm-0056.000. The minimum
buffer size Q~n is the minimum size of the buffer in number of
cells when the shared buffer is completely full. Q",~,~ is the
maximum queue occupancy (in number of cells) allowed for a
particular connection. For unspecified bit rate (UBR) service,
Q,~,~ is purely a function of the total shared buffer size and Q~n
is a function of total shared buffer size and number of
backlogged connections N. For a given service category, the
value of the y parameter should be chosen such that the
resulting value of Q,r,aX is greater than or equal to the maximum
value of Q",,ln for the service category. Moreover, for a given
service category, y should be set proportionally to the expected
queue length of a connection in the category.

CA 02338218 2001-O1-19
WO 00/05656 PCT/US99/16477
9
Several properties of the buffer management scheme can be
ascertained from an analysis of the t~:reshold formula shown in
equation (9). For example, if there are N connections each
having a queue threshold defined by T:i and yi, and if all
connections are completely backlogged (i.e. their corresponding
queue lengths are at their corresponding dynamic thresholds Ti (i
- 1, 2, 3,..., N)), then the steady-state vc threshold (or the
queue length) for each connection i can be expressed as shown in
equat ion ( 10 ) .
,y N
Tp''1+ ~ ykJ+Y~IB- TF
(10) T = k-!lk~i) k=1(ksi) t
i vc N
1+ ~
k~l j
The truth of equation (10) can be proven by iterative
computation for N?2. For example, where N=2, there will be two
iterations of equation (9), one for i=1 and one for i=2. If the
second equation is rewritten as a function of U as shown in
equation (11), it can be substituted into the first equation to
establish the relationship between the two thresholds as shown
in equation (12) .
~TF -Tz)
(11) U= =yz +B
r, r,
T l-T F~- r, ~T F=+ r, ~T _
(12)
Under a complete backlog condition U=TI+T2 which can be used
to rewrite the second iteration of eauation (9), i.e. where i=2,
as equation (13) .
T z-T F + yzB yzT r y_T z
(13)

CA 02338218 2001-O1-19
WO 00105656 PCT/US99I16477
Substituting equation (12) in equation (13) yields equation
(14) which is exemplary of equation (10).
T _ T i~~l+yl~+yzyB TFO
(14) 2 ~1+yl+Y2~
Similarly, if the expression for T2 from equation (14) is
substituted in equation (12), equation (15) is produced which is
also exemplary of equation (10).
T _ TF; .~1+y2~+y1 yB Tay
(15) 1 ~1 +yi+ya~
Repeating this process iteratively for higher values of N, will
establish the truth of equation (10).
A first corollary to the proof of equation (10) is that if
there are N backlogged connections, each with the same yi but
with different TFi, then their steady-state queue lengths will be
given by equat ion ( 16 ) .
N
TF(1+(N-1)y)+y B- ~ T~
( 16 ) T - Q _ ; xmlx.;)
(1 +Ny)
A second corollary to the proof of equation (10) is that if
there are N backlogged connections with the same yi and with the
same TFi, then their steady-state queue lengths will be given by
equation (17).
T + yB
(17) a ~, (I+Ny)
The analytical results of equations (10), (16), and (17)
were compared with simulation results obtained by simulating
three connections sharing a common memory pool. The simulation

CA 02338218 2001-O1-19
WO 00/05656 PCT/US99/16477
11
memory was partitioned into per connection logical queues.
Complete backlogged conditions were created by having per
connection input rates exceed the output rates. A comparison of
the simulation results with the analytical results is
illustrated in Table 2.
Connection Queue Queue
Number Parameters Lengths Lengths
of (B=1 via via
~~ Analytical Simulations
cells) Results
ConnectionsY1~TF1 Y2TF2 cQells~ ~s ills ~ ~
I Y3TF3 s
1 l~lp ~ - 505 - - 504
, I ~
2 1,10 2,15 - 253.7502.5 254 502
~ ~
~
3 1,10 2,15 4,20 129.3253.7497.5128 254 498
,
3 1,10 1,20 ~ 1,30 245 ~ 265 ~ ~ 256 264
255 244
Table 2
As can be seen in Table 2, the analytical results and the
simulation results are virtually identical. The small
differences between the results are because the simulation
results were truncated to the nearest integer.
Those skilled in the art will appreciate that the dynamic
buffer management scheme may be implemented in a combination of
hardware and software in order to perform the functions outlined
above. Referring now to Figure 2, an apparatus according to the
invention will determine at 10 when a new virtual connection is
about to be established. If a new VC is being established, the
apparatus will determine at 12 the service category of the new
VC and will set the parameters based on the service category at
19 . These parameters include TF, Y, Q~X. and Q",in . At 16, the
apparatus will determine the amount of free space in the shared
buffer and at 18 the apparatus will set the dynamic queue
threshold using equation (9). The apparatus will return to step

CA 02338218 2001-O1-19
WO 00/05656 PCT/US99/16477
12
10. When no new VC is being established the apparatus will
continue to monitor the amount of free space in the shared
buffer at 16 and will reset the dynamic queue thresholds at 18
accordingly. Based on the queue thresholds, determination may
be made by the apparatus to discard cells which would cause the
queue length to exceed the queue threshold.
There have been described and illustrated herein several
embodiments of a dynamic buffer management scheme for ATM
switched. While particular embodiments of the invention have
been described, it is not intended that the invention be limited
thereto, as it is intended that the invention be as broad in
scope as the art will allow and that the specification be read
likewise. It will therefore be appreciated by those skilled in
the art that yet other modifications could be made to the
provided invention without deviating from its spirit and scope
as so claimed.

Dessin représentatif