Reversibility and flows in queueing networks

Abstract

In this paper we analyze the relationships between the flows of customers in a queueing network whose queue length process is a Markov process. A flow is a stochastic process formed by embedding the queue length process at transitions corresponding to: customers arriving to the network at a node; customers departing the network from a node; customers moving from one node to another node; all customers entering a node; all customers leaving a node; superpositions and decompositions of the flows described above.

We show that flow processes in queueing networks are Markov renewal processes. In fact, we construct two Markov renewal processes corresponding to a flow. One Markov renewal process is formed by embedding the queue length process just before transitions of interest. The other Markov renewal process is formed by embedding the queue length process just after the transitions of interest.

If a queueing network is a Jackson network and if the queue length process is reversible then the Markov renewal process formed by embedding the queue length process just before inputs to a node is the reverse process of the Markov renewal process formed by embedding the queue length process just after outputs from the node. Similar results hold for other flows in the network.

We extend the above results to networks of symmetric queues where the service times are restricted to the Erlang distributed. To do this we need to introduce the concept of the quasi-reversed process of a Markov renewal process.

A closed queueing network is constructed where the queue length process is not reversible yet the input process is the reverse process of the output process at each node. Another closed network is constructed where the queue length process is not reversible and the input process is not the reverse process of the output process at a node. From these two examples we conclude that reversibility is not a necessary condition for the input process to be the reverse process of the output process at a node and that the input process is not always the reverse process of the output process. Some implications of these results when applied to the decomposition or recomposition of stochastic processes are discussed.