Lectures 10 & 11 Reservations Systems M/G/1 queues with Priority Eytan Modiano MIT Eytan Modiano Slide 1RESERVATION SYSTEMS • Single channel shared by multiple users • Only one user can use the channel at a time • Need to coordinate transmissions between users • Polling systems – Polling station polls the users in order Pollingto see if they have something to send station – A scheduler can be used to receive and schedule transmission requests U1 U2 U3 U4 U5 R1 D1 R2 D2 R3 D3 R1 D1 – Reservation interval (R) used for polling or making reservations – Data interval (D) used for the actual data transmission Eytan Modiano Slide 2Reservations and polling systems • Gated system - users can transmit only those packets that arrived prior to start of reservation interval – E.g., explicit reservations • Partially gated system - Can transmit all packets that arrived before the start of the data interval • Exhaustive system - Can transmit all packets that arrive prior to the end of the data interval – E.g., token ring networks • Limited service system - only one (K) packets can be transmitted in a data interval R1 R2 R3 R1D1 D2 D3 D1 Gated system arrivals Partially gated system arrival Exhaustive system arrivals Eytan Modiano Slide 3Single user exhaustive systems • Let Vj be the duration of the jth reservation interval – Assume reservation intervals are iid • Consider the ith data packet: E[Wi] = Ri + E[Ni]/µ Ri = residual time for current packet or reservation interval Ni = Number of packets in queue • Identical to M/G/1 with vacations W =λE[X 2] E[V 2] 2(1 −ρ) + 2E[V] When V = A (constant)⇒ W =λE[X 2] A Eytan Modiano 2(1 −ρ) + 2Slide 4Single user gated system (e.g.,reservations) i arrives Wi i-2i-3i-4X X X ViVi-1 i-1X Xi Ri Time -> Ni = 4 i-1 Wi = Ri +  Xj + V i j=i- Ni E[Wi] = E[Ri] +E[Ni]E[X] + E[V] W = R + NQE[X] + E[V] (NQ=λW) W = (R + E[V])/(1-ρ) Eytan Modiano Slide 5SINGLE USER RESERVATION SYSTEM • The residual service time is the same as in the vacation case, R = λ E[X2] + (1-ρ )E[V2] 2 2 E[V] • Hence, W = λ E[X2] + E[V2] + E[V] 2(1-ρ ) 2 E[V] 1-ρ • If all reservation intervals are of constant duration A, W = λ E[X2] + A 22(1- ρ ) 1- ρ +A Eytan Modiano Slide 6Multi-user exhaustive system • Consider m incoming streams of packets, each of rate λ/m • Service times {Xn} are IID and independent of arrivals with mean 1/µ, second moment E[X2]. • Server serves all packets from stream 0, then all from stream 1, ..., then all from m-1, then all from 0, etc. • There is a reservation interval of fixed duration Vi = V (for all i) Arrival from stream 0 Time -> W m = 3 V0V1 V2 V0 V1 V2 Stream 0 Stream 1 Stream 2 Stream 0 Eytan Modiano Slide 7Multi-user exhaustive system • Consider arbitrary packet i • Let Yi = the duration of whole reservation intervals during whichpacket i must wait (E[Yi] = Y) W = R + ρW+ Y • Packet i may arrive during the reservation or data interval of anyof the m streams with equal probability (1/m) – If it arrives during its own interval Yi = 0, etc…, hence, Yi ={iV w. p.1/ m 0 ≤ i < m Vm −1i = V (m − 1)Y = E[Yi ] = m ∑i =02 R + YR = (1 −ρ)V 2 +λE[ X2] Eytan Modiano W = (1 −ρ), 2V 2 Slide 8Multi-user exhaustive system W = (1 −ρ)V +λE[ X 2] + V (m − 1),2(1 −ρ) V V( m − 1) λE[ X2]= 2 + 2(1 −ρ) + 2(1 −ρ) • In text, V = A/m and hence, A A(m − 1) λE[ X 2]W = 2m + 2m(1 −ρ) + 2(1 −ρ) λE[ X2] V(m −ρ)= 2(1 −ρ) + 2(1 −ρ) λE[ X 2] A(1 −ρ/ m)= 2(1−ρ) + 2(1 −ρ) Eytan Modiano Slide 9Gated System • When a packet arrives during its own reservation interval, it must wait m full reservation intervals Yi ={iV w. p.1/ m 1 ≤ i ≤ m VmY = E[Yi ] = m ∑i =1 i = V(m 2 + 1) W = V 2 + V( m + 1) λE[ X2] 2(1 −ρ) + 2(1 −ρ) WithV = A/m, λE[X2] A A(1 + 1/ m) λE[ X 2] A 2(1 −ρ) + 2 m + 2(1 −ρ) = 2(1 −ρ) + 2 (1 + (2 −ρ)/ m ) (1 −ρ) Eytan Modiano Slide 10M/G/1 Priority Queueing • Priority classes 1, …, n (class 1 highest and n lowest) λk = arrivalrate for class k µk = service rate for class k E[Xk 2] = sec ond moment of servicetime(class k) • Non-preemptive system: Customer receiving service is allowed tocomplete service without interruption i = n iE[Xi 2] λ∑λi =1Wk = 2(1 −ρ1 − ... −ρk −1)(1 −ρ i µ1 − ... −ρk ), ρ= ii • Notice that the waiting time of high priority traffic is affected bylower priority traffic Eytan Modiano Slide 11Preemptive-resume systems • When a higher priority customer arrives, lower priority customer is interrupted – Service is resumed when no higher priority customers remain – Notice that the delay of high priority customers is no longer affected by that of lower priority customers – Preemption is not always practical and usually involves some overhead • Consider a class k arrival and let, – Wk = waiting time for customers of class k or higher priority classes (1..K-1) alreadyin the system Rk = residual time for class k or higher customers Notice that lower priority customers in service don’t affect Wk because they are preempted – WI = Waiting time for higher priority customers that arrive while priority k customeris already in the system – TK = Average system time for priority K customer Tk = Wk + WI + 1/µ Eytan Modiano Slide 12Preemptive-resume, continued… k Rk ∑λiE[Xi2] Wk = 1 −ρ1 − ... −ρk, Rk = i=12 k −1 k −1 WI =∑(λi/µi)Tk =∑(ρi)Tk i =1 i =1 1 Rk k −1 Tk =µk + 1−ρ1 − ... −ρk + Tk ∑ρi i =1 Tk = (1) (1 −ρ1 − ... −ρk) + Rk 1 − ... −ρk −1)(1 −ρµk (1 −ρ 1 − ... −ρk) • Notice independence of lower priority traffic Eytan Modiano Slide 13Stability of Queueing Systems • Possible Definitions – Average Delay is bounded E(delay) < infinity) – Delay is finite with probability 1 P(delay < infinity) = 1 – Existence of a stationary occupancy distribution Occupancy does not drift to infinity Eytan Modiano Slide 14Eytan ModianoSlide 15E(delay) < Infinity• Example: M/M/1 queue• Example: M/G/1 queueT =1µ−λ<∞∀λ<µ⇒ρ< 1T =1µ+λE[X2]2(1−ρ)<∞ if (ρ< 1) and (E[X2] <∞)Eytan ModianoSlide 16P(Delay< Infinity) = 1• Slightly weaker definition than E[delay] < infinity• P(delay < infinity) = 1 even if E(delay) = infinity• Example:• In general it can be shown that for any G/G/1