Queuing Theory 2014 - Exercises

Ioannis Glaropoulos
February 13, 2014

1
1 Probability Theory and Transforms
1.1 Exercise 1.2
X is a random variable chosen from X1 with probability a and from X2 with
probability b. Calculate E[X] and σX for α = 0.2 and b = 0.8. X1 is an expo-
nentially distributed r.v. with parameter λ1 = 0.1 and X2 is an exponentially
distributed r.v. with parameter λ2 = 0.02. Let the r.v. Y be chosen from
D1 with probability α and from D2 with probability b, where D1 and D2 are
deterministic r.v.s. Calculate the values D1 and D2 so that E[X] = E[Y ] and
σX = σY .
Solution: a) We directly apply the conditional expectation formula:

E[X] = αE[X1 ] + bE[X2 ].

We can do this since the expectation is a raw moment – not central. The proof
is straightforward: we have

fX (x) = αfX1 (x) + bfX2 (x) →

R∞ R∞ R∞
→ E[X] = 0 xfX (x)dx = α 0 xfX1 (x)dx + b 0 xfX2 (x)dx =
= αE[X1 ] + bE[X2 ].

We then replace the given data

1 1 1 1
E[X] = α +b = 0.2 + 0.8 = 42. (1)
λ1 λ2 0.1 0.02
We can not calculate the variance (or the standard deviation) in the same way,
since this is a central moment. Instead, we proceed with calculating the expected
square of the r.v. X, which is a raw moment:
R∞ R∞ R∞
E[X 2 ] = 0 x2 fX (x)dx = α 0 x2 fX1 (x)dx + b 0 x2 fX2 (x)dx =
= αE[X12 ] + bE[X22 ].

Replacing the data we get

2 2 2 2
E[X] = α + b 2 = 0.2 2 + 0.8 = 4040. (2)
λ21 λ2 0.1 0.022

Finally, we use the relation between the expectation, square mean and variance
2 2
σX = E[X 2 ] − [E[X]] = 4040 − 422 → σX = 47.70. (3)

b) We have E[Y ] = αd1 + bd2 and E[Y 2 ] = αd21 + bd22 . So the system of
equations becomes

0.2d1 + 0.8d2 = 42,

(4)
0.2d21 + 0.8d22 = 4040

Solving this 2 by 2 non-linear system we obtain the solution. Notice that because
of the second order of the equation we may in general have more than one
solutions.

2
1.2 Exercise 1.3
k
X is a discrete stochastic variable, pk = P (X = k) = ak! e−a , k = 0, 1, 2, ... and
a is a positive constant.
P∞
a) Prove that k=0 pk = 1.
P∞
b) Determine the z-transform (generating function) P (z) = k=0 z k pk .
c) Calculate E[X], Var[X] and E[X(X − 1)...(X − r + 1)], r = 1, 2, ... with
and without using z-transforms.
Solution a) We have
∞ ∞ ∞
X X ak X ak
pk = e−a = e−a = e−a ea = 1.
k! k!
k=0 k=0 k=0

Notice this useful and well-known infinite series summation.

b) We replace the definition of the mass function and gradually have:
∞ ∞ ∞
X ak −a X ak X (za)k
P (z) = zk e = e−a zk = e−a = e−a eaz = e−a(1−z) .
k! k! k!
k=0 k=0 k=0

c) First, we try without the z-transform, i.e. using the definitions in the
probability domain. We start from the third sentence, using the definition of
expectation: Z ∞
E[g(X)] = g(x)fX (x)dx (5)
−∞

P∞
E[X(X − 1)...(X − r + 1)] = k=0 k(k − 1)...(k − r + 1)pk =
k
ak
P∞ P∞
= k=0 k(k − 1)...(k − r + 1) ak! e−a = k=0 (k−r)! e−a =
P∞ a(k−r)
= e−a ar k=0 (k−r)! = ar e−a ea = ar .

Then clearly, we have (by setting r = 1) E[X] = a1 = a. And, finally,

2
Var[X] = E[X 2 ]−[E[X]] = E[X 2 ]−a2 = E[X(X −1)]+E[X]−a2 = a2 +a−a2 .

We try, now, with the z-transform. We differentiate r times the definition of

the z-transform:
∞ ∞
dr dr X k X
P (z) = z pk = k(k − 1)...(k − r + 1)z k−r pk
dz r dz r
k=0 k=0

If we replace z = 1 we get

dr

P (z) = E[X(X − 1)...(X − r + 1)].
dz r z=1

We, then, calculate,

dr

P (z) = ar e−a(1−1) = ar .
dz r z=1

3
1.3 Exercise 1.4
ak
Xi ’s are independent Poisson distributed random variables, thus, pk = k!i e−ai ,
k = 0, 1, 2, ..., and each ai , i = 1, 2, ...,
Pnn is a positive constant. Give the proba-
bility distribution function of X = i=1 .
Solution: This problem indicates the usefulness of the z-transform in the
calculation of the distribution of the sum of variables. We have proven that
the ZT of the sum of independent random variables is the product of
their individual z-transforms. Thus,
n
Y n
Y Pn
P (z) = Pi (z) = e−ai (1−z) = e i=1 −ai (1−z)
= e−α(1−z) ,
i=1 i=1
Pn
where α = i=1 −ai . This proves that the distribution is also Poisson with
parameter α, i.e. the sum of parameters. The proof is based on the uniqueness
of z-transform1 . As a result, the distribution function will be

αk −α
pX (k) = e
k!

1.4 Exercise 1.5

X is a positive stochastic continuous variable with probability distribution func-
tion (PDF) 
0, x < 0,
F (x) = P (X ≤ x) =
1 − e−ax , x ≥ 0.
a) Give the probability density function f (x) = dF (x)/dx.
b) Give F (x) = P (X > x). R∞
c) Calculate the Laplace Transform f ∗ (s) = E[e−sX ] = 0 e−sx f (x)dx.
d) Calculate the expected values m = E[X], E[X k ], k = 0, 1, 2, ..., the vari-
2
ance σX , the standard deviation σX and the coefficient of variation c = σ/m,
with and without the transform F ∗ (s).
Solution: a) For the calculation of f (x) we just need to differentiate:

f (x) = dF (x)/dx = d(1 − e−ax )/dx = ae−ax .

b) The complementary PDF is simply given as

F X (x) = P (X > x) = 1 − P (X ≤ x) = 1 − FX (x) = e−ax .

c) Calculation of the Laplace Transform with simple integration

Z∞ Z∞ Z∞
∗ −sx −sx −ax a
f (s) = e f (x)dx = e ae dx = a e−x(s+a) dx = .
s+a
0 0 0

d) We proceed first, without the help of Laplace transforms, using the defi-
nition of the expectation
R∞ R∞
E[X 0 ] = 0 x0 f (x)dx = 0 f (x)dx = 1.
1 or the 1-1 correspondence between the mass function and the ZT

4
 R∞ R∞ R ∞ k −ax 0
E[X k ] = 0 xk f (x)dx = 0 xk ae−ax dx = a −1
a 0
x (e ) dx =
R ∞ k−1 −ax ∞ ∞
dx = ka 0 xk−1 ae−ax dx = 0 xk−1 f (x)dx =
R R
=k 0 x e
= ka E[X k−1 ].

This is a recursive formula that enables the calculation of any moment. We

have:
k kk−1 kk−1 1 kk−1 1 k!
E[X k ] = E[X k−1 ] = E[X k−2 ] = .. E[X 0 ] = .. = k
a a a a a a a a a a
which gives, simply, E[X] = 1/a, for k = 1. The variance is calculated through
the usual formula, and the raw moments are taken from above:
 2
2 1
σ 2 = E[X 2 ] − [E[X]]2 = − = 1/a2 .
a2 a

so the standard deviation is simply the square root of the variance, 1/a, and
the coefficient of variation is 1. Notice that this is special for the exponential
distribution.
We try, now, with the help of the Laplace transforms.

dk
∗ k d k
a (−1)k ak!
E[X k ] = (−1)k dsk f (s) = (−1) dsk s+a = (s+a)k+1
.

We find this formula by differentiating k times the Laplace transform and re-
placing s = 0. The rest follows with simple replacement k = 1, 2, ...

