A Combinatorial Lemma and Its Application to Concentrating Trees of Discrete-Time Queues

In this paper we consider concentrating rooted tree networks of discrete-time single server queues, all with unit service time. Such networks occur as subnetworks connecting remote access terminals to a node in a data communications network.1 Our purpose is to show that the rooted tree network of queues may be replaced by a single queue, with prescribed input, which has the same output as the queue at the root of the tree. In particular, the result is applied to the case of queues in tandem. In Section II we consider the pooling of data from M buffers into a single buffer, which also receives data from another source, as depicted in Fig. 1. We establish a combinatorial lemma which shows that there is a single equivalent buffer, with prescribed input, and the same output as the buffer in which the data is pooled. It is then pointed out how this result may be applied to a concentrating rooted tree network of queues, such as the one depicted in Fig. 3. A related observation was made by Kaspi and Rubinovitch2 in connection with networks of continuous time queues involving the pooling of data from inputs with idle periods that are exponentially distributed. 1645