Transcript Discrete Event Simulation

A Quick Introduction to Queuing Theory.
The material here is taken from:
1) A. M. Law & W. D. Kelton, Simulation, Modeling and Analysis,
Third Edition, McGraw-Hill, 2000.
2) H. Kobayashi, Modeling and Analysis, Addison-Wesley, 1978.
3) M. Schwartz, Broadband Integrated Networks, Prentice-Hall,
1996.
4) R. W. Wolff, Stochastic Modeling and the Theory of Queues,
Prentice-Hall, 1989.
5) W. Feller, An Introduction to Probability Theory and its
Applications, Second Edition, Wiley, 1957.
7/21/2015
1
A Quick Introduction to Queuing Theory.
Examples of Queuing Systems.
System
Bank
Hospital
Servers
Tellers
Doctors, nurses,
beds
Computer System CPU, I/O devices
Manufacturing
Machines, workers
System
Runways, gates,
Airport
security check-in
stations
Communications
Nodes, links
network
7/21/2015
Customers
Customers
Patients
Jobs
Parts
Airplanes,
travelers
Messages,
packets
2
A Quick Introduction to Queuing Theory.
Components of a Queuing System.
1) Arrival Process. This specifies how customers arrive to the
system. We use Ai to denote the time interval between the
arrival of the (i - 1)st and i th customer - the inter-arrival time.
We will generally assume that the successive times A1, A2, …, An,
… are Independent Identically Distributed random variables.
Their mean - or expected - inter-arrival time will be denoted by
E(A), and we shall call l = 1/E(A) the arrival rate of the
customers. Please note the physical units: if Ai is in, say,
seconds, then l is in reciprocal seconds.
Notice that giving an arrival rate is not sufficient - we will
always need to give a probability distribution, for which the
arrival rate will provide the mean - or the reciprocal of the
mean. Unless specified, though, we usually mean an
exponential distribution with given mean...
7/21/2015
3
A Quick Introduction to Queuing Theory.
2) Service Mechanism.
This is specified by the number of servers, usually denoted by
the variable s, and the probability distribution of the service
times. In particular, is S1, S2, …, Sn, … are IID random variables
giving the service times of a sequence of customers, the mean
service time of a customer will be denoted by E(S), and w = 1/E(S)
will stand for the service rate of a server.
3) Queue Discipline.
This is the rule by which we choose the next customer to be
served. Common ones are
FIFO: First In First Out (a standard queue)
LIFO: Last In First Out (a stack)
Priority: some way is defined to determine the priority of a
customer (a priority queue)
7/21/2015
4
A Quick Introduction to Queuing Theory.
Notation for Queuing Systems.
A notational system originally introduced by D. G. Kendall has
become standard.
1. s servers in parallel and one
1
2
n
FIFO queue feeding servers.
2. A1, A2, … are IID random
variables.
3. S1, S2, … are IID random
variables.
4. The Ai's and Si's are
independent.
Such a system is denoted by GI/G/s, for a General Independent
distribution of the Ai's, a General distribution of the Si's and the
presence of s servers.
7/21/2015
5
A Quick Introduction to Queuing Theory.
• A system with one server, exponential arrivals and exponential
service is denoted by M/M/1; M is used for Markovian, or
memory-less.
• Ek is used for k-Erlang, obtained as a sum of k exponential
random variables.
• D is used to denote deterministic (or constant) arrivals or
service.
• r = l/(sw is called the utilization factor, and is a measure of
how heavily the resources of the queuing systems are used.
Note that, under normal circumstances, r ≤ 1. w is the service
rate of a single server, and there are s servers.
7/21/2015
6
A Quick Introduction to Queuing Theory.
Measures of Performance for Queuing Systems.
Given a queuing system, what are "relevant" elements to
measure? Let:
1) Di = delay in queue of ith customer;
2) Wi = Di + Si = waiting time in system of ith customer;
3) Q(t) = number of customers in queue at time t;
4) L(t) = number of customers in system at time t = number of
customers in queue + number of customers being served.
a) Steady-State Average Delay:
n
D
i
d  lim i 1 , w.p. 1
n
n
where w.p. stands for with probability and means that the limit
holds for almost all sequences D1, D2, ...
7/21/2015
7
A Quick Introduction to Queuing Theory.
b) Steady-State Average Waiting Time:
n
W
i
w  lim i 1 , w.p.1
n 
n
c) Steady-State Time-Average Number in Queue:
T
Q  lim
 Qt dt
