Acyclic fork-join queuing networks

ABSTRACT

In this paper the class of acyclic fork-join queuing networks that arise in various applications, including parallel processing and flexible manufacturing are studied. In such queuing networks, a fork describes the simultaneous creation of several new customers, which are sent to different queues. The corresponding join occurs when the services of all these new customers are completed. The evolution equations that govern the behavior of such networks are derived. From this, the stability conditions are obtained and upper and lower bounds on the network response times are developed. These bounds are based on various stochastic ordering principles and on the notion of association of random variables.

REFERENCES

• 1: BACCELLI, F. Two parallel queues created by arrivals with two demands: The M/G/2 symmetrical case. Report INRIA, No. 426, July 1985.
• 2: BACCELLI, F., AND BREMAUD, P. Palm probabilities and stationary queues. In Lecture Notes in Statistics, vol. 41, Springer-Verlag, New York, 1987.
• 3: BACCELLI, F., AND MAKOWSKI, A. Simple computable bounds for the fork-join queue. In Proceedings of the Conference oJ lnJormation Science Systems. Johns Hopkins Univ., Baltimore, Md., Mar. I985, pp. 436-44I.
• 4: BACCELLI, F., AND MAKOWSKI, A. Stability and bounds for single server queues in random environment, in Stochasiic/vlodels, vol. 2, no. 2. Marcel Dekker, 1986.
• 5: BACCELLI, F., AND MASSEY, W.A. Series-parallel, fork-join queueing networks and their stochastic ordering. INRIA Report No 534. INRIA, Paris, France, June 1986.
• 6: François Baccelli , Erol Gelenbe , Brigitte Plateau, An End-to-End Approach to the Resequencing Problem, Journal of the ACM (JACM), v.31 n.3, p.474-485, July 1984 [doi>10.1145/828.1883]
• 7: BACCELLI, F., MAKOWSKI, A., AND SHWARTZ, A. Fork-join queue and related systems with synchro_niTation cnn~traint.~: ~qtaehn~tie ordering, approximations and comp,~tnhle bo,,nd~ J. App/. Prob., to appear.
• 8: Francois Baccelli , William A. Massey , Don Towsley, Acyclic Fork-Join Queueing Networks, University of Massachusetts, Amherst, MA, 1987
• 9: BARLOW, R., AND PROSCHAN, F. Statistical theory of reliability and life testing. Holt, Rinehart, and Winston, New York, 1975.
• 10: BRINCH HANSEN, P. The programming language concurrent Pascal. IEEE Trans. Softw. Eng. SE-I (June 1975), 199-207.
• 11: COHEN, J.W. The Single Server Queue. North Holland, Amsterdam, 1982.
• 12: FLATTO, L., AND HAHN, S. Two parallel queues created by arrivals with two demands, }. SIAM J. Appl. Math. 44 (1984), 1041-1053.
• 13: Bruce Hajek, The Proof of a Folk Theorem on Queuing Delay with Applications to Routing in Networks, Journal of the ACM (JACM), v.30 n.4, p.834-851, Oct. 1983 [doi>10.1145/2157.322409]
• 14: IqOARE, C. A.R. Communicating Sequential Processes. Prentice-Hail, London, England, i 985.
• 15: Clyde P. Kruskal , Alan Weiss, Allocating independent subtasks on parallel processors, IEEE Transactions on Software Engineering, v.11 n.10, p.1001-1016, Oct. 1985 [doi>10.1109/TSE.1985.231547]
• 16: LO~Ne~, K. ~v,. The stability of queues with nonindependent interarrival and service times. Proc. Cambridge Phys. Soc. 58 (1962), 497-510.
• 17: MASSEV, W.A. Asymptotic analysis of the time dependent M/M/1 Queue. Math. Oper. Res. I0, i- \ZVAUV t --'~--J~. t.
• 18: R. Nelson , A. N. Tantawi, Approximate Analysis of Fork/Join Synchronization in Parallel Queues, IEEE Transactions on Computers, v.37 n.6, p.739-743, June 1988 [doi>10.1109/12.2213]
• 19: Randolph Nelson , Don Towsley , Asser N. Tantawi, Performance Analysis of Parallel Processing Systems, IEEE Transactions on Software Engineering, v.14 n.4, p.532-540, April 1988 [doi>10.1109/32.4676]
• 20: Ian C. Pyle, ADA Programming Language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 21: ROLSKI, T. Comparison theorems for queues with dependent inter-arrival times. In Modelling and Performance Evaluation Methodology. Lecture Notes in Control and Information Sciences, vol. 60, Springer-Verlag, New York, 1984.
• 22: K. Sigman, Queues as Harris recurrent Markov chains, Queueing Systems: Theory and Applications, v.3 n.2, p.179-198, April 1988 [doi>10.1007/BF01189048]
• 23: STOYAN, D. Comparison Methods for Queues and Other Stochastic Models, English translation, D. J. Daley, ed. Wiley, New York, 1984.
• 24: Don Towsley , Shou Yu, Bounds for Two Server Fork-Join Queueing Systems, University of Massachusetts, Amherst, MA, 1987
• 25: TOWSLEY, O., ROMMEL, J. A., AND STANKOVIC, J. A. The performance of processor sharing schedulding fork-join in multiprocessing.In High-Performance Computer Systems, E.Gelenbe, ed. North-Holland, Amsterdam, 1988, pp. 146-156.
• 26: WmTT, W. Comparing and counting processes and queues. Adv. Appl. Prob. 13 (1981), 207-220.
• 27: WHITT, W. Minimizinga delays in the GI/G/I queue. Oper. Res. 32(1984), 41-51.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Design, Performance, Theory, Verification