Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
258 7 Queuing Analysis
Table 7.2 Relation of the
queue states and the
M/D/1/B queue occupancy
States Queue occupancy
s
0,0
–s
3,0
Queue empty
s
0,1
–s
3,1
One customer in queue
s
0,2
–s
3,2
Two customers in queue
.
.
.
.
.
.
s
0, j
–s
3, j
j customers in queue
.
.
.
.
.
.
is full. The state of occupancy of the queue is indicated in Table 7.2. In that case,
we know that a packet leaves when the queue is in one of the bottom states s
3,1
, s
3,2
,
s
3,3
,ors
3,4
.
The state vector s can be grouped into B sub vectors
s =
s
0
s
1
···s
B
t
(7.141)
where the subvector s
j
corresponds to the jth column in Fig. 7.8 and is given by
s
j
=
s
0, j
s
1, j
···s
n−1, j
t
(7.142)
corresponds to the case when there are j customers in the queue.
The state transition matrix P corresponding to the state vector s will be of dimen-
sion n(B +1) ×n(B +1). We describe the transition matrix P as a composite matrix
of size (B + 1) ×(B + 1) as follows:
P =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
AC0··· 000
BDC··· 000
0BD··· 000
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
000··· DC0
000··· BDC
000··· 0BE
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
(7.143)
where all the matrices A, B, C, D, and E are of dimension n×n. For the case
n = 4,
we can write
A =
⎡
⎢
⎢
⎣
0001
b 000
0 b 00
00b 0
⎤
⎥
⎥
⎦
, B =
⎡
⎢
⎢
⎣
0000
a 000
0 a 00
00a 0
⎤
⎥
⎥
⎦
, C =
⎡
⎢
⎢
⎣
000b
0000
0000
0000
⎤
⎥
⎥
⎦
D =
⎡
⎢
⎢
⎣
000a
b 000
0 b 00
00b 0
⎤
⎥
⎥
⎦
, E =
⎡
⎢
⎢
⎣
000a
1000
0100
0010
⎤
⎥
⎥
⎦
7.10 The M/D/1/B Queue 259
Having found the state transition matrix, we are now able to find the steady-
state value for the distribution vector of the M/D/1/B queue. At steady state, the
distribution vector s is derived from the two equations
Ps= s (7.144)
1s= 1 (7.145)
where 1 is a row vector whose components are all 1s.
We can find the vector s by iterations as follows. We start by assuming a value
for element s
0,0
= 1. As a consequence, all the elements of the vector s
0
can be
found as follows:
s
1,0
= bs
0,0
= b (7.146)
s
2,0
= bs
1,0
= b
2
(7.147)
s
3,0
= bs
2,0
= b
3
(7.148)
.
.
.
Thus we know s
0
.Tofinds
1
, we use the equation
s
0
= As
0
+Cs
1
(7.149)
or
s
1
= C
−1
(I −A)s
0
(7.150)
Since we have an initial assumed value for s
0
, we now know s
1
. In general, we
can write the iterative expressions
s
i
= C
−1
(I −A)s
i−1
1 ≤ i ≤ B (7.151)
Having found all the vectors s
i
, we obtain the normalized distribution vector s
as
s
= s
!
n−1
i=0
B
j=0
s
i, j
(7.152)
7.10.1 Performance of the M/ D/1/B Queue
The average input traffic N
a
(in) is needed to estimate the efficiency of the queue and
queue delay. N
a
(in) is given by
N
a
(in) = Na (7.153)
260 7 Queuing Analysis
The throughput of the queue is given by
Th = a
B
j=0
s
n−1, j
(7.154)
The efficiency of the D/M/1/B queue is given by
η =
Th
N
a
(in)
=
1
N
×
B
j=0
s
n−1, j
(7.155)
Packets are lost in the M/D/1/B queue when the queue is full and a packet
arrives but does not leave. The average lost traffic is given by
N
a
(lost) = a
n−2
i=0
s
i,B
(7.156)
The packet loss probability L is given by
L =
N
a
(lost)
N
a
(in)
=
1
N
n−2
i=0
s
i,B
(7.157)
The average queue size is given by
Q
a
=
n−1
i=0
B
j=0
is
i, j
(7.158)
7.11 Systems of Communicating Markov Chains
In the previous sections, we investigated the behavior of single Markov chains or
single queues. More often than not, communication systems are composed of in-
terconnected or interdependent Markov chains or queues. As an example, let us
consider Figure 7.10. This system represents an entity that is connected to a bus or
a communication channel in general. This could be the Ethernet network interface
Transmit
Buffer (B)
Traffic
Source
Medium
Access
Module
Communication
Channel
Fig. 7.10 A system of several Markov chains or queues
7.11 Systems of Communicating Markov Chains 261
card (NIC) on a computer connected to a local-area network. The system to be
analyzed consists of
1. Traffic source
2. Packet or transmit buffer
3. Medium access module
Each one of these components can be modeled individually using Markov chain
analysis. For example, the traffic source can be modeled using the techniques in
Chapter 11. The transmit buffer is of course modeled using any of the queuing
models discussed in this chapter. The medium access module could be modeled
using the techniques discussed in Chapter 10.
Let us assume that the Markov models for the three components are characterized
by s
1
states for the traffic source, s
2
states for the queue, and s
3
states for the medium
access module. We could develop a unified Markov model for our system and this
would probably require s
1
×s
2
×s
3
states. This is the state explosion problem asso-
ciated with most Markov chain models. If we, on the other hand, treat the problem
as a system of dependent Markov chains, then we are in effect dealing with the
individual components and the total number of states is s
1
+s
2
+s
3
. Of course, we
cannot solve each system separately since the state of each component depends on
the other components communicating with it.
We can generalize the problem by considering a communicating Markov chain
system composed of n modules. Module i is characterized by four quantities:
1. State transition matrix P
i
2. Steady-state distribution vector s
i
3. Probabilities x
i
corresponding to the module inputs
4. Probabilities y
i
corresponding to the module outputs
The parameters of each transition matrix P
i
(0 ≤ i < n) depend, in general,
on the values of s
j
, x
j
, and y
j
of all the other modules or systems. Furthermore,
the module inputs and outputs x
i
and y
i
might also depend on the queue param-
eters such as s
j
. In this analysis, we assume that x
i
and y
i
are independent vari-
ables for simplicity. Figure 7.11 shows the system of n interdependent Markov
chains.
Fig. 7.11 Model of a network
of interdependent Markov
chains
P
0
, s
0
x
0
y
0
P
1
, s
1
x
1
y
1
P
n–1
, s
n–1
x
n–1
y
n–1
...
262 7 Queuing Analysis
If we attempt to model the system in Fig. 7.11 as a single Markov chain, the
number of states we have to deal with would be given by
Merged number of states =
n−1
⌸
i=0
K
i
where K
i
is the number of states of module i. If all the modules had the same
number of states (K ), then the total number of states would have been
Merged number of states = K
n
If we deal with the system as a system of communicating and dependent Markov
chains, then the total number of states we have to deal with would be given by
Number of states =
n−1
i=0
K
i
where K
i
is the number of states of module i. If all the modules had the same
number of states (K ), then the total number of states would have been
Number of states = nK
For typical systems, the quantity nK is much smaller than K
n
. As an example,
assume a modest system where each module has K = 10 states and we have n
modules where n = 5. The number of states using the two approaches yields
Number of states = K
n
= 10
5
= 100, 000
Number of states = nK = 50
The situation is even worse and had K = 100 where our states would have been
10 billion using the former approach compared to 500 using the latter.
This is one reason that researchers and engineers alike attempt to use Petri nets
to describe typical systems [6, 7]. However, Petri nets are basically graphical tools.
Our approach in this section could be very loosely considered as approaching Petri
nets through establishing the communicating channels and dependencies between
the different modules of the system.
For each module in the system, we can write the steady-state equation
P
i
(s
j
, x
j
, y
j
) ×s
i
= s
i
0 ≤ i, j < n (7.159)
where the notation P
i
(s
j
, x
j
, y
j
) indicates that P
i
is a function of s
j
, x
j
, and y
j
.
Example 7.12 Assume a system of two interdependent queues such that the first
queue is a simple M/M/1/B queue with parameters: arrival probability a, departure
probability c, and size B = 2. The second queue depends on the first queue as
indicated by the state transition matrix
7.11 Systems of Communicating Markov Chains 263
Y =
α 1 − x
0
1 −α x
0
where α<0 and x
0
is the probability that the first queue is empty. Explain how the
steady-state distribution vectors x and y of the two queues could be obtained.
We have for the first queue
X =
⎡
⎣
1 −ad bc 0
ad f bc
0 ad 1 −bc
⎤
⎦
x =
x
0
x
1
x
2
t
where f = ac +bd. Since the first queue is not dependent on the second queue, the
steady-state distribution vector is found using Equation (7.17)
x =
1 −ρ
1 −ρ
3
×
1 ρρ
2
t
where ρ = ad/bc.
For the second queue, we have
Y =
α 1 − x
0
1 −α x
0
y =
y
0
y
1
t
Matrix Y is determined since we know the value of x
0
. Thus, we can find the
value of y using any of the techniques that we studied in Chapter 4.
7.11.1 A General Solution for Communicating Markov Chains
In the general case, a simple solution for the system is not possible due to the com-
plexity of the transition matrices. The general steps we recommend to employ can
be summarized as follows:
Step 0: Initialization of s
i
Set initial nonzero values for all the distribution vectors s
i
(0) for all 0 ≤ i < n.Of
course, each vector must be normalized in the sense that the sum of its components
must always be 1. In general, at iteration k, the estimated value of s
i
(k)isknown.
The notation s
i
(k) indicates the value of s
i
at iteration k.
Step 1: Estimating P
i
The elements of the transition matrices P
i
(k) at iteration k can now be estimated
since s
i
(k), x
i
, and y
i
are known. Initially, k = 0 to start our iterations and we are
then able to calculate the initial P
i
(0).
Step 2: Calculating s
i
Knowing P
i
(k) we can now calculate the values s
i,c
(k), where the notation s
i,c
(k)
indicates the calculated value of s
i
(k) which will most probably be different from
the assumed s
i
(k). We calculate s
i,c
(k) using the equation
264 7 Queuing Analysis
s
i,c
(k) = P
i
(k) s
i
(k) (7.160)
Again, initially k = 0 at the start of iterations.
Step 3: Calculating the Estimation Error e
i
(k)
The calculated value s
i,c
(k) will not be equal to the values s
i
(k). The estimation error
vector is calculated as
e
i
(k) = s
i,c
(k) −s
i
(k) (7.161)
The magnitude of the estimation error for s
i
(k)isgivenby
i
(k) =
e
t
i
(k) e
i
(k) (7.162)
Step 4: Updating Value of s
i
(k)
We are now able to update our guess of the state vectors and obtain new and better
values s
i
(k + 1) according to the update equations
s
i
(k +1) = s
i
(k) +αe
i
(k)0≤ i < n (7.163)
where α 1 is a small correction factor to ensure smooth convergence.
Step 5: Improving the Estimated Values of s
i
(k)
We repeat steps 1–4 with the new values s
i
(k +1) until the total error measure
t
is
below an acceptable level
t
=
n
i=0
i
≤ γ (7.164)
where γ is the acceptable error threshold.
We are “confident” that convergence will take place since at each iteration the
matrices P
i
(k) are all column stochastic and their eigenvalues satisfy the inequality
λ ≤ 1.
Problems
Throughput and Efficiency
7.1 Consider a switch that generates its own traffic, N
a
(internal), in addition to the
traffic arriving at its input, N
a
(in), according to the discussion in Section 7.3.
Define the throughput and the efficiency for this system in terms of N
a
(in),
N
a
(internal), and N
a
(out), such that η never exceeds unity.
Problems 265
M/M/1 Queue
7.2 Prove that (7.13) on page 229 is true when the M/M/1 queue is stable.
7.3 Consider an M/M/1 with a distribution vector ρ very close to unity such that
ρ = 1 −
where 1. Find the equilibrium distribution vector.
7.4 Consider an M/M/1 queue with arrival probability a = 0.5 and departure
probability c = 0.6.
(a) Construct the first six rows and columns of the transition matrix P.
(b) Find the values of the first ten components of the equilibrium distribution
vector.
(c) Calculate the queue performance.
7.5 Repeat Problem 7.4 when the departure probability becomes almost equal to
the arrival probability (e.g., c = 0.55).
7.6 Consider an M/M/1 queue with arrival probability a = 0.1 and departure
probability c = 0.5.
(a) Construct the first six rows and columns of the transition matrix P.
(b) Find the values of the first ten components of the equilibrium distribution
vector.
(c) Calculate the queue performance.
7.7 Repeat Problem 7.6 when the departure probability becomes almost equal to
the arrival probability (e.g., c = 0.11).
7.8 In an M/M/1 queue, it was found out that the average queue size Q
a
= 5
packets and the average waiting time is W = 20 time steps. Calculate the
queue arrival and departure probabilities and find the first ten entries of the
distribution vector.
7.9 In an M/M/1 queue, it was found out that the average queue size Q
a
= 2
packets and the average waiting time is W = 100 time steps. Calculate the
queue arrival and departure probabilities and find the first ten entries of the
distribution vector.
7.10 Equation (7.7) describes the M/M/1 queue when a packet could be served in
the same time step at which it arrives. Suppose that an arriving packet cannot
be served until the next time step. What will be the expression for the state
matrix? Compare your result to (7.7).
7.11 Derive the performance for the M/M/1 queue described in Problem 7.10.
7.12 In the M/M/1 queue in Problem 7.10, it was found that the average queue
size is Q
a
= 2 packets and the average waiting time is W = 100 time steps.
Calculate the queue arrival and departure probabilities and find the first ten
entries of the distribution vector.
266 7 Queuing Analysis
M/M/1/B Queue
7.13 Prove the average queue size formula for the M/M/1/B queue given in (7.47)
on page 236.
7.14 Consider an M/M/1/B queue with arrival probability a = 0.5, departure
probability c = 0.6, and the maximum queue size is B = 4.
(a) Construct the transition matrix P.
(b) Find the values of the components of the equilibrium distribution vector.
(c) Calculate the queue performance.
(d) Compare your results with those of the M/M/1 queue in Problem 7.4
having the same arrival and departure probabilities.
7.15 Repeat Problem 7.14 when the departure probability becomes almost equal
to the arrival probability (e.g., c = 0.55). Compare your results with those
of the M/M/1 queue in Problem 7.5 having the same arrival and departure
probabilities.
7.16 Repeat Problem 7.14 when the departure probability actually exceeds the
arrival probability (e.g., c = 0.8). Compare your results with those of the
M/M/1 queue in Problem 7.5 having the same arrival and departure proba-
bilities.
7.17 Consider an M/M/1/B queue with arrival probability a = 0.1, departure
probability c = 0.5, and maximum queue size B = 5.
(a) Construct the transition matrix P.
(b) Find the values of the equilibrium distribution vector.
(c) Calculate the queue performance.
(d) Compare your results with those of the
M/M/1 queue in Problem 7.6
having the same arrival and departure probabilities.
7.18 Repeat Problem 7.17 when the departure probability becomes almost equal
to the arrival probability (i.e., c = 0.11). Compare your results with those
of the M/M/1 queue in Problem 7.7 having the same arrival and departure
probabilities.
7.19 Equation (7.30), on page 234, describes the M/M/1/B queue when a packet
could be served in the same time step at which it arrives. Suppose that an
arriving packet cannot be served until the next time step. What will be the
expression for the state matrix? Compare your result to (7.30).
7.20 Derive the performance for the M/M/1/B queue described in Problem 7.19.
7.21 Consider an M/M/1/B queue with arrival probability a = 0.4, departure
probability c = 0.39, and maximum queue size B = 5. The queue is not
stable since the arrival probability is larger than the departure probability.
(a) Construct the transition matrix P.
(b) Find the values of the equilibrium distribution vector.
(c) Calculate the queue performance.
Problems 267
7.22 In the M/M/1 queue in Problem 7.20 it was found out that the average queue
size Q
a
= 2 packets and the average waiting time is W = 100 time steps.
Calculate the queue arrival and departure probabilities and find the first ten
entries of the distribution vector.
M
m
/M/1/B Queue
7.23 Write down the entries for the transition matrix of an M
m
/M/1/B queue in
terms of the arrival and departure statistics a
k
and c, respectively. Consider the
case when B = 4.
7.24 Equation (7.63), on page 241, describes the M
m
/M/1/B queue when up to
m packets could arrive at one time step. Prove that for the special case when
m = 1, (7.63) becomes identical to (7.30).
7.25 Equation (7.63) describes the M
m
/M/1/B queue when a packet could be
served in the same time step at which it arrives. Suppose that an arriving packet
cannot be served until the next time step. What will be the expression for the
state matrix? Compare your result to (7.63).
7.26 Consider an M
m
/M/1/B queue with arrival probability a = 0.2, m = 2,
departure probability c = 0.39, and maximum queue size B = 5. The queue
is not stable since the average number of arrivals is larger than the average
number of departures.
(a) Construct the transition matrix P.
(b) Find the values of the equilibrium distribution vector.
(c) Calculate the queue performance.
7.27 In the analysis of the M
m
/M/1 queue, it was assumed that when a packet
arrives, it can be serviced at the same time step. Suppose the arriving packet
is serviced the next time step. Draw the state transition diagram and at write
down the corresponding transition matrix. Derive the main performance equa-
tions of such a queue.
M/M
m
/1/B Queue
7.28 Write down the entries for the transition matrix of an M/M
m
/1/B queue in
terms of the arrival and departure statistics a and c
k
, respectively. Consider the
case when B = 4.
7.29 Equation (7.94), on page 248, describes the M/M
m
/1/B queue when up to
m packets could leave at one time step. Prove that for the special case when
m = 1, (7.94) becomes identical to (7.30).
7.30 Equation (7.94) describes the M
m
/M/1/B queue when a packet could be
served in the same time step at which it arrives. Suppose that an arriving packet