0
T
T
, w.p.1
c) Steady-State Time-Average Number in System:
T
 Lt dt
L  lim 0
T
T
, w.p.1
• Note that in all cases r < 1 is a necessary condition for the
limits to exist (the average number of arrivals must be less than
the average number of possible departures).
7/21/2015
8
A Quick Introduction to Queuing Theory.
Two conservation equations, valid for any queuing systems
for which the limits d and w exist are:
Q = l d and
L = l w (Little's law, or Little's formula)
A proof can be found in [Wolff, p. 286], and a simpler
presentation in [Kobayashi, p. 118].
In words: the time-average number in queue is given by the
product of the mean arrival rate and the average delay. The
time-average number in system is given by the product of the
mean arrival rate and the average waiting time.
Since time in queue and waiting time are related, we can also
obtain a formula relating them (their averages): w = d + E(S).
7/21/2015
9
A Quick Introduction to Queuing Theory.
The number of arrival and service distributions for which
analytical results can be obtained is rather small - exponential
distributions (and their Erlang variants) are good candidates and, usually, at least one of them must be exponential for an
analytical attack to be successful.
We now look at the simplest case, the M/M/1 queue.
Another term often used to describe an arrival process with
exponentially distributed inter-arrival times is "Poisson Process".
This refers to arrivals (for inter-arrival times) or to service times
(for servers).
7/21/2015
10
A Quick Introduction to Queuing Theory.
Poisson Processes. There are a number of different (but
equivalent) definitions of a Poisson process. We will introduce
one and derive a number of properties. You should be aware that
there are multiple way of deriving the properties.
Definition: a function f(x) is a member of the o(h) class, denoted
by f o(h) if lim f h   0 .
h0
h
Let Pn(t) denote the probability that exactly n arrivals will occur
in a time interval of length t ≥ 0. Let l be a positive number. We
introduce two postulates:
a) The probability that an arrival occurs during (t, t + h) is lh +
o(h).
b) The probability that more than one arrival occurs during (t, t +
h) is o(h).
7/21/2015
11
A Quick Introduction to Queuing Theory.
The next step is the derivation of a system of differential
equations for Pn(t), n = 0, 1, 2, …. Examine the interval (0, t + h) = (0,
t) U [t, t + h). Pn(t + h), n ≥ 1, can be computed as:
a) the probability of n arrivals during (0, t) and no arrivals during
[t, t + h);
b) the probability of n - 1 arrivals during (0, t) and one arrival
during [t, t + h);
c) the probability of x ≥ 2 arrivals during [t, t + h) and n - x arrivals
during (0, t).
These are three mutually exclusive and exhaustive possibilities
(they cover all cases). They give:
Pn(t + h)= Pn(t)(1 - lh - o(h)) + Pn-1(t) lh + o(h)
= Pn(t)(1 - lh) + Pn-1(t) lh + o(h)
Rearranging and dividing by h gives:
7/21/2015
12
A Quick Introduction to Queuing Theory.
Pn t  h  Pnt 
oh
  lPnt   lPn1t  
,
h
h
n1, t 0
Taking the limit as h -> 0+, gives the (infinite) system of
differential equations (actually claim the two-sided limit is
justified):
Pn' t    lPnt   lPn 1t , n  1, t 0.
Applying similar reasoning to the case n = 0, we have
P0' t    lP0t ,
fort  0.
A moment of thought allows us to conclude that P0(0) = 1 (there
have been no arrivals at all), so the last equation comes to us
complete with initial condition. Its unique solution is P0(t) =e-lt.
We can also observe that Pn(0) = 0 for all n ≥ 1. Using the just
computed expression for P0(t) , we obtain:
P1'(t) = -lP1(t) + l e-lt, P1(0) = 0.
7/21/2015
13
A Quick Introduction to Queuing Theory.
This is a non-homogeneous equation and its solution involves a
trick: first fine the general solution of the corresponding
homogeneous equation:
P1'(t) = -lP1(t)
-> P1(t) = C1 e-lt.
Replace the constant by a function of t: z(t)e-lt, and attempt to
determine z(t) by simply inserting into the original equation and
seeing what happens:
z'(t) e-lt - l z(t) e-lt = - l z(t) e-lt + l e-lt
z'(t) = l -> z(t) = C1 + lt
P1(t) = (C1 + lt) e-lt, P1(0) = 0.
Finally:
P1(t) = lt e-lt.
We can repeat the construction for P2(t), P3(t), … etc., and a final
induction proof lets us conclude that:
7/21/2015
14
A Quick Introduction to Queuing Theory.
Pn t  
lt 
n
n!
e lt
the probability of exactly n arrivals during (0, t). It is easy to
n
verify that

 l t 
 lt