1.5 Exercise 1.6

Xi ’s are independent, exponentially distributed random variables with a mean
value of 1/a, a > 0, i = 1, 2, ..., n. Calculate P (X ≤ x) and P (X ≥ x) where
a) X = min(X1 , X2 , ..., Xn ),
b) X = max(X1 , X2 , ..., Xn ).
Solution: a) The key point in this exercise is the fact that the random
variables are independent (mutually independent). We gradually have:

P (X ≤ x) = P (min(X1 , X2 , ..., Xn ) ≤ x) = 1 − P (min(X1 , X2 , ..., Xn ) > x)

Qn
= 1 − P (X1 > x, X2 > x, ..., Xn > x) = 1 − i=1 P (Xi > x)
Qn Pn
= 1 − i=1 e−ax = 1 − e− i=1 ax = 1 − e−nax

This shows that the minimum of exponentially distributed random variables is

also an exponential variable and its rate is the sum of the individual rates.
b) Similar calculations:

P (X ≤ x) = P (max(X1 , X2 , ..., Xn ) ≤ x) = P (X1 ≤ x, X2 ≤ x, ..., Xn ≤ x)

Qn Qn
= i=1 P (Xi ≤ x) = i=1 (1 − e−ax ) = (1 − e−ax )n .

Cleary, the variable X is, now, not exponential.

5
2 Balance equations, birth-death processes, con-
tinuous Markov Chains
2.1 Exercise 3.2
Consider a birth-death process with 3 states, where the transition rate from state
2 to state 1 is q21 = µ and q23 = λ. Show that the mean time spent in state 2
is exponentially distributed with mean 1/(λ + µ).2

Solution: Suppose that the system has just arrived at state 2. The time until
next ”birth“ – denoted here as TB – is exponentially distributed with cumu-
lative distribution function FTB (t) = 1 − e−λt . Similarly, the time until next
”death“ – denoted here as TD – is exponentially distributed with cumulative
distribution function FTD (t) = 1 − e−µt . The random variables TB and TD are
independent.
Denote by T2 the time the system spends in state 2. The system will depart
from state 2 when the first of the two events (birth or death) occurs. Conse-
quently we have T2 = min{TB , TD }. We, then, apply the result from exercise
1.6, that is the minimum of independent exponential random variables is an
exponential random variable. We can actually show this:

FT2 (t) = Pr{T2 ≤ t} =

= Pr{min{TB , TD } ≤ t} =
= 1 − Pr{min{TB , TD } > t} =
= 1 − Pr{TB > t, TD > t} =
= 1 − Pr{TB > t} · Pr{TD > t} =
= 1 − e−λt · e−µt =
= 1 − e−(λ+µ)t

so T2 is exponentially distributed with parameter λ + µ.

Notice that we can generalize to the case with more than two transition
branches. This exercise reveals the property of continuous time Markov chains,
that is, the time spent on a state is exponentially distributed.

2.2 Exercise 3.3

Assume that the number of call arrivals between two locations has Poisson distri-
bution with intensity λ. Also, assume that the holding times of the conversations
are exponentially distributed with a mean of 1/µ. Calculate the average number
of call arrivals for a period of a conversation.

Solution: Denote by NC the number of arriving calls during the period of one
conversation. Denote by T the duration of this conversation. Given that T = t,
NC |T = t is Poisson distributed with parameter λ · t so the probability mass
function of the number of calls will be
(λt)k −λt
Pr{arriving calls within t = k} = Pk (t) = e .
k!
2 This exercise is similar to Exercise 6 from Chapter 1: ”The minimum of independent

exponential variables is exponential.”

6
with an average number of calls: E[NC |T = t] = λt.
Moreover T is exponentially distributed, with parameter µ so the density
function will be:
fT (t) = µe−µt .
We apply the conditional expectation formula:
Z∞ Z∞ Z∞
−µt λ
E[NC ] = E[NC |T = t] · fT (t)dt = λtµe dt = λ tµe−µt dt = .
µ
0 0 0

2.3 Exercise 3.4

Consider a communication link with a constant rate of 4.8kbit/sec. Over the
link we transmit two types of messages, both of exponentially distributed size.
Messages arrive in a Poisson fashion with λ = 10 messages/second. With prob-
ability 0.5 (independent from previous arrivals) the arriving message is of type
1 and has a mean length of 300 bits. Otherwise a message of type 2 arrives with
a mean length of 150 bits. The buffer at the link can at most hold one message
of type 1 or two messages of type 2. A message being transmitted still takes a
place in the buffer.
a) Determine the mean and the coefficient of variation of the service time of
a randomly chosen arriving message.
b) Determine the average times in the system for accepted messages of type
1 and 2.
c) Determine the message loss probabilities for messages of type 1 and 2.

Solution:
a) We have a link with a constant transmission rate. So the service time
distributions follow the packet length distributions. Consequently, the service
times of both packet types are exponential with mean values of
300 1
• Type 1: E[T1 ] = 4800 = 16 sec,
150 1
• Type 2: E[T2 ] = 4800 = 32 sec.
As a result the parameters of the exponential distributions are µ1 = 16 and
µ2 = 32, respectively. A random arriving packet is of Type 1 or Type 2 with
probability 0.5. We apply the conditional expectation 3 :
1 1 3
E[T ] = E[T1 ] + E[T2 ] =
2 2 64
Similarly, we calculate the mean square:
1 1 1 2 1 2 5
E[T 2 ] = E[T12 ] + E[T22 ] = + = 16−2 + 32−2 = · 16−2 .
2 2 2 µ21 2 µ22 4
2 2
p] = E[T ] − (E[T ]) . Then we compute
The variance of T is derived from V ar[T
the standard deviation σT as σT = V ar[T ], and finally the coefficient of
σT
variation is given as: cT = E[T ].

3 This is similar to exercise 1.2

7
 µ1 λ/2 λ/2 λ/2

S11 S0 S12 S22

λ/2 λ/2 µ2 µ2

Figure 1: State Diagram for Exercise 3.4

b) For this part of the exercise, we need to draw the Markov Chain (Fig. 1)
and solve it in the steady state. The state space must be defined in such a
way that we can guarantee that all transitions – from state to state – have an
exponential rate. We choose here to define such a Markov chain with 4 states:
State 0; Empty buffer.
State 11; 1 packet of Type 1.
State 21; 1 packet of Type 2.
State 22; 2 packets of Type 2.
Then we solve the balance equations in the local form:

µ2 P22 = λ/2P21
µ2 P21 = λ/2P0
µ1 P11 = λ/2P0
P0 + P11 + P21 + P22 = 1(norm. equation)

Solution:
P0 = 0.670, P21 = 0.105, P22 = 0.016, P11 = 0.209.
An accepted message of Type 1 can only arrive at state 0, otherwise it is rejected.
So its the average service time will be E[T1 ].
An accepted message of Type 2 can arrive at states 0 and 21, otherwise it is
rejected. Then, the average service time will be (E[T2 ]P0 + 2E[T2 ]P(21 )/(P0 +
P21 ). 4
c) The loss probabilities are equal to the probabilities of the system being in
BLOCKING states, for each of the two packet types. We underline that this is
always true for homogeneous Markov chains, that is, Markov chains where the
arrival rates do not depend on the system state.

2.4 Exercise 3.5

Consider a Markovian system with discouraged job arrivals. Jobs arrive to a
server in a Poisson fashion, with an intensity of one job per 7 seconds. The
jobs observe the queue. They do NOT join the queue with probability lk if they
observe k jobs in the queue. lk = k/4 if k < 4, or 0, otherwise. The service
time is exponentially distributed with mean time of 6 seconds.
a) Determine the mean number of customers in the system, and
b) the number of jobs served in 100 seconds.

Solution:
4 The occurrence of acceptance reduces the sample space to two states only. Then the

probabilities are normalized.

8
 λ λ 3λ/4 2λ/4 λ/4 0
S0 S1 S2 S3 S4 S5

µ µ µ µ µ

Figure 2: State diagram for Exercise 3.5

