Delay Distributions in Discrete Time Multiclass Tandem Communication Network Models

Abstract

An exact computational algorithm for the solution of a discrete time multiclass tandem network with a primary class and cross-traffic at each queue is developed. A sequence of truncated Lindley recursions is defined at each queue relating the delays experienced by the first packet from consecutive batches of a class at that queue. Using this sequence of recursions, a convolve-and-sweep algorithm is developed to compute the stationary distributions of the delay and inter-departure processes of each class at a queue, delays experienced by a typical packet from the primary class along its path as well as the mean end-to-end delay of such a packet. The proposed approach is designed to handle the non-renewal arrival processes arising in the network. The algorithmic solution is implemented as an abstract class which permits its easy adaptation to analyze different network configurations and sizes. The delays of a packet at different queues are shown to be associated random variables from which it follows that the variance of total delay is lower bounded by the sum of variances of delays at the queues along the path. The developed algorithm and the proposed lower bound on the variance of total delay are validated against simulation for a tandem network of two queues with three classes under different batch size distributions.