Queuing Systems: Lecture 2 Amedeo R. Odoni October 15, 2001 Lecture Outline ? Birth-and-death processes ? State transition diagrams ? Steady-state probabilities ? M/M/1 ? M/M/m ? M/M/￥ ? M/M/1: finite system capacity, K ? M/M/m: finite system capacity, K ? M/M/m: finite system capacity, K=m ? Related observations and extensions Birth-and-Death Queuing Systems 1. m parallel, identical servers. 2. Infinite queue capacity. 3. Whenever n users are in system (in queue plus in service) arrivals are Poisson at rate of ln per unit of time. 4. Whenever n users are in system, service completions are Poisson at rate of mn per unit of time. 5. FCFS discipline. M/M/1: Observing State Transition Diagram from Two Points 10 P?P m= ? From point 1: 0 1 2 n-1 n+1n… l m l l l l l l m m m m m m 201)( PPP mlml +=+ ? From point 2: 0 1 2 n-1 n+1n… l m l l l l l l m m m m m m 10 P?P m= 21 PP ml = 1+= nn PP ml 11)( +? +=+ nnn PPP mlml M/M/1: Derivation of P0 and Pn 00 2 201 ,,, PPPPPP n n ??? ? ??? ?= ??? ? ??? ?== m l m l m l L ∑ ∑∑ ∞ = ∞ = ∞ = ??? ? ??? ? =?=?? ? ? ??? ??= 0 0 0 0 0 1 1 ,1 n n n nn n PPP m lm l )1(1 111 then , 00 <?=??==?? ? ? ??? ?= ∞∞ = ∞ = ∑∑ rrrrrmlmlr Q n n n n )1(and 11 0 0 rrr r ?=?== ∑∞ = n n n n PP Step 1: Step 2: Step 3: Step 4: M/M/1: Derivation of L, W, Wq, and Lq lm l ml ml r r rrr rrrrrrrr rrrrrrr ?=?=?=??? ? ??? ? ??= ??? ? ??? ? ??=?? ?? ? ??= ?=?=?==? ∑ ∑∑∑∑ ∞ = ∞ = ? ∞ = ∞ = ∞ = 1)1()1( 1)1( 1 1)1()1( )1( )1( )1( 2 0 1 1 000 d d d d nnnnPL n n n n n n n n n n lmllm l l ?=??==? 11LW )( 111 lmm l mlmm ?=??=?=? WWq )()( 2 lmm l lmm lll ?=??==? qq WL Additional important M/M/1 results www eewf )()1( )()1()( lmmr lmmr ???? ?=?= ? The pdf for the total time in the system, w, can be computed for a M/M/1 system: for w? 0 Thus, as already shown, W = 1/(m -l) = 1/[m (1-r)] ? The standard deviation of N, w, Nq, wq are all proportional to 1/(1-r), just like their expected values (L, W, Lq, Wq, respectively) ? The expected length of the “busy period”, E[B], is also equal to 1/(m -l) M/M/m (infinite queue capacity) …0 1 2 m-1 m m+1 l l l l l l l 3m2mm (m-1)m mm mm mm …. 1,....,2,1,0! )( 0 ?== mnforPnP n n m l ,....2,1, ! )( 0 ++=?= ? mmmnforPmmP mn n n m l ? Condition for steady state? M/M/￥ (infinite no. of servers) …0 1 2 m-1 m m+1 l l l l l l l 3m2mm (m-1)m mm (m+1}m (m+2)m … ,.....2,1,0! )( )( = ? = ? nforn e P n n m l m l ? N is Poisson distributed! ? L = l / m ; W = 1 / m ; Lq = 0; Wq = 0 ? Many applications M/M/1: finite system capacity, K; customers finding system full are lost …0 1 2 K-1 K l l l l l mmm m m KnforP K n n .....,,2,1,01 )1( 1 =? ??= +r rr ? Steady state is always reached ? Be careful in applying Little’s Law! Must count only the customers who actually join the system: )1( KP??=′ ll M/M/m: finite system capacity, K; customers finding system full are lost 0 1 2 m m+1 K-1 l l l l l l 3m2mm mm mm mm K l mmmm l …… …… ? Can write system balance equations and obtain closed form expressions for Pn, L, W, Lq, Wq ? Often useful in practice M/M/m: finite system capacity, m; special case! ……0 1 2 m-1 m l l l l l 3m2mm (m-1)m mm mnfor i nP m i i n n ,...2,1,0 ! )( ! )( 0 == ∑ = m l m l ? Probability of full system, Pm, is “Erlang’s loss formula” ? Exactly same expression for Pn of M/G/m system with K=m