a) This is a simple model but requires careful design. After building the
correct state diagram, the solution is found, based on the LOCAL balance equa-
tions.
We have a system with 6 states. State space: Sk : k jobs in the system. The
system diagram is shown in Fig. 2).
Balance Equation System:

λP0 = µP1
λP1 = µP2
3λ/4P2 = µP3
λ/2P2 = µP4
λ/4P2 = µP5
P5
k=1 Pk = 1

Solution: P0 ≈ 0.3, and the remaining probabilities are computed based on

P0 and the equations above. After determining the state probabilities, we derive
the average number of customers in the system through
5
X
E[N ] = k · Pk
k=0

We find E[N ] ≈ 1.43.

b) We have, here, a system with different arrival rates in each state. These
systems are defined as non-homogeneous. However, the service rate is constant.
The server is busy with probability (1−P0 ). When it is busy, it serves jobs. The
service rate is µ = 1/6sec−1 . As a result, the server can serve 100 · µ · (1 − P0 )
jobs in 100 seconds on AVERAGE!

2.5 Exercise 3.6

Consider a network node that can serve 1 and store 2 packets altogether. Packets
arrive to the node according to a Poisson process. Serving a packet involves two
independent sequentially performed tasks: the ERROR CHECK and the packet
TRANSMISSION to the output link. Each task requires an exponentially dis-
tributed time with an average of 30msec. Give, that we observe that the node is
empty in 60% of the time, what is the average time spend in the node for one
packet?

Solution: As always, we need to construct the state diagram is such a way

9
 λ λ
λ
S0 S10 S20

S11 S21
µ µ µ µ
λ
λ

Figure 3: State Diagram for Exercise 3.6

that all transitions rates are guaranteed to be exponential. The selected state
space:

S0 : Empty network node,

S11 : One packet under transmission,
S10 : One packet under error-check,
S20 : One packet under error-check and one buffered,
S21 : One packet under transmission and one buffered,

The state diagram is shown in Fig. 3. We can form the global balance equations
parameterized by λ. Then we apply information that is given: P0 = 0.6; This
extra information enables the solution of the system of equations, and leads to
the calculation of λ:
λP0 = µP11
(λ + µ)P11 = µP10
(λ + µ)P10 = λP0 + µP21
µP21 = λP11 + µP22
P11 + P10 + P21 + P22 = 1 − P0 = 0.4

Solution: P10 ≈ 0.1636, P11 ≈ 0.1337, P20 ≈ 0.0365, P21 ≈ 0.0663, λ ≈ 7.63.
For the calculation of the total average system time for a packet, we apply
Little’s formula.
N 1 · (P10 + P11 ) + 2 · (P21 + P22 )
N = λef f · E[Tsys ] → E[Tsys ] = = .
λef f λef f

We always apply the effective arrival rate at Little’s formula, because the formula
needs the actual average arrival rate at the system, excluding possible drops.
Here, the effective rate is not equal to λ, since we have packet drops. However,
since the arrival rate for this system does not change with time, the effective
arrival rate is simply:

λef f = λ · (P0 + P10 + P11 ).

10
3 Chapter 4 – Queuing Systems
3.1 Exercise 4.1
Packets arrive to a communication node with a single output link according to
a Poisson Process. Give the Kendall notation for the following cases:
1. the packet lengths are exponentially distributed, the buffer capacity at the
node is infinite
2. the packet length is fixed, the buffer can store n packets
3. the packet length is L with probability pL amd l with probability pl and
there is no buffer in the node

Solution: Kendall Notation

1. Arrival Process
2. Service Time
3. Number of Servers
4. Number of Total Positions (servers and queues)
5. Population
The Poisson arrivals (M) and the Single server (1) are fixed: M/?/1/?/?
1. M/M/1, as the buffer is infinite
2. M/D/1/n+1, as the service is deterministic and the buffer is n
3. M/G/1/1, as the service is general and there is no buffer

3.2 Exercise 4.2

Give the Kendall notation for the following systems. Telephone calls arrive to
a PBX with C output links. The calls arrive as Poisson process and the call
holding times are exponentially distributed.
1. Calls arriving when all the output links are busy are blocked
2. Up to c calls can wait when all the output links are blocked

Solution:
1. M/M/C/C
2. M/M/C/C+c

3.3 Exercise 4.3

Why is it not a good idea to have a G/G/10/12/5 System? Solution: 10 servers
for 5 users!

11
4 Exercise 4.4
Which system provides the best performance, an M/M/3/300/100 or an
M/M/3/100/100?
Solution: They have the same performance, since the users fit to both
queues. Of course, the first system wastes buffer positions!

4.1 Exercise 4.5

A PBX was installed to handle the voice traffic generated by 300 employees in
an office. Each employee on average makes 2 calls per hour with an average call
duration of 4.5 minutes The PBX has 90 outgoing links.

1. What is the offered load to the PBX?

2. What is the utilization of the outgoing links? Assume that calls arriving
when all the links are busy are queued up.

2
Solution: Offered Load ρ → λT = 300 · 60 · 4.5 = 45 Erlang. Generally, the
actual load is not the offered load.
Link Utilization:
actual load
# servers
The existence of an infinite queue here means that no load is dropped, or
that the offered load is the actual load. So,
offered load 45
utilization = = = 0.5
90 90
.

12
 λ λ λ λ λ
S0 S1 S2 ... Sk Sk+1 ...

µC µC µC µC µC

Figure 4: System diagram for the M/M/1 chain of exercise 5.1

5 Chapter 5 – M/M/1 Systems

5.1 Exercise 5.1
In a computer network a link has a transmission rate of C bit/s. Messages arrive
to this link in a Poisson fashion with rate λ messages per second. Assume that
the messages have exponentially distributed length with a mean of 1/µ bits and
the messages are queued in a FCFS fashion if the link is busy.
a) Determine the minimum required C for given λ and µ such that the average
system time (service time + waiting time) is less than a given time T0 .
Solution: System Description
• Single communication link: C bits per second
• Poisson arrivals: λ messages per second

• Exponential Service times: E[T ] = E[X]/C = 1/(µC), so the exponential

rate is µC.
• First Come First Served policy
• Infinite Queue5

This is a typical M/M/1 System. We see the system diagram in Fig. 4.

We first derive the state distribution (steady-state) of this system through the
solution of the balance equations. We define ρ = λ/(µC). For a no-loss system,
ρ is the OFFERED and, at the same time, the ACTUAL load.

λP0 = (µC)P1 → P1 = ρP0

λP1 = (µC)P2 → P2 = ρP1 = ρ2 P0
λP2 = (µC)P3 → P3 = ρP2 = ρ3 P0
.............................................................................
λPk = (µC)Pk+1 → Pk+1 = ρPk = ρk P0
........................................

Then, we calculate the P0 through the normalization equation:

∞ ∞ ∞
X X X 1
Pk = 1 → ρ k P0 = 1 → P0 ρ k = 1 → P0 · = 1 → P0 = 1 − ρ.
1−ρ
k=0 k=0 k=0
5 If no buffer capacity is mentioned, we always assume that this is infinite.

13
Finally, the state distribution is given as

Pk = (1 − ρ)ρk .

We, now, derive the average number of messages in the system, using the state
distribution:
P∞ P∞ P∞
N = k=0 kPk = k=0 k(1 − ρ)ρk = (1 − ρ)ρ k=0 kρk−1 =
d( ∞ k
k=0 ρ )
P
P∞ dρk
= (1 − ρ)ρ k=0 dρ = (1 − ρ)ρ dρ = (1 − ρ)ρ d(1/(1−ρ))
dρ = ρ
1−ρ .

In order to solve the first question we can use the LITTLE’s formula:

N ρ/(1 − ρ) λ/(µC)/(1 − λ/(µC))

N = λeff E[Ttotal ] → E[Ttotal ] = = = ,
λ λ λ
since λef f = λ, so, finally,

1
E[Ttotal ] = .
(µC) − λ

The minimum required C is determined by:

1 λ + T0−1
≤ T0 → µC − λ ≥ T0−1 → C ≥ .
µC − λ µ

5.2 Exercise 5.5

Consider a queuing system with a single server. The arrival events can be
modeled with Poisson distribution, but two customers arrive at the system at
each arrival event. Each customer requires an exponentially distributed service
time.
1. Draw the state diagram
2. Determine pk using local balance equations
P∞
3. Let P (z) = k=0 z k pk . Calculate P (z) for the system. Note, that P (z)
must be finite for |z| < 1, and we know P (1) = 1.
4. Calculate the mean number of customers in the system with the help of
P (z) and compare it with the one of the M/M/1 system.

Solution: The system can be described by an M/M/1 model, since there is a

single server, the service times are exponential service and the arrival process
is Poisson. We must notice, however, that this Poisson Process models arrival
events, but the events consist of two customer arrivals. (The departure events
are still one-by-one, though.)
As always, for a Markovian System we must guarantee that all transitions
are exponential. We define the usual state space: Sk : k customers in the

14
 λ λ λ λ

S0 S1 S2 S3 ... Sk Sk+1 ...

µ µ µ µ µ µ

Figure 5: System diagram for the M/M/1 chain of exercise 5.5

system. Then, the state diagram is straightforward. Special care must be taken
on determining the transitions and rates from state to state.

Departure rate = µ
Arrival Event rate = λ

Clearly, the average customer arrival rate is 2λ and is NOT Poisson! What IS
Poisson is the group arrival rate. We also DEFINE ρ = µλ . This is neither the
offered nor the actual load. We just use ρ to define this fraction.
The system diagram is given in Fig. 5.
Local Balance Equations:

λP0 = µP1
λPk−2 + λPk−1 = µPk , k≥2

We can go ahead and solve them numerically. Alternatively, we can use

the ZT methodology, since we only want to compute the average number of
customers.
We consider the parametric local balance equation:

µPk = λPk−1 + λPk−2 →

P∞ P∞
→ k=2 z k µPk = k=2 z k (λPk−1 + λPk−2 )
P∞ P∞
→ µ(P (z) − zP1 − P0 ) = k=2 λz k Pk−1 + k=2 λz k Pk−2
P∞ P∞
→ µ(P (z) − zP1 − P0 ) = λz k=2 λz k−1 Pk−1 + λz 2 k=2 λz k−2 Pk−2

→ µ(P (z) − zP1 − P0 ) = λz(P (z) − P0 ) + λz 2 P (z)

We solve the equation with respect to P (z)

µP0 + µzP1 − λzP0 P0 + zP1 − ρzP0

P (z) = 2
= . (6)
µ − λz − λz 1 − ρz − ρz 2
We need to apply two conditions that HOLD, in order to determine the unknown
terms above. The first condition comes from the balance equation that we did
not consider. We replace P1 = ρP0 in (6), and obtain:

P0
P (z) = . (7)
1 − ρz − ρz 2

15
The second condition comes from the NORMALIZATION in the probability or
in the Z-domain:
X∞
Pk = 1, or, P (z = 1) = 1.
k=0

Replacing that in (7) we obtain P0 = 1 − 2ρ, so finally

1 − 2ρ
P (z) = (8)
1 − ρz − ρz 2

Finally, we need to compute the mean number of customers. We have

 
dP (z)
N= .
dz z=1

Proof:
   P∞ k  "∞ # ∞
dP (z) d k=0 z Pk X X
= = kz k−1 Pk = kPk = N .
dz z=1 dz z=1 k=0 z=1 k=0

So, this is what we will do. We differentiate the derived ZT in (8):

dP (z) (−1)(1 − 2ρ)(−ρ − 2ρz)

=
dz (1 − ρz − ρz 2 )2

Replacing z = 1 we obtain
3ρ 3λ
N= = .
1 − 2ρ µ − 2λ

The typical M/M/1 system with the same average customer arrival rate (2λ)
ρ
and service rate (µ) has N M/M/1 = 1−ρ , where ρ is its offered load, and is equal
to ρ = 2λ/µ. So, finally,
2λ
N M/M/1 =
µ − 2λ
so it is different, and, actually, less. Why?

5.3 Exercise 5.6

A queuing system has one server and infinite queuing capacity. The number of
customers in the system can be modeled as a birth-death process with λk = λ
and µk = kµ, k = 0, 1, 2, ... thus, the server increases the speed of the service
with the number of customers in the queue. Calculate the average number of
customers in the system as a function of ρ = λ/µ.
Solution: The system is an M/M/1 queue, since it has infinite buffer, 1
server, and Markovian arrival and departure process. However, as we can see, it
is not a typical M/M/1 case, as the service rates depend on the current system
state. The system diagram is shown in Fig. 6. We need to solve the system of
balance equations:

16
 λ λ λ λ λ
S0 S1 S2 ... Sk Sk+1 ...

µ 2µ 3µ kµ (k + 1)µ

Figure 6: System diagram for the M/M/1 chain of exercise 5.6

λP0 = µP1 → P1 = ρP0

λP1 = 2µP2 → P2 = 12 ρP1 = 21 ρ2 P0
λP2 = 3µP3 → P3 = 13 ρP2 = 1 3
2·3 ρ P0

.........................................................................
λPk−1 = kµPk → Pk = k1 ρPk−1 = ... = k! 1 k
ρ P0
.........................................................................
P∞
k=0 Pk = 1 (normalization)

From the last general equation and the normalization equation we obtain
the state distribution:
∞
X ρk
P0 = 1 → P0 eρ = 1 → P0 = e−ρ .
k!
k=0

so finally, for each k

ρk −ρ
e Pk =
k!
so the state distribution is POISSON! Then, we can calculate the average num-
ber of customers from the state distribution
∞
X
N= kPk = ρ
k=0

or simply say that the average is ρ, from the Poisson distribution.

From LITTLE we can, also, calculate the average system time

N 1
E[Ttotal ] = = .
λ µ
This means that the arriving customers only stay in the system for an average
time equal to the service time!6

5.4 Exercise 5.7

Customers arrive to a single server system in groups of 1,2,3 and 4 customers.
The number of customers per group is i.i.d. There are in total 4 places in the
6 This is equivalent to the case where there is no queue and each customer is served in

parallel with the others, so actually this system is equivalent to an M/M/∞ system!

17
system. If a group of customers does not fit into the system, none of the members
of the group joins the queue. 10% of the customers arrive in a group of 1, 20%
of the customers arrive in groups of 2, 30% in a group of 3 and 40% in a group
of 4 customers. The average number of arriving customers is 75 customers
per hour, the interarrival time between groups is exponentially distributed. The
service time is exponentially distributed with a mean of 0.5 minutes.
1. Give the Kendall notation of the system and draw the state transition
diagram.

2. Calculate the average number of customers in the queue and the mean
waiting time per customer.
3. Calculate the probability that the system is full and the probability that a
customer arriving in a group of k customers can not join the queue.

4. Calculate the probability that an arriving customer in general can not join
the queue and the probability that an arriving group of customers can not
join the queue.
5. What is the average waiting time for a customer arriving in a group of 3
customers?

Solution: This is a very interesting problem that reveals the problems when
the arriving process is complex and not straightforward so it must be derived.
First, we give the Kendall notation of the system. We have:

• Exponential GROUP inter-arrival times, so the arrival time will be Marko-

vian.7
• The service times are exponentially distributed
• The system has a single server

• The total capacity is 4

Consequently, the Kendall notation is M/M/1/4.
We must draw the state transition diagram. We consider the typical state space
where Sk means ”k customers in the system”. As a result the system has 5
states in total. The service rates are always the same, with
1 1
µ= = = 120h−1 .
E[Ts ] 0.5/60

The difficulty lies in deriving the arrival transition rates. We are given
that the number of customers per group is i.i.d. We assume, naturally, that
the GROUP arrival process is HOMOGENEOUS, that is, groups arrive in each
state with the same rate! Also, since the inter-arrival times between GROUP ar-
rivals are exponential we conclude that the GROUP arrivals is a Poisson process.

7 It is our task to find an appropriate state space where the event arrival process is Poisson.

18
We are given that the number of customers per group is an i.i.d. process,
but we are NOT given the distribution. Let

q1 , q2 , q3 , q4

