Page 226 - A First Course In Stochastic Models

QUEUEING NETWORKS 219

the rate out of a state due to a particular job is equal to the rate into that state due
to that same job.

BCMP extension for the product-form solution
The product form has been established under the assumption that each service sta-
tion has the first-come first-served discipline and that the service times are expo-
nentially distributed. In an important paper of Baskett et al. (1975) it has been
shown that the product-form solution (5.6.10) also holds when each service station
uses one of the following four service disciplines, or BCMP disciplines:

1. The service discipline is first-come-first-served and the service times of the
customers are exponentially distributed (multiple servers or state-dependent ser-
vice is allowed).
2. The service discipline is processor-sharing; that is, if n customers are present at
the station, each customer is served and receives service at a rate of 1/n. The
service time of a customer is allowed to have a general probability distribution.
3. The service discipline is determined by an infinite number of servers; that is,
each arriving customer gets immediately assigned a free server. The service time
of a customer is allowed to have a general probability distribution.
4. The service discipline is pre-emptive resume, last-in first-out; that is, customers
are served one at a time in reverse order of arrival and a newly arriving customer
gets immediate service, pre-empting anyone in service. The service time of a
customer is allowed to have a general probability distribution.
The product-form solution (5.6.10) remains valid but the marginal probability
distribution {p k (n), n = 0, 1, . . . } of the number of customers present at station
k depends on the service discipline at station k. Under service discipline 1 with
c k identical servers, the marginal distribution {p k (n)} is given by the equilibrium
distribution of the number of customers present in the M/M/c queue with arrival
rate λ = λ k , service rate µ = µ k and c = c k servers. Under service discipline 3
at station k the marginal distribution {p k (n)} is given by the Poisson distribution
with mean λ k E(S k ), where the random variable S k denotes the service time of
a customer at each visit to station k. Under both service discipline 2 and service
discipline 4, at station k the marginal distribution {p k (n)} is given by the geometric
n
distribution {(1 − ρ k )ρ , n = 0, 1, . . . } with ρ k = λ k E(S k ), where S k denotes the
k
service time of a customer at each visit to station k.
5.6.2 Closed Network Model
In the performance evaluation of computer systems and flexible manufacturing sys-
tems it is often more convenient to consider a closed network with a fixed number
of customers (jobs). A job may leave the system but is then immediately replaced
by a new one. The basic closed Jackson network is as follows:

• The network consists of K service stations numbered as j = 1, . . . , K.