Networks of Queues: Product Form Solution
Jeremiah F. Hayes, Thimma V. J. Ganesh Babu · 2004
Time reversibility is used to prove Burke's theorem, which, in turn is used to show that the queues in feed-forward networks, with Poisson inputs and random routing, have joint probability distribution of number of messages in queues as that of all independent M/M/S queues(product form). By deriving a multi-dimensional Kolmogorov equation it is shown that the result applies to open networks with feedback satisfying certain general conditions. These are the Jackson networks. The result is used to find the average delay in networks, given routing and input flows to the network. The average delay is minimized by an optimum allocation of capacity in the links in the network. The same results are then derived for closed networks of queues. The next step in the development is extending the model from FCFS nodes with exponential servers to arbitrary service and the processor sharing, infinite service and LCFS disciplines. The results are applied to forward packet switching nodes, window flow control and cellular wireless.