An invariance relation and a unified method to derive stationary queue-length distributions

Abstract

For a broad class of discrete- and continuous-time queueing systems, we show that the stationary number of customers in system (queue plus servers) is the sum of two independent random variables, one of which is the stationary number of customers in queue and the other is the number of customers that arrive during the time a customer spends in service. We call this relation an invariance relation in the sense that it does not change for a variety of single-sever queues (with batch arrivals and batch services) and some multiserver queues (with batch arrivals and deterministic service times) that satisfy a certain set of assumptions. Making use of this relation, we also present a simple method of deriving the probability generating functions (PGFs) of the stationary numbers in queue and in system, as well as some of their properties. This is illustrated by several examples, which show that new simple derivations of old results as well as new results can be obtained in a unified manner. Furthermore, we show that the invariance relation and the method we are presenting are easily generalized to analyze queues with batch Markovian arrival process (BMAP) arrivals. Most of the results are presented under the discrete-time setting. The corresponding continuous-time results, however, are covered as well because deriving the results for continuous-time queues runs exactly parallel to that for their discrete-time counterparts.