A queueing theoretic methodology for the analysis of separable conflict resolution algorithms with variable length elementary rates

The authors describe a queueing theoretic approach to the delay analysis for the class of synchronous random-access protocols consisting of a Capetanakis-type Tree Algorithm for conflict resolution and a window algorithm for channel access. The present method features a stochastic decomposition, in which a major component of the delay is viewed as a discrete time queueing problem, where each window (selected by the channel access algorithm) becomes a customer requiring service in the form of conflict resolution. This technique is sufficiently powerful to give the authors the distribution of the packet delay in steady state. In this paper, they extend the present method to allow the durations of elementary algorithmic steps to take on a general distribution (rather than being constants), which allows the authors to provide a unified treatment of channels with shared errors, some types of explicit reservation systems, and Local Area Networks with carrier sensing and/or collision detection, possibly in combination with variable size packets.