denote the probabilities that a random arriving group contains 1,2,3,4 customers
respectively.
Let λG denote the Poisson group arrival rate. Then, the individual rates
for each groups is ALSO a Poisson process, based on the Poisson split property,
with rates
λG q1 , λG q2 , λG q3 , λG q4 .
For any i = 1, 2, 3, 4,
λG · qi
defines the (average) rate of arrivals for group’s of type i, and, consequently,

λG · qi · i

defines the (average) rate of arrivals of customers belonging to group of type i.

Based on the given data from the exercise regarding the ratio of customers
arriving in any of the groups, we obtain the following equations:

λG q1 · 1 = 10% · 75
λG q2 · 2 = 20% · 75
λG q3 · 3 = 30% · 75
λG q4 · 4 = 40% · 75

From the above it is clear that q1 = q2 = q3 = q4 → qi = 41 , ∀i = 1, 2, 3, 4.

Finally, using any of the above equations we compute the group arrival rate:

λG = 30 groups / hour

We can now complete the state diagram (Fig. 7). Then, we solve the LOCAL
balance equations, to define the state probabilities.
We can compute BOTH the average number of customers in the system, and
the average number of customers in the queue:

N queue = 1 · P2 + 2 · P3 + 3 · P4
N = 1 · P1 + 2 · P2 + 3 · P3 + 4 · P4

For the average waiting time, we could apply the LITTLE result. For that
we need the effective customer arrival rate, which is different from the nominal,
since there are losses in the system.
It is important to notice again that the system is HOMOGENEOUS in group
arrivals but not in customer arrivals.
We have

λef f = P0 λG ·(q1 +2q2 +3q3 +4q4 )+P1 λG ·(q1 +2q2 +3q3 )+P2 λG ·(q1 +2q2 )+P3 λG ·(q1 ).

19
 λG q4

λG q3 λG q3

λG q2 λG q2 λG q2
λG q1 λG
λG q1 λG q1 λG q1
S0 S1 S2 S3 S4

µ µ µ µ

λG q4 λG q3 + λG q4 λG q2 + λG q3 + λG q4

Figure 7: System diagram for the M/M/1 chain of exercise 5.7

Then, from LITTLE we compute first the system time, N = λef f E[T ], and
then the average waiting time will be W = E[T ] − E[Ts ].

The probability that the system is full (as seen by an independent observer)
is simply P4 .

The probability that a customer of a group k does not join the queue is, actu-
ally, the probability that the whole particular group does not join the queue.
Since the system is homogeneous in group arrivals (a random group SEES state
distribution),

Pr(a random group 1 is blocked) = P4

Pr(a random group 2 is blocked) = P4 + P3
Pr(a random group 3 is blocked) = P4 + P3 + P2
Pr(a random group 4 is blocked) = P4 + P3 + P2 + P1

An arriving customer in general, belongs to groups 1,2,3,4 with probabilities

10%, 20%, 30% and 40%. So given these probabilities, he follows the group
blocking probabilities:

Pr(a random customer is blocked) =

= 40% · (P1 + P2 + P3 + P4 ) + 30% · (P2 + P3 + P4 ) + 20%2 · (P3 + P4 ) + 10% · P4

20
 An arriving group of customers is blocked with probability

Pr(a random group is blocked) =

P4
= i=1 Pr{a random group has i customers} · Pr{a random group i is blocked} =
= P4 + P3 · 3/4 + P2 · 1/2 + P1 · 1/4.

A customer that arrives in group of 3 customers MEANS that the arrived

group sees either state 0 or state 1, otherwise there is no mean of WAITING
time, since the group is rejected. The arrivals are homogeneous in groups, so
the groups see state 0, 1 with probabilities P0 , P1 , respectively. So
P0 P1
W3 = · W30 + · W31
P0 + P1 P0 + P1
where the two waiting times are
1 1
W30 = (0.5 + 1 + 0), W31 = (0.5 + 1 + 1.5)
3 3

21
 λ λ λ λ λ λ λ
S0 S1 S2 S3 ... S9 S10

µ 2µ 3µ 4µ 9µ 10µ

Figure 8: System diagram for exercise 6.5

6 Chapter 6 – M/M/m/m Loss Systems

Abstract
The importance for this tutorial is to introduce the students into the
loss systems, and, to underline the difference between the concepts of
call-blocking and time-blocking probabilities, and to understand under
which conditions these probabilities are identical. The selected exercises
introduce, also, the Erlang tables, which is an important tool for easy
calculations for the blocking probabilities.

6.1 Exercise 6.5

A telephone switch has 10 output lines and a large number of incoming lines.
Upon arrival a call on the input line is assigned an output line if such line
is available – otherwise the call is blocked and lost. The output line remains
assigned to the call for its entire duration which is of exponentially distributed
length. Assume that 180 calls / hour arrive in Poisson fashion whereas the
mean call duration is 110 seconds.
1. Determine the blocking probability.
2. How many calls are rejected per hour?
3. What is the average load per server (in Erlang)?
4. What is the maximum arrival rate at which a blocking probability of (at
most) 2% can be guaranteed?

Solution: This is an introductory problem for the Markovian Loss Systems.

We start with the system mode and the Kendall Notation:
• Poisson arrivals with rate λ = 180 calls per hour
1 3600
• Exponential service times with rate µ = E[T ] = 110

• 10 Servers
• No buffer
The Kendall Notation is: M/M/10/10.
We draw the system diagram (Fig. 8) and, based on that, we build the
balance equations to compute the state probabilities. A state, S, defines the
number of active calls in the system. We define
λ
ρ=
µ

22
which, here, is also the offered load of the system; of course this is NOT the
actual load, since the system may drop calls when it is blocked. We have:

λP0 = µP1 → P1 = ρP0

ρ2
λP1 = 2µP2 → P2 = ρ2 P1 = 2 P0
ρ3
λP2 = 3µP3 → P3 = ρ3 P2 = 3·2 P0

.............................................................
k
λPk−1 = kµPk → Pk = kρ Pk−1 = ρk! P0

We use the normalization equation to compute the P0 :

n n
X X ρk 1
Pk = 1 → P0 = 1 → P0 = Pn ρk
.
k! k=0 k!
k=0 k=0

where, here, n = 10. The blocking probability is the probability that the system
can not accept new calls, and this is equal to the probability of the system being
in state Sn (S10 ). This probability is, also, the TIME BLOCKING, i.e. the
percentage of time the system can not accept new calls, and it is the one seen
by an independent observer.
ρn
Pblock = Pn = Pnn! ρk
k=0 k!

General rule: In Markov chains where the arrival rates do not depend on the
system state, the time blocking is also equal to the probability of a random
event being blocked. The latter is defined as CALL BLOCKING probability.

You can compute the Pblock from the equation above, but you could also do
it by using the Erlang tables.

• Servers: n = 10
λ 180
• Offered Load: ρ = µ = 3600 = 5.5
110

We search in the tables for the solution. E10 (5.5) ≈ 0.029.

The rate of rejected calls is ALWAYS given by: λ · Pcall block . However, as
stated above, here,
Pcall block = Pblock
since the arrival process is independent of the system state8 . We get:

λrejected = λPblock ≈ 180 · 0.029 = 5.27.

8 or, as we say, alternatively, the arrival process is homogeneous.

23
To find the average load per server, we first need to find the total ACTUAL
load. The actual load is the nominal (offered) load minus the rejected load:

λef f = λ − λrejected = λ(1 − P1 0) = 5.5 · (1 − 0.029)

For the average load per server, we divide the above with the number of severs.9

As we see the blocking probability is above the target of 2%. So we must

decrease the offered load, keeping the number of servers to 10. We check in the
tables the maximum offered load that guarantees the blocking probability below
the target. Then, from that we find the nominal arrival rate.

7 Exercise 6.3
We consider two types of call arrivals to a cell in a mobile telephone network:
new calls that originate in a cell and calls that are handed over from neighboring
cells. It is desirable to give preference to handover calls over new calls. For this
reason, some of the channels in the cell are reserved for handover calls, while
the rest of the channels are available to both types of calls. For the questions
below, assume the following: Channels in the cell are held for two minutes on
average, with exponential distribution. All calls arrive according to a Poisson
process with rate λnc = 125 calls per hour for new calls, and λho = 50 calls
per hour for handover calls. The cell has a capacity of 10 channels; each call
occupies 1 channel.
1. Draw a state diagram of the channel occupancy in a cell when 2 channels
are used exclusively for handover calls.
2. Calculate the blocking probability in the cell if no channels are reserved for
handover calls. What is the average number of channels used?
3. Find the minimum number of channels reserved for handover calls so that
their blocking probability is below 1 percent. What is the blocking probabil-
ity for the new calls in this case?

