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