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: