Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T11:17:34.266Z Has data issue: false hasContentIssue false

Characterizations of Poisson traffic streams in Jackson queueing networks

Published online by Cambridge University Press:  01 July 2016

Benjamin Melamed*
Affiliation:
Northwestern University
*
Postal address: Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60201, U.S.A.

Abstract

The equilibrium behavior of Jackson queueing networks (Poisson arrivals, exponential servers and Bernoulli switches) has recently been investigated in some detail. In particular, it was found that in equilibrium, the traffic processes on the so-called exit arcs of a Jackson network with single server nodes constitute Poisson processes—a result extending Burke's theorem from single queues to networks of queues.

A conjecture made by Burke and others contends that the traffic processes on non-exit arcs cannot be Poisson in equilibrium. This paper proves this conjecture to be true for a variety of Jackson networks with single server nodes. Subsequently, a number of characterizations of the equilibrium traffic streams on the arcs of open Jackson networks emerge, whereby Poisson-related stochastic properties of traffic streams are shown to be equivalent to a simple graph-theoretical property of the underlying arcs. These results then help to identify some inherent limitations on the feasibility of equilibrium decompositions of Jackson networks, and to point out conditions under which further decompositions are ‘approximately’ valid.

Type
Research Article
Copyright
Copyright © Applied Probability Trust 1979 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This research was partially supported by NSF Grant ENG-75-20223, Air Force Office of Scientific Research Grant AFOSR-76-2903, and by the Office of Naval Research Contract N00014-75-C-0492 (NR 042-296).

References

1. Barbour, A. D. (1976) Networks of queues and the method of stages. Adv. Appl. Prob. 8, 584591.Google Scholar
2. Beutler, F. J., Melamed, B. and Zeigler, B. P. (1977 Equilibrium properties of arbitrarily interconnected queueing networks. In Multivariate Analysis IV, ed. Krishnaiah, P. R. North-Holland, Amsterdam.Google Scholar
3. Beutler, F. J. and Melamed, B. (1978) Decomposition and customer streams of feedback queueing networks in equilibrium. Opns Res. 26, 10591072.Google Scholar
4. Burke, P. J. (1956) The output of a queueing system. Opns Res. 4, 699704.CrossRefGoogle Scholar
5. Burke, P. J. (1972) Output processes and tandem queues. In Proceedings of the Symposium on Computer Communications Networks and Teletraffic, ed. Fox, J. Polytechnic Press, Brooklyn, N.Y. Google Scholar
6. Burke, P. J. (1976) Proof of a conjecture on the interarrival-time distribution in an M/M/1 queue with feedback. IEEE Trans. Comm. Google Scholar
7. Disney, R. L., Farrell, R. L. and Demorais, P. R. (1973) A characterization of M/G/1 queues with renewal departure processes. Management Sci. 19, 12221228.Google Scholar
8. Gordon, W. J. and Newell, G. F. (1967) Closed queueing systems with exponential servers. Opns Res. 15, 254265.Google Scholar
9. Jackson, J. R. (1957) Networks of waiting lines. Opns Res. 5, 518521.CrossRefGoogle Scholar
10. Jackson, R. R. P. (1956) Random queueing processes with phase-type service. J. R. Statist. Soc. B 18, 129132.Google Scholar
11. Kelly, F. P. (1975) Networks of queues with customers of different types. J. Appl. Prob. 12, 542554.Google Scholar
12. Kelly, F. P. (1976) Networks of queues. Adv. Appl. Prob. 8, 416432.Google Scholar
13. Melamed, B. (1976) Analysis and Simplifications of Discrete Event Systems and Jackson Queueing Networks. Doctoral Dissertation, Technical Report No. 195, Dept. of CCS, University of Michigan, Ann Arbor.Google Scholar
14. Melamed, B. (1979) On Poisson traffic processes in discrete-state Markovian systems with applications to queueing theory. Adv. Appl. Prob. 11, 218239.Google Scholar
15. Muntz, R. R. (1972) Poisson departure processes and queueing networks. IBM Research Report RC4145, December 1972.Google Scholar
16. Reich, E. (1957) Waiting times when queues are in tandem. Ann. Math. Statist. 28, 768773.Google Scholar
17. Saaty, T. L. (1965) Stochastic network flows: advances in networks of queues. In Proceedings of the Symposium on Congestion Theory, ed. Smith, W. L. and Wilkinson, W. E., University of North Carolina Press, Chapel Hill, 76107.Google Scholar