Sample path decompositions and queueing analysis via LCFS-PR
applied to teletraffic multiplexing
Michael Shalmon, University of Quebec - INRS, Montreal, Quebec, Canada

Abstract:
I first review a sample path decomposition of the unfinished work process during a busy-idle cycle of the GI/GI/1 queue.  The decomposition is interpretable in terms of the LCFS-PR discipline, in terms of the ladders of the random walk (and its time reverse), and (for M/G/1) also in terms of a birth-death branching process. This decomposition (applicable to GI/M/k) illuminates queueing analysis and leads to a finer cycle analysis with many applications.

While stationary analysis is equivalent to computing the expectation of cycle statistics, the decomposition alows one to compute higher moments. As one application, I review formulas for the asymptotic variance of estimators of the M/G/1 queueing performance and of its peformance gradient with respect to the arrival rate or service rate as a function of the number of observations. These formulas quantify the time needed to estimate within a given accuracy by simulation or by real time measurements, and provide a rough, reliable guide for traffic more general than Poisson.

I then examine multiplexing of aggregated ON-OFF traffic sources and I show that multiplexing of such sources is (in part) analyzable as anM/G/1 queue.

Host: Mor Harchol-Balter