Lectures 8 & 9
M/G/1 Queues
Eytan Modiano
MIT
Eytan Modiano
Slide 1
M/G/1 QUEUE
Poisson
Service times
M/G/1
General independent
? Poisson arrivals at rate λ
? Service time has arbitrary distribution with given E[X] and E[X
2
]
– Service times are independent and identically distributed (IID)
– Independent of arrival times
– E[service time] = 1/μ
– Single Server queue
Eytan Modiano
Slide 2
Pollaczek-Khinchin (P-K) Formula
W =
λE[X
2
]
2(1 ? ρ)
where ρ = λ/μ = λE[X] = line utilization
From Little’s formula,
N
Q
= λW
T = E[X] + W
N = λT= N
Q
+ ρ
Eytan Modiano
Slide 3
M/G/1 EXAMPLES
? Example 1: M/M/1
E[X] = 1/μ ; E[X
2
] = 2/μ
2
W =
λ
μ
2
(1-
ρ
)
=
ρ
μ
(1-
ρ
)
?
Example 2: M/D/1 (Constant service time 1/μ)
E[X] = 1/μ ; E[X
2
] = 1/μ
2
W =
λ
=
ρ
2
μ
2
(1-
ρ
)
2
μ
(1-
ρ
)
Eytan Modiano
Slide 4
Proof of Pollaczek-Khinchin
? Let W
i
= waiting time in queue of i
th
arrival
R
i
= Residual service time seen by I (I.e., amount of time for current
customer receiving service to be done)
N
i
= Number of customers found in queue by i
i arrives
W
i
R
i
i-3
X
i-2
X
i-1
X
X
i
Time ->
N
i
= 3
i-1
W
i
= R
i
+
?
X
j
j=i- N
i
? E[W
i
] = E[R
i
] + E[X]E[N
i
] = R + N
Q
/μ
– Here we have used PASTA property plus independent service time property
? W = R + λW/μ => W = R/(1-ρ)
Eytan Modiano
– Using little’s formula
Slide 5
What is R?
(Time Average Residual Service Time)
Residual Service
Time R(t)
X
X
X
X
1
2
3
4
X
1
X
2
X
3
X
4 time ->
Let M(t) = Number of customers served by time t
E[R(t)] = 1/t (sum of area in triangles)
t
2
M(t)
X
i
M(t)
X
i
1 M(t)
?
2
R
t
=
1
t
0
R( τ
)d τ
=
1
? =
2 t M(t)
t
i=1 i=1
As t -> Infinity
M(t)
= average departure rate = average arrival rate
t
M(t)
X
i
2
M(t)
?
M(t)
= E[X
2
]
=> R = λE[X
2
]/2
t
Eytan Modiano
Slide 6
i=1
M/G/1 Queue with Vacations
? Useful for polling and reservation systems (e.g., token rings)
? When the queue is empty, the server takes a vacation
? Vacation times are IID and independent of service times and
arrival times
– If system is empty after a vacation, the server takes another vacation
– The only impact on the analysis is that a packet arriving to an empty
system must wait for the end of the vacation
i arrives
W
i
R
i
V
j
i-3
X
i-2
X
i-1
X
X
i
Time ->
N
i
= 3
i-1
W
i
= R
i
+
?
X
j
j=i- N
i
Eytan Modiano
Slide 7
E[W
i
] = E[R
i
] + E[X]E[N
i
] = R + N
Q
/μ = R/(1-ρ)
Average Residual Service Time
(with vacations)
Residual Service
Time R(t)
X
X
X
X
1
2
3
4
V
1
X
1
X
2
V
1
X
3
X
4
time ->
0
t
M(t)
2
L(t)
2
R = [R(t)]=
1
R(
τ
)d
τ
=
1
(
?
X
i
+
?
V
j
)
t t 2 2
i=1 j=1
R = lim
E[M(t)] E[X
2
]
+
L(t) E[V
2
]
t →∞
t 2 t 2
? Where L(t) is the number of vacations taken up to time t
? M(t) is the number of customers served by time t
Eytan Modiano
Slide 8
Average Residual Service Time
(with vacations)
? As t->∞, M(t)/t -> λ and L(t)/t -> λ
v
= vacation rate
? Now, let I = 1 if system is on vacation and I = 0 if system is busy
? By Little’s Theorem we have,
– E[I] =E[#vacations] = P(system idle) = 1-ρ = λ
v
E[V]
– => λ
v
= (1-ρ)/E[V]
? Hence,
remember W = R/(1-ρ)
R
λ
E[X
2
]
2
+
(1-
ρ
)
E[V
2
]
2
E[V]
= W
λ
E[X
2
]
2(1-
ρ
)
+
E[V
2
]
2
E[V]
=
Eytan Modiano
Slide 9
Example: Slotted M/D/1 system
1/μ
Each slot = one packet transmission time = 1/μ
? Transmission can begin only at start of a slot
? If system is empty at the start of a slot, server not available for the
duration of the slot (vacation)
λ / μ
2
λ / μ
? E[X] = E[v] = 1/μ
2/μ
? E[X
2
] = E[v
2
] = 1/μ
2
W =
2(1 ? λ /μ)
+
1/ μ
2
=
2(μ?λ)
+
1/
2
μ
= W
M / D /1
+ E[ X]/2
? Notice that an average of 1/2 slot is spent waiting for the start of a slot
Eytan Modiano
Slide 10
FDM EXAMPLE
? Assume m Poisson streams of fixed length packets of arrival rate λ/m each
multiplexed by FDM on m subchannels. Total traffic = λ
Suppose it takes m time units to transmit a packet, so μ=1/m.
The total system load: ρ = λ
?
User 2
User m
User 1 SLOT for User 1
SLOT for User 2
SLOT for User m
FDM
SLOT for User m
IDLE
IDLE
Frames
? We have an M/D/1 system { W=λE[x2]/2(1-ρ) }
2
W
=
(λ
/m) m
ρ
m
=
FDM
2
(1-
ρ )
2
(1-
ρ )
Eytan Modiano
Slide 11
Slotted FDM
? Suppose now that system is slotted and transmissions start only on m
time unit boundaries.
User 2
User m
User 1 SLOT for User 1
SLOT for User 2
SLOTTED FDM
SLOT for User m
SLOT for User 2
Vacation for User m
Frames
? This is M/D/1 with vacations
– Server goes on vacation for m time units when there is nothing to transmit
E[V] = m; E[V
2
] = m
2
.
W
SFDM
= W
FDM
+ E[V
2
]/2E[V]
= W
FDM
+ m/2
Eytan Modiano
Slide 12
TDM EXAMPLE
slot 1
slot 2
slot m
. . .
TDM
slot m
Frame
? TDM with one packet slots is the same (a session has to wait for
its own slot boundary), so
W = R/(1-ρ)
R =
λ=
E[X
2
]
+
(1-
ρ=
)
E[V
2
]
2 2
E[V]
E[X
2
]
E[V
2
]
W =
λ=
+
2(1-
ρ=
)
2
E[V]
Eytan Modiano
Slide 13
TDM EXAMPLE
? Therefore, W
TDM
= W
FDM
+ m/2
Adding the packet transmission time, TDM comes out best
because transmission time = 1 instead of m.
T
FDM
= [W
FDM
] + m
T
SFDM
= [W
FDM
+ m/2]+m
T
TDM
= [W
FDM
+ m/2]+1
= T
FDM
- [m/2-1]
Eytan Modiano
Slide 14