Solution:
This is an interesting exercise that models a Mobile network, like GSM,
UTRAN etc. We have a system which prioritizes some calls (handover) over
some others (new).
We draw the state transition diagram for the case of 2 reserved channels for
handover calls (Fig. 9)

• Poisson arrivals – λ = λnc + λho for states 0,1,2,...,7, λ = λho for states
8,9. This is a nce application of the Poisson SPLIT property.
1 1
• Exponential Service times – µ = E[t] = 2/60 = 30.

• 10 servers, no buffer
9 Check also exercise 4.5.

24
 λno λnc

λnc + λho λnc + λho λλnc

nc +
+ λλho
ho λho λho λnc + λho

S0 S1 S2 ... S8 S9 S10

µ 2µ 3µ 8µ 9µ 10µ

Figure 9: State diagram for exercise 6.3. Case of 2 reserved channels for han-
dover calls. Notice that the system accepts only handover arrivals when only 2
channels remain vacant. In state 10, both handover and new calls are dropped.

We can draw and solve the balance equations for this system, and calculate, for
example, the average number of active calls in the cell. The offered load in the
system is
λtotal · E[T ] = (λnc + λho ) · E[T ].
What is the actual load of this system?

We consider, now, the case where no channels are reserved for handover calls.
The Kendall notation is then M/M/10/10. So, the system resembles a standard
M/M/10/10 case!
2 35
• Offered Load: ρ = (λnc + λh o)E[T ] = 175 · 60 = 6 .

• Servers: n = 10
• Blocking Probability: E10 ( 35
6 ) = ...

Consequently, the effective, or actual load of the system is λef f = 175 · (1 −

E10 (35/6)) = ...
We can apply the state probabilities to derive the average number of calls
in the cell. However, since we know the effective load, and the average system
time, we can also apply the LITTLE formula

N = λef f · E[T ] = ...

For the third question we need to go step by step. First, we do the calcula-
tions with one reserved channel. The diagram in shown in Fig. 10 We have the
result:
9
λho λtot λho
10µ 9!µ9 10µ
Pblock = P10 = λ2tot λ9tot λho λ9tot
= 1 λho
λtot +
1+ µ + 2µ2 + ... + 9!µ9 + 10!µ10 E9 (ρ) 10µ

If we replace the number we find a blocking probability of 1.1%, which is above

the target. We now do the calculations for two reserved channels (Fig. 11):
λ2ho λ8tot λ2ho
10µ9µ 8!µ8 10·9µ2
Pblock = P10 = λ2tot λ8tot λho λ8tot λ2ho λ8tot
= λ2ho
λtot 1 λho
1+ µ + 2µ2 + ... + 8!µ 8 + 9!µ9 + 10!µ10 E8 (ρ) + 9µ + 10·9µ2

25
 λnc

λnc + λho λnc + λho λλnc

nc +
+ λλho
ho λnc + λho λho λnc + λho

S0 S1 S2 ... S8 S9 S10

µ 2µ 3µ 8µ 9µ 10µ

Figure 10: State diagram for exercise 6.3c. Case of 1 reserved channel for
handover calls. Notice that the system accepts only handover arrivals when
only one channel remains vacant. State S9 is now green, to show that it is a
non-blocked state for handover calls.

λno λnc

λnc + λho λnc + λho λλnc

nc +
+ λλho
ho λho λho λnc + λho

S0 S1 S2 ... S8 S9 S10

µ 2µ 3µ 8µ 9µ 10µ

Figure 11: State diagram for exercise 6.3c. Case of 2 reserved channel for
handover calls. Notice that the system accepts only handover arrivals when
only one channel remains vacant. State S9 is now green, to show that it is a
non-blocked state for handover calls.

We do again the calculations and find a probability of 0.2%, which is accept-

able.
Finally, the blocking probability for the new calls is P8 + P9 + P10 , since
the system is time homogeneous and the last two channels are reserved for the
handovers.

7.1 Exercise 8 [Collection of Exam Problems]

Consider two M/M/2 loss systems, A and B. A has 40 subscribers; to B there
are 4 subscribers connected. Each subscriber generates on average 1 call per
minute. The mean service time is 6 seconds.
1. Compare the call blocking probability for A and B
2. Compare the mean blocking time for A and B
3. Compare the mean time without blocking for A and B
4. How many additional servers do you have to provide to system A to achieve
a time blocking that is not higher than that of system B?

Solution: There is a clear difference between the two system, and that is, the
user population. In Fig. 12 we depict the two system diagrams. Both systems
have finite population, i.e. the user arrival rate depends on the system state.

26
 40λ 39λ 38λ
S0 S1 S2

µ 2µ
(a)

4λ 3λ 2λ
S0 S1 S2

µ 2µ
(b)

Figure 12: State diagrams for the A and B systems of exercise 8.

However, the first system (A) could be approximated with a typical M/M/2/2
system, since the population size (40) is high compared to the number of servers
(2). In other words, 40λ ≈ 39λ ≈ 38λ. We can not say the same for system B.

System A The offered load is

40λ 6
ρ= = 40λ · E[T ] = 40 · 1 · = 4 Erl.
µ 60
We can either draw and solve the balance equations, or use the Erlang Tables
to compute the TIME blocking probability (P2 ). In the second case, we obtain:

Em (ρ) = E2 (4) = 0.615.

We notice that the TIME Blocking probability is equal to the CALL blocking
probability since the arrival intensity is constant and does not depend on the
state (we assumed typical M/M/2/2). So, we obtain:

Pblock = P2 = 0.615

The mean blocking time (Tb ) is the average time the system CONTINU-
OUSLY remains in state S2 , i.e. from the time it arrives at S2 until it departs
to S1 . The transition rate (S2 → S1 ) is 2µ, so the average time the system stays
at S2 is E[Tb ] = 1/2µ = 3sec.
The mean time without blocking (Tn ) is the average time between a
departure from state S2 and an arrival at state S2 . It is not the percentage
of time without blocking! That would be, simply, P0 + P1 .

We must calculate E[Tn ] based on Pb , E[Tb ]. We define a cycle of the sys-

tem as a set of adjacent blocking and non-blocking periods. Consider that we
observe the system for a large period of cycles, say M. Then it holds:
PM i
T
Pb = lim PM i=1 b , (9)
M →∞ i i
i=1 Tb + Tn

27
where Tbi is the duration of the blocking period at cycle i and Tni is the duration
of the non-blocking period at cycle i. We rewrite the above as
1
PM 1
PM
Ti limM →∞ i
i=1 Tb
Pb = lim 1 PM i=1 b
M
= 1
M
PM (10)
M →∞ i i i i
M i=1 Tb + Tn limM →∞ M i=1 Tb + Tn

and finally:
1
PM i
limM →∞ M i=1 Tb E[Tb ]
Pb = 1
PM i 1
PM = . (11)
limM →∞ i=1 Tb + limM →∞
i
i=1 Tn
E[Tb ] + E[Tn ]
M M

From the above we can calculate E[Tn ] with respect to Pb and E[Tb ].
The solution for system B is similar to the one for system A, EXCEPT that
we can not use the approximation from the Erlang tables, so we need to derive
the steady-state solution by solving the balance equations.
We calculate the mean blocking time and the mean time without block in
the same way.
Note, however, that the call blocking probability is different, now, since this
chain is non-homogeneous, as the arrival rate is state-dependent! In particular:
2λP2
Pcall block =
4λP0 + 3λP1 + 2λP2

