Lectures 10 & 11 Reservations Systems M/G/1 queues with Priority Eytan Modiano MIT Eytan Modiano Slide 1 RESERVATION 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 Polling to 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 2 Reservations 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 3 Single user exhaustive systems ? Let V j be the duration of the j th reservation interval – Assume reservation intervals are iid ? Consider the i th data packet: E[W i ] = R i + E[N i ]/μ R i = residual time for current packet or reservation interval N i = 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 ? ρ) + 2 Slide 4 Single user gated system (e.g.,reservations) i arrives W i i-2 i-3 i-4 X X X V i V i-1 i-1 X X i R i Time -> N i = 4 i-1 W i = R i + X j + V i j=i- N i E[W i ] = E[R i ] +E[N i ]E[X] + E[V] W = R + N Q E[X] + E[V] (NQ=λW) W = (R + E[V])/(1-ρ) Eytan Modiano Slide 5 SINGLE USER RESERVATION SYSTEM ? The residual service time is the same as in the vacation case, R = λ E[X 2 ] + (1- ρ ) E[V 2 ] 2 2 E[V] ? Hence, W = λ E[X 2 ] + E[V 2 ] + E[V] 2(1- ρ ) 2 E[V] 1- ρ ? If all reservation intervals are of constant duration A, W = λ E[X 2 ] + A 2 2(1- ρ ) 1- ρ + A Eytan Modiano Slide 6 Multi-user exhaustive system ? Consider m incoming streams of packets, each of rate λ/m ? Service times {X n } are IID and independent of arrivals with mean 1/μ, second moment E[X 2 ]. ? 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 V i = V (for all i) Arrival from stream 0 Time -> W m = 3 V 0 V 1 V 2 V 0 V 1 V 2 Stream 0 Stream 1 Stream 2 Stream 0 Eytan Modiano Slide 7 Multi-user exhaustive system ? Consider arbitrary packet i ? Let Y i = the duration of whole reservation intervals during which packet i must wait (E[Y i ] = Y) W = R + ρW+ Y ? Packet i may arrive during the reservation or data interval of any of the m streams with equal probability (1/m) – If it arrives during its own interval Y i = 0, etc…, hence, Y i = { iV w. p.1/ m 0 ≤ i < m V m ?1 i = V (m ? 1) Y = E[Y i ] = m ∑ i =0 2 R + Y R = (1 ?ρ)V 2 + λE[ X 2 ] Eytan Modiano W = (1 ? ρ) , 2V 2 Slide 8 Multi-user exhaustive system W = (1 ? ρ)V + λE[ X 2 ] + V (m ? 1) , 2(1 ? ρ) V V( m ? 1) λE[ X 2 ] = 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[ X 2 ] V(m ?ρ) = 2(1 ?ρ) + 2(1 ?ρ) λE[ X 2 ] A(1 ? ρ/ m) = 2(1? ρ) + 2(1 ? ρ) Eytan Modiano Slide 9 Gated System ? When a packet arrives during its own reservation interval, it must wait m full reservation intervals Y i = { iV w. p.1/ m 1 ≤ i ≤ m V m Y = E[Y i ] = m ∑ i =1 i = V(m 2 + 1) W = V 2 + V( m + 1) λE[ X 2 ] 2(1 ? ρ) + 2(1 ?ρ) WithV = A/m, λE[X 2 ] 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 10 M/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[X k 2 ] = sec ondmomentof servicetime(classk) ? Non-preemptive system: Customer receiving service is allowed to complete service without interruption i = n i E[X i 2 ] λ ∑ λ i =1 W k = 2(1 ?ρ 1 ? ... ?ρ k ?1 )(1 ?ρ i μ 1 ? ... ?ρ k ) , ρ = i i ? Notice that the waiting time of high priority traffic is affected by lower priority traffic Eytan Modiano Slide 11 Preemptive-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, – W k = waiting time for customers of class k or higher priority classes (1..K-1) already in the system R k = residual time for class k or higher customers Notice that lower priority customers in service don’t affect W k because they are preempted – W I = Waiting time for higher priority customers that arrive while priority k customer is already in the system – T K = Average system time for priority K customer T k = W k + W I + 1/μ Eytan Modiano Slide 12 Preemptive-resume, continued… k R k ∑ λ i E[X i 2 ] W k = 1 ?ρ 1 ? ... ?ρ k , R k = i=1 2 k ?1 k ?1 W I = ∑ (λ i /μ i )T k = ∑ (ρ i )T k i =1 i =1 1 R k k ?1 T k = μ k + 1? ρ 1 ? ... ? ρ k + T k ∑ ρ i i =1 T k = ( 1 ) (1 ?ρ 1 ? ... ?ρ k ) + R k 1 ? ... ?ρ k ?1 )(1 ?ρμ k (1 ? ρ 1 ? ... ?ρ k ) ? Notice independence of lower priority traffic Eytan Modiano Slide 13 Stability 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 14 Eytan Modiano Slide 15 E(delay) < Infinity ? Example: M/M/1 queue ? Example: M/G/1 queue T = 1 μ ?λ <∞?λ <μ? ρ<1 T = 1 μ + λE[X 2 ] 2(1?ρ) <∞if (ρ<1) and (E[X 2 ]<∞) Eytan Modiano Slide 16 P(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 queue – Arrival and service time distributions may even be correlated! If λ < μ, P(delay < Infinity) = 1 even if E(delay) not finite f D (d) = 2 π(1+ d 2 ) , d > 0 E[Delay]= 2d π(1+ d 2 )0 ∞ ∫ = Log[1+ d 2 ] π 0 ∞ ?∞ P[Delay < x] = 2 π(1+ d 2 ) 0 x ∫ = 2arctan(x) π → x→∞ 1 Eytan Modiano Slide 17 Existence of a stationary occupancy distribution ? Irreducible and Aperiodic Markov chain – Pj > 0 for all states j => all states are visited infinitely often ? Drift: ? When in state I, D i > 0 => state tends to increase D i < 0 => state tends to decrease ? Intuitively, we don’t want the state to drift to infinity, hence for large enough states the drift better get negative! ? Lemma: If D i < infinity for all i and for some δ > 0 and i’ > 0, D i < - δ for all i > i’ , then the Markov chain has a stationary distribution D i = EX n+1 ? X n | X n = i [] = kP (i,i+k) k =i ∞ ∑ Irriducible: all states communicate (I.e., positive probability of getting from every state to every other state) Periodic state : self transitions are possible only after a number of transitions (n) that is a multiple of some constant d (I.e., n = 3, 6, 9, …). Aperiodic => no state is periodic Eytan Modiano Slide 18 Examples ? M/M/1 ? M/M/m ? M/M/Inf λδ μδ i i+1 D i = EX n+1 ? X n | X n = i [] =1(λδ)?1(μδ) = (λ?μ)δ D i < 0?λ <μ D i = EX n+1 ? X n | X n = i [] =1(λδ)?1(mμδ) ?i≥ m D i < 0?λ < mμ ?i≥ m D i = EX n+1 ? X n | X n = i [] =1(λδ)?1( iμδ) D i < 0?λ < iμ Forany λ<∞and 1/μ<∞ ?i' s.t., D i < 0?i> i' λδ (ι+1)μδ i i+1