Page 431 - A First Course In Stochastic Models

426 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

Whenever a source is on, it generates service requests according to a Poisson process with
rate δ. There is a buffer of capacity N for temporarily storing service requests which find the
server busy upon arrival; an arriving service request finding the buffer full is rejected. The
service time of a request is distributed as a mixture of Erlangian distributions with the same
scale parameters. This queueing system is a special case of the so-called MAP/G/1/N + 1
queue with a Markov modulated Poisson arrival process.
Develop a computer program to test the performance of formula (9.8.8) as an approximate
formula for the rejection probabilities P rej . Use the results from Exercise 5.27 to compute
(∞)
the customer-average probabilities π in the infinite-buffer model. Check your computer
j
program with the results that are given below for the case of E 2 services, m = 25 sources,
ν on = ν off = 0.1 and the two values 0.2 and 0.8 for the system load ρ.
ρ = 0.2 exa app ρ = 0.8 exa app

N = 0 1.708 × 10 −1 1.723 × 10 −1 N = 0 4.496 × 10 −1 4.616 × 10 −1
N = 5 1.766 × 10 −5 1.817 × 10 −5 N = 5 5.455 × 10 −2 5.825 × 10 −2
N = 10 1.972 × 10 −9 2.042 × 10 −9 N = 50 9.453 × 10 −7 1.002 × 10 −6
N = 15 2.437 × 10 −13 2.530 × 10 −13 N = 100 6.139 × 10 −12 6.511 × 10 −12
9.16 Consider the discrete-time SBBP/D/c/c + N queueing system. In this model there is
an underlying phase process that is alternately in the states 1 and 2. The sojourn times in the
successive states are independent positive random variables that have a geometric distribution
with mean 1/ω i in state i for i = 1, 2. If the phase process is in state i at the beginning
of a time slot, then the number of packets arriving during that time slot has the discrete
(i)
probability distribution {a k , k ≥ 0} for i = 1, 2. This phase process is called a switched-
batch Bernoulli process (SBBP). There is a buffer of capacity N to store incoming packets.
Any arriving packet finding the buffer full is rejected. The transmission of a packet can only
start at the beginning of a time slot. The transmission time of a packet is deterministic and
∞ (i)
equals any time slot. There are c service channels. Letting α i = ka for i = 1, 2, the
k=1 k
system load ρ is defined by ρ = λ/c with λ = (α 1 /ω 1 + α 2 /ω 2 )/(1/ω 1 + 1/ω 2 ) denoting
the average arrival rate of packets. It is assumed that ρ < 1. For the infinite-buffer model,
(∞)
define u as the long-run fraction of time slots at whose beginning n packets are present
n,i
z for i = 1, 2.
and the phase process is in state i. Let U (i) (z) = ∞ u (∞) n
n=0 n,i
(a) Use discrete-time Markov chain analysis to verify that
c−1
(1) c (2) (∞) (2) c (∞) c k
[A (z){γ 1 z − γ A (z)}u + A (z)ω 2 z u ] × (z − z )
k,1 k,2
(1) k=0
U (z) = ,
c
z 2c − [γ 1 A (1) (z) + γ 2 A (2) (z)]z + γ A (1) (z)A (2) (z)
(i) ∞ (i) n
a
where A (z) = n=0 n z and γ i = 1 − ω i for i = 1, 2 and γ = 1 − ω 1 − ω 2 . The
expression for U (2) (z) is obtained by interchanging the roles of 1 and 2 in the expression
for U (1) (z). Argue that
 
2 c−1 2 c−1
(∞) (∞)
nu + c  1 − u  = cρ
n,i n,i
i=1 n=1 i=1 n=0
(∞)
and argue that an additional 2c−1 relations between the 2c unknowns u for 0 ≤ n ≤ c−1
n,i
(1) (2)
and i = 1, 2 are obtained by noting that U (z) and U (z) are analytic for |z| ≤ 1.