28
8 Tutorial 7 – M/M/m systems
8.1 Exercise 7.2
The performance of a system with one processor and another with two processors
will be compared. Let the inter-arrival times of jobs be exponentially distributed
with parameter λ. We consider, first, the system with one processor. The service
time of the jobs is exponentially distributed with a mean of 0.5sec.
1. For an average response time of 2.5sec (the total time for a job in the
system) how many jobs per second can be handled?
2. For an increase of λ with 10% how much will the response time increase?
3. Calculate the average waiting time, the average number of customers in
the server and the utilization of the server. What is the probability of the
server being empty?
Let us now compare this system with a system of two cheaper processors, each
with a mean service time of 1 sec.
1. How many jobs can now be handled per second with a mean response time
of 2.5 sec?
2. For an increase of λ with 10% how much will the response time increase?
3. Calculate the average waiting time, the average number of customers in
the server and the utilization of the server. What is the probability of both
of the servers being busy?
Solution: We consider first the system with one processor. Clearly, since we are
not given any information regarding the buffer data, and we are also told that
there is waiting time, we can safely conclude that the buffer is infinite.

As a result we are dealing with a typical M/M/1 system, and we will derive
the answers from the M/M/1 formulas. The average number of jobs in the
M/M/1 system is given as

ρ λ/2 λ
N= = =
1−ρ 1 − λ/2 2−λ
1 1
since µ = E[T ] = 0.5 = 2. Applying the LITTLE’s formula, we get

N 1
T system = = → λ = 1.6
λ 2−λ

since T system = 2.5. Assume now that we increase the arrival rate by 10%. The
new rate will be λ̂ = 1.1 · 1.6 = 1.76. This will change the offered load of the
system to ρ̂ = µλ̂ = 1.762 = 0.88. Then the response time will be given in a
similar way:
1 1
T̂system = = = 4.1666sec
µ − λ̂ 2 − 1.76
4.166−2.5
So the increase is 2.5 = 66.66%

29
 λ λ λ λ
S0 S1 S2 S3 ...

µ 2µ 2µ 2µ

Figure 13: System diagram for the second model of exercise 7.2

For the initial (λ = 1.6) system the average waiting time is W = T system −
E[T ] = T system − µ1 = 2sec, the mean number of customers in the system is
N = ρ/(1 − ρ) = 0.8/0.2 = 4, and the probability of empty server is 1 − ρ = 0.2.
The utilization is of course ρ and is equal to the mean number of customers in
the server.

We consider now the second system. This one has 2 processors with µ = 1,
so half of the service rate. The offered load for this system is ρ = λ/1 = λ. The
state diagram is given in Fig 13. We could use the formulas for the M/M/2
system. However, since we only have 2 servers, we can solve it analytically with
the Balance Equations.
λP0 = µP1 → P1 = ρP0
2
λP1 = 2µP2 → P2 = 21 ρP1 = ρ2 P0
3
λP2 = 2µP3 → P3 = 12 ρP2 = ρ4 P0
............................................
ρk
λPk−1 = µPk → Pk = 2k−1 P0
From the above equation set and the normalization equation we derive
∞
!
X ρk−1 2−ρ
P0 1 + ρ k−1
= 1 → P0 = .
2 2+ρ
k=1

Then, we calculate the mean number of customers in the system, from the state
distribution
∞ ∞
X X ρk 2 − ρ 4ρ 4λ
N= kPk = k = ... = = .
2k−1 2 + ρ (2 + ρ)(2 − ρ) (2 + λ)(2 − λ)
k=1 k=1

Then, based on LITTLE we compute the average system time:

r
N 4 6
T system = = →λ= ≈ 1.54919
λ (2 + λ)(2 − λ) 2.5
This is the maximum allowed arrival rate, in order to guarantee the target
response time of 2.5 seconds. As we can see, it is lower than 1.6, meaning that
the second system is worse than the first, so for the same performance objective
it can serve less incoming load.
We increase, now the λ by 10%, so λ̂ = 1.704 [of the original = 1.54919
load]. The average system time will, then be
4
T̂system = = ... = 3.65sec
(2 + 1.704)(2 − 1.704)

30
 3.65−2.5
So the increase is 2.5 = ....

Note that for a fair comparison with the previous system we must compute
the response time for λ = 1.76. Calculations give:
4
T̂system = = ... = 4.4326sec
(2 + 1.76)(2 − 1.76)

which is larger than the 4.1666 of the previous system, as expected.

The average waiting time will be given through the series:
∞
X
W = Pk = 1 − P0 − P1 = ...
k=2

1
but, simply, can be given as T system − µ = 1.5 sec.

The average number of customers in the servers (together) is: N server = P1 +

2 · (1 − P0 − P1 ) = ...

Utilization of an ARBITRARY server: U = 0 · P0 + 12 P1 + 1 · (1 − P0 − P1 ),

since at state S1 a server is utilized with probability 1/2. Alternatively, we can
divide the offered load, which is also the actual load, by the number of servers.
The probability that both servers are busy is: 1 − P0 − P1 .

8.2 Exercise 7.6

Consider a pure delay system where customers arrive according to a Poisson
process with intensity λ = 3. The service time is exponentially distributed with
mean value 1/3. The queuing discipline is FCFS. There are two servers in the
system, and one of them is always available. The other one starts service when
the queue length would become two (so that it immediately becomes one). If
there are no more customers in the queue, the server which becomes idle first
is closed (and stays closed until the queue length becomes two again). Let us
denote the state of the system with (i,j) where i is the total number of customers
in the system and j is the number of open servers. Give the Kendall notation of
the system and draw the system diagram.

Solution: In this problem the state space is given. Sij denotes the state where
the total number of customers [in the server(s) and in the queue] is i and the
number of active servers is j. Given the state space we draw the system dia-
gram in Fig. 14. The system has 2 servers, infinite queue, Poisson arrivals and
exponential service times, so the Kendall notation is: M/M/2, although it is
not a typical case, as you see in the diagram.

31
 λ λ λ
S22 S32 S42 ...

2µ 2µ 2µ

2µ λ

λ λ

S01 S11 S21

µ µ

Figure 14: System diagram for exercise 7.6. Notice that the system transits
from S21 to S32 , since this new arrival would make the queue length become 2,
so the second server is activated, and the queue length remains one, while both
servers, now, serve a customer.

32
9 Tutorial 8 – M/M/m systems with limited
number of customers
10 Exercise 6.6
There are K computers in an office, and a single repairman. Each computer
breaks down after an exponentially distributed time with parameter α. The re-
pair takes an exponentially distributed amount of time with parameter β. Only
one computer is being repaired at a time, computers break down independently
from the repair process, and repair times and lifetimes of the computers are
independent.
1. What is the probability that i computers are working at time t?
2. What is the average failure rate (i.e. the average number of computers
that fail per time unit)?
3. What is the percentage of time a repairman is busy?
4. What is the percentage of time when all computers are out-of-order (bro-
ken)?
5. How many computers should we have if we would like to have K computers
to work on average?

Solution:

By reading the first question of this problem we already realize what the desired
State Space could be. We try with the obvious selection:
State Si : i computers working, i = 0, 1, 2, ..., K
The K computers in the system is the population size of our model. And it is,
clearly, finite. The single repairman represents the servers in our model (1).
Each computer needs an exponentially distributed time for repair, so the service
rates in our model are exponential. Finally, each computer breaks-down after
an exponentially distributed time (after its repair) so the arrival process in the
system is, also, Markovian.
To summarize:
• A break-down of a computer is an ”arrival”
• A repair of a computer is a ”departure” or a ”service”
Based on the above, we depict the diagram in Fig. 10. We denote γ = β/α. We
draw the Balance Equations:
β
βP0 = αP1 → P1 = α P0 = γP0 ,
β
βP1 = 2αP2 → P2 = 2α P1 = 21 γP1 = 12 γ 2 P0 ,
βP1 = 3αP2 → β
P2 = 3α P1 = 31 γP1 = 1 3 (12)
2·3 γ P0 ,
...............................................................
β 1 K
βPK−1 = KαPK → PK = Kα PK−1 = .... = K! γ P0 .

33
 β β β β β

S0 S1 S2 ... SK−1 SK

α 2α 3α(K − 1)α Kα

Figure 15: System diagram for exercise 6.6

From the above it is clear that the probability of an arbitrary state Si is

γi
Pi = P0 , i = 0, 1, 2, ..., K (13)
i!
From the above and the normalization equation we derive the P0 :
K K
X X 1 j 1
Pj = 1 → γ P0 = 1 → P0 = PK 1 . (14)
j=1 j=1
j! j=1 j! γ
j

P0 gives the probability that all computers are out of order. In addition, the
probability that i computers are working (in the steady-state) is given by:

γi
Pi = PK γj
. (15)
i! j=1 j!

The repairman is busy in all states, except state SK , where all computers are
working properly. So the percentage of time the repairman is busy, will be:

Prep. busy = 1 − PK . (16)

Next, we want to calculate the average failure rate (λfail rate ). We notice that
the failure rate depends on the state of the system. For example, the failure
rate in state SK is Kα, while, in case S0 is it zero! We use the conditional
expectation calculation to compute it:
K
X K
X
λfail rate = j · αPj = α j · Pj , (17)
j=1 j=1

where Pj is given above. The average number of working computers will be

calculated based on the state probability distribution, that is:
K K
X X γi
N= i · Pi = i· PK γj
(18)
i=1 i=1 i! j=1 j!

We would like to have a system with K computers working (on average). Assume
the required number of computers is M . Then M can be found as the lowest
integer that satisfies the inequality:
M
X γi
N ≥K → i· PM γj
≥ K. (19)
i=1 i! j=1 j!

34
We can find the require M by trial-and-error.
Extra question: What is the probability that a broken computer can
not be repaired immediately?
This probability can be found by taking the ratio of the rate of computer break-
downs that can not be served immediately, over the total average rate of com-
puter break-downs:
PK−1
j=1 αjPj
λW = PK (20)
j=1 αjPj

11 Exercise 8.6
In a kitchen dormitory corridor there are two hobs for cooking and 3 places
on the sofa. There are 8 students living in the corridor, each of them goes on
average every 1/α hours to the kitchen to cook (if he is not cooking already),
the inter-arrival time is exponentially distributed. If on arrival the 2 hobs are
occupied, the student looks for a place on the sofa. If the sofa is occupied as well,
the student goes back to his room and tries again at a later time. Students spend
an exponentially distributed amount of time cooking with mean 1/β. α = 0.5
hours, β = 1 hours.
1. Draw the state transition diagram
2. Calculate the mean waiting time of the students
3. Calculate the ratio of time the kitchen is completely full, e.g. a student
arriving has to go back to his room.
4. Calculate the probability that a student finds the kitchen completely full
5. Calculate the probability that a student has to wait more than 2 hours
(supposing that he can sit down in the kitchen)

Solution:

This is a complex problem that discusses all important matters in the Marko-
vian systems with finite population size. It is, perhaps, easy to choose the state
space; it could, clearly, be the number of places occupied by students at some
point in time, either in the kitchen counter (hobs) or the kitchen sofa:

State Space: Sk , k positions occupied, k = 0, 1, ..., 5. (21)

The population of the system is the number of students (8). The number of
servers is the number of hobs (2) and the number of queuing positions is the
number of places on the sofa (3). The inter-arrival times between student ar-
rivals at the kitchen is exponentially distributed and the rate depends on the
remaining number of students that are still at their rooms (not already cooking
or waiting at the sofa). The service times are the cooking times and are also
exponentially distributed. Consequently, the system is Markovian, with Kendall
notation: M/M/2/5/8. The system diagram is depicted in Fig. 16. We define:

35
 8α 7α 6α 5α 4α 3α
S0 S1 S2 S3 S4 S5

β 2β 2β 2β 2β

Figure 16: System diagram for exercise 8.6

α 1
ρ= = .
β 2
Notice that is not the offered load at the system. We draw the balance equa-
tions:
8αP0 = βP1 → P1 = 8ρP0 ,
7αP1 = 2βP2 → P2 = 27 ρP1 = 28ρ2 P0 ,
6αP2 = 2βP3 → P3 = 3ρP2 = 84ρ3 P0 , (22)
5αP3 = 2βP4 → P4 = 25 ρP3 = 210ρ4 P0 ,
4αP4 = 2βP5 → P5 = 2ρP2 = 420ρ5 P0

Applying the normalization equation:

5
X
Pk = 1, (23)
k=0

we calculate the values of the state probabilities.

Through the state probabilities we calculate, first, the percentage of time the
kitchen is completely full, simply:

Pfull = P5 . (24)

Now, since the system has finite population, the arrival rates depend on the
state, and, so the probability that a random student finds the system (kitchen)
full is NOT equal to P5 . The average student arrival rate is calculated using
the conditional expectation and taking into account the different arrival rates
in each state:
X5
λ= λk · Pk , (25)
k=0

where λk is the arrival rate at state Sk . Based on the diagram we obtain:

λ = 8αP0 + 7αP1 + 6αP2 + 5αP3 + 4αP4 + 3αP3 . (26)

The average student block rate is the average rate of students that are
blocked, i.e. find the kitchen completely full. Since they are only blocked at
state S5 we obtain:
λblock = 3αP5 . (27)

36
The ratio between the two average arrival rates gives the percentage of students
that are blocked, or, equivalently, the probability that an arbitrary student is
blocked (Pblocked ):

λblock 3P5
Pblocked = = (28)
λ 8P 0 + 7P 1 + 6P 2 + 5P3 + 4P4 + 3P3

Clearly, the effective arrival rate of the system is the total average arrival rate
minus the blocked arrival rate:

λeff = λ − λblock = 8αP0 + 7αP1 + 6αP2 + 5αP3 + 4αP4 . (29)

We can find the mean waiting time of the student with the help of LITTLE’s
formula. First, we need to compute the average number of students in the
kitchen:
X 5
N= kPk = P1 + 2P2 + 3P3 + 4P4 + 5P5 . (30)
i=0

Then, using LITTLE we can find the average SYSTEM time for a student:

N
E[Tsystem ] = . (31)
λeff
Then the average waiting time will be equal to the average system time minus
the average service (cooking) time:
1
W = E[Tsystem ] − . (32)
β
There is another way to do this; that of considering the arrivals at
each state and the waiting time a student experiences given the state
of arrival. Here, we must reject the blocked arrivals cause they have
no waiting time.

The last question is a bit challenging. We are asked to consider ONLY those
students that are not rejected. So we must consider students that arrive at
states Sk , k = 0, ...4. Generally, we use the total probability theorem, and
obtain:
4
X
Pr{W > 2h} = Pr{W > 2h|Student sees state Sk }·Pr{Student sees state Sk }
k=0
(33)
1. If the student observes state S0 or S1 there is not waiting time. (Cooks
immediately)
2. If the student observes state S2 the student waits for an exponential
amount of time with parameter 2β.
3. If the student observes state S3 the student waits for a sum of two expo-
nential amounts of time, each with parameter 2β.

37
 4. If the student observes state S4 the student waits for a sum of three
exponential amounts of time, each with parameter 2β.

One option is to realize that the sum of exponential variables is an Erlang-

distributed variable, and use the Erlang distribution formulas to calculate the
Pr{W > 2h|.....}.

There is however, a better option. We can realize that the times between de-
partures are exponentially distributed variables with rate 2β, considering fully
loaded kitchen counter. So, the number of departures within some time interval
will be a Poisson random variable! This is the duality between the exponential
and the Poisson distributions!

So, for example, if the student observes S4 he will want for more than T =2h, if
less than 3 departures occur during these two hours, and the number of these
departures is Poisson (2β · T ):
 
)0 )1 )2
Pr{W > T |Student sees state S4 } = (2βT 0! + (2βT
1! + (2βT
2! e−2βT
 0 1

Pr{W > T |Student sees state S3 } = (2βT )
+ (2βT ) e−2βT (34)
 0! 0  1!
(2βT ) −2βT
Pr{W > T |Student sees state S2 } = 0! + e

The last thing to calculate the probabilities that a random student observes
a particular state. Using the same reasoning as in the calculation of the blocked
students, we get:
6αP2
Pr{Student sees state S2 } = λeff
5αP3
Pr{Student sees state S2 } = λeff (35)
4αP4
Pr{Student sees state S2 } = λeff

Notice that we used λeff because we exclude those students that arrive at state
S5 and are blocked (because they have no waiting time).

38