Consider a sampled-time M/D/m/m queueing system. The arrival process is Bernoulli with probability λ 1 of arrival in each time unit. There are m servers; each arrival enters a server if a server is not busy and otherwise the arrival is discarded. If an arrival enters a server, it keeps the server busy for d units of time and then departs; d is some integer constant and is the same for each server.
Let n, 0 ≤ n ≤ m be the number of customers in service at a given time and let xi be the number of time units that the ith of those n customers (in order of arrival) has been in service. Thus the state of the system can be taken as (n, x) = (n, x1, x2, ... , xn), where 0 ≤ n ≤ m and 1 ≤ x1 x2 ··· xn ≤ d.
Let A(n, x) denote the next state if the present state is (n, x) and a new arrival enters service. That is,
A(n, x) = (n + 1, 1, x1 + 1, x2 + 1, ... , xn + 1) for n <>m and xn <>d, (7.100)
A(n, x) = (n, 1, x1 + 1, x2 + 1, ... , xn-1 + 1) for n ≤ m and xn = d. (7.101)
That is, the new customer receives one unit of service by the next state time, and all the old customers receive one additional unit of service. If the oldest customer has received d units of service, then it leaves the system by the next state time. Note that it is possible for a customer with d units of service at the present time to leave the system and be replaced by an arrival at the present time (i.e., (7.101) with n = m, xn = d). Let B(n, x) denote the next state if either no arrival occurs or if a new arrival is discarded:
B(n, x) = (n, x1 + 1, x2 + 1, ... , xn + 1) for xn d, (7.102)
B(n, x) = (n - 1, x1 + 1, x2 + 1, ... , xn-1 + 1) for xn = d. (7.103)
(a) Hypothesize that the backward chain for this system is also a sampled-time M/D/m/m queueing system, but that the state (n, x1, ... , xn)(0 ≤ n ≤ m,1 ≤ x1 <>x2 ... xn ≤ d) has a different interpretation: n is the number of customers as before, but xi is now the remaining service required by customer i. Explain how this hypothesis leads to the following steady-state equations:
|
λΠn,x = (1 - λ)ΠA(n,x),
|
n <>m, xn d,
|
(7.104)
|
|
λπn,x = λΠA(n,x),
|
n ≤ m, xn = d,
|
(7.105)
|
|
(1 - λ)πn,x = λπB(n,x),
|
n ≤ m, xn = d,
|
(7.106)
|
|
(1 - λ)πn,x = (1 - λ)πB(n,x),
|
n ≤ m, xn d.
|
(7.107)
|
(b) Using this hypothesis, find Πn,x in terms of Π0, where π0 is the probability of an empty system. Hint: Use (7.106) and (7.107); your answer should depend on n, but not x.
(c) Verify that the above hypothesis is correct.
(d) Find an expression for Π0.
(e) Find an expression for the steady-state probability that an arriving customer is discarded.
Text Book: Stochastic Processes: Theory for Applications By Robert G. Gallager.