Gebali F. Analysis Of Computer And Communication Networks
Подождите немного. Документ загружается.
6.16 Identification of Markov Chains 217
Inspection of the elements of the transition matrix does not help much except
for the simplest case when we are dealing with a strongly periodic Markov chain.
In that case, the transition matrix will be a 0–1 matrix. However, determining the
period of the chain is not easy since we have to rearrange the matrix to correspond
to the form (6.48) on page 198.
A faster and more direct way to classify a Markov chain is to simply study its
eigenvalues and eigenvector corresponding to λ = 1. The following subsections
summarize the different cases that can be encountered.
6.16.1 Nonperiodic Markov chain
This is the case when only one eigenvalue is 1 and all other eigenvalues lie inside
the unit circle:
|
λ
i
|
< 1 (6.75)
For large values of the time index n →∞, all modes will decay except the one
corresponding to λ
1
= 1, which gives us the steady-state distribution vector.
6.16.2 Strongly periodic Markov chain
This is the case when all the eigenvalues of the transition matrix lie on the unit
circle:
λ
i
= exp
j2π ×
i
γ
(6.76)
where 1 ≤ i ≤ γ .
For all values of the time index, the distribution vector will exhibit periodic be-
havior, and the period of the system is γ .
6.16.3 Weakly periodic Markov chain
This is the case when γ eigenvalues of the transition matrix lie on the unit circle,
and the rest of the eigenvalues lie inside the unit circle. Thus we can write
|
λ
i
|
= 1 when 1 ≤ i ≤ γ (6.77)
|
λ
i
|
< 1 when γ<i ≤ m (6.78)
The eigenvalues that lie on the unit circle will be given by
λ
i
= exp
j2π ×
i
γ
(6.79)
218 6 Periodic Markov Chains
where 1 ≤ i ≤ γ .
For large values of the time index n →∞, some of the modes will decay but γ
of them will not, and the distribution vector will never settle down to a stable value.
The period of the system is γ .
6.17 Problems
Strongly Periodic Markov Chains
6.1 The following matrix is a circulant matrix of order 3, we denote it by C
3
.Ifit
corresponds to a transition matrix, then the resulting Markov chain is strongly
periodic. Find the period of the Markov chain.
P =
⎡
⎣
001
100
010
⎤
⎦
6.2 Prove Theorem 6.5 using the result of Theorem 6.1 and the fact that all eigen-
values of a column stochastic matrix are in the range 0 ≤|λ|≤1.
6.3 Does the following transition matrix represent a strongly periodic Markov
chain?
P =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0001000
0100000
0000100
0000001
0010000
1000000
0000010
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
6.4 Verify that the following transition matrix corresponds to a periodic Markov
chain and find the period. Find also the values of all the eigenvalues.
P =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
0000001
0001000
0000100
0000010
0010000
1000000
0100000
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
6.5 Prove that the m×m circulant matrix in (6.47) has a period γ = m. You can do
that by observing the effect of premultiplying any m ×k matrix by this matrix.
6.17 Problems 219
From that, you will be able to find a pattern for the repeated multiplication of
the transition matrix by itself.
Weakly Periodic Markov Chains
6.6 Does the following transition matrix represent a periodic Markov chain?
P =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
1/30 0 0 01/31/3
1/31/300001/3
1/31/31/30000
01/31/31/30 0 0
001/31/31/30 0
0001/31/31/30
00001/31/31/3
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
6.7 The weather in a certain island in the middle of nowhere is either sunny or
rainy. A recent shipwreck survivor found that if the day is sunny, then the
next day will be sunny with 80% probability. If the day is rainy, then the next
day will be rainy with 70% probability. Find the asymptotic behavior of the
weather on this island.
6.8 A traffic source is modeled as a periodic Markov chain with three stages. Each
stage has three states: silent, transmitting at rate λ
1
, and transmitting at rate
λ
2
.
(a) Draw the periodic transition diagram.
(b) Write down the transition matrix.
(c) Assign transition probabilities to the system and find the asymptotic be-
havior of the source.
(d) Plot the state of the system versus time by choosing the state with the
highest probability at each time instant. Can you see any periodic behavior
in the traffic pattern?
6.9 A computer goes through the familiar fetch, decode, and execute stages for in-
struction execution. Assume that the fetch stage has three states depending on
the location of the operands in cache, RAM, or in main memory. The decode
stage has three states depending on the instruction type. The execute state also
has three states depending on the length of the instruction.
(a) Draw the periodic transition diagram.
(b) Write down the transition matrix.
(c) Assign transition probabilities to the system and find the asymptotic be-
havior of the program being run on the machine.
6.10 Table look up for packet routing can be divided into three phases: database
search, packet classification, and packet processing. Assume that the database
220 6 Periodic Markov Chains
search phase consists of four states depending on the location of the data
among the different storage modules. The packet classification phase consists
of three states depending on the type of packet received. The packet processing
phase consists of four different states depending on the nature of the process-
ing being performed.
(a) Draw the periodic transition diagram.
(b) Write down the transition matrix.
(c) Assign transition probabilities to the system and find the asymptotic be-
havior of the lookup table operation.
6.11 A bus company did a study on commuter habits during a typical week. Es-
sentially, the company wanted to know the percentage of commuters who use
the bus, their own car, or stay at home each day of the week. Based on this
study, the company can plan ahead and assign more buses or even bigger buses
during heavy usage days.
(a) Draw the periodic transition diagram.
(b) Write down the transition matrix.
(c) Assign transition probabilities to the system and find the asymptotic be-
havior of the commuter patterns.
6.12 Assume a certain species of wild parrot to have two colors: red and blue. It
was found that when a red–red pair breeds, their offspring are red with a 90%
probability due to some obscure reasons related to recessed genes and so on.
When a blue–blue pair breeds, their offspring are blue with a 70% probability.
When a red–blue pair breeds, their offspring are blue with a 50% probability.
(a) Draw the periodic transition diagram.
(b) Write down the transition matrix.
(c) Assign transition probabilities to the system and find the asymptotic be-
havior of the parrot colors in the wild.
6.13 A packet source is modeled using periodic Markov chain. The source is as-
sumed to go through four repeating phases and each phase has two states:
idle and active. Transitions from phase 1 to phase 2 are such that the source
switches to the other state with a probability 0.05. Transitions from phase 2 to
phase 3 are such that the source switches to the other state with a probability
0.1. Transitions from phase 3 to phase 4 are such that the source switches to
the other state with a probability 0.2. Transitions from phase 4 to phase 1 are
such that the source switches to the other state with a probability 0.90.
(a) Draw the periodic transition diagram.
(b) Write down the transition matrix.
(c) Assign transition probabilities to the system and find the asymptotic be-
havior of the source.
References 221
6.14 The predator and prey populations are related as was explained at the start
of this chapter. Assume that the states of the predator–prey population are as
follows.
State Predator polulation Prey population
s
0
Low Low
s
1
Low High
s
2
High Low
s
3
High High
The transitions between the states of the system take place once each year. The
transition probabilities are left for the reader to determine or assume.
1. Construct state transition diagram and a Markov transition matrix.
2. Justify the entries you choose for the matrix.
3. Study the periodicity of the system.
References
1. W.J. Stewart, Introduction to Numerical Solutions of Markov Chains, Princeton University
Press, Princeton, New Jersey, 1994.
2. R. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, England,
1985.
3. Private discussions with Dr. W.-S. Lu of the Department of Electrical & Computer Engineering,
University of Victoria, 2001.
Chapter 7
Queuing Analysis
7.1 Introduction
Queuing analysis is one of the most important tools for studying communication
systems. The analysis allows us to answer endless questions about the system per-
formance. This chapter explains that queuing analysis is a special case of Markov
chains. Some examples of queues are as follows:
• The number of patients in a doctor’s waiting room
• The number of customers in a store checkout line
• The number of packets stored in a router’s buffer
• The number of print jobs present in a printer’s queue
• The number of workstations requesting access to the LAN
Without being specific to a certain system, we can state that queuing analysis
deals with queues where customers compete to be processed by shared servers.The
queue size is the waiting room provided for the customers that have not been served
yet plus the customers that are being served. We will talk about packets instead of
customers in this chapter since most of networking analysis deals with transmitting
and processing packets.
The objective of queuing analysis is to predict the system performance such as
how many customers get processed per time step, the average delay a customer en-
dures before being served, and the size of the queue or waiting room required. These
performance measures have obvious applications in telecommunication systems and
the design of hardware for such systems.
We list here some typical examples of queues and point out the customers and
servers in each.
• People lining up at a bank where the bank teller is the server and the bank patrons
are of course the customers.
• Workstations connected in a local-area network (LAN) where the communication
medium (e.g., Ethernet cable) represents the shared resource while the commu-
nicating applications represent the customers and the server is the media access
control (MAC) protocol that enables access to the medium.
F. Gebali, Analysis of Computer and Communication Networks,
DOI: 10.1007/978-0-387-74437-7
7,
C
Springer Science+Business Media, LLC 2008
223
224 7 Queuing Analysis
• A parallel processing system in which a common shared memory is accessed
by all the computers. The computers, or rather the memory requests, represent
the customers and the arbitration protocol that resolves memory access conflicts
represents the server.
Most of the literature and textbooks deal with continuous-time systems. In these
systems, only single customer arrival or departure takes place at a given time instant.
However, analyzing the systems for general arrival or departure statistics proved to
be difficult such that most textbooks simply provide tables of performance formulas
for the most common situations. Subsequent researchers simply adopt these formu-
las without any form of adaptation or innovation.
Most of computer and communication systems, however, are migrating to the
digital domain. In this domain, time is measured in discrete units or steps of finite
size. As a consequence, there could be multiple arrivals or departures at a given
time step. We will find that discrete-time systems are simple to analyze compared
to continuous-time systems. Adapting discrete-time systems to a large variety of
situations is really simple using the techniques we provide in this book.
In this chapter, we study different types of discrete-time queues characterized by
the following attributes:
1. The total number of customers in the system.
2. The number of customers that could possibly request service at a given time step.
3. The arrival process statistics for the customers.
4. The number of servers which dictate how many customers can leave the queue
at a given time step.
5. The service discipline for deciding which customer or customers are to be served.
Examples of service disciplines are first-come-first-serve (FIFO), random selec-
tion, polling, and priority [1].
6. The size of the queue to accommodate customers waiting for service.
7.1.1 Kendall’s Notation
Kendall’s notation is frequently used to succinctly describe a queuing system. This
notation is represented as A/B/c/n/ p, where [2]
A Arrival statistics
B Service or departure statistics
c Number of servers
n Queue size
p Customer population size
The final two fields are optional and are assumed infinite if they are omitted [3].
The letters A and B denoting arrival and server statistics are given the following
notations:
7.2 Queue Throughput (Th) 225
D Deterministic, process has fixed arrival or service rates
M Markovian, process is Poisson or binomial
G General or constant time
A common practice is to attach a superscript to the letters A and B to denote
multiple arrivals or “batch service”. Using this notation, the discrete-time M/M/1
queue has binomial, or Poisson, arrivals and departures. At a given time step at most
one customer arrives and at most one customer departs. The queue has infinite buffer
size and the population size is also infinite.
The queue M/M/1/B has binomial, or Poisson, arrivals and departures. At a
given time step, at most one customer arrives and at most one customer departs. The
queue has a finite buffer of size B and the population size is infinite. This queue is
frequently encountered when the time step is so short that only one customer can
arrive or depart in that time.
The queue M/M/J/B has binomial, or Poisson, arrivals and departures. At a
given time step, at most one customer arrives and at most one customer could depart
through one of the J available servers. The queue has a finite buffer of size B and the
population size is infinite. This type of queue might be encountered when a server
might be busy serving a customer at a given time step and the remaining servers
become available to serve other customers in the queue.
The queue M
m
/M/1/B has binomial, or Poisson, arrivals and departures. There
is one server in the queue, and at a given time step, at most m customers arrive and
at most one customer departs because there is one server. The queue has a finite
buffer of size B and the population size is infinite.
The queue M/M
m
/1/B has binomial, or Poisson, arrivals and departures. There
is one server in the queue, and at a given time step, at most one customer arrives
and at most J customers depart because the server could handle J customers in one
time step. The queue has a finite buffer of size B and the population size is infinite.
The queues we shall deal with here will be one of the following types:
1. Single arrival, single departure infinite-sized queues in which the transition
matrix P is tridiagonal. Such a queue will be denoted by the symbols M/M/1.
2. Single arrival, single departure finite-sized queues in which P is tridiagonal. Such
a queue will be denoted by the symbols M/M/1/B.
3. Multiple arrival, single departure finite queues in which P is lower Hessenberg.
Such a queue will be denoted by the symbols M
m
/M/1/B.
4. Single arrival, multiple departure finite-sized queues in which P is upper
Hessenberg. Such a queue will be denoted by the symbols M/M
m
/1/B.
7.2 Queue Throughput (Th)
Most often we are interested in estimating the rate of customers leaving the queue;
which is expressed as customers per time step or customers per second. We call
this rate the average output traffic N
a
(out), or throughput (Th) of a queue. The
throughput is given by
226 7 Queuing Analysis
Th = output data rate = N
a
(out) (7.1)
The units of Th in the above expression are packets/time step. Notice that this
definition implies that Th could never be negative.
When we talk about throughput of packets, we usually mean goodput which
represents the packets that got through intact without collisions or other problems.
Sometimes authors talk about throughput to include good and corrupted packets.
The difference between throughput and goodput is seldom discussed and the reader
is advised to make certain which quantity is being dealt with in any discussion.
Throughout this book, we shall use the term throughput to imply good packets that
got sent without corruption.
7.3 Efficiency (η) or Access Probability (p
a
)
The efficiency (η) of the queue or its access probability (p
a
) essentially gives the
percentage of customers or packets transmitted in one time step through the system
relative to the total number of arriving customers or packets in one time step also.
We shall use the term efficiency when we talk about queues and switches and will
use the term access probability when we talk about interconnection networks. Effi-
ciency or access probability essentially measures the effectiveness of the queue at
processing data present at the input.
We define the access probability (p
a
)orefficiency η as the ratio of the average
output traffic relative to the average input traffic:
p
a
= η =
N
a
(out)
N
a
(in)
(7.2)
This can be expressed in terms of the throughput
p
a
= η =
N
a
(out)
N
a
(in)
=
Th
N
a
(in)
≤ 1 (7.3)
Notice that the access probability or efficiency could never be negative and could
never be more than one.
If customers or packets are created within the queue, then we have to modify our
definitions of both the input and output traffic to ensure that the efficiency never
exceeds unity. This situation could in fact happen. For example, consider a packet
switch that receives packets at its inputs and then routes these packets to the output
ports. We expect that the number of packets leaving the switch per unit time will
be smaller than or equal to the number of packets coming to the switch per unit
time. The output traffic could be smaller than the input traffic when packets are lost
within the switch when its internal buffers become full. However, the switch itself
might generate its own packets to communicate with other switches or routers in the
7.5 M/M/1 Queue 227
network. In that case, the traffic at the input could in fact be smaller than the output
traffic due to the internally generated traffic. Let us leave this point to the problems
at the end of the chapter.
Throughput and access probability are very useful in describing the behavior of
a system. The two concepts are not equivalent and in fact we will see that the curves
showing variation of efficiency with the queue parameters are not scaled version
of throughput variation with queue parameters. This point is clearly illustrated in
Fig. 14.4 on page 515, or Fig. 14.20 on page 538.
If the queue produces three customers on the average per time step while five
customers could arrive, then the throughput is Th = 3 while its efficiency is
η = 3/5 = 60%. On the other hand, if the queue produces four customers on the
average per time step while a maximum of six customers could potentially leave,
then the throughput is Th = 4 and its efficiency is η = 4/6 = 66.67%.
7.4 Traffic Conservation
When the queue reaches steady state, the incoming customers or packets have two
options when they arrive at a queue: either they get processed and move through the
queue or they get lost. We can therefore write the traffic conservation as
N
a
(in) = N
a
(out) + N
a
(lost) (7.4)
where N
a
(lost) is the average number of lost traffic or customers per unit time. The
above equation is valid at steady state since the number of packets in the queue will
be constant.
Dividing the above equation by N
a
(in) to normalize, we get
η + L = 1 (7.5)
where L is the customer, or traffic loss probability,
L = 1 −η (7.6)
Systems that have high efficiency will have low loss probability and vice versa.
This situation is very similar to mechanical or electrical energy conversion systems
characterized by input power, output power, and lost power due to friction or resis-
tive effects.
7.5 M/M/1 Queue
In an M/M/1 queue at any time step, at most one customer could arrive and at most
one customer could leave. An example of an M/M/1 queue is a first-in-first-out
buffer of a communication system. This gives rise to simplest of queues in queuing
analysis. The queue size here is assumed infinite. This is the discrete time equivalent