Transcript Continuous Time Markov Chains

Queuing Theory
Basic properties, Markovian models, Networks of
queues, General service time distributions, Finite
source models, Multiserver queues
Chapter 8
1
Kendall’s Notation for Queuing Systems
A/B/X/Y/Z:
A = interarrival time distribution
B = service time distribution
G = general (i.e., not specified); M = Markovian
(exponential); D = deterministic
X = number of parallel service channels
Y = limit on system pop. (in queue + in service); default is 
Z = queue discipline; default is FCFS (first come first served)
Others are LCFS, random, priority
Chapter 8
2
Other Notation
Random variables:
X(t) = Number of customers in the system at time t
S = Service time of an arbitrary customer
W* = Amount of time an arbitrary customer spends in the system
WQ* = Amount of time an arbitrary customer spends waiting for service
Often we are most interested in the averages or expectations:
L  E  X  t  
LQ  Average number in the queue
LS  Average number in service
Chapter 8
W  E W *
WQ  E WQ *
3
Little’s Formula
wn * is the time spent in the system by the nth customer.
Assume these
k
system times are uniformly finite and let w  limk  1k n1 wn *
be the customer average time spent in the system.
s
1
Also, let X  lims s  X (t )dt
0
be the time average number of jobs in the system.
Then under very general conditions, X  la w
where la is the arrival rate. This is usually written L = laW.
The mean number of customers in the system is proportional
to the mean time in the system!
Chapter 8
4
Heuristic Proof of Little’s Formula
A(t)
B(t) = cum. area
between curves
D(t)
T
T
N
Two ways to compute B(T )   n1 wn *   X (t )dt
0
Mean time in system in (0,T): W (T )  B(T ) N  B(T ) A(T )
Mean number in system in (0,T): X (T )  B(T ) T
X (T )  lim
Then Tlim

T 
B(T ) A(T )
 lim l T W (T ), or L  laW
T 
A(T ) T
Chapter 8
5
Other Little’s Formulae
In queue: LQ  laWQ
In service: LS  la E  S 
and their implications…
Expected number of busy servers LS  la E  S   
Expected number of idle servers
# servers  
Single server utilization
LS  la E  S   
Single server prob. of empty system
1 
Chapter 8
6
Observation Times
Pn  limt  P  X (t )  n , n  0,1,...
an = Proportion of arriving customers that find n in the system
dn = Proportion of departing customers that leave behind n in the
system
If customers arrive one at a time and are served one at a time then
an  d n
But these proportions may not match the limiting probability
of having n in the system (long run proportion of time that n
are in the system)
However, if arrivals follow a Poisson process then an  Pn
This is known as PASTA (Poisson Arrivals See Time Averages)
Chapter 8
7
M/M/1 Model
Single server, Poisson arrivals (rate l), exponential service
times (rate )
CTMC (birth-death) model:
Chapter 8
8
M/M/1 Steady-State Probabilities
Pn  limt  P  X (t )  n , n  0,1,...
Level-crossing equations:
l Pn   Pn1 , n  0,1,
Solve for Pn in terms of P0
Pn 
 
l

Then use the facts that
and substitute   l / 
to get
n
n
P0 , n  1, 2,
n0 Pn  1,

Pn   (1   ), n  0,1,
Chapter 8
n
1
r

(1

r
)
if r  1
 n 0

if   1
9
M/M/1 Performance Measures
Steady-state expected number of customers in the system
L   n 0 nPn 


Mean time in system
W
L
la

Mean time in queue
, if   1
1
1

by Little's Formula
 (1   )   l
WQ  W 
Mean number in queue
1 
1

=
l
   -l 
l2
LQ  lWQ =
   -l 
Chapter 8
10
M/M/1 Performance Measures
Distribution of time in system (FCFS)
P[W *  x]   n 0 an P[W *  x | arrival sees n customers]

  n 0 (1   )  n P[W *  x | W * gamma(n  1,  )]

  n 0 (1   )  n  l  n 1 e   x (  x)l l !  1  e   (1  ) x , x  0


Exponential with parameter (1-)
Reversibility: Departure process is Poisson with rate l
Chapter 8
11
Finite Capacity: M/M/1/N Model
Single server, exponential service times (rate )
Poisson arrivals (rate l) as long as there are  N in the system
CTMC (birth-death) model:
Chapter 8
12
M/M/1/N Steady-State Probabilities
Pn  limt  P  X (t )  n , n  0,1,...
Level-crossing equations:
l Pn   Pn1 , n  0,1, , N  1
Solve for Pn in terms of P0
Then use the facts that
N 1

