Page 201 - A First Course In Stochastic Models

194 MARKOV CHAINS AND QUEUES

stationary process {X(t)} it holds that P {X(t) = j} = p j , j ∈ I, for all t ≥ 0. It can
be shown that the condition (5.1.15) is satisfied if and only if the stationary version
of the Markov process {X(t)} has the property that for all n ≥ 1 and all u > 0,

(X(u 1 ), . . . , X(u n )) is distributed as (X(u − u 1 ), . . . , X(u − u n )) (5.1.16)
for all 0 ≤ u 1 < · · · < u n ≤ u. A Markov process with this property is said to be
time reversible. In other words, the process reversed in time has the same prob-
abilistic structure as the original process when the process has reached statistical
equilibrium. It is as if you would see the same film shown in reverse. Let us return
to the M/M/c system. In the M/M/c system the rate at which the process goes
directly from state i to state i +1 is then equal to the rate at which the process goes
directly from state i+1 to state i; see relation (5.1.8). Hence the M/M/c system has
the property (5.1.16). Going forward in time, the time points at which the number
in the system increases by 1 are exactly the arrival epochs of customers and thus
constitute a Poisson process. Going backwards in time, the time points at which the
number in the system increases by 1 are exactly the time points at which customers
depart. Hence, by time reversibility, the departure process of customers must be a
Poisson process when the M/M/c system has reached statistical equilibrium.

5.2 LOSS MODELS

In a delay system each customer finding no free server upon arrival waits until
a server becomes available. Opposite to delay systems are loss systems in which
customers finding no free server upon arrival are lost and have no further influence
on the system. In this section we consider two basic loss models. The famous
Erlang loss model with Poisson input is dealt with in Section 5.2.1. Section 5.2.2
considers the Engset loss model with finite-source input.

5.2.1 The Erlang Loss Model

Consider a communication system with c transmission channels at which messages
are offered according to a Poisson process with rate λ. The system has no buffer to
temporarily store messages that arrive when all channels are occupied. An arriving
message that finds all c channels busy is lost and has no further influence on the
system; otherwise, the message is assigned to a free channel and its transmission
immediately starts. The transmission times of the messages are independent and
identically distributed random variables. Also, the arrival process and the trans-
mission times are independent of each other. The goal is to find an expression for
the long-run fraction of messages that are lost. This model is called Erlang’s loss
model after the Danish telephone engineer A.K. Erlang. It is often abbreviated as
the M/G/c/c queue. In the early 1900s Erlang studied this model in the frame-
work of a telephone switch which can handle only c calls. Though the theory of
stochastic processes was not yet developed in Erlang’s time, Erlang (1917) was able