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