n0
Pn t    n0
n!
1
e
From this, we can also compute the probabilities of at least N
arrivals, or at most N arrivals, etc. Something we have not
quite addressed, yet, is the meaning of l. It seems to be an
expected arrival rate, but we need to show it.
Let E(n, t) denote the expected number of arrivals during (0, t).
From standard probability theory - and some elementary
algebra - we have:
En,t   n 0 n  Pn t    n 0 n


lt 
n
n!
e  lt  lt
so that l is the expected number of arrivals in unit time, or the
arrival rate. What is the relationship between l and interarrival times?
7/21/2015
15
A Quick Introduction to Queuing Theory.
Let L(t) denote the number of arrivals during (0, t). The
probability that the first arrival time, t1, satisfy t1 > t is given by
P(t1 > t) = P(L(t + 0) - L(0) = 0)= P0(t) = e-lt.
If we assume that the number of arrivals over an interval
depends only on the length of the interval, and not on when the
interval occurs, we also have (t2 is the interval between first and
second arrival):
P(t2 > t| t1 = x) = P(L(t + x) - L(x) = 0) = P0((t +x) - x) = P0(t)= e-lt,


and P t i 1  t | i t j  x  P L t  x   L x   0  P0 t   e  lt
j 1
We conclude that the probability that any inter-arrival time t is
greater than t is given by G(t) = P(t > t) = P0(t) = e-lt. Inter-arrival
times are thus IID random variables with cumulative
probability distribution function F(t) = 1 - G(t) = 1 - e-lt, and
probability density function f(t) = l e-lt:
t
Ft    le
0
7/21/2015
lt
dt  e
lt
t
0
1  e l t
16
A Quick Introduction to Queuing Theory.
The expected inter-arrival time is thus given by


0
0
Et    t f t dt   t l e

 0 e
0
 lt
 lt
dt   t e
 lt
1
 lt 
l
0
dt   e


0

  e  lt dt
0
1
l
Another interesting question - useful to help us choose
theoretical distributions matching empirical data sets - is that of
the position of the median relative to the mean.
Let t be the random variable representing inter-arrival time.
1
l
1

 1
Pt
F
 1 e l  1 e 1  0.632121;

 l
l
1

1
1
Pt    1  F    e  0.367879.
l
l
A way of interpreting this result is that, for an exponential
distribution, the median is less than the mean.
7/21/2015
17
A Quick Introduction to Queuing Theory.
We can now ask the question: what is the probability pn(t) that
an M/M/1 system with mean arrival rate l and mean service rate
m will have n customers in the system at time t? Can we obtain a
steady-state probability, i.e., does lim pnt exist? We can easily
t 
see
pn t  t   pn t 1  m t 1  l t   m t l t  ot 
 pn 1 t m t 1 l t  ot 
 pn 1 t l t1  m t  ot , n  1.
For n = 0, the first term on the right hand must reflect a
probability 0 for a departure, and the third term must be
absent. Assuming smoothness in t for pn(t), we can use the
approximation pn(t + t) = pn(t) + pn'(t)t. Replacing into the
equation above, and letting t -> 0, we have
p'n t   l  mpn t   m pn1t   l pn 1t 
7/21/2015
18
A Quick Introduction to Queuing Theory.
A necessary condition for a steady-state solution is that pn'(t)
vanish identically, leaving us with a time-independent system of
infinitely many equations:
l p0 = m p1;
(l + m) pn = m pn+1 + l pn-1, for n ≥ 1.
We recall that r  l/m is what we called utilization. We can now
proceed with, essentially, and induction:
p1 = r p0;
p2 = (r + 1)p1 - rp0 = r2p0;
….
pn = rnp0, for all n ≥ 0.
Since   pn  r n p0  1 , we must have r < 1. Summing the
n0
0
geometric series: p0 = (1 - r), pn = (1 - r) rn. From r = 1 - p0, we can
conclude that r is the probability the system is not empty.
7/21/2015
19
A Quick Introduction to Queuing Theory.
The expected number of customers in the system is given by
En   0 n pn  0 n 1 r r n 


r
1r
An easy derivation of the closed form of the sum follows from
observing that
1
d  1 
d


