Random walk ladders, tree decompositions and queueing analysis

M. Shalmon

University of Quebec, INRS-Telecommunications


I. First, I review a tree-like sample path decomposition of the GI/GI/1 unfinished work process during a busy-idle cycle. The decomposition is interpretable in terms of the ladders of the associated random walk (and its time reverse) and also in terms of the LCFS preemptive resume discipline (for which there is a dual decomposition of the accumulated work process). (1) Besides providing simple probabilistic derivations of the equations satisfied by the stationary distributions (for the standard queue and the queue with set-up times or vacations), the decomposition generalizes for exponential service times to multiple servers (GI/M/k queue), and leads to a finer cycle analysis and in particular to the calculation of the variance of the various cycle statistics used in queueing estimation of the expected performance and its gradient. (2) For Poisson arrivals (M/G/1 queue) the decomposition provides a mapping between the unfinished (and/or accumulated) work process during a cycle and the random tree of a birth-death branching process with constant birth rate and age dependent death rate (there is a similar mapping for the queue length process which corresponds to the LCFS nonpreemptive discipline). In particular, the number of level crossings at x corresponds to the number of "individuals" alive at "time" x while the family and "life" structure is interpretable in terms of the ascending ladders of the time reversed random walk and/or in terms of the LCFS preemptive resume discipline. This mapping is relevant to a number of issues and in particular to reversibility. (N.B. This connection to branching processes is not the classical one due to Borel, Kendall and I.J. Good). The above observations are due to Shalmon (1985 Mc.Gill, 1988 Prob.Eng.Inf.Sci, 1989 IMS Sheffield Conf, 1991 Bernoulli Stoch.Proc.App Conf, 1993 ORSA-TIMS App.Prob. Conf) although particular aspects can be found earlier in the theoretical and applied probability litterature. The M/G/1 branching decomposition (i.e. for compound Poisson) has been recently generalized to Levy processes by theoretical probabilists.

II. Second, I review early queueing analyses of multiplexors and of tree traffic concentrating networks. The assumptions are: regenerative ON-OFF inputs, the ON durations being generally distributed; service FCFS, prioritized or cyclic; the ON rate of each individual source is not smaller than the service capacity which furthermore is constant in the network (analytically, nondecreasing in the direction of the traffic flow). Under these assumptions, it is possible to obtain the complete queueing analysis (i.e the joint mgf of the waiting times of each source at all the stations in its path):
(i) for the general tree network and the priority or cyclic disciplines.
(ii)for the tandem network with intermediate compound Poisson arrivals. and partial analysis in the general case.
These analyses are based on sample path decompositions and (embedded) reductions to the M/G/1 queue.

[M. Shalmon]
[University of Quebec, INRS-Telecommunications]