Transcript Continuous Time Markov Chains

Continuous Time Markov Chains
and Basic Queueing Theory
EE384X Review 4
Winter 2004
Review: DTMC
• pij is the transition probability from i to j
over one time slot
• The time spent in a state is geometrically
distributed
– Result of the Markov (memoryless) property
• When there is a jump from state i, it goes to
state j with probability
Continuous Time Version
qij
i
j
qik
k
• qij is the transition rate from state i to state j
CTMC
• Upon entering state i, a random timer Tij»Exp(qij)
is started for each potential transition i!j
– These timers are independent of each other
– Recall that Exponential distribution is memoryless
• When the first timer expires, the MC makes the
corresponding transition
• Let Ti be the time spent in state i, and qi=ji qij,
then Ti » Exp(qi)
• When there is a transition, the probability of
jumping to state j is qij /qi
Definitions
• {X(t):t¸0} is a continuous time Markov
chain if
P{X(s+t)=j | X(u); u·s} = P{X(s+t)=j | X(s)}
• Similar to Discrete Time MCs, Continuous
Time MCs have stationary distribution p
– Exists when Markov chain is positive recurrent
and irreducible
Stationary Distribution
• Balance equations:
• Transition rates in and out of state i are equal
• Define matrix transition rate Q = (qij) with
qii= -qi , then p Q = 0, where p is a row vector
• Together with i p(i) = 1, can solve for p
Queueing Theory Notation
• A/S/s/k
– A is the arrival process, e.g., Geometric, Poisson,
Deterministic
– S is the service distribution, e.g., Geometric,
Exponential, Deterministic
– s is the number of servers, e.g., 1, N, 1
– k is the buffer size (if k is absent, then k = 1)
• E.g., Geom/M/1, M/M/1, M/D/1, M/M/1
M/M/1 Queue
0
m
3
2
1
m
l
l
l
l
m
m
• Arrivals are Poisson with rate l
– Inter-arrival times are exp(l)
• Services are exponential with rate m
• These are also transition rates for the Markov chain
• This looks very similar to Geom/Geom/1 queue,
but different
Solving M/M/1 Queue
• We have pi l = pi+1 m
• Let r = l/m, then pi = pi-1 r = p0 ri
• If r < 1, the stationary distribution exists:
pi = (1 - r) ri
• Average Queue size:
M/M/1 Queue
• NQ is the queue size, excluding the one in
service:
M/M/1 Queue
0
m
3
2
1
2m
l
l
l
l
3m
4m
• Customer arrival process is Poisson(l)
• All customers are served in parallel »exp(m)
– Departure rate proportional to # of customers
Solving M/M/1 Queue
• We have pi-1 l = pi i m
• Let r = l/m, then
• Thus
M/M/1 Queue
• The queue size distribution of the M/M/1
queue is Poisson(r)
• Therefore the average queue size is E(Q)=r
• What’s the condition for the queue to be
recurrent?