N
1

r
n
P

1,
r
 n 0 n
 n0  1  r (note: r need not be < 1)
 l   1  l  
n
to get Pn 
1 l  
N 1
, n  0,1,
Chapter 8
,N
13
M/M/1/N Performance Measures
(In the unlikely event that l  , for n = 1,…, N, Pn  P0  1  N  1)
Steady-state expected number of customers in the system, L,
has a “messy” closed form
L
Mean time in system W 
by Little's Formula
la
but here, la is the rate of arrival into the system la  l 1  PN 
WQ  W 
1

LQ  l 1  PN WQ
Chapter 8
14
Tandem Queue
l
1
2
If arrivals to the first server follow a Poisson process and
service times are exponential, then arrivals to the second
server also follow a Poisson process and the two queues
behave as independent M/M/1 systems:
P{n customers at server 1 and m customers at server 2} =
l 
 
 1 
n
m

l  l  
l 
1

1


  





1  2  
2 
Chapter 8
15
Open Network of Queues
• k servers, customers arrive at server k from outside the
system according to a Poisson process with rate rk,
independent of the other servers
• Upon completing service at server i, customer goes to
server j with probability Pij, where  j Pij  1
k
For j = 1,…, k, the total arrival rate to server j is l j  rj   li Pij
i 1
The number of customers at each server is independent nand
  

If lj < j for all j, then P{n customers at server j}   l j  1  l j 
  
 j 
 j 
that is, each acts like an independent M/M/1 queue!
Chapter 8
16
Closed Queuing Network
• m customers move among k servers
• Upon completing service at server i, customer goes to server j
with probability Pij, where  j Pij  1
• Let p be the stationary probabilities for the Markov chain
describing the sequence of servers visited by a customer:
k
p j  p i Pij ,
i 1
k
p
j 1
j
1
Then the probability distribution of the nnumber at each server is
k p 
k
j
Pm  n1 , n2 ,..., nk   Cm    if  n j  m
 
j 1
j 1   j 
j
Chapter 8
17
CQN Performance
Computation of the normalizing constant Cm to get the
stationary distribution can be lengthy; but may be mostly
j
l

interested in the throughput m  j 1 lm  j 
where lm(j) is the arrival rate to (and departure rate from) j.
Arrival Theorem: In the CQN with m customers, the system
as seen by arrivals to server j has the same distribution as
the whole system when it contains only m-1 customers.
This leads to mean value analysis to find lm(j) along with
Wm(j) = the average time a customer spends at server j, and
Lm(j) = the average number of customers at server j.
Chapter 8
18
Mean Value Analysis
Solve iteratively:
Wm  j  
1  Lm 1  j 
j
Lm  j   lm  j Wm  j  , where lm  j   p j lm
lm 
Begin with W1  j  
m

k
i 1
p iWm  i 
throughput
1
j
Chapter 8
19
M/G/1
Best combination of tractability & usefulness
•
Assumption of Poisson arrivals may be reasonable based
on Poisson approximation to binomial distribution
–
-
•
•
many potential customers decide independently about arriving
(arrival = “success”),
each has small probability of arriving in any particular time
interval
Probability of arrival in a small interval is approximately
proportional to the length of the interval – no bulk
arrivals
Amount of time since last arrival gives no indication of
amount of time until the next arrival (exponential –
memoryless)
Chapter 8
20
M/G/1
Best combination of tractability & usefulness
• Exponential distribution is frequently a bad model for
service times
– memorylessness
– large probability of very short service times with occasional very
long service times
• May not want to use one of the “standard” distributions for
service times, either
– in a real situation, collect data on service times and fit an empirical
distribution
• Distributions of number of customers in the system and
waiting time depend on service time distribution to be
specified
Chapter 8
21
M/G/1
Best combination of tractability & usefulness
• Assumption of Poisson arrivals may be reasonable based
on Poisson approximation to binomial distribution
– many potential customers decide independently about
arriving (arrival = “success”),
- each has small probability of arriving in any particular
time interval
- Distributions of number of customers in the system and
waiting time depend on service time distribution
Chapter 8
22
M/G/1 Performance
How many customers? How much time?
S is the length of an arbitrary service time (random variable)
l is the arrival rate of customers; define  = lE[S] and
assume it is < 1.
Expected values can be found from generalizing Little’s
formula from # customers in the system to amount of work in
the system:
An arriving customer brings S time units of work:
The time average amount of work in the system (V)
= l * the customer average amount of work remaining in
the system
Chapter 8
23
Work Content
WQ* is the (random variable) waiting time in queue
Expected amount of work per customer is
S
*

