Analysis of a Correlated Queue in a Communication System

Abstract

A family of queues where the service time Bnof customer n depends on the interarrival time In between customers n — 1 and n is studied. In particular, the focus is on dependencies that arise naturally in the context of communication systems, where the finite speed of the communication links constrains the amount of data that can be received in a given time interval. Specifically, queues are studied where the random variables In and Bnexhibit some form of proportionality relation. Such dependencies can have significant impact on system performance and it is, therefore, critical to develop tractable models that account for them. The paper starts with the simple case of a deterministic proportionality relation between the service time of a customer and its preceding interarrival time. This is then extended to allow for the addition of an independent, generally distributed overhead to the service time of each customer. Next, several models that capture the ON—OFF behavior of communication links in packet networks are considered. In all cases, expressions for the delay experienced by a packet in the system are provided. Numerical examples that illustrate the impact of dependencies through comparison with less accurate models are also supplied. While the paper is clearly motivated by problems that originated in the field of communications and in particular packet switching networks, its results should be of relevance to other environments as well. © 1993 IEEE.