Queuing Systems: Lecture 2 Amedeo odoni October 15. 2001
Queuing Systems: Lecture 2 Amedeo R. Odoni October 15, 2001
Lecture outline Birth-and-death processes State transition diagrams Steady-state probabilities M/M/ M/M/m M/Moo M/M/: finite system capacity, K M/Mm: finite system capacity, K M/M/m: finite system capacity, Kem Related observations and extensions
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 mn per unit of time 4. Whenever n users are in system, service completions are Poisson at rate of un per unit of time 5. FCFS discipline
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 From point 1 20=pB(λ+p)B1=B0+P (+u)P=2P+uP From point 2 AP=uP QoI
M/M/1: Observing State Transition Diagram from Two Points 0 P1 ?P = m • From point 1: 0 1 2 … n-1 n n+1 l m l l l l l l m m m m m m 1 0 2 (l + m)P = lP + mP • From point 2: 0 1 2 … n-1 n n+1 l m l l l l l l m m m m m m 0 P1 ?P = m P1 mP2 l = +1 = P n mP n l 1 1 ( ) - + + = + P n P n mP n l m l
MM/1: Derivation of Po and Pn Step 1: P=P, P P step2:∑P= n=0 ∑ step3:p=,then∑a=∑ (∵:p<l1) p Step 4: Po 1-p and P=p"(1-P)
M/M/1: Derivation of P0 and Pn 0 0 2 1 0 2 P P , P P , , P P n n ÷ ÷ ø ö ç ç è æ = ÷ ÷ ø ö ç ç è æ = = m l m l m l L å å å ¥ = ¥ = ¥ = ÷ ÷ ø ö ç ç è æ = Þ = ÷ ÷ ø ö ç ç è æ = Þ 0 0 0 0 0 1 1, 1 n n n n n Pn P P m m l l ( 1) 1 1 1 1 , then 0 0 < - = - - = = ÷ ÷ ø ö ç ç è æ = ¥ ¥ = ¥ = å å r r r r r m l m l r Q n n n n 1 and (1 ) 1 0 0 r r r r = = - = - å ¥ = n n n n P P Step 1: Step 2: Step 3: Step 4:
M/M/1: Derivation of L, W, Wg, and Lg ∑mP=∑mp"(-p)=(-p)∑np”=(1-p)p∑mp =(1-p)p O(2 =(-p)p 1-p)2)(1-p)1 L元 W λ-2 W=W q uu(u .L=nW=2. (4-1)(-x)
M/M/1: Derivation of L, W, Wq , and Lq m l l m l m l r r r r r r r r r r r r r r r r r r r r - = - = - =÷ ÷ ø ö ç ç è æ - = - ÷ ÷ ø ö ç ç è æ - ÷ = - ø ö ç è æ = - · = = - = - = - å å å å å ¥ = ¥ = - ¥ = ¥ = ¥ = (1 ) (1 ) 1 1 (1 ) 1 1 (1 ) (1 ) (1 ) (1 ) (1 ) 2 0 1 1 0 0 0 d d d d L nP n n n n n n n n n n n n n m l l m l l l - × = - · = = L 1 1 W ( ) 1 1 1 m m l l m m l m - - = - · W = W - = q ( ) ( ) 2 m m l l m m l l l l - = - · = = × L q W q
Additional important M/M/1 results The pdf for the total time in the system, W, can be computed for a M/M/1 system fn(m)=(1-p)e-p)pm=(-) -入 W forw0 Thus, as already shown, W=l/u-2)=l/u(1-P)] The standard deviation of N, w, No, w, are all proportional to 1/(1-p), just like their expected values(L, W, Lo, Wo, respectively) The expected length of the"busy period,, E[B, is also equal to 1/(u-1)
Additional important M/M/1 results w w fw w e e (1 ) ( ) ( ) (1 ) ( ) r m m l r m m l - - - - = - = - • 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/Mm(infinite queue capacity) m-1L 2 n forn=0,1,2,,m-1 n-m -Po for n=m, m+l, m+ 2, Condition for steady state?
M/M/m (infinite queue capacity) … 0 1 2 m-1 m m+1 l l l l l l l 3m m 2m (m-1)m mm mm mm …. 0, 1, 2,...., 1 ! ( ) = P0 for n = m - n P n n m l , 1, 2,.... ! ( ) 0 = + + × = - P for n m m m m m P n m n n m l • Condition for steady state?
M/Moo(infinite no of servers (m-1) (m:+1y m+2 2 Pn or n= N is Poisson distributed! L=/p;W=1p;a=0;W=0 Many applications
M/M/¥ (infinite no. of servers) … 0 1 2 m-1 m m+1 l l l l l l l 3m m 2m (m-1)m mm (m+1}m (m+2)m … 0,1, 2,..... ! ( ) ( ) = × = - for n n 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 p"·(1-p) K+1 forn=0,1,2,…,k Steady state is always reached Be careful in applying Little's Law! Must count only the customers who actually join the system =:(1-Pk)
M/M/1: finite system capacity, K; customers finding system full are lost … 0 1 2 K-1 K l l l l l m m m m m P for n K K n n 0, 1, 2, ....., 1 (1 ) 1 = - × - = + r r r • Steady state is always reached • Be careful in applying Little’s Law! Must count only the customers who actually join the system: l¢ = l ×(1- PK )
