Queuing Systems: Lecture 3 Amedeo R. Odoni October 17, 2001 Lecture Outline ? 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 ? M/E2/1 example ? M/G/1: epochs and transition probabilities ? M/G/1: derivation of L ? Why M/G/m, G/G/1, etc. are difficult 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 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 Variations and extensions of birth-and-death queuing systems ? Huge number of extensions on the previous models ? Most common is arrival rates and service rates that depend on state of the system; some lead to closed-form expressions ? Systems which are not birth-and-death, but can be modeled by continuous time, discrete state Markov processes can also be analyzed ? State representation is the key (e.g. M/Ek/1) M/G/1: Background ? Poisson arrivals; rate l ? General service times, S; fS(s); E[S]=1/m; sS ? Infinite queue capacity ? The system is NOT a continuous time Markov process (most of the time “it has memory”) ? We can, however, identify certain instants of time (“epochs”) at which all we need to know is the number of customers in the system to determine the probability that at the next epoch there will be 0, 1, 2, …, n customers in the system ? Epochs = instants immediately following the completion of a service M/G/1: Transition probabilities for system states at epochs (1) N = number of customers in the system at a random epoch, i.e., just after a service has been completed N' = number of customers in the system at the immediately following epoch R = number of new customers arriving during the service time of the first customer to be served after an epoch N' = N + R – 1 if N > 0 N' = R if N = 0 ? Note: make sure to understand how R is defined Epochs and the value of R t1 t2 t3 t4 t5 t6 t N Between t1 and t2, R=2 Between t5 and t6, R=0 M/G/1: Transition probabilities for system states at epochs (2) ? Transition probabilities can be written in terms of the probabilities: P[number of new arrivals during a service time = r] = ? Can now draw a state transition diagram at epochs ,...2,1,0)()(!)(0 =???= ∫∞ ? rfortdtfr et S tr r ll a A Critical Observation ? The probabilities P[N=n] of having n customers in the system at a random epoch are equal to the steady state probabilities, Pn, of having n customers in the system at any random time ? The PASTA property: “Poisson arrivals see time averages” ? Can now use same argument as for M/M/1 system to write: P0 = 1- l / m and E[B] = 1/(m – l) ? Can also derive closed-form expressions for L, W, Lq and Wq Expected values for M/G/1 )1()1(2 222 <? ?++= rrslrr SL )1(2 222 r slr ? ?+= S qL )1(2 1 222 rl slr m ? ?++= SW 2 )1( )1( 1 )1(2 )1( )1(2 222222 SSS q CCW +? ??=? += ? ?+= r r mrl r rl slr SSS SECNote sm s ?== ][: