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