E SWQ    S  x  dx 


0
 E  SWQ*  
E  S 2 
2
Work
remaining
S
Enter
Begin
service
Depart
If a customer’s service time
is independent of own wait in queue, get average work in system
2


l
E
S

*
V  l E  S  E WQ  
2
Chapter 8
24
Mean waiting time
WQ = Customer mean waiting time = average work in the system
when a customer arrives
From PASTA, WQ = V. Therefore, (Pollaczek-Khintchine formula)
WQ  l E  S WQ 
l E  S 2 
 WQ 
2
l E  S 2 
2 1  l E  S 
And the other measures of performance are:
LQ  lWQ 
l 2 E  S 2 
2 1  l E  S 
, W  WQ  E  S  , L  lW
Chapter 8
25
Priority Queues
Different types of customers may differ in importance.
• Type i customers arrive according to a Poisson process with
rate li and require service times with distribution Gi, i = 1, 2.
• Type 1 customers have (nonpreemptive) priority:
– service does not begin on a type 2 customer if there is a type 1
customer waiting.
– If a type 1 customer arrives during a type 2 service, the service is
continued to completion.
What is the average wait in queue of a type i customer, WQi
Chapter 8
26
Two customer types w/o priority
l1
l2
G  x   G1  x   G2  x 
l
l
M/G/1 model with l  l1  l2
Average work in system is
2
2
2



l  l1 l  E  S1    l2 l  E  S2 
l E  S 
V

2 1  l E  S  2 1  l   l1 l  E  S1    l2 l  E  S2  



l1 E  S12   l2 E  S2 2 
2 1  l1 E  S1   l2 E  S 2 
If the server is not allowed to be idle when the system is not
empty, this quantity is the same for the system with priority.
Chapter 8
27
Two customer types with priority
Let Vi be the average amount of type i work in the system
2

li E  Si 
i
i
V  li E  Si WQ 
2
in queue
in service
VQi
VSi
Now focus on a type 1 customer. Waiting time = amt. of type 1
work in system + amt. of type 2 work in service when this
customer arrives, so
2
2




l
E
S
l
E
S
1
1
2
2
 
 
WQ1  V 1  VS2  l1E  S1 WQ1 
2
2
Chapter 8
28
Two customer types with priority
WQ1 
l1 E  S12   l2 E  S2 2 
2 1  l1 E  S1 
if l1 E  S1   1
But a type 2 customer has to wait for everyone ahead,
plus any type 1 customers who arrive during the type 2 wait, so
WQ2  V  l1 E  S1 WQ2  WQ2 
l1 E  S12   l2 E  S2 2 
2 1  l1 E  S1   l2 E  S2  1  l1 E  S1 
if l1 E  S1   l2 E  S2   1
Chapter 8
29
M/M/k Model
k identical machines in parallel, Poisson arrivals (rate l),
exponential service times (rate )
CTMC (birth-death) model:
Chapter 8
30
M/M/k Steady-State Probabilities
Level-crossing equations:
l Pn   n  1  Pn1 , n  0,1,..., k  1
l Pn  k  Pn1 , n  k , k  1,...
Define =l/k, solve for Pn in terms of P0
(k  )

 n! P0 , n  0,1,..., k
Pn   k n
k 

 k ! P0 , n  k  1, k  2,...


P

1,
Then use the facts that n0 n
n0 r n  (1  r )1 if r  1
n
to get
 k 1 (k  )
(k  ) 
P0   n 0


n!
(1   ) k !

n
k
Chapter 8
1
if   1
 is the utilization
of each server
31
M/M/k Performance Measures
Steady-state expected number of customers in the system
 (k  ) k
L   n0 nPn  k   
 k!

  
P , if   1

2  0
 (1   )  
Mean flow time
 1   (k  ) k 
W  = 
 P0 by Little's Formula

l   k  - l  k !(1   ) 
L
1
Expected waiting time
WQ  W 
1

Expected number in the queue (k is expected number of busy servers)
LQ  lWQ  L  k 
Chapter 8
32
Erlang Loss System
M/M/k/k system: k servers and a capacity of k: an arrival who
finds all servers busy does not enter the system (is lost)
(k  )n
Pn 
P0 , n  0,1,..., k
n!
( k  )i
Pi 
i!
(k  ) n
 n0 n! , i  0,..., k
k
Above is called Erlang’s loss formula, and it holds for M/G/k/k
as well, if k   l E  S 
Chapter 8
33