Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
278 8 Modeling Traffic Flow Control Protocols
where x = a
0
+a
1
and
z
i
= 1 −
i
j =0
a
j
(8.27)
8.2.5 Leaky Bucket Performance (M
m
/M /1/B Case)
Having obtained the transition matrix, we are able to calculate the performance of
the leaky bucket protocol.
The throughput of the leaky bucket algorithm when the M
m
/M/1/B model is
used is given from Section 7.7 on page 241 with a departure probability c = 1
Th = 1 −a
0
s
0
(8.28)
The throughput is measured in units of packets/time step and the throughput in
units of packets/second is
Th
= Th ×λ
b
packets/s (8.29)
The lost or tagged packets are given by
N
a
(lost) = N
a
(in) − N
a
(out)
= Na −
(
1 −a
0
s
0
)
(8.30)
The lost traffic is measured in units of packets/time step. The average lost traffic
per second is given by
N
a
(lost) =
N
a
(lost)
T
=
[
Na −
(
1 −a
0
s
0
)
]
λ
b
(8.31)
The packet loss probability l is the ratio of lost traffic relative to the input traffic
L =
N
a
(lost)
N
a
(in)
= 1 −
1 −a
0
s
0
Na
(8.32)
The average queue size is given by
Q
a
=
B
i=0
is
i
(8.33)
where s
i
is the probability that the data buffer has i packets.
8.2 The Leaky Bucket Algorithm 279
Using Little’s result, the average wait time in the buffer is
W =
Q
a
Th
(8.34)
The wait time is measured in units of time steps. The wait time in units of seconds
is given by
W
=
Q
a
Th
(8.35)
Example 8.2 Repeat Example 8.1 using the M
m
/M/1/B modeling approach.
The average input data rate is
λ
a
= 1 ×0.3 +4 ×0.7 = 3.1 Mbps
N is found as
N =
$
σ
λ
b
%
= 3
The packet arrival probability is
a = λ
a
× T = 0.6889
The probability that k packets arrive in one time step is
a
k
=
3
k
a
k
b
3−k
K = 0, 1, 2, 3
The transition matrix will be
P =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0.2301 0.0301 0000
0.4429 0.2000 0.0301 0 0 0
0.3269 0.4429 0.2000 0.0301 0 0
00.3269 0.4429 0.2000 0.0301 0
000.3269 0.4429 0.2000 0.0301
0000.3269 0.7699 0.9699
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
The equilibrium distribution vector is
s =
000.0001 0.0014 0.0370 0.9615
t
We see that 96% of the time the packet buffer is full. The other performance
parameters are:
280 8 Modeling Traffic Flow Control Protocols
Th = 1 packets/time step
Th
=3.7500 ×10
3
packets/s
N
a
(lost) = 1.0667 packets/time step
L = 0.5161
Q
a
= 4.9600 packets
W =4.96 timesteps
W
=1.3 ms
Comparing these performance figures with those obtained for the same system
using the M/M/1/B queue, we see that the packet throughput and delay in the
system are approximately similar. One possible reason for the small variation is the
use of the ceiling function in the M
m
/M/1/B analysis.
8.3 The Token Bucket Algorithm
Token bucket is a credit-based algorithm for controlling the volume of traffic arriv-
ing from a source. Tokens are issued at a constant rate and arriving packets can leave
the system only if there are tokens available in the token buffer. Figure 8.5 shows the
token bucket algorithm as it applies to a packet buffer. Figure 8.5(a) shows the input
data buffer and token buffer. Input data arrive with a variable rate while the tokens
arrive with a constant rate. There is mutual coupling or feedback between the two
Input traffic arrive
at a variable rate
Packet buffer
Output traffic with
variable rate
4
4
5
5
time
12
2
3
3
6 7
1
(a)
(b)
Input traffic with
variable rate
Arriving token
at a constant rate
6
8
Token arrive
at a constant rate
Token buffer
Tokens and output
traffic depart with
same variable rate
Mutual coupling
Fig. 8.5 The token bucket algorithm smoothes input variable rate traffic by buffering it and regu-
lating the maximum buffer output traffic rate: (a) Packet buffer; (b) Packet arrival and departure
8.3 The Token Bucket Algorithm 281
buffers such that both the tokens and the packets depart at the same rate which varies
depending on the states of both queues.
Figure 8.5(b) shows the events of packet arrival and departure as well as token
arrival (indicated by the grey circles). Depending on the data arrival rate and the
state of occupancy of the token buffer, the following scenarios could take place.
1. No data arrive and tokens are stored in the buffer and count as credit for the
source. This is similar to the situation before the arrival of packet 1 in Fig. 8.5(b).
2. Data arrive at a rate lower than the token issue rate. In that cases, data will be
accepted and the excess tokens will be stored in the token buffer as credit since
the source is conforming. This is similar to the arrival of packets 1, 2 and 3 in
Fig. 8.5(b). More token arrive than data and token buffer starts filling up.
3. Data arrive at a rate higher than the token issue rate. In that cases, data will be
accepted as long as there are tokens in the buffer. This is similar to the arrival of
packets 4 and 5 in Fig. 8.5(b). Packets 4 and 5 go through although no tokens
have arrived because the token buffer was not empty. When the token buffer
becomes empty, data will be treated as in the following step.
4. Data arrive but no tokens are present. Only a portion of the data will be ac-
cepted at a rate equal to the token issue rate. The excess data can be discarded
or tagged as nonconforming. This is similar to the arrival of packets 6, 7, and 8
in Fig. 8.5(b). Packets 6 and 7 arrive when the token buffer is empty and do not
go through. The packets get stored in the packet buffer and when a token arrives
packet 6 goes through.
Figure 8.6 shows the variation of output data rate in relation to the input data
rate. Grey areas indicate input data rate and solid black lines indicate output data
rate. The dashed line in the middle of the figure indicates the token arrival rate. We
see that output data rate can temporarily exceed the token rate but only for a short
time. The duration of this burst depends on the amount of tokens stored in the token
buffer. Bigger token buffer size allows for longer bursts from the source. However,
a bursty source will not allow the token buffer enough time to fill up.
On the other hand, the packet buffer allows for temporary storage of arriving
packets when there are no tokens in the token buffer.
Time
0
Token arrival rate
Data rate
Fig. 8.6 Control of data rate by the token bucket algorithm. Data rate at the input is indicated by
the grey areas, data rate at the output is indicated by the black lines and the dashed line is the token
issue rate
282 8 Modeling Traffic Flow Control Protocols
8.3.1 Modeling the Token Bucket Algorithm
In this section, we perform Markov chain analysis of the token bucket algorithm.
The states of the Markov chain represent the number of tokens stored in the token
buffer or bucket and the number of packets stored in the packet buffer.
We cannot model the token buffer separately from the packet buffer since the
departure from one buffer depends on the state of occupancy of the other buffer. In
a sense, we have two mutually coupled queues as was shown in Fig. 8.5(a).
The token bucket algorithm can be modeled using two different types of queues
depending on our choice of the time step. These two approaches are explained in
the following two sections.
8.3.2 Single Arrival/Single Departures Model (M /M /1 /B)
In this approach to modeling the token bucket algorithm, we take the time step equal
to the inverse of the maximum data rate on the line
T =
1
λ
l
(8.36)
where T is measured in units of seconds and λ
l
is the maximum input line rate in
units of packets/second. Usually, λ
l
is specified in units of bits per second. In that
case, T is obtained as
T =
A
λ
l
(8.37)
where A is the average packet length.
Figure 8.7 shows the events of packet arrival and departure and also the time step
value as indicated by the spacing between the grey tick marks.
Output traffic with
variable rate
4
4
5
5
time
12
2
3
3
6
7
1
Input traffic with
variable rate
Arriving token
at fixed rate
6
8
time step
Fig. 8.7 The token bucket algorithm where the time step is chosen equal to the inverse of the
maximum line rate
8.3 The Token Bucket Algorithm 283
Packets arrive at the input of the buffer at a rate λ
a
which varies with time because
of the burstiness of the source. To model the source burstiness in a simple manner,
we assume the data source has the following parameters:
λ
a
Source average data rate.
σ Source burst rate.
λ
a
and σ typically satisfy the relations
λ
a
<λ
t
(8.38)
σ>λ
t
(8.39)
where λ
t
is the token arrival rate.
The overall average data rate of the source as seen by the token bucket algorithm
is given by λ
a
. At a given time step a maximum of one token could arrive at or leave
the token buffer. Thus the packet buffer is described by an M/M/1/B queue. The
token arrival probability (a)isgivenby
a =
λ
t
λ
l
(8.40)
We also define b = 1 −a as the probability that a token does not arrive.
At a given time step, a maximum of one packet could arrive or leave the packet
buffer. Since a token leaves the token buffer each time a packet arrives, the token
departure probability c is given by
c =
λ
a
λ
l
(8.41)
We also define d = 1 −c as the probability that a token does not leave the token
buffer.
The state of occupancy of the token buffer depends on the statistics of token and
packet arrivals as follows
1. The token buffer will stay at the same state with probability ac+bd, i.e., when a
token arrives and a packet arrives or when no token arrives and no packet arrives
too.
2. The token buffer will increase in size by one with probability ad; i.e., if a token
arrives but no packets arrive.
3. The token buffer will decrease in size by one with probability bc; i.e., if no token
arrives but one packet arrives.
The state of occupancy of the packet buffer depends on the statistics of the token
and packet arrivals as follows
284 8 Modeling Traffic Flow Control Protocols
1. The packet buffer will stay at the same state with probability ac+bd, i.e., when a
token arrives and a packet arrives or when no token arrives and no packet arrives
too.
2. The packet buffer will increase in size by one with probability bc; i.e., if no token
arrives but one packet arrives.
3. The packet buffer will decrease in size by one with probability ad; i.e., if a token
arrives but no packets arrive.
Based on the above discussion, we have two single-input, single-output buffers.
The size of the token buffer is assumed B
t
and the size of the packet buffer is as-
sumed B
p
.
Figure 8.8 shows the Markov chain transition diagram for the system comprising
the token and packet buffers. The upper row represents the states of the token buffer
and the lower row represents the states of the packet buffer. The transition proba-
bilities are dictated by the token and packet arrival probabilities and the states of
occupancy of the token and packet buffers. The figure shows a token buffer whose
size is B
t
= 4 and a packet buffer whose size is B
p
= 3.
The numbering of the states is completely arbitrary and does not necessarily
represent the number of tokens or packets in a buffer. The meaning of each state is
shown in Table 8.1.
ad
ad ad
ac+bd
bc
bc bc
ac+bdac+bd
s
7
s
8
s
5
s
4
s
3
s
2
s
6
s
1
ac+bd
ac+bd
1-ad
1-bc
ac+bd
bc
bc
ad
ad
bc
ad
ad
bc
Token buffer states
Packet buffer states
Fig. 8.8 Markov chain transition diagram for the system comprising the token and packet buffers.
Token buffer size is B
t
= 4 and packet buffer size is B
p
= 3
Table 8.1 Defining the
binomial coefficient
Token buffer Packet buffer
State occupancy occupancy
s
1
00
s
2
10
s
3
20
s
4
30
s
5
40
s
6
01
s
7
02
s
8
03
8.3 The Token Bucket Algorithm 285
The transition matrix of the composite system is a
B
t
+ B
p
+1
×
B
t
+ B
p
+1
tridiagonal matrix. For the case when B
t
= 4 and B
p
= 3, the matrix is given by
P =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
fbc00 0 ad 00
ad f bc 00000
0 ad f bc 0000
00ad f bc 00 0
000ad 1 −bc 00 0
bc 000 0 fad 0
0000 0 bc f ad
0000 0 0bc 1 −ad
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
(8.42)
where b = 1 −a, d = 1 −c, and f = ac +bd = 1 −ad −bc.
8.3.3 Token Bucket Performance (M /M /1 /B Case)
Having obtained the transition matrix, we are able to calculate the performance of
the token bucket protocol.
The throughput of the token bucket algorithm is the average number of packets
per time step that are produced without being tagged or lost. To find the throughput
we must study all the states of the combined system. It is much easier to obtain the
throughput using the traffic conservation principle after we find the lost traffic.
Packets are lost or tagged for future discard if they arrive when the packet buffer
is full and no token arrives at that time step. The average number of lost or tagged
packets per time step is
N
a
(lost) = bc s
B
t
+ B
p
+1
(8.43)
The lost traffic is measured in units of packets/time step. And the number of
packets lost in units of packets/second is
N
a
(lost) =
N
a
(lost)
T
= N
a
(lost) λ
l
(8.44)
The average number of packets arriving per time step is given by
N
a
(in) = c (8.45)
The packet loss probability is
L =
N
a
(lost)
N
a
(in)
=
bc s
B
t
+ B
p
+1
c
= bs
B
t
+ B
p
+1
(8.46)
286 8 Modeling Traffic Flow Control Protocols
The throughput of the token bucket algorithm is obtained using the traffic con-
servation principle
Th = N
a
(in) − N
a
(lost)
= c −bc s
B
t
+ B
p
+1
= c
1 −bs
B
t
+ B
p
+1
(8.47)
The throughput is measured in units of packets/time step. The throughput in units
of packets/second is expressed as
Th
=
Th
T
= Th ×
λ
l
A
(8.48)
whereweassumedλ
l
was given in units of bits/second.
The packet acceptance probability p
a
or η of the token bucket algorithm is
p
a
=
Th
N
a
(in)
= 1 − L
= 1 −bs
B
t
+ B
p
+1
(8.49)
We remind the reader that packet acceptance probability is just another name
for the efficiency of the token bucket algorithm. It merely indicates the percent-
age of packets that make it through that traffic regulator without getting lost or
tagged.
The average queue size for the tokens is given by
Q
t
=
B
t
i=1
is
i+1
(8.50)
Notice the range of values of the state index in the above equation.
Similarly, the average queue size for the packets is given by
Q
p
=
B
p
i=1
is
i+B
t
+1
(8.51)
Notice the range of values of the state index in the above equation.
Using Little’s result, the average wait time or delay for the packets in the packet
buffer is
W =
Q
p
Th
(8.52)
8.3 The Token Bucket Algorithm 287
The wait time is measured in units of time steps. The wait time in seconds is
given by
W
=
Q
p
Th
(8.53)
Example 8.3 Find the performance of a token bucket traffic shaper that has the fol-
lowing parameters, where A is the average packet length.
λ
a
= 10 Mbps σ = 50 Mbps
λ
t
= 15 Mbps λ
l
= 100 Mbps
A = 400 bits B
t
= 2 packets
B
p
= 3 packets
The token arrival probability is
a =
λ
t
λ
l
= 0.15
The average data rate at the input is
λ
a
= p λ
a
+(1 − p) σ = 26 Mbps
The token departure probability is
c =
λ
a
λ
l
= 0.26
The transition matrix will be
P =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0.6680 0.2210 0 0.1110 0 0
0.1110 0.6680 0.2210 0 0 0
00.1110 0.7790 0 0 0
0.2210 0 0 0.6680 0.1110 0
0000.2210 0.6680 0.1110
00000.2210 0.8890
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
The equilibrium distribution vector is
s =
0.0641 0.0322 0.0162 0.1276 0.2541 0.5059
t
We see that 50.59% of the time the packet buffer is full indicating that the source
is misbehaving. The other performance parameters are
N
a
(lost) = 0.1118 packets/time step
N
a
(lost) = 2.7949 ×10
4
packets/s