Lectures 8&9 M/G/l Queues Eytan Modiano MIT
Lectures 8 & 9 M/G/1 Queues Eytan Modiano MIT Eytan Modiano Slide 1
M/G/1 QUEUE Poisson General independent M/G/ Service times Poisson arrivals at rate n Service time has arbitrary distribution with given E[X] and E[X2I Service times are independent and identically distributed (ID) Independent of arrival times E[service time]=1/u Single Server queue
M/G/1 QUEUE Poisson Service times M/G/1 General independent • Poisson arrivals at rate λ • Service time has arbitrary distribution with given E[X] and E[X2] – Service times are independent and identically distributed (IID) – Independent of arrival times – E[service time] = 1/µ – Single Server queue Eytan Modiano Slide 2
Pollaczek-Khinchin(P-K Formula MEIX 2(1-p) where P=MH=NE[X]= line utilization From Little's formula EⅨ]+W N=久T
Pollaczek-Khinchin (P-K) Formula W = λE[X2 ] 2(1 − ρ) where ρ = λ/µ = λE[X] = line utilization From Little’s formula, NQ = λW T = E[X] + W N = λT= NQ + ρ Eytan Modiano Slide 3
M/G/1 EXAMPLES Example 1: M/M/ E[X=1;EX2=2μ2 入 p 1p)1p Example 2: M/D/1(Constant service time 1/p) EⅨX=1;EX2=1p2 入 p 22(1-p)2(1P)
M/G/1 EXAMPLES • Example 1: M/M/1 E[X] = 1/µ ; E[X2] = 2/µ2 W = λ µ2(1-ρ) = ρ µ(1-ρ) • Example 2: M/D/1 (Constant service time 1/µ) E[X] = 1/µ ; E[X2] = 1/µ2 W = λ = ρ 2µ2(1-ρ) 2µ(1-ρ) Eytan Modiano Slide 4
Proof of pollaczek-Khinchin Let Wi= waiting time in queue of itn arrival R: Residual service time seen by l( l.e., amount of time for current customer receiving service to be done) N;= Number of customers found in queue by i i arrives W ⅹ3X2Xx1 R Time R;+ E=E[R]+E[XEN]=R+N/μ Here we have used PaSta property plus independent service time property W=R+MW=>W=R/(1-) Using little' s formula
Proof of Pollaczek-Khinchin • Let Wi = waiting time in queue of ith arrival Ri = Residual service time seen by I (I.e., amount of time for current customer receiving service to be done) Ni = Number of customers found in queue by i i arrives Wi Ri X i-3 X i-2 X i-1 Xi Time -> Ni = 3 i-1 W i = R i + � X j j=iN i • E[Wi] = E[Ri] + E[X]E[Ni] = R + N Q/µ – Here we have used PAST A prope rty plus independent service time property • W = R + λW/ µ => W = R/(1- ρ) Eytan Modiano – Using little’s form ula Slide 5
What is r? (Time Average Residual Service Time) Residual service Time R(t) X X X time→> Let M(t=Number of customers served by time t E[R(t]=1/t (sum of area in triangles) M(t)、2 M(t)、2 (r)dτ 10口 2 t M(t) Ast→ Infini M(t average departure rate average arrival rate M(t)、2 Mt E2]=>R=ME2]2 Mt
What is R? (Time Average Residual Service Time) Residual Service Time R(t) X X X X 1 2 3 4 X1 X2 X3 X4 time -> Let M(t) = Number of customers served by time t E[R(t)] = 1/t (sum of area in triangles) t 2 M(t) X i M(t) X i 1 M(t) � 2 R t = 1 t 0 R( τ )d τ = 1 � = 2 t M(t) t i=1 i=1 As t -> Infinity M(t) = average departure rate = average arrival rate t M(t) X i 2 M(t) � M(t) = E[X2] => R = λE[X2]/2 t Eytan Modiano Slide 6 i=1
M/G/ Queue with Vacations Useful for polling and reservation systems(e.g, token rings) When the queue is empty, the server takes a vacation Vacation times are lID and independent of service times and arrival times If system is empty after a vacation, the server takes another vacation The only impact on the analysis is that a packet arriving to an empty system must wait for the end of the vacation I arrives ⅤX3X2X1X Time→ R:+ EW]= E[R]+ EDX]ENI =R+Nou=R/(1-p)
M/G/1 Queue with Vacations • Useful for polling and reservation systems (e.g., token rings) • When the queue is empty, the server takes a vacation • Vacation times are IID and independent of service times and arrival times – If system is empty after a vacation, the server takes another vacation – The only impact on the analysis is that a packet arriving to an empty system must w ait for t he end of the vacation i arrives Wi Ri Vj X i-3 X i-2 X i-1 Xi Time -> Ni = 3 i-1 W i = R i + � X j j=iN i Eytan Modiano Slide 7 E[Wi] = E[Ri] + E[X]E[Ni] = R + N Q/µ = R/(1- ρ)
Average residual service Time (with vacations) Residual service Time R(t) X 4 time M(t) R=[R()= (τ)d 2 2 R=imE/N(]EⅨ L(t EV 2 Where l(t is the number of vacations taken up to time t M(t) is the number of customers served by time t
Average Residual Service Time (with vacations) Residual Service Time R(t) X X X X 1 2 3 V 4 1 X1 X2 V1 X3 X4 time -> 0 t M(t) 2 L(t) 2 R = [R(t)]= 1 R( τ )d τ = 1 (� X i + � V j ) t t 2 2 i=1 j=1 R = lim E[M(t)] E[X 2] + L(t) E[V 2] t →∞ t 2 t 2 • Where L(t) is the number of vacations taken up to time t • M(t) is the number of customers served by time t Eytan Modiano Slide 8
Average residual service Time (with vacations) As t-> M(t)t→>λandL(t)t→= vacation rate Now, let I= 1 if system is on vacation and I=0 if system is busy By Little's Theorem we have E[=Efvacations]=P(system idle)=1-P=A EM >my=(1-P)EMV Hence, remember W=R/(1-P) E ElV R=λ EⅨ21,(1-p)E 2 2EV] 2(1-P)2E[V]
Average Residual Service Time (with vacations) • As t-> ∞ , M(t)/t -> λ and L(t)/t -> λv = vacation rate • Now, let I = 1 if system is on vacation and I = 0 if system is busy • By Little’s Theorem w e have, – E[I] =E[#vacations] = P(system idle) = 1- ρ = λ v E[V] – => λv = (1- ρ)/E[V] • Hence, remember W = R/(1- ρ) R λ E[X 2] 2 + (1- ρ )E[V 2] 2 E[V] = W λ E[X 2] 2(1- ρ ) + E[V 2 ] 2 E[V] = Eytan Modiano Slide 9
Example: Slotted M/D/1 system Each slot= one packet transmission time =1/1 Transmission can begin only at start of a slot If system is empty at the start of a slot, server not available for the duration of the slot (vacation) a/21/n22 E冈]=EM=1 EⅨ]=E=1 2(1-/)2/12(4-1)2 W M/D/1 +E灯2 Notice that an average of 1/2 slot is spent waiting for the start of a slot
Example: Slotted M/D/1 system 1/ µ Each slot = one packet transmission time = 1/ µ • Transmission can begin only at start of a slot • If system is empty at t he star t of a slot, server not available f or the duration of the slot (vacation) λ / µ2 λ / µ • E[X] = E[v] = 1/ µ 2 / µ • E[X 2] = E[v 2] = 1/ µ 2 W = 2(1 − λ / µ) + 1/ µ2 = 2( µ − λ) + 1/ 2 µ = WM / D /1 + E[ X]/ 2 • Notice t hat an average of 1/2 slot is spent waiting for t he star t of a slot Eytan Modiano Slide 10