Page 350 - A First Course In Stochastic Models

THE M/G/1 QUEUE 345

Little’s formula
The most basic result for queueing systems is Little’s formula. This formula relates
certain averages like the average number of customers in queue and the average
delay in queue per customer. Little’s formula is valid for almost any queueing
system. In particular, for the GI/G/c/c + N queue, we have the fundamental
relations

L q = λ(1 − P rej )W q , L = λ(1 − P rej )W, (9.1.1)
the long-run average number of busy servers = (1 − P rej )E(S). (9.1.2)
Note that P rej = 0 if N = ∞. A heuristic but insightful motivation of these for-
mulas was given in Section 2.3. The result (9.1.2) has two interesting implications.
First, since each of the c servers carries on average the same load,
1
the long-run fraction of time a given server is busy = λ(1 − P rej )E(S).
c
In particular, the long-run fraction of time a given server is busy equals ρ in the
GI/G/c queue. Second, since p j represents the long-run fraction of time that j
customers are present, the long-run average number of busy servers is also given
c−1
by the expression j=0 jp j + c j≥c p j . Thus we obtain the useful identity
 
c−1 c−1

jp j + c 1 − p j  = λ(1 − P rej )E(S). (9.1.3)

j=1 j=0
In particular, we find the relation p 0 = 1 − λE(S) for the GI/G/1 queue. The
above relations can be directly extended to queueing systems with batch arrivals.

9.2 THE M/G/1 QUEUE

In the M/G/1 queue, customers arrive according to a Poisson process with rate
λ and the service times of the customers are independent random variables with a
common general probability distribution function B(x) with B(0) = 0. There is a
single server and an infinite waiting room. Denoting by the random variable S the
service time of a customer, it is assumed that the server utilization ρ = λE(S) is
smaller than 1.
In Section 9.2.1 we derive a recursive algorithm for the computation of the state
probabilities. Several derivations are possible for the recursion relation. Our deriva-
tion uses the so-called regenerative approach, which involves simple renewal-
theoretic arguments. The regenerative approach directly leads to a numerically
stable recursion scheme for the state probabilities and also allows in a natural
way for generalizations to more complex queueing models. Using the technique of
generating functions, we also derive an asymptotic expansion for the state prob-
abilities. Since an explicit expression is available for the generating function of