Vol.14 No.3
JOURNAL OF ELECTRONICS
July 1997
A N A L Y S I S OF T H E L E A K Y B U C K E T O U T P U T P R O C E S S E S FOR BURSTY SOURCES IN ATM NETWORKS* Liao Jianxin (National Lab. of Switching Tech. and Telecom. Networks BUPT of Chlna, Belting 100088)
Li Lemin
Sun Hairong
(National Key Lab. of Optical Fiber Commun. UEST of China, Chengdu 610054) Abstract
In A T M
networks, bursty sources can be described as the Interrupted Bernoulli
Process(IBP). With the use of the thin process theory, the Probability Generating Function(PGF) of the IBP is obtained. A n iterativealgorithm, which can be used to calculatethe IBP probability distribution, is presented. The bursty source's equivalent description is discussed. It is proposed that the leaky bucket output process can be approximately described as the IBP. The accuracy of the analyticalresults has been largelyvalidated by means of the simulation approach. Moreover, how to improve its accuracy is discussed. The smoothing function of the leaky bucket algorithm is quantitativelyanalyzed. Key
words
A T M ; Bursty source, IBP, Leaky bucket algorithm, Output process, Traffic
smoothing
I. I n t r o d u c t i o n Traffic control is a key technique in an ATM network. Recommendation 1.371 specified by ITU-T[1]: When a new connection request is received at the network, the call admission procedure is executed to decide whether to accept or reject the call. A cMl is accepted if the network has enough resources to provide the quality-of-service requirements of the connection request without affecting the quality of service provided to existing connections. The procedure referred to as Call Admission Control(CAC). The traffic is high burstiness in an ATM network. Call admission is not sufficient to prevent congestion mainly because users may not stay within the connection parameters negotiated at the call set-up phase. Accordingly, the network must ensure that sources stay within their connection parameters negotiated at the connection set-up phase. The function referred to as traffic policing or usage parameter control (UPC). The large amount of study show that the leaky bucket algorithm is a kind of effective UPC algorithm. After the leaky bucket scheme was introduced by S. Akhtar, a number of its variants have been proposed 12]. The leaky bucket algorithm has been studied in Refs.[3-6]. The smoothing effect is characterized by the squared coefficient of variation of the interdeparture time from the leaky bucket. Very little work has been done to obtain the smoothing effect of the leaky bucket. The analysis of the output process of the leaky bucket was performed under the hypothesis of Poisson modelfE. But the ATM bursty traffic cannot always be described *Supported by the National Postdoctorial Science lhmd of China
No.3
ANALYSIS O F T H E L E A K Y B U C K E T O U T P U T PROCESSES
229
in term of Poisson model. The average rate and the variance of the output process of the leaky bucket were analyzed by the fluid-flow ways in Ref.[8]. The paper is organized as follows: In Section II, the Probability Generating Function(PGF) of the IBP is obtained with the use of the thin process. An iterative algorithm, which can be used to calculate the IBP probability distribution, is presented. The bursty source's equivalent description is discussed. In Section III, it is proposed that the leaky bucket output process can be approximately described as the IBP. In Section IV, the accuracy of the analytical results has been largely validated by means of the simulation approach. Moreover, how to improve its accuracy is discussed. The smoothing function of the leaky bucket algorithm is quantitatively analyzed. Section V provides the conclusions.
II. B u r s t y Source M o d e l The bursty source was described as the IBP. The IBP is defined over a slotted time (discrete-time) time axis and it comprises two states, an "ON" state and an "OFF" state, which alternate. The time the process spends in each state is geometrically distributed. The mean values are ToN and TOFF, respectively. Cells occur in a Bernoulli fashion when the process is in the "ON" state. No cell occurs if the process is in the "OFF" state. A slot contains a cell with probability f , if the process is in the "ON" state. Given that the process is in the "ON" states (or "OFF" state) at slot i, it will change to "OFF" state (or "ON" state) in the next slot i + 1 with probability a = 1/ToFF (or /3 = 1/ToN). The bursty source traffic can be effectively described as the three parameters IBP model [9]. IBP is a special thin process which can be expressed by the three parameters, a,/3 and f[a0]. The reverse thin process N occur in the active state fashion. AI (z) represents the P G F of the reverse thin process N, we have Al(Z) : (1 - / 3 ) z + ot/3z2/[1 - (1 - or)z]
(1)
AIBP(Z) represents the P G F of the IBP, we have AIBP(Z) : f, Al(z)/[1 - (1 - f,)Aa(z)] = (a2z 2 + aaz)/(b2z 2 + blz + 1)
(2)
where a2 = - f , , ( 1 b2 :
AIBP(Z)
(1 -
- a -/3),
al = f8(1 -/3)
f,,)(1 - a - / 3 ) ,
bl = - [ ( 1 - a ) + (1 - I,,)(1 - / 3 ) ]
has been defined as z-transform for the interarrival times of the IBP-stream
cells. The probability distribution of the interarrive time can be obtained inverting AIBp(z). Let Pi be the probability that the interarrive times is equal to i service slots. We can then solve for Pi, i =.0, 1 , . . . , recursively as follows:
P,=a,-
min{2,i} Z bjP,_j, 3=1
where ai = O, i > 2.
i=0,1,2,...
(3)
230
JOURNAL OF ELECTRONICS
Vol.14
From Eq.(2), the average arrivalrate, fa and the squared coefficientof variation of the interarrivaltime, C2Bp are as follows:
/~ =/o~I(~ + 8)
(4)
C ~ s P ~- 1 -~- f 8 [ ~ ( 2 -- O~ -- ~ ) / ( 0 ~ -~- 8 ) 2 -- 1]
(5)
C~BP can be seen as a measure of the burstiness. A complete description of a bursty source is given by three parameters: the peak rate fo, the average rate f , and the average bursty length BL[ TM
/J = f ~ / B L a
=
fof~/[BL(fo
(6) -
1~)]
(7)
c~Bp can be obt~ned by Eqs.(5), (6) and (~) as Ci2Bp = I -~-fa -- 218 + 2BL(1 -/,,~Is)2
(S)
Obviously, by decreasing the bursty length, we can decrease the burstiness. In addition, by decreasing the peak rate, keeping the average load and the average bursty length constant, we can decrease the burstiness.
III. O u t p u t P r o c e s s A n a l y s i s The basic idea of the leaky bucket algorithm is that a cell, before entering the network, must obtain a token from consuming one token and immediately depart from the leaky bucket if there is at least one token available in the token pool. Tokens are generated at a constant rate R and placed in a token pool. Although variations exist, there are generally two parameters of a leaky bucket: the token pool size B, and the token generation rate R. A token size equals to a cell size. An additional parameter is buffer M, the cell is buffered and only allowed to enter the network after the tokens are obtained. Here the leaky bucket performs a shaping function. We model the leaky bucket by making use the fictitious queue illustrated in Fig1. The peak rate, the average rate and the average burst length of the burst sources are represented by Fs, Fa and BL, respectively. The fictitious queue length Q/ is introduced for easy analysis. In fact, the fictitious queue length Q! is not exist.
Input M~
1
Output
J
R
-Illlill 07 Fig.1 Fictitious queue leaky bucket model
No.3
ANALYSIS OF T H E LEAKY B U C K E T O U T P U T PROCESSES
231
Let us define the following joint probability distribution:
Fo(q) = Pr
{OFF s t a t e : Qf <_ q}
(9)
Fl(q) = P,.
{ON state : Q ! _< q}
(10)
The fictitious queue length distribution is given by
Pf(q) = P,.{Q! <_ q}
(11)
Pf(q) = Fo(q) + Fx(q)
(12)
Obviously, Making use of the fluid-flow method, Fo(q) and Fl(q) are given by [9]
Fo(q) = c0i I - 7)e e~ + cl (p - 7)e ~'q
(13)
Fl(q) = co7 eeOq -~ c17 e t l q
(14)
where 7 = Fa/F,, p = F,~/R, ~0 = 0, el = - p ( 1 - p)/[BL(1 - 7)(P - 7)], co = [1 - (p 7)e'Ir
-- 7)] - 1 ,
= --co.
Note that for R > Fo, the leaky bucket fictitious queue remains empty at all times, and hence no cell are rejected, marked or buffered. Therefore, we are only interested in the case when R < F~ and hence p > 7. The probabilities of the output rate at F~, R, and 0 are FI(B), 1 - P f ( B ) , and Fo(B), respectively. The average output rate is
f'~ = FoFI(B) + R[1 - Pf(B)]
(15)
Obviously, the peak output rate F~ still is the peak rate F, of bursty source. However, this duration is the average sojourn time of the output at the peak rate F,, given by[ 12]
Tpe~,k = B L . (1 - 7)" FI(B)/[Fo "7" F0(S)]
(16)
The output cell stream from the leaky bucket fed by the bursty source is a very complicated stochastic process which cannot described by a exact mathematical model. Based on the analysis of output cell stream characteristic, we propose that the stochastic process can be approximately described as the IBP. The accuracy of the analytical results has been largely validated by the simulation approach. The IBP is a slotted random point process. One slot s equals to a cell transmission time. Let s = cell / F, where the cell is 53 byte and F is the output link rate. At most one cell can occur in a slot, let F > F,. The output IBP can be described by the average traffic f~ (-----F~/F), the peak traffic f~(-- F , / F ) , the average bursty length B L ' ( =
Tpeak /s). IV.
Numerical
Results
If the average traffic, the peak traffic and the average bursty length of the IBP have been obtained, the IBP can be completely described by the three parameters. The probability distribution of the IBP can be calculated by the iterative method in Section II. Therefore we propose the analysis method to calculate the output process distribution from the leaky bucket fed by the bursty source. But the analysis way is approximately, the accuracy of the analytical results has been largely validated by means of the simulation approach. In
232
JOURNAL OF ELECTRONICS
Vol.14
this paper, the computer simulation programs and the numerical analysis programs are completed with Fortran 5.0. The independent and uniform characteristic of random number are tested in the simulation program. It can take l0 T slots in the computer simulation. The results of the analysis and the simulation show that the output process from the leaky bucket fed by the bursty sources can be well approximately described by the IBP. Tab,1 and Tab.2 illustrated the results of the analysis and simulation for comparison when M = 30 cell, B=60 cell, and M = 60 cell, B = 30 cell, respectively. The bursty source can be described by the average rate 15 Mbit/s, the peak rate 25 Mbit/s, and the average bursty length 30 cell. Where one cell is equal to 424 bit, F is equal to 150 Mbit/s. Tab.1 Comparison between analysis, nodiflcation and distribution o f probabilty M = 3 0 ,
B=60
Slot
Analysis
Simulation
Modification
1
1 . 6 2 0 3 1 4 x 10 - 1
1 . 6 4 8 6 6 3 x 10 - 1
1 . 6 2 8 0 1 6 x 10 - 1
2
1 . 3 1 4 6 4 3 x 10 - 1
1.365492 x 10- 1
1 . 3 2 3 4 5 2 x 10- 1
3
1 . 0 6 8 4 8 7 x 10 - 1
1.133206 x 10 - I
1 . 0 7 8 6 1 9 x 10 - I
4
8 . 7 0 1 9 0 6 x 10 - 2
9.440309 x 10- 2
8 . 8 0 4 5 5 2 x 10 - 2
5
7 . 1 0 3 8 2 5 x 10 - 2
7.778744 x 10- 2
7 . 2 0 0 1 9 6 x 10 - 2
6
5 . 8 1 5 2 9 4 x 10 - 2
6.551542 x 10- 2
5 . 9 0 0 8 5 0 x 10 - 2
7
4 . 7 7 5 7 4 3 x 10 - 2
5 . 4 2 5 4 2 8 x 10 - 2
4 . 8 4 8 1 0 5 x 10 - 2
8
3 . 9 3 6 4 7 8 x 10 - 2
4 . 4 5 8 3 1 9 x 10 - 2
3 . 9 9 4 7 4 9 x 10 - 2
9
3 . 2 5 8 3 4 8 • 10 - 2
3 . 7 2 4 8 9 8 x 10 - 2
3 . 3 0 2 6 2 3 x 10 - 2
10
2 . 7 0 9 8 7 6 x 10 - 2
3 . 0 9 7 4 5 4 x 10 - 2
2 . 7 4 0 8 8 2 x 10 - 2
11
2 . 2 6 5 7 5 4 x 10 - 2
2 . 5 5 6 2 5 4 x 10 - 2
2 . 2 8 4 5 9 5 x 10 - 2
12
1 . 9 0 5 6 3 1 x 10 - 2
2 . 1 2 9 7 4 4 x 10 - 2
1 . 9 1 3 6 1 1 x 10 - 2
13
1 . 6 1 3 1 4 6 x 10 - 2
1 . 7 8 3 2 6 7 x 10 - 2
1.611641 x 10 - 2
14
1 . 3 7 5 1 3 8 x 10 - 2
1 . 4 8 0 9 6 4 x 10 - 2
1 . 3 6 5 5 1 5 x 10 - 2
15
1 . 1 8 1 0 2 8 x 10 - 2
1 . 2 1 9 3 2 9 x 10 - 2
1.164591 x 10 - 2
16
1 . 0 2 2 3 0 5 x 10 - 2
1 . 0 0 2 9 6 9 x 10 - 2
1 . 0 0 0 2 6 3 x 10 - 2
17
8 . 9 2 1 2 4 4 x 10 - 3
8 . 5 1 9 1 7 5 x 10 - 3
8 . 6 5 5 7 3 2 x 10 - 3
18
7.649806 x 10- 3
7 . 2 5 4 0 7 1 x 10 - 3
7 . 5 4 8 9 8 2 x 10 - 3
19
6.964443 X 10 - 3
5 . 7 9 5 6 4 4 • 10 - 3
6 . 6 3 6 8 9 7 • 10 - 3
20
6.229517 x 10-3
4 . 8 7 8 1 1 7 x 10 - 3
5 . 8 8 2 7 0 4 x 10 - 3
Tab.1 and Tab.2 show that the analysis method has a satisfactory accuracy. The main reason of the difference are: Firstly, the fluid-flow method is a approximately analysis way; Secondly, the output process is not exact IBP. To improve its accuracy, the parameters of the output IBP can be appropriately modified so that the resulting IBP has the smallest error e(n). Let P~i't be the analysis probability that the interdeparture time is equal to i slot (s). Let/~/imu be the simulation probability that the interdeparture time is equal to i slot (s). Then, we have
i=l
where n is the number of distribution points to be compared.
No.3
ANALYSIS OF T H E LEAKY B U C K E T O U T P U T PROCESSES
Tab.2 C o m p a r i s o n b e t w e e n analysis, modification and d i s t r i b u t i o n o f probabilty M : 8 0 ,
233
B-----30
Slot
Analysis
Simulation
Modification
1
1.619041 • 10 - 1
1 . 5 9 4 7 6 0 • 10 - 1
1.625000 x 10 -1 1.321875 x 10-1
2
1.312688 x I0 -I
1 . 3 3 8 0 4 4 x 10 - 1
3
1 . 0 6 6 2 5 4 x 10 - 1
1 . 1 1 7 6 1 6 x 10 - 1
1.076797 x 10 -1
4
8 . 6 7 9 4 5 8 x 10 - 2
9 . 2 9 5 0 7 0 x 10 - 2
8.785997 • 10- 2
5
7.082945 x 10 - 2
7 . 7 5 9 6 7 0 x 10 - 2
7.182669 x 10- 2
6
5.796962 x 10- 2
6 . 4 8 9 9 8 4 x 10 - 2
5.885177 x 10 - 2
7
4.760454 • 10- 2
5 . 4 2 2 9 3 2 x 10 - 2
4.834730 x 10 - 2
8
3.924396 x 10- 2
4 . 5 3 8 9 2 0 x 10 - 2
3.983851 x 10 - 2
9
3.249417 x 10- 2
3 . 7 8 8 9 6 5 x 10 - 2
3.294203 x 10 - 2
10
2.703905 x 10- 2
3 . 1 7 9 9 6 3 x 10 - 2
2 . 7 3 4 8 2 7 x 10 - 2
11
2.262471 x 10- 2
2 . 6 5 5 1 3 4 x 10 - 2
2 . 2 8 0 7 2 2 x 10 - 2
12
1.904726 x 10- 2
2 . 2 2 8 0 7 4 x 10 - 2
1 . 9 1 1 6 9 8 • 10 = 2
13
1.614296 x 10- 2
1 . 8 2 3 9 0 5 x 10 - 2
1 . 6 1 1 4 4 9 • 10 - 2
14
1.378028 • 10- 2
1 . 5 4 7 1 9 6 x 10 - 2
1 . 3 6 6 8 0 9 • 10 - 2
15
1.185360 • 10- 2
1 . 2 9 8 7 7 7 x 10 - 2
1 . 1 6 7 1 4 1 • 10 - 2
16
1.027805 x 10 - 2
1 . 0 9 3 6 4 3 x 10 - 2
1 . 0 0 3 8 5 6 • 10 - 2
17
8.985465 x 10 - 3
9 . 1 3 7 0 2 1 x 10 - 3
8 . 7 0 0 1 5 9 • 10 - 3
18
7.921072 x 10 - 3
7.554537 x 10 - 3
7 . 6 0 0 1 5 6 • 10 - 3
19
7.040856 • 10- 3
6.296947 x 10 - 3
6 . 6 9 3 2 7 8 x 10 - 3
20
6.309447 X 10 - 3
5.456221 x 10 - 3
5 . 9 4 2 9 4 8 • 10 - 3
We modify the B~ of the output IBP so that it has the smallest error 6(n). The algorithm is summarized as follows: Step 1 Step 2 Step 3
Set B L ' = Tpeak/S , ~ ---- 1.0 x 10 -6, 60 = 1.0 X 102, r = 2Tpeak/S. Set B L -- B L + r If B L ' > r stop. Calculate 61 -- 6(n).
Step 4 If 6~ > 61 , set 60 > 61, B L " = B L ~. Go to Step 2. Tab. 1 and Tab.2 also show the modified IBP probability distribution. In Tab. 1, B L ~ - - 6 . 8 3 3 4 3 (6(30) -- 8.656588 x 102), B L " = 7.66676(6(30) = 7.427257 • 102). In Tab.2, B L ' = 6.666671(6(30) = 8.413593 • 102), B L " = 7.427257 x 102(6(30) -- 7.36062 • 10~). The modified probability distribution curves of the o u t p u t IBP are shown in Fig.2. For simulation and analysis, the parameters M, B and R of the leaky bucket are 30 cell, 60 cell, and 20 Mbit/s, respectively. The parameters Fa and B L of the bursty sources are 15 Mbit/s and 30 cell, respectively. Curve 1, Curve 2 and Curve 3 repres~ent 48 Mbit/s, 35 Mbit/s and 25 Mbit/s of the bursty source peak rate, respectively. The analytical curves are compared with the results arising from simulation runs, represented by their 95% confidence intervals. The burstiness of the output process vary with R, which is shown in Fig.3, to quantitatively analyze the smoothing function of the leaky bucket algorithm. In Fig.3, the average rate, the peak rate and the average bursty length of the bursty source are 15 Mbit/s, 50 Mbit/s and 30 cell, respectively. The burstiness of the bursty source is 29.83. Curve 1 represent M = 60 cell and B - - 3 0 cell. Curve 2 represent M = 30 cell and B = 30 cell. Curve
234
JOURNAL OF ELECTRONICS
,~
~
0.25
.
2
o.2 -9 ~':t o
Vol.14
.j
3
f-,, 0.15-'.~
~ ! 0 2
6
tO 14 18 22 26 30
Slot Fig.2 Probability distribution comparison
3.4-
"~
2.8-
~
_
~
.~J~'/:\
2.6-
\
2.4~~"~\\\,.
16
20
2.4
7,8 32 R (Mbids)
36
40
Fig.3 The relation of the burstiness and the leaky bucket parameters 3 represent M=30 and B=60. Therefore when the parameters of the leaky bucket are designed, we are expect to increase M, decrease B and decrease R for the smoothing of the bursty sources. But the performance of the leaky bucket (e.g. delay, delay variance and cell loss rate) get worse. The results show that, when the parameters of the leaky bucket are designed, the smoothing function, delay, delay variance, loss rate of leaky bucket and the performance of the node successive to the leaky bucket are all considered. V . Conclusions This paper propose that the output process from the leaky bucket fed by the bursty source can be approximately described as the IBP. We have developed a solution methodology which can be utilized in calculating the probability distribution of the output process. In this paper, the analysis result, the simulation results and the conclusions have a significant meaning for the reasonable selecting of the leaky bucket parameters and the analysis of leaky bucket algorithm affecting on the performance of the ATM networks.
No.3
ANALYSIS OF THE LEAKY BUCKET O U T PU T PROCESSES
235
References [1] Draft Recommendation 1.371, CCITT Period 1989-1992, July 1992. [2] Gu Xuedao, Current studies and future prospects on asynchronous transfer mode (ATM). Journal of China Institute of Communications, 15(1994)3, 1-15, (in Chinese).
[3] G. H. Michael et al., On the queueing behavior of multiplexed leaky bucket regulated sources. Proc. IEEE INFOCOM'93, San l~rancisco, USA: 1993, 672-679. [4] J. F. Ren et al., Asymptotic analysis of a leaky bucket controlled ATM multiplexer. Proc. IEEE ICC'93, Geneva Switzerland: 1993, 1386-1390. [51 I. E. Anwar, M. Debasis, Fluid models for the analysis and design of multiple classes of bursty traffic. Porc. IEEE INFOCOM'92, Florence, Italy: 1992, 415-425. [6] Sun Hairong, Li Lemin, Performance analysis of leaky bucket algorithm with bursty traffic input in ATM networks. J o u r n a / o f Electronics. Jan. 17(1995)1, 48-54, (in Chinese). [7] M. Sidi et al., Congestion control through input rate regulation. IEEE Trans. on COM, C O M 41(1993)3, 471--477. [8] N. Yin, G. H. Michael, Analysis of the leaky bucket algorithm for ON-OFF data sources. Proc IEEE GLOBECOM'91, Phenix, USA: 1991, 254-260. [9] Jiang Zhigang, Li Lemin, Leaky bucket flow control in ATM networks. J o u r n a / o f China Institute of Communications, 15(1994)3, 102-108, (in Chinese).
[10] Den Yonglu, Liang Zhiyu, Stochastic Point Processes with Application. Science Press, 1992, (in Chinese). [11] G. Stefano, P. Achille, Performance analysis of traffic patterns. Proc. IEEE INFOCOM'93, San Francison, USA: 1993, 943-952. [12] J. Keiison, Sojourn times, exit times, and jitter in multiwariable Markov process. Adv. Appl. Prob.,
13(1974)6, 747-756.