Page 373 - A First Course In Stochastic Models

368 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

Derivation of the proportionality relation
Several proofs can be given for the proportionality relation (9.4.2). An insight-
ful proof can be based on renewal-theoretic arguments. The workload process
{V (K) (t), t ≥ 0} regenerates itself each time the buffer becomes empty. Let a
cycle be the time interval between two consecutive regeneration epochs. Denote
by the random variable T (K) the length of one cycle and by the random variable
T (K) (x) the amount of time in one cycle that the work in system is no more than x.
The corresponding random variables for the workload process {V t } in the infinite-
buffer M/G/1 queue are denoted by T (∞) and T (∞) (x). Then, by the theory of
regenerative processes,

(K) (∞)
E T (x) E T (x)
V K (x) = and V ∞ (x) = (9.4.3)
E(T (K) ) E(T (∞) )
for 0 ≤ x ≤ K. The crucial observation is that T (K) (x) has the same distribution as
T (∞) (x) for any 0 ≤ x ≤ K. The assumption of Poisson arrivals and the assumption
of partial overflow of work in excess of the buffer capacity are essential in order
to establish this result. A rigorous proof requires a lot of technical machinery. The
result can be made plausible as follows. In the infinite-buffer model the distribution
of T (∞) (x) for 0 ≤ x ≤ K does not depend on the duration of excursions of the
workload process above the level K. The workload process in the infinite-buffer
system returns to the level K after each upcrossing of the level K. However, by the
lack of memory of the Poisson process, the situation in the infinite-buffer system
at the epochs at which a return to level K occurs is probabilistically the same as in
the finite-buffer system at the epochs at which an overflow of level K occurs. This
explains why T (K) (x) and T (∞) (x) have the same distribution for any 0 ≤ x ≤ K.
Thus we can conclude from (9.4.3) that, for the constant γ = E[T (∞) ]/E(T (K) ),

V K (x) = γ V ∞ (x), 0 ≤ x ≤ K. (9.4.4)

Since V K (K) = 1, we next get the desired result (9.4.2). A rigorous proof of (9.4.4)
can be found in Hooghiemstra (1987).

Other performance measures
Other performance measures of interest are:

f (K) = the long-run fraction of input that overflows,
I (K) = the long-run average amount of work in the buffer.

The following results hold:

(1 − ρ)[1 − V ∞ (K)]
f (K) = (9.4.5)
ρV ∞ (K)