Introduction

to Queueing
Theory

Motivation

First developed to analyze

statistical behavior of phone
switches.

Queueing Systems

model processes in which

customers arrive.
wait their turn for service.
 are serviced and then leave.

Page 1
Examples

supermarket checkouts
stands.
 world series ticket booths.
 doctors waiting rooms etc..

Five components of a
Queueing system:
1. Interarrival-time probability
density function (pdf)
2. service-time pdf
3. Number of servers
4. queueing discipline
5. size of queue.

ASSUME

an infinite number of

customers (i.e. long queue
does not reduce customer
number).

Page 2
Assumption is bad in :

a time-sharing model.
with finite number of
customers.
if half wait for response,
input rate will be reduced.

Interarrival-time pdf

record elapsed time since

previous arrival.
list the histogram of inter-
arrival times (i.e. 10 0.1 sec,
20 0.2 sec ...).
This is a pdf character.

Service time

how long in the server?

i.e. one customer has a
shopping cart full the other
a box of cookies.
Need a PDF to analyze this.

Page 3
Number of servers

banks have multiserver

queueing systems.
food stores have a collection
of independent single-server
queues.

Queueing discipline

order of customer process-

ing.
 i.e. supermarkets are first-
come-first served.
Hospital emergency rooms
use sickest first.

Finite Length Queues

Some queues have

finite length: when full
customers are rejected.

Page 4
 ASSUME

infinite-buffer.
single-server system with
first-come.
 first-served queues.

Kendall’s notation
 Simple queuing systems are conventionally labelled by
A / B / m / / K / W
 A and B denote the interarrival and service time
distribution
– most important abbreviations are D for deterministic, M for
exponential and G for general (i.e. unspecified) distribution
 m is the number of servers
 is the system capacity (max. # customers in service and
queue)
 K is the total population
 W is the queuing discipline (e.g. FIFO,LIFO,Priority
based)
 and W are optional with default values   
and W = FIFO

Kendall’s notation
(continued)

 Example: an M/M/m queue is a simple

queuing system with exponential
interarrival and service times, m servers,
unlimited system capacity, and FIFO
queuing discipline.
 Tacit assumption when Kendall’s
notation is used:
– interarrival times are independent and identically
distributed (i.i.d.)
– service times are i.i.d.
– interarrival and service times are independent

Page 5
 Arrival and service rates

 The arrival rate is the expected number of

arrivals per unit time (e.g. per hour)
 The service rate  is the expected number of
customers that can be served by one of the
servers per unit time
 The expected service time per customer is 1/ 
 The expected time between two arrivals is 1/
 Arrival rate and service rate often depend on the
time of the day, week, year,etc. (seasonal rates)

The utilization factor

 Suppose a G/G/m queue
– arrival rate 
– service rate,
 The utilization factor (or traffic intensity)is
defined by

 Interpretation:  is the fraction of time we expect
the service facility to be busy (i.e. at least one of
the servers to be busy)
 If then the queue “explodes”
 What if 

A/B/m notation

A=interarrival-time pdf
B=service-time
pdf
m=number of servers.

Page 6
A,B are chosen from the set:

M=exponential pdf (M stands

for Markov)
D= all customers have the same
value (D is for deterministic)
G=general (i.e. arbitrary pdf)

Analysibility

M/M/1 is known.
G/G/m is not.

M/M/1 system

For M/M/1 the probability

of exactly n customers
arriving during an interval
of length t is given by the
Poisson law.

Page 7
Poisson’s Law

(  t) n   t
Pn (t )  e (1)
n!

Poisson’s Law in
Physics
radio active decay
–P[k alpha particles in t
seconds]
– = avg # of prtcls per
second

Poisson’s Law in
Operations Research
planning switchboard
sizes
–P[k calls in t seconds]
– =avg number of calls
per sec

Page 8
Poisson’s Law in
Biology
waterpollution
monitoring
–P[k coliform bacteria in
1000 CCs]
– =avg # of coliform
bacteria per cc

Poisson’s Law in
Transportation
planningsize of
highway tolls
–P[k autos in t minutes]
–  =avg# of autos per
minute

Poisson’s Law in
Optics
indesigning an
optical recvr
–P[k photons per sec over
the surface of area A]
– =avg# of photons per
second per unit area

Page 9
Poisson’s Law in
Communications
 in designing a fiber
optic xmit-rcvr link
–P[k photoelectrons
generated at the rcvr in
one second]
–=avg # of photoelectrons
per sec.

 - Rate parameter
 =event per unit interval
(time distance volume...)

Analysis

Depend on the condition:

  interarrival rate  10 cust. per min
n  the number of customers = 100
we should get 100 custs in
10 minutes (max prob).

Page 10
To obtain numbers
with a Poisson pdf,
you can write a
program:

