Lectures 8 & 9 M/G/1 Queues Eytan Modiano MIT Eytan Modiano Slide 1M/G/1 QUEUE Poisson Service timesM/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 2Pollaczek-Khinchin (P-K) Formula W =λE[X 2] 2(1 −ρ) where ρ = λ/µ = λE[X] = line utilization From Little’s formula, NQ = λW T = E[X] + W N = λT= NQ + ρ Eytan Modiano Slide 3M/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 4Proof 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 currentcustomer receiving service to be done) Ni = Number of customers found in queue by i i arrives Wi Ri i-3X i-2X i-1X Xi Time -> Ni = 3 i-1 Wi = Ri + � Xjj=i- Ni • E[Wi] = E[Ri] + E[X]E[Ni] = R + NQ/µ – Here we have used PASTA property plus independent service time property • W = R + λW/µ => W = R/(1-ρ) Eytan Modiano – Using little’s formula Slide 5What 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) Xi M(t) Xi 1 M(t)� 2 R t = 1t 0 R( τ )d τ = 1� = 2 t M(t)t i=1 i=1 As t -> Infinity M(t) = average departure rate = average arrival ratet M(t) Xi 2 M(t) � M(t) = E[X2] => R = λE[X2]/2tEytan Modiano Slide 6 i=1M/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 andarrival 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 Wi Ri Vj i-3X i-2X i-1X Xi Time -> Ni = 3 i-1 Wi = Ri + � Xjj=i- Ni Eytan Modiano Slide 7 E[Wi] = E[Ri] + E[X]E[Ni] = R + NQ/µ = R/(1-ρ)Average Residual Service Time (with vacations) Residual Service Time R(t) X X X X 1 2 3 4V1 X1 X2 V1 X3 X4 time -> 0 t M(t) 2 L(t) 2 R = [R(t)]= 1 R( τ )d τ = 1(� Xi + � Vj)t t2 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 8Average 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 we have, – E[I] =E[#vacations] = P(system idle) = 1-ρ = λvE[V] – => λv = (1-ρ)/E[V] • Hence, remember W = R/(1-ρ) R λ E[X2] 2 + (1-ρ )E[V 2] 2 E[V] = W λ E[X 2] 2(1-ρ ) +E[V 2 ] 2 E[V] = Eytan Modiano Slide 9Example: 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 the start of a slot, server not available for the duration of the slot (vacation) λ / µ2 λ / µ • E[X] = E[v] = 1/µ 2/µ• E[X2] = E[v2] = 1/µ2 W = 2(1 −λ/µ) + 1/ µ2 = 2(µ−λ) + 1/2 µ = WM / D /1 + E[ X]/2 • Notice that an average of 1/2 slot is spent waiting for the start of a slot Eytan Modiano Slide 10FDM EXAMPLE • Assume m Poisson streams of fixed length packets of arrival rate λ/m each multiplexed by FDM on m subchannels. Total traffic = λ Suppose it takes m time units to transmit a packet, so µ=1/m. The total system load: ρ = λ • User 2 User m User 1 SLOT for User 1 SLOT for User 2 SLOT for User m FDM SLOT for User m IDLE IDLE Frames • We have an M/D/1 system { W=λE[x2]/2(1-ρ) } 2 W = (λ/m) m ρ m = FDM 2 (1-ρ ) 2 (1-ρ ) Eytan Modiano Slide 11Slotted FDM • Suppose now that system is slotted and transmissions start only on mtime unit boundaries. User 2 User m User 1 SLOT for User 1 SLOT for User 2 SLOTTED FDM SLOT for User m SLOT for User 2 Vacation for User m Frames • This is M/D/1 with vacations – Server goes on vacation for m time units when there is nothing to transmit E[V] = m; E[V2] = m2. WSFDM = WFDM + E[V2]/2E[V] = WFDM + m/2 Eytan Modiano Slide 12TDM EXAMPLE slot 1 slot 2 slot m. . . TDM slot m Frame • TDM with one packet slots is the same (a session has to wait forits own slot boundary), so W = R/(1-ρ) R = λ=E[X2] + (1-ρ=)E[V2] 22 E[V] E[X 2] E[V 2]W = λ=+ 2(1-ρ=) 2 E[V] Eytan Modiano Slide 13TDM EXAMPLE • Therefore, WTDM = WFDM + m/2 Adding the packet transmission time, TDM comes out bestbecause transmission time = 1 instead of m. TFDM = [WFDM] + m TSFDM = [WFDM + m/2]+m TTDM = [WFDM + m/2]+1 = TFDM - [m/2-1] Eytan Modiano Slide