
Queueing Syst (2008) 58: 65–76
DOI 10.1007/s1113400790590
The M/M/∞ queue in a random environment
G. Falin
Received: 24 November 2006 / Revised: 20 November 2007 / Published online: 25 January 2008
© Springer Science+Business Media, LLC 2008
Abstract We consider the M/M/∞ queueing system with arrival and service rate
depending on the state of an auxiliary semiMarkov process (which can be viewed
as an external environment) and find the mean number of customers in the system in
steady state. In a particular case when the external environment can be only in two
states we find the distribution of the number of customers in the system.
Keywords Infinite server queue · Random environment
Mathematics Subject Classification (2000) 60K25 · 60K37 · 90B22
1 Introduction
Stochastic models whose parameters vary randomly over time depending on the state
of some external stochastic process (random environment) are of great interest for
applications. Such models arise naturally in operations research, biology, the reliability theory, the queueing theory. Our contribution is motivated by a recent paper by
M. BaykalGursoy and W. Xiao [1] who considered an infiniteserver queue with service rate varying depending on the state of an alternating renewal process C(t) with
two states, say 0 and 1, and exponentially distributed sojourn times of the process
in the states (C(t) can be also viewed as a continuoustime Markov chain with two
states). This model could be used, for example, to evaluate the influence of incidents
on the congestions of vehicles on a part of a highway. The state 0 means normal
traffic flow and the state 1 means traffic flow with a lower speed after an incident.
G. Falin ()
Department of Probability, Mechanics and Mathematics Faculty, Moscow State University, Moscow
119992, Russian Federation
email: gennadi_falin@mtunet.ru
66
Queueing Syst (2008) 58: 65–76
In the present paper we consider a more general model when the external environment C(t) is a general semiMarkov process. Besides we assume that the state of
the external environment affects both the service rate and the arrival rate of the main
infiniteserver queue.
2 Model description
The model under discussion consists of two parts: an external environment and a
service system.
As a model of the external environment we consider a semiMarkov process C(t)
with a finite state space S. The stochastic dynamic of the process C(t) is defined by
functions Aij (x), i, j ∈ S, that can be thought of as follows. Suppose that the process
C(t) has just changed its state to i. Then Aij (x) is the probability that the sojourn
time in the state i is less than x and the new state of the process is j .
The variables rij = Aij (+∞), i, j ∈ S, can be viewed as onestep transition probabilities of the embedded Markov chain. We assume that this chain is irreducible and
denote by πi , i ∈ S, its stationary distribution.
The distribution function of the sojourn time in the state i is Ai (x) = j Aij (x).
+∞
+∞
Let mi = 0 xdAi (x) > 0 and vi = 0 x 2 dAi (x) be the first and the second
+∞
+∞
moments of the sojourn time and mij = 0 xdAij (x), vij = 0 x 2 dAij (x).
∞ −sx
Let also αij (s) = 0 e dAij (x) be the LaplaceStieltjes transform of the func∞
tion Aij (x) and αi (s) = 0 e−sx dAi (x) = j αij (s) be the LaplaceStieltjes transform of the sojourn time distribution function Ai (x).
To deal with a Markov process we introduce a supplementary variable ξ(t) as the
elapsed sojourn time of the process C(t) in the current state.
The service system consists of an infinite number of homogeneous servers. When
the state of the process C(t) is i, customers arrive according to a Poisson flow with
rate λi and are served with rate μi .
Let N (t) be the number of customers in the system at time t. For the model under
consideration the threedimensional process (C(t), ξ(t), N (t)) is Markovian.
We will study the system in steady state which exists iff at least one of the rates
μi is positive. To prove this fact consider the embedded process N (ηk ), where ηk is
the time of the kth visit of the process C(t) to a fixed environment state i. It is easy
to see that the sequence of random variables {N (ηk )} forms a discretetime Markov
chain and
N (ηk+1 ) = N (ηk ) + Ak − Bk ,
where Ak is the number of customers which arrived in the system during period
[ηk ; ηk+1 ] and Bk is the number of customers which left the system during this period.
The random variable Ak does not depend on events which have occurred before epoch
ηk and has finite mean. The random variable Bk depends on the history of the system
before time ηk only
∞through N (ηk ) and its conditional mean value E(Bk N (ηk ) = n)
is not less than n 0 (1 − e−μi x )dAi (x) = n(1 − αi (μi )). Thus the mean draft
xn ≡ E(N (ηk+1 ) − N (ηk )N (ηk = n)) ≤ EAk − n(1 − αi (μi ))
Queueing Syst (2008) 58: 65–76
67
and if μi > 0 then limn→∞ xn = −∞. Therefore if at least one of the rates μi is
positive we can guarantee that the embedded Markov chain {N (ηk )} is ergodic. This
in turn yields ergodicity of the original process (C(t), ξ(t), N (t)).
3 The mean number of customers in the system
Theorem 1 The mean number of customers in the system in steady state is
(πi λi Di + Mi zi )
,
EN (t) = i
i πi mi
(1)
where
Mi =
Di =
1−αi (μi )
,
μi
mi ,
if μi > 0,
if μi = 0,
mi − 1−αμi i(μi ) , if μi > 0,
1
μi
1
2 vi ,
if μi = 0,
and the variables zi can be found as the solution of the following set of linear equations:
πj λj Mj i +
zj αj i (μj ),
(2)
zi =
j
where
j
Mj i =
rj i −αj i (μj )
,
μj
mj i ,
if μj > 0,
if μj = 0.
Proof Let
pin (x)dx = P (C(t) = i, x < ξ(t) < x + dx, N (t) = n)
be the stationary joint distribution of the number of customers in the system, the state
of the external environment and the elapsed sojourn time.
In a general way we obtain the following equations of statistical equilibrium:
(x) = − (λi + nμi + ai (x)) pin (x) + λi pi,n−1 (x) + (n + 1)μi pi,n+1 (x),
pin
+∞
dAj i (x)
,
pj n (x)
pin (0) =
1 − Aj (x)
0
j
A (x)
where ai (x) = 1−Ai i (x) is the instantaneous intensity of transition from the state i
given that the elapsed sojourn time in the state equals x.
68
Queueing Syst (2008) 58: 65–76
For the generating functions
pi (z, x) =
+∞
zn pin (x)
n=0
these equations give:
∂pi (z, x)
∂pi (z, x)
= − (λi − λi z + ai (x)) pi (z, x) + (μi − μi z)
,
∂x
∂z
+∞
dAj i (x)
.
pj (z, x)
pi (z, 0) =
1 − Aj (x)
0
(3)
(4)
j
Introduce new unknown functions qi (z, x) by
pi (z, x) = (1 − Ai (x)) qi (z, x).
For (3) becomes:
∂qi (z, x)
∂qi (z, x)
= −(λi − λi z)qi (z, x) + (μi − μi z)
.
∂x
∂z
(5)
This equation is wellknown in queueing theory. It describes the generating function
of the number of customers at time x in the M/M/∞ queue with arrival rate λi and
service rate μi . Its solution is given by
λi
qi (z, x) = qi (1 − (1 − z)e−μi x , 0) · exp
(z − 1) 1 − e−μi x , if μi > 0,
μi
and
qi (z, x) = qi (z, 0) · exp (λi (z − 1)x) ,
if μi = 0.
Since pi (z, 0) = qi (z, 0), this gives dependence of pi (z, x) on x:
if μi > 0, then
λi
−μi x
−μi x
pi (z, x) = (1 − Ai (x)) · pi 1 − (1 − z)e
,
, 0 · exp
(z − 1) 1 − e
μi
(6)
and if μi = 0, then
pi (z, x) = (1 − Ai (x)) · pi (z, 0) · exp (λi (z − 1)x) .
(7)
When z = 1 both (6) and (7) give:
pi (1, x) = (1 − Ai (x)) · pi (1, 0).
Thus,
pi (1) ≡
0
+∞
pi (1, x)dx = mi · pi (1, 0),
(8)
(9)
Queueing Syst (2008) 58: 65–76
69
so that
pi (1, x) =
1 − Ai (x)
pi (1).
mi
(10)
Using relation (8) we get from (4):
pi (1, 0) =
pj (1, 0)rj i .
j
Thus pi (1, 0) = Const · πi and therefore
pi (1) = Const · πi mi .
Since
i
pi (1) = 1, we find the constant:
1
.
π
i i mi
Const =
Finally,
πi mi
pi (1) = P (C(t) = i) =
,
j πj mj
(11)
πi
.
j πj mj
pi (1, 0) =
Relation (11) is wellknown from the general theory of semiMarkov processes.
Now differentiate (6), (7) and (4) with respect to z at the point z = 1:
∂pi (1, x)
λi
= (1 − Ai (x))
1 − e−μi x · pi (1, 0)
∂z
μi
+ (1 − Ai (x)) e−μi x
∂pi (1, 0)
,
∂z
if μi > 0,
∂pi (1, x)
= (1 − Ai (x)) λi x · pi (1, 0)
∂z
∂pi (1, 0)
, if μi = 0,
+ (1 − Ai (x))
∂z
∂pi (1, 0) +∞ ∂pj (1, x) dAj i (x)
=
.
∂z
∂z
1 − Aj (x)
0
j
Substituting (12), (13) into (14) gives:
∂pj (1, 0)
∂pi (1, 0)
=
αj i (μj ).
λj Mj i pj (1, 0) +
∂z
∂z
j
j
(12)
(13)
(14)
70
Queueing Syst (2008) 58: 65–76
The mean number
of customers in the system in steady state, EN(t), can be obtained
as the sum i Ni , where
+∞
Ni ≡
0
Thus,
∂pi (1, x)
∂pi (1, 0)
dx = λi Di pi (1, 0) + Mi
.
∂z
∂z
πi λi Di ∂pi (1, 0)
.
EN(t) = i
+
Mi
∂z
i πi mi
i
∂pi (1,0)
∂z
Introducing zi =
· j πj mj completes the proof.
It should be noted that variables Mi , Di and Mij considered as functions of the
parameter μi are continuous at the point μi = 0.
Using a similar approach one can get the variance of the number of customers in
the system in steady state. The analysis is along the lines of the proved theorem, but
it is necessary to differentiate equations (3), (4) twice with respect to z at the point
z = 1. The formula for V arN (t) is not given here because of its complexity.
3.1 The environment with two states
Consider now the case when the state space of the process C(t) consists of two points,
say, 0 and 1. In the context of transportation the state 0 could be thought of as normal
traffic flow and the state 1 means traffic flow with a lower speed after an incident (the
partial failure of the group of servers).
Without loss of generality we may assume that the transition matrix (rij ) is
0 1
,
1 0
so that α01 (s) = α0 (s), α10 (s) = α1 (s), π0 = π1 = 12 .
In this case the set of linear equations (2) can be easily solved which gives the
following result.
Theorem 2 If the external environment is an alternating renewal process then for
μ0 , μ1 > 0
m0
m1
λ1
λ0
+
EN(t) =
μ0 m0 + m1 μ1 m0 + m1
λ1
1
1
(1 − α0 (μ0 ))(1 − α1 (μ1 ))
λ0
1
(15)
+
−
−
1 − α0 (μ0 )α1 (μ1 )
m0 + m1 μ1 μ0
μ0 μ1
and for μ0 > 0, μ1 = 0
EN(t) =
λ0
λ1 m1
+
μ0 m0 + m1
1
λ1 v 1
α0 (μ0 )
+
.
+ m1
μ0
1 − α0 (μ0 )
2(m0 + m1 )
(16)
Queueing Syst (2008) 58: 65–76
71
4 The environment with two states, exponential distribution of “normal”
periods and full interruption of service during “failure”
Under additional assumptions it is possible to find the distribution of the number
of customers in the system in steady state. Assume, for example, that μ1 = 0 (full
interruption of service when the state of the external environment is 1, i.e. the whole
group of servers is down) and the sojourn time of the process C(t) in the state 0
(the state of “normal” functioning of the system) is exponentially distributed with
parameter f = m10 . Then the following theorem holds.
Theorem 3 Assume that
• the state space of the process C(t) consist of two points: S = {0, 1},
• the sojourn time of the process C(t) in the state 0 (the state of “normal” functioning of the system) is exponentially distributed with parameter f = m10 ,
• μ1 = 0 (during the “failure” periods service is fully interrupted).
Then the generating function of the number of customers in the system in steady
state is
λ0
N (t)
= exp
(z − 1) · F (z) · G(z),
(17)
p(z) ≡ Ez
μ0
where
F (z) =
m0
m1
+
ϕ(z),
m0 + m1 m0 + m1
1 − α1 (λ1 − λ1 z)
,
m1 (λ1 − λ1 z)
λ1 m1 z
G(z) = exp
ϕ(u)du .
μ0 m0 1
ϕ(z) =
(18)
(19)
(20)
Proof In the case under consideration general equations (3), (4) become:
∂p0 (z, x)
∂p0 (z, x)
= − (λ0 − λ0 z + f ) p0 (z, x) + (μ0 − μ0 z)
,
∂x
∂z
∂p1 (z, x)
= − (λ1 − λ1 z + a1 (x)) p1 (z, x),
∂x
+∞
p1 (z, x)a1 (x)dx,
p0 (z, 0) =
(21)
(22)
(23)
0
p1 (z, 0) =
+∞
p0 (z, x)f dx ≡ f · p0 (z).
(24)
0
As we have shown (see (7)), p1 (z, x) depends on x as follows:
p1 (z, x) = (1 − A1 (x)) · p1 (z, 0) · exp (λ1 (z − 1)x) ,
(25)
72
Queueing Syst (2008) 58: 65–76
so that (23) becomes
p0 (z, 0) = α1 (λ1 − λ1 z)p1 (z, 0).
(26)
Now integrate (21) with respect to x from x = 0 to +∞:
−p0 (z, 0) = − (λ0 − λ0 z + f ) p0 (z) + (μ0 − μ0 z)
∂p0 (z)
.
∂z
Using (26) and (24) we can transform this relation to the following differential equation:
dp0 (z)
λ0
f α1 (λ1 − λ1 z) − 1
=
· p0 (z).
+
dz
μ0 μ0
z−1
Here the function
α1 (λ1 − λ1 z) − 1
z−1
is defined at the point z = 1 as limz→1 f (z) = λ1 m1 .
We can solve this simple differential equation, which yields
λ0
p0 (z) = p0 (1) exp
(z − 1) · G(z),
μ0
f (z) =
(27)
where the function G(z) is defined by (20).
Using relation (25) we have:
+∞
1 − α1 (λ1 − λ1 z)
1 − α1 (λ1 − λ1 z)
p1 (z) ≡
= fp0 (z)
,
p1 (z, x)dx = p1 (z, 0)
λ
−
λ
z
λ1 − λ1 z
1
1
0
so that
1 − α1 (λ1 − λ1 z)
p(z) ≡ p0 (z) + p1 (z) = 1 + f
· p0 (z).
λ1 − λ1 z
Since p0 (1) =
m0
m0 +m1 ,
this completes the proof.
1
1
If the process C(t) is pure Markovian, i.e. α0 (s) = 1+m
, α1 (s) = 1+m
, and
0s
1s
λ0 = λ1 = λ, then (15) and (17) give the corresponding results of paper [1].
5 Stochastic decomposition
Now consider (17) in more detail. The righthand side of the equation consist of three
multipliers.
The first one, exp{ μλ00 (z − 1)}, is the generating function of a random variable
ν1 which has Poisson distribution with parameter μλ00 . The variable ν1 describes the
number of customers in the stationary M/M/∞ system without failures.
The function ϕ(z) can be rewritten as follows:
+∞
1 − A1 (x)
ϕ(z) =
eλ1 x(z−1)
dx.
m1
0
Queueing Syst (2008) 58: 65–76
73
Thus ϕ(z) is the generating function of a random variable ν2 which has randomized
Poisson distribution with parameter λ1 χ , where the random variable χ has density
1
m1 (1 − A1 (x)):
ϕ(z) = Ezν2 ,
+∞
(λ1 x)n −λ1 x 1 − A1 (x)
e
dx.
P (ν2 = n) =
n!
m1
0
The random variable χ describes the elapsed time from the last failure given the
group of servers is down, so that the random variable ν2 describes the total number
of arrivals during this time.
Thus the second multiplier, F (z), is the generating function of random variable
ζ ν2 , where the random variable ζ is a Bernoulli random variable which has the same
distribution as the external environment:
m1
m0
,
P (ζ = 1) =
,
P (ζ = 0) =
m0 + m1
m0 + m1
and random variables ζ and ν2 are independent.
The third multiplier, G(z), can be rewritten as
G(z) = eaψ(z)−a ,
where a =
λ1 m1
μ0 m0
and
ψ(z) = 1 +
z
ϕ(u)du = 1 +
1
=
∞
n=0
=E
z
∞
un P (ν2 = n)du
1 n=0
∞
n
P (ν2 = n)
P (ν2 = n) +
zn+1
n+1
n+1
n=0
+ zν2 +1
ν2
.
ν2 + 1
Thus G(z) is the generating function of a certain random variable ν3 , which has
1
the compound Poisson distribution with the Poisson parameter a = μλ10m
m0 and the
z
claim size generating function ψ(z) = 1 + 1 ϕ(u)du:
ν3 = γ1 + · · · + γν ,
where ν, γ1 , γ2 , . . . are independent, and
a n −a
e , n ≥ 0,
n!
1
P (γk = n) = P (ν2 = n − 1),
n
ν2
.
P (γk = 0) = E
ν2 + 1
P (ν = n) =
if n ≥ 1,
74
Queueing Syst (2008) 58: 65–76
It should be noted that the third multiplier, G(z), equals
p0 (z)
= E zN (t) C(t) = 0
p0 (1)
if the parameter λ0 = 0. Thus the distribution of the random variable ν3 coincides
with the conditional distribution of the number of customers in the corresponding
M/M/∞ system with λ0 = 0 given that the system is in the “normal” state.
T