Acceptance
Rejection Method

Prove:
Poisson arrivals gene-
rate an exponential
interarrival pdf.

The M/M/1 queue in

equilibrium

queue

server

Page 11
State of the system:

There are 4 people in the

system.
3 in the queue.
1 in the server.

Memory of M/M/1:

The amount of time the person

in the server has already spent
being served is independent of
the probability of the
remaining service time.

Memoryless

M/M/1 queues are memoryless

(a popular item with queueing
theorists, and a feature unique
to exponential pdfs).
.
P k  equilibrium prob
that there are k in system

Page 12
Birth-death system

In a birth-death system once

serviced a customer moves
to the next state.
This is like a
nondeterminis-tic finite-
state machine.

State-transition Diagram

 The following state-transition

diagram is called a Markov
chain model.
Directed branches represent
transitions between the states.
Exponential pdf parameters
appear on the branch label.

Single-server queueing
system

Po  P1  P k -1 P k
0 1 2 ... k-1 k k+1

 P1 P 2 P k  P k +1

Page 13
 Symbles:

  mean arrival rate (cust. /sec)

 P0 mean number of transitions/ sec
from state 0 to 1
  mean service rate (cust./ sec)
 P1  mean number of transitions/ sec
from state 1 to 0

States

State 0 = system empty

State 1 = cust. in server
State 2 = cust in server, 1
cust in queue etc...

Probalility of Given State

Prob. of a given state is

invariant if system is in
equilibrium.
The prob. of k cust’s in system
is constant.

Page 14
Similar to AC

This is like AC current entering

a node
is called detailed balancing
the number leaving a node
must equal the number
entering

Derivation

3 P0  P1
P
3a P 1  0

4  P1   P 2

 P1
4a P 2 


by 3a

P0

 2 P 0
4 P2  = P2 
 2
since

5 P k  P k+1

Page 15
then:

k P0
6 P k  k   k P0



where  = traffic intensity < 1


since all prob. sum to one

 
  k P0  1  P0  1
k
6a
k0 k0

Note: the sum of a geometric series is


1
7 k 
1 
k0


1
 
k

k0 1 

 Suppose that it is right, cross

multiply and simplify:
 
 k   k 1
k0 k0

 
So  k   k   1
0

k0 k 1

Q.E.D.

Page 16
subst 7 into 6a

6a P0 
k
1
k 0

P0
7a 1 and
1 
7b P0 1
=prob server is empty

subst into

k P0
6 Pk    k P0
k
yields:

8 P k  (1   )  k

Mean value:

letN=mean number of cust’s in

the system
To compute the average (mean)
value use:

8a E[k ]   kP k
k 0

Page 17
Subst (8) into (8a)

8 Pk  (1)k

8a E[ k ]   kP k
k 0

we obtain
 
8b E[k]   k(1  ) k  (1 ) k k
k 0 k 0

differentiate (7) wrt k


1
7  k 
1 
k0

we get
 
1 1
8c Dk  k  Dk  k k1 
1  k 0 (1 )2
k 0

multiply both sides of

(8c) by 


8d  k k 
(1   ) 2
k0

 
9 E[k]N(1) 
(1)2 (1)

Page 18
Relationship of , N

80

60

40

20
rho
0 0.2 0.4 0.6 0.8 1
0

as r approaches 1, N grows quickly.

T and 

T=mean interval between cust.

arrival and departure, including
service.
  mean arrival rate (cust. /sec)

Little’s result:

In 1961 D.C. Little gave us

Little’s result:

N /  1/  1
10 T   
 1 1 

Page 19
 For example:
A public bird bath has a
mean arrival rate of 3
birds/min in Poisson
distribution.
Bath-time is exponentially
distributed, the mean bath
time being 10 sec/bird.

Compute how long a bird

waits in the Queue (on
average):

  0. 05 cust / sec = 3 birds / min * 1 min / 60 sec

= mean arrival rate

1 bird
 = 0.1 bird/ sec =
10 sec
= mean service rate

Result:

So the mean service-time is 10

seconds/bird =(1/ service rate)
1 1
T  20 sec
  0.10.05
for wait + service

Page 20
 Mean Queueing Time

The mean queueing time is the

waiting time in the system
minus the time being served,
20-10=10 seconds.

M/G/1 Queueing System

Tannenbaum says that the
mean number of customers in
the system for an M/G/1
queueing system is:
2 1 Cb2
11 N  
2(1 )
This is known as the
Pollaczek-Khinchine equation.

What is Cb

standard deviati
Cb 
mean

of the service time.

Page 21
 Note:

M/G/1 means that it is valid for

any service-time distribution.
For identical service time
means, the large standard
deviation will give a longer
service time.

Introduction
to Queueing
Theory

Page 22