1 
n
n1
n


r

n
r

n
r
2

n 0

r n 0
1  r dr  1  r  dr n 0

7/21/2015

20
A Quick Introduction to Queuing Theory.
Note that with a utilization of r = 0.5, the expected number of
customers in the system is 1.
One can also show that, for a general service distribution with
exponential arrivals, the steady-state average delay in queue is
given by the formula
2
l Var S  E S
d

21 l E  S

where S is the service distribution, and Var(S) is the variance of
the service distribution.
We can go a little further in this direction by computing variance
of the number of customers in the system, and the variance of
an exponential distribution with mean 1/l. - the service
distributions we have considered up to this point are all
exponential anyway (although they don't have to be: for ATM
53Byte packets, the service distribution is uniform).
7/21/2015
21
A Quick Introduction to Queuing Theory.
Variance of the number of customers in the system.
r2
  En  En   n 0 n pn  E n   1 rn 0 n r 
2
1
r


2

2
2

2
2
2
n
We use the same differentiation trick as before, but now
differentiate twice:
2
d 2  1  d 2

3 
2
1  r dr  1 r  dr 2
1


1
 2  n0 n r  2 n 0 n r  2  n0 n r 
2
r
r
r
r1  r 

2
n
1

n
n 2
r

n

n

1

r
n 0
n 0


1
n

2
n
where we used the result obtained two slides ago. Some simple
algebra gives:
r1  r

2 n

finally leading to:
7/21/2015
n0
n r 
2 
1  r 
3
r
2
1  r
22
A Quick Introduction to Queuing Theory.
Variance of an exponential distribution with mean 1/l.
Recall that the exponential distribution with mean 1/l has
probability density function f(t) = le-lt. To compute the variance:
Vart   Et 2  Et 2   t 2 le lt

0
1
dt 
 l
2

1
1
 lt
lt
2t e dt 
  2t e dt 
 l
0
l 
2

1  lt 
1 lt
2   lt
1
 1
 2t e |0  0 2 e dt     0 e dt   
l
l
l
l
l
2
 t 2 e  lt |0  


0
2
2
2 lt   1  2  1  2
  2 e |0 



 l
l
l
The variance is the square of the mean: another point to
help us decide whether an empirical distribution is exponential
or not.
7/21/2015
23
A Quick Introduction to Queuing Theory.
Expected value and variance of the number of customers
in queue.
We observe that when the number of customers in the system is
0, we will have 0 customers in the queue, when the number of
customers in the system is 1, the number of customers in queue
is still 0, while when the number of customers in the system is n
> 1, the number of customers in queue is n - 1. This observation
leads to the formula for the expected number of customers in
queue:

EnQ  n 1n  1pn
where pn = (1 - r)rn, the probability of having n customers in the
system. Making use of the summation formulae just derived, we
can compute
r2
EnQ 
1 r
 r En
as well as E(n) = E(nQ) + r.: the expected number of customers in
system is exactly r (the utilization) larger than the expected
number in queue.
7/21/2015
24
A Quick Introduction to Queuing Theory.
We can compute variance:
2
2
r
1
r

r


 Q2  n1n 1 pn  En 
2
1 r

2
2
making use of the summation formulae previously derived.
Mean Waiting and Mean Delay Time.
In some texts you will find "waiting time" to be defined as
"response time" and "delay time" as "waiting time" (the
rationale being that the delay time is the time you are waiting in
queue - which is actual waiting - while the total time you spent
is the time it takes the system to respond to your request,
fulfilling it). Using our definitions, we have the relation:
Wi = Di + Si
Let W denote the mean waiting time, let D denote the mean
delay time, let L denote the mean number of customers in
system, and let Q denote the mean number of customers in
queue.
7/21/2015
25
A Quick Introduction to Queuing Theory.
If 1/l is the mean interarrival interval, and 1/m is the mean
service time, we have, by definition, r  l/m. Little's Law (see
slide 9) gives:
D
Q
l
L

r2
l1  r

r
m1 r
r
1
W 

l l1  r m1 r
What would this be good for? In the various simulations, you
computed time-averaged delays and time-averaged waiting
times. This provides you with a theoretical check: if your results
don't match (within some statistical confidence level) the
theoretically predicted ones, you are in some kind of trouble…
They also allow you to avoid - in some simple cases - going
through the whole simulation process: a "back-of-the-napkin"
computation can give you the results.
7/21/2015
26