Shanghai Jiao Tong University RESERVATION SYSTEMS,PRIORITY QUEUEING AND SYSTEM STABILITY Weigiang Sun Communication Networks
Weiqiang Sun Communication Networks RESERVATION SYSTEMS, PRIORITY QUEUEING AND SYSTEM STABILITY Shanghai Jiao Tong University
Reservation systems Reservation systems Single server/channel shared by multiple users Only one user can use the channel at a time Need to coordinate between users 。Polling station Polls the users to see if they have anything to send One cycle R1 D1 R2 D2 R3 D3 R1 D1 R2 D2 Transmission interval Reservation interval,no transmission Weigiang Sun Communication Networks
Weiqiang Sun Communication Networks Reservation systems • Reservation systems – Single server/channel shared by multiple users – Only one user can use the channel at a time – Need to coordinate between users • Polling station – Polls the users to see if they have anything to send 2 R1 D1 R2 D2 R3 D3 R1 D1 R2 D2 Reservation interval, no transmission Transmission interval One cycle
Types of polling systems ·Exhaustive system Can send data arrives prior to the end of data interval Gated system Can send data arrives prior to reservation interval o Partially gated system Can send data arrives prior to data interval Limited service system Only one (k)packets can be sent in one data interval R1 D1 R2 D2 R3 D3 R1 D1 R2 D2 Gated system→ —Exhaustive system Partially gated system Weigiang Sun Communication Networks 3
Weiqiang Sun Communication Networks Types of polling systems • Exhaustive system – Can send data arrives prior to the end of data interval • Gated system – Can send data arrives prior to reservation interval • Partially gated system – Can send data arrives prior to data interval • Limited service system – Only one (k) packets can be sent in one data interval 3 R1 D1 R2 D2 R3 D3 R1 D1 R2 D2 Gated system Exhaustive system Partially gated system
Single user exhaustive system R D R D R D R D R D Customer i arrives ©X Xi-1 X-2 Xi-3 W Assume reservation intervals are i.i.d Identical to M/G/1 with vacations x2,2 W= Vacation period reservation period 2(1-p)'2V AX2 A If V=A (constant),then W= 2(1-p) 2 Weigiang Sun Communication Networks 4
Weiqiang Sun Communication Networks Single user exhaustive system • Assume reservation intervals are i.i.d • Identical to M/G/1 with vacations – Vacation period = reservation period 4 R D R D R D R D R D Xi Xi-1 Xi-2 Xi-3 Customer i arrives Wi Ri 2 2 2 1 2 X V W V If V=A (constant), then 2 2 1 2 X A W
Single user gated system R D R D R D R D R D Customer i arrives @X, X-2 Xi-3 亚 W R W,=R+∑X,+V Weigiang Sun Communication Networks 5
Weiqiang Sun Communication Networks Single user gated system 5 R D R D R D R D R D Xi Xi-2 Vi Xi-3 Customer i arrives Wi Vi-1 Ri W R X V i i i i
Single user gated system (cont. Waiting time in the single user gated systems W,=R+∑X,+ ● S0, W=R+No/u+EV]3W=(R+EV)/(1-P) And the residual time is the same as in the vacation case R=ix.(-e) 2 2V ·Hence, X2 2 W= 21-p+2+1-p Weigiang Sun Communication Networks 6
Weiqiang Sun Communication Networks Single user gated system (cont.) 6 W R X V i i i i W R N E V Q / 2 2 1 2 2 X V R V • Waiting time in the single user gated systems • So, W R E V / 1 • And the residual time is the same as in the vacation case • Hence, 2 2 2(1 ) 1 2 X V V W V
Multi-user systems ·Assume 一 m incoming streams,each of rate A/m 一 Service times are i.i.d and independent of arrivals with mean 1/u,second moment E[X2] Server serves all packets from stream 1,then all packets from stream 2 and so on... Fixed reservation interval Vi =V(for all i),but data transmission intervals are not fixed Packet i from stream 3 arrives Start of packet i transmission R3 R1 R2 R3 R1 长 Residual Packets in queue to wait for Reservation intervals to wait for Weigiang Sun Communication Networks
Weiqiang Sun Communication Networks Multi-user systems • Assume – m incoming streams, each of rate λ/m – Service times are i.i.d and independent of arrivals with mean 1/μ, second moment E[X2 ] – Server serves all packets from stream 1, then all packets from stream 2 and so on… – Fixed reservation interval Vi = V (for all i), but data transmission intervals are not fixed 7 R3 R1 R2 R3 R1 Packet i from stream 3 arrives Start of packet i transmission Residual Packets in queue to wait for Reservation intervals to wait for
Multi-user systems (cont. Packet i from stream 3 arrives Start of packet i transmission R3 R1 R2 R3 R1 斗长 Residual Packets in queue to wait for Reservation intervals to wait for -羽☑ =R+oW+Y Let it be Y,will be treated according to ∑N=pw types of systems X2,(1-p)V2 R= 2 2V Weigiang Sun Communication Networks 8
Weiqiang Sun Communication Networks Multi-user systems (cont.) 8 R3 R1 R2 R3 R1 Packet i from stream 3 arrives Start of packet i transmission Residual Packets in queue to wait for Reservation intervals to wait for i i i i N E W E R E Y 2 2 1 2 2 X V R V Ni W Let it be Y, will be treated according to types of systems R W Y
Y for different types of reservation systems For exhaustive systems A packet doesn't need to wait for a reservation interval in case it arrives in its own interval.So the maximum reservation interval to wait is m-1 Packet can arrive randomly within m slots with equal probability of 1/m -henc Y-E- m i=o ·For gated systems A packet has to wait for a reservation interval even if it arrives in its own interval.So the maximum reservation interval to wait is m Packet can arrive randomly within m slots with equal probability of 1/m Y-]- i=0 Weigiang Sun Communication Networks 9
Weiqiang Sun Communication Networks Y for different types of reservation systems • For exhaustive systems – A packet doesn’t need to wait for a reservation interval in case it arrives in its own interval. So the maximum reservation interval to wait is m-1 – Packet can arrive randomly within m slots with equal probability of 1/m – hence 9 • For gated systems – A packet has to wait for a reservation interval even if it arrives in its own interval. So the maximum reservation interval to wait is m – Packet can arrive randomly within m slots with equal probability of 1/m 1 0 1 1 2 m i i m Y E Y i V V m 0 1 1 2 m i i m Y E Y i V V m
Hence,W is For exhaustive systems y--2r-”2 m i=o W=R+pW+Y→W= R+Y ax2 (m-p)v 1-p2(1-p)'2(1-p) ·For gated systems =I2r空 m m i=o W-3 2x2(m-p+2)严 1-p) 2(1-p) Weigiang Sun Communication Networks 10
Weiqiang Sun Communication Networks Hence, W is 10 • For exhaustive systems • For gated systems 1 0 1 1 2 m i i m Y E Y i V V m 0 1 1 2 m i i m Y E Y i V V m 2 1 2 1 2 1 R Y X m V W R W Y W 2 2 2 1 2 1 X m V W
