A class of multi-queue problems arising in communication systems

Multi-queue problems seem to occur naturally in the design and analysis of many communication systems. The difficulty in treating such problems is this: A complete description of the state of the queues requires the specification of joint probabilities depending upon a large number of indices. Hence, though methods now standard [1] often enable us in principle to obtain a set of exact equations for these probabilities, this set, in practice, is generally far too complicated to be tractable.

An approximate method, based upon the idea of a “self-consistent” probability distribution has been developed to handle an important class of such queueing problems [2]. The specific situation considered in [2] was the following: We have N queues with a single server. The input to each queue is Poisson with mean interarrival time 1/λ. The queues are served in cyclicorder; i.e., they can be numbered 1, 2, ..., N such that the (j+1)^st queue is served immediately after the j -th and the first queue immediately after the N-th. At any queue, the server serves all units that were there when he arrives; units entering later must wait until the server has cycled the system again. We let s(t) denote the service time density (with mean 1/μ) and, w(t), the walking time density (with mean w). The latter is the time required by the server to go from one queue to the next. Finally, no limit is placed on the length of the queues.