Lectures 10& 11 Reservations Systems M/G/1 queues with Priority Eytan Modiano MIT
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 P g olins to see if they have something to send station A scheduler can be used to receive and schedule transmission requests @⑩四 R1 DI R2 D2 R3 D3 R1 DI Reservation interval (r) used for polling or making reservations Data interval (D)used for the actual data transmission
RESERVATION SYSTEMS • Single channel shared by multiple users • Only one user can use t he channel at a time • Nee d 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) u sed 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 DI D2 R3 D3R1DI Exhaustive system arrivals Gated system arrivals y gated sys stem arriv
Reservations and polling systems • Gated system - users can transmit only those packets that arrived prior to start of reservation int erval – 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 D1 R2 D2 R3 D3 R1 D1 Gated system arrivals Partially gated s ystem arrival Exhaustive s ystem arrivals Eytan Modiano Slide 3
Single user exhaustive systems Let vi be the duration of the jth reservation interval Assume reservation intervals are iid Consider the ith data packet E=R1+E[N]μ R=residual time for current packet or reservation interval N=Number of packets in queue Identical to mg 1 with vacations W=2X1+ 2(1-p)2E[ When v=A( constant→∥=2r,A 2(1-p)2
Single 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 = Num ber of packets in queue • Identical to M/G/1 with vacations W = λE [ X 2 ] E [ V 2] 2(1 − ρ) + 2 E [ V] When V = A (constant) ⇒ W = λE [ X 2] A Eytan Modiano 2(1 − ρ) + Slide 4 2
Single user gated system(e.g, reservations I arrives W X X V,I XM1X R Time→ R.+ Ⅹ.+V EW=E[R]+E[NEⅨ+En W=R+No eX]+ EMv (NQ=nW) W=(R+E)(1p)
Single user gated system (e.g.,reservations) i arrives Wi X i-4 X i-3 X i-2 Vi Vi-1 X i-1 Xi Ri Time -> Ni = 4 i-1 W i = R i + X j + V i j=iNi E[Wi] = E[Ri] +E[Ni]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Ⅸ(1pEFV2 2 2EIV Hence EX 2]+ E(V1.EMM 2(1-p)2EV If all reservation intervals are of constant duration a EⅨ21]AA
SINGLE 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[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(1- ρ ) 1- ρ 2 + A Eytan Modiano Slide 6
Multi-user exhaustive system Consider m incoming streams of packets, each of rate n/m Service times X] are lID and independent of arrivals with mean 17) second moment E[XI 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 Arrival from stream o Time→> Stream Stream 1 Stream 2 Stream 0
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 Vi = V (for all i) Arrival from stream 0 W Time -> m = 3 V0 V 1 V2 V 0 V1 V 2 Stream 0 Stream 1 Stream 2 Stream 0 Eytan Modiano Slide 7
Multi-user exhaustive system Consider arbitrary packet Let y s the duration of whole reservation intervals during which packet i must wait (ETY]=Y) W=R+ow+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 Yi=0, etc.,, hence, w,p.1m0≤<m Y=E[]=∑ V( R+y R 1-p)2,AE[X 2 2
Multi-user exhaustive system • Consider arbitrary packet i • Let Yi = the duration of whole reservation intervals during which packet i must wait (E[Yi] = 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 Yi = 0, etc…, hence, Yi = {iV w. p. 1/ m 0 ≤ i < m V m −1 i = V ( m −1) Y = E [ Yi ] = m ∑i = 0 2 R + Y R = (1 − ρ) V2 + λE[ X2 ] Eytan Modiano W = (1 − ρ), 2 V 2 Slide 8
Multi-user exhaustive system 1-p)+AE[x2]+V(m-1) 2(1-p) 今×c (m-1)E[X]E[X2]V( 2(1-p)2(1-p)2(1-p)2(1-p) In text, V= A/m and hence W A(m-1),E[Y2]E2].A( 2m2m(1-p)2(1-p)2(1-p)2(1-p)
Multi-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 = 2 m + 2 m(1 − ρ) + 2(1 − ρ) λE[ X2 ] 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 X={wp.1m1si≤m Y=ElY (m+1 1+(m+)2BLX 22(1-p)2(1-p) With∨=Am aE[P2]A4(1+1/m)E +(2-p)/m 2(1-p)2m× S>xn 2(1-p)2(1-p)
Gated 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 V m Y = E[Yi ] = m ∑i =1 i = V(m2 +1) W = V 2 + V( m +1) λE[ X2 ] 2(1 − ρ) + 2(1 − ρ) WithV = A/m, λE[X2 ] A A(1 +1/ m) λE[ X2 ] A 2(1 − ρ) + 2 m + 2(1 − ρ) = 2(1 − ρ) + 2 (1 +(2 − ρ)/ m) (1 − ρ) Eytan Modiano Slide 10