Transient queueing approximations for modeling computer networks

Abstract

The objective of this research was to further develop and evaluate the performance of a transient queueing approximation when it is applied to modeling computer communication networks. An operational computer network that uses the ISO IS-IS routing protocol was modeled as a Jackson network. The primary goal of the approximation pursued in this study was to provide transient queue statistics comparable in accuracy to the results from conventional Monte Carlo simulations. A closure approximation of the M/M/1 queueing system extended to the general Jackson network has been used to obtain transient queue statistics. Approximations were necessary since a closed form solution for the transient behavior of a network of queues remains an intractable problem. The performance of the approximation was compared to a discrete event simulation under both stationary and nonstationary conditions. The nonstationary conditions included link/node failures, link cost changes, and time-varying input loads. The simulation was executed for a variety of network conditions including network topologies, traffic patterns, and loadings. The approximations for the mean and variance of the number of packets in the queue were fairly close to the simulation values. In the nonstationary conditions, the average errors for mean and variance were less than 17% and 26%, respectively. The performance of the approximation for the average packet delay was not as good as that of mean and variance. The relative errors between approximation and simulation were acceptably small. The approximations based on a Jackson network were compared to the results from the Monte Carlo simulations with non-Poisson arrivals. This comparison does not work very well since the Jackson network model assumes that the external arrivals follow a Poisson distribution. For certain non-Poisson arrivals, however, the average errors between the Monte Carlo simulation and the approximation were fairly small. The routing protocol employed in this research has the capability of splitting traffic on equal-cost paths. A new algorithm was proposed for load splitting. The performance of the proposed algorithm was compared to that of the known load splitting algorithms based on the average packet delay. The performance of the load splitting algorithms was also compared using the closure approximation in order to evaluate its usefulness in a practical network design problem.