Queuing Theory Exercises.
E3
Course coordinator: Armin Halilovic
Exercises 3
M/M/1 Queueing System is a single-server queueing system with Poisson input,
exponential service times and unlimited number of waiting positions.
Thus, an M/M/1 system has the following characteristics:
1. There is a single server with exponential service times and the service rate customers
per time unit
2. Customers arriving according a Poisson process with the arrival rate customers per
time unit
3. Number of waiting positions =
M/M/1 Queueing System
Arriving
customers
Queue
Single Server
Arrival rate =
Service rate =
Unlimited number of waiting positions
Figure 1.
------------------------------------------------------------------------
Figure 2. Rate transition diagram for an M/M/1 Queueing System,
------------------------------------------------------------------------
Notation
Description
Departing
customers
Queuing Theory Exercises. E3
Course coordinator: Armin Halilovic
Average number of customers in the system , N = N q + N s
Nq
Average number of customers in the queue
Ns
~
x
Average number of customers in the service facilities
x
~
w
W
~
s
eff
Random variable which describes time spent in the service
facility by a customer
Average service time for a customer, x = E (x~ )
Random variable which describes time spent in the waiting
queue by a customer
Average waiting time spent in the queue by a customer
~)
W = E (w
Random variable which describes time spent in the system
~
s =~
x +w
by a customer; ~
Average time spent in the system by a customer T = E (s~ ) ,
T =W + x
Arrival rate
The effective arrival rate
Service rate
, offered load (offered traffic)
Stationary probabilities; p k is the probability that there are k
customers in the system
Some formulas for M/M/1 Queueing System
N = Nq + Ns
T =W + x
1
x=
pk
pk = p0 k
p0 = 1
N=
T=
F~s (t ) = P (~
s t ) = 1 e ( )t
Littles formulas:
N = eff T
(For an M/M/1 system eff = , since there are no blocked customers)
N q = eff W
N s = eff x
Queuing Theory Exercises. E3
Course coordinator: Armin Halilovic
1. Consider an M/M/1 system in which customers arrive according to a Poisson process of
rate . Service rate is = 20 customers /minute.
The average number of customers is N =3.
Calculate and W.
Answer:
= 15 , W=0.15 minutes (=9 sec)
2. Consider an M/M/1 queueing system with arrival rate and service rate .
a) Derive the formula for the average number of customers in the system
N=
1
b) Calculate the average total time T if the service rate is = 50 customers /minute and
the average number of customers is N =4.
Solution:
a)
M/M/1 system , rate transition diagram
From the rate transition diagram we have
p k = p0 k ,
p0 = 1
The average number of the customers in the system can be calculated using the formula for
the expectation of a discrete random variable:
N = kp k = kp0 k = p 0 k k 1 (*)
If we differentiate with respect to the formula for the sum of a geometric series
1
0 k = 1
we obtain
1
0 k k 1 = (1 ) 2 (**)
d 1 d
(1 )1 = (chain rule) = (1 )2 ( 1) = (1 )2 = 1 2 ]
[Remark:
=
d 1 d
(1 )
We substitute (**) in (*) and get
which proves the formula.
N = p 0 k k 1 = (1 )
=
2
1
(1 )
0
Queuing Theory Exercises. E3
Course coordinator: Armin Halilovic
b) N =
Now =
4=
4
5
4
=
= 40 .
5 50
From the Littles formula
N = eff T , since eff = , we obtain
1
min = 6 sec
10
3. An M/M/1 system has the service rate = 10 customers per minute. Average time in the
system for one customer is T =3 minutes.
1
a) derive the formula T =
( You can start with N =
)
1
b) Evaluate , N and x .
4 = 40 T T =
Answer: b) = 9.6666 , N =29,
x =0.1 minutes.
4. A communication channel is operating at a transmission rate of 1000 000 bps.
To the channel arrive packets according to a Poisson process with rate =100
packets per second. The packets have an exponentially distributed length with a
mean of
v= 5 000 bits.
We assume that the channel can be modeled as an M/M/1 system with queueing
discipline FCFS (First- Come- First- Served).
Calculate
a)
b) c ) x c) N d) T e) W f) N q
Answer:
a) =200
b) =1/2 c ) x =1/200 s c) N =1
d) T =1/100 s e) W =1/200 f) N q =1/2
5. Data packets arrive to a communication node according to a Poisson process
with an average rate of =2400 packets per minute. The packets have
exponentially distributed lengths with a mean of v= 1000 bits. A single outgoing
communication link is operating at a transmission rate of K bits/second.
We assume that the link has a very large buffer so that it can be modeled as an
M/M/1 system with queueing discipline FCFS (First- Come- First- Served).
a) Evaluate K if the average system time is T= 1 s.
For that value of K determine:
b)
c) N d) x e) W
Answer: a) K= 41 000 bits per second. b) = 41 packets per second c) N
= 40
1
40
d) x = s
e) W =
s
41
41
6. Jobs (customers) arriving at an M/M/1 system according to a Poisson
process with an average rate of 8 jobs per second. The Service rate is =10
jobs per second.
Queuing Theory Exercises. E3
Course coordinator: Armin Halilovic
Find
a) The offered load
b) The probability that the system is idle (no customers in the system)
c) The probability that there are exact 2 customers in the system.
d) Average number of customers in the system
e) Average number of customers in the queue
Answer:
a) = 0.8 b) p 0 = 0.2 , c) p 2 = 0.128 d) N=4 e) N q = 3.2
7. Consider an M/M/1 system in which customers arrive according to a Poisson process of
rate . Service rate is = 10 customers /second
The average system time is T =0.2 s .
a) Calculate
b) Find T if we replace server with a faster one, which has a service rate of
= 40 customers /second (but the arrival rate remains the same, customers /second )
Answer:
a) = 5 customers /second,
b) T =1/35s
