I want to study this pdf file in a 30 minutes. I know almost nothing about its concept and I want you to:
1. create an index from all the contents it provides 2. Give me a comprehensive, but casual description about what it contains in a way that I understand the main points of this pdf file, (If it could make a sense you may gimme an example in which contains a scenario related to the main point of this pdf)


Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 1
Queuing theory
The M/G/1 queue
Michela Meo
Telecommunication Networks GroupMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 2
About the assumptions
• Markovian queues lead to simple results and allow the
investigation of a number of interesting phenomena in
queuing systems
• However, they must rely on some fundamental
assumptions
– Markovian arrival processes
– Markovian (exponential) service times
• In many situations of practical interest these assumptions
are not realistic and we would like to consider other cases
• Unfortunately, non Markovian queues are – almost always –
difficult to treat
• But... there is a very interesting and simple result for the
M/G/1 queueMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 3
The M/G/1 queue
• Arrivals occur according to a Poisson process
• Service times are independent and described by the r.v. S
distributed according to a generic pdf fS(t) or CDF FS(t)
– sometimes it is denoted by M/GI/1 to emphasize independence of
service times
• 1 server
• Infinite waiting line
arrivals, l services, SMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 4
Evolution of the queue state
5 4 3 2 1
t
S1 S2 S3 S4
A2 A3 A4
N(t)
• We are interested in understanding the evolution of the
queue state, represented by the no. of customers in the
queueMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 5
Evolution of the queue
• Define:
– Y
n: no. of customers left in the queue by the n-th
departure
– Z
n: no. of customers that arrive during the n-th service
• Write the operational equation:
Y
n+1
=
Y
n
+ Z
n+1
−1 if Y
n
> 0
Z
n+1
if Y
n
= 0
"$#$% Yn
+1
=Y
n
+ Z
n+1
−u(Y
n
)
step (or indicator)
function
the (n+1)-th customer
who leaves the queueMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 6
Evolution of the queue
• Take the mean and the limit for nà ∞
u(Y ) = 0 queue is empty
1 queue is not empty
!#"#$
E[Y
n+1
] = E[Y
n
] +E[Z
n+1
] −E[u(Y
n
)]
lim
n→∞
E[Y
n+1
] = lim
n→∞
E[Y
n
] = E[Y]
E[Y] = E[Y] +E[Z ] −E[u(Y )]
E[Z ] = E[u(Y )]
E[u(Y )] = P {server busy} = λE[S] = ρ
E[Z ] = E[u(Y )]
E[u(Y )] = ρMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 7
Evolution of the queue
Y
n+1
2
=Y
2 n
+ Z
n+1
2
+u(Y
n
) +2Y
Zn
n+1
−2Y
un
(Y
n
) −2Z
n+1
u(Y
n
)
E[Y
n+1
2 ] = E[Y
2 n
] +E[Z
n+1
2 ] +E[u(Y
n
)] +2E[Y
n
]E[Z
n+1
] −2E[Y
n
] −2E[Z
n+1
]E[u(Y
n
)]
independent independent
E[Y2 ] = E[Y2 ] +E[Z2 ] +E[u(Y )] +2E[Y ]E[Z ] −2E[Y ] −2E[Z ]E[u(Y )]
0 = E[Z 2] +E[Z ] +2E[Y]E[Z ] −2E[Y] −2E 2[Z ]
2{1 −E[Z ]}E[Y] = E[Z 2] +E[Z ] −2E 2[Z ]
sum E[Z]-E[Z]
previous result
• Take the square of the operational equation, the mean and the limit
E[Y] =E[Z2 ] +E[Z ] −2E2 [Z ]
2{1 −E[Z ]}
= E[Z ] + E[Z 2] −E[Z ]
2{1 −E[Z ]}Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 8
Evolution of the queue
E[Z2 ] = k2P {Z = k }
k=1
∞∑
= k 2 (λt)k
k
0 !
∞∫
e−λtf
S
(t)dt
k=1
∞∑
= k 2
k=1
∞∑
(λt)k
k
0 !
∞∫
e−λtf
S
(t)dt
= (λ2t 2 + λt)fS (t)dt
∞∫0
= λ2E[S 2] + λE[S]
E[Y] = E[Z ] +E[Z2 ] −E[Z ]
2{1 −E[Z ]}
prob. of k arrivals from the Poisson
process during a time t
k2 (λt)k
k
!
= (λt)
k=1
∞∑
k (λt)k−1
k=1 (k −1)!
∞∑
= (λt) (j + 1) (λt)j
j=0 j !
∞∑
= (λt) e λt + (λt)j
j=1 (j −1)!
∞∑
⎛⎜⎜⎝
⎞⎟⎟⎠
= λte λt (1 + λt)
mean no. arrivalsMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 9
Evolution of the queue
E[Y] = E[Z ] +E[Z2 ] −E[Z ]
2{1 −E[Z ]}
E[Z2 ] = λ2E[S2 ] + λE[S]
E[Y] = ρ +λ2E[S2 ]
2(1 − ρ)
C
S
2
=
E[S2] −E2[S]
E2[S]
→ E[S 2] = C
S
2E 2[S] +E 2[S]
E[Y] = ρ +λ2E[S2 ] + λE[S] − λE[S]
2(1 −E[Z ])
= ρ +
2λ
E[S2 ]
2(1 −E[Z ])Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 10
Evolution of the queue
E[Y] = ρ +λ2E[S2 ]
2(1 − ρ)
= ρ + ρ2 (1 +C S2 )
2(1 − ρ)
E[N] = ρ + ρ2 (1 +C2S)
2(1 − ρ) Pollaczek-Khintchin
formula
E[T ] = E[S] + ρE[S]
(1 +C
S
2)
2(1 − ρ)
Little’s law
E[N] = E[Y]
Due to a theorem that proves that for
single-server queues with Poisson arrivals
the distribution at the departure is equal to
the averageMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 11
The P-K formula
• The P-K formula tells us that:
– the second moment of the distribution (or the variance)
has an important impact on the queue performance
– large values of the variance imply long queues and large
times in the queue
arrivals, l
services, S
E[T ] = E[S] + ρE[S]
(1 +C
S
2)
2(1 − ρ)Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 12
Applying the P-K formula
• Compare an M/M/1 queue with an M/D/1 queue
with
– Poisson arrival process with rate l
– Service times that are
• a) Exponential with rate µ
• b) Constant and equal to 1/µ
• For the M/M/1 queue, CS2=1 (E[S2]=2/l2)
• For the M/D/1 queue, CS2=0Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 13
Applying the P-K formula
E[T (a) ] = 1
µ
+
ρ µ
1
1 − ρ
=
1 − ρ + ρ
µ(1 − ρ)
=
1
µ − λ
• For the M/D/1 queue
• For the M/M/1 queue
E[T (b) ] = 1
µ
+
ρ µ
1
2(1 − ρ)
=
2 −2ρ + ρ
2µ(1 − ρ)
=
2 − ρ
2
1
µ − λ
service
time
waiting time
• The waiting time of the M/D/1 queue is half the
waiting time of the M/M/1 queueMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 14
Model of a router
• The output queue of a router can be modeled as a
queuing system, e.g. M/M/1
• There are some issues
– Packet arrival processes are not Poisson
• Inter-arrival times are not exp distributed
• Inter-arrival times are not independent
– Service times are not exponentially distributed
• The M/G/1 model can help us to improve the
description of the service timesMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 15
Model of a router
• Service time distribution:
– Measure packet size distribution, L with fL(x)
– Let B be the output link capacity
– The service time is given by S=L/B
– Derive fS(t) from fL(x) and compute E[S2] and E[S]
– Use the M/G/1 model to estimate the queue length and average time
in the queue
x
fL(x)Michela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 16
Model of a router
• Arrival process:
– Measure the packet arrival rates in a day
– Take the peak arrival rate and set l to the peak rate
– Assume Poisson arrival process with rate equal to the peak rate
t
l(t) peak rateMichela Meo – TNG group - Politecnico di Torino Management and Content Delivery... - 17
Model of a router
• Major limits of this model:
– Arrival process is not given by independent instances of
interarrival times
• Burstiness
• Long-range dependence (users/protocols/network behaviors)
• Feedbacks on sources from network performance (TCP closed loop)
– There is a time-variable arrival rate