CS 547 Lecture 35: Markov Chains and Queues

1 CS 547 Lecture 35: Markov Chains and QueuesDaniel MyersIf you read older texts on queueing theory, they tend to derive their major results with Markov Chains . Inthis framework, each state of the chain corresponds to the number of customers in the queue, and statetransitions occur when new customers arrive to the queue or customers complete their service and Time Markov ChainsOur previous examples focused ondiscrete timeMarkov Chains with a finite number of states. Queueingmodels, by contrast, may have an infinite number of states (because the buffer may contain any number ofcustomers), and allow transitions incontinuous time. Our previous solution approaches relied on writingdown the transition probability matrixPand either multiplying it by itself or solving the stationary equationsto obtain the long run probability of being in each solve continuous time models, we need a new strategy that doesn t require writing down the entiretransition matrix.

2 Our new method will be to set up and solve thebalance equationsassociated with , the number of transitions into a state must be balanced by the number of transitions out of thestate in other words,what goes in must come out. If we transition into a state at some time, we musttransition back out at some time in the future (note that this includes transitions from a state back to itself,which are treated the same as any other transition in a Markov chain ).Consider a queueing model, and let 0denote the probability of being in state 0 (that is, the probability ofhaving zero customers in the queue) and 1denote the probability of being in state 1. Let the queue receivePoisson arrivals at rate and have exponentially distributed service times with rate.

3 Suppose we measure the queue for some long, statistically representative time period of lengthT. The totalamount of time spent in state 0 will be 0 Tand the total amount of time spent in state 1 will be occur at constant rate, so the expected number of times we go from having an empty queue toa queue with one customer must be 0T (the total amount of time that the queue is empty times thearrival rate). Similarly, departures from the queue occur at constant rate , so the total number of timeswe transition from having a queue with one customer to a queue with zero customers is 1T . The balancecondition requires that these two values must be equal. 0T = 1T Dividing each side by thge length of the time periodTgives therateof transition between the two states, withthe LHS representing the rate of transition from state 0 to state 1 due to arrivals and the RHS representingthe rate of transition from state 1 to state 0 due to departures.

4 0 = 1 1M/M/1 Let s apply the balance concept to the M/M/1 queue. The figure shows a graphical version of the model,with forward transitions corresponding to Poisson arrivals at rate and backwards transitions correspondingto completions at rate .Figure 1: Markov chain model for the M/M/1 queueOur overall goal is to derive an expression for k, the probability of havingkcustomers in the queue. To doso, we ll start solving the balance equations until a general pattern , analyze state 0. The rate of leaving state 0 due to arrivals is 0 . The rate of entering state 0 fromstate 1 is 1 . The two rates must be equal, so we can solve for 1in terms of 0. 1= 0 Now, analyze state 1.

5 The total rate of leaving state 1 due to both arrivals and departures is ( + ) 1. Therate of entering state 1 depends on arrivals from state 0 and departures from state 2.( + ) 1= 0+ 2 Substituting 1= 0, 2 0+ 0= 0+ 2 Solving for 2, 2=( )2 0If we continue solving the balance equations for higher states, a general pattern emerges. k=( )k 0 This is almost the solution we need we just need a value for the initial condition that the values representprobabilitiesof being in each state. Therefore, the total probability found by adding up allthe values must equal 1, to make a valid distribution. k=0 k= 1 0 k=0( )k= 11If you keep in mind that 0is the probability of having an empty queue, it s obvious that 0= 1 U, but it s nice to showthe general solution summation is a geometric series, which converges when <1.

6 011 = 1 0= 1 By the utilization law, =U, so 0= 1 U, exactly as final formula is k=Uk(1 U)which we already derived as the queue length distribution for M/M/1 using Little s