Equivalence, reversibility, symmetry and concavity properties in fork-join queuing networks with blocking

ABSTRACT

In this paper, we study quantitative as well as qualitative properties of Fork-Join Queuing Networks with Blocking (FJQN/Bs). Specifically, we prove results regarding the equivalence of the behavior of a FJQN/B and that of its duals and a strongly connected marked graph. In addition, we obtain general conditions that must be satisfied by the service times to guarantee the existence of a long-term throughput and its independence on the initial configuration. We also establish conditions under which the reverse of a FJQN/B has the same throughput as the original network. By combining the equivalence result for duals and the reversibility result, we establish a symmetry property for the throughput of a FJQN/B. Last, we establish that the throughput is a concave function of the buffer sizes and the initial marking, provided that the service times are mutually independent random variables belonging to the class of PERT distributions that includes the Erlang distributions. This last result coupled with the symmetry property can be used to identify the initial configuration that maximizes the long-term throughput in closed series-parallel networks.

REFERENCES

• 1: M. H. Ammar , S. B. Gershwin, Equivalence relations in queueing models of fork/join networks with blocking, Performance Evaluation, v.10 n.3, p.233-245, December 1989 [doi>10.1016/0166-5316(89)90013-8]
• 2: ~ANANTHARAM, V., AND TSOUCAS, P. 1990. Stochastic concavity of throughput in series of queues ~with finite buffers. Adt,. Appl. Prob. 22, 761-763.
• 3: Gregory R. Andrews , Fred B. Schneider, Concepts and Notations for Concurrent Programming, ACM Computing Surveys (CSUR), v.15 n.1, p.3-43, March 1983 [doi>10.1145/356901.356903]
• 4: ~BACCELLI, F. (1992). Ergodic theory of stochastic Petn networks, Ann. Prob. 20, 1,350 374.
• 5: ~BACCELL1, F., BAMBOS, N., AND WALRAND, J. 1991. On flows in stochastic Markov graphs. Prob. ~Eng. Inf. Set. 5, 145-157.
• 6: François Baccelli , Zhen Liu, On the execution of parallel programs on multiprocessor systems—a queuing theory approach, Journal of the ACM (JACM), v.37 n.2, p.373-414, April 1990 [doi>10.1145/77600.77622]
• 7: ~BACCELLI, P., AND LlU, Z. 1992a On a class of stochastic recursive sequences arising in queueing ~theory. Ann. Prob. 20, 350-374.
• 8: ~BACCELLI, F., AND LIU, Z. 1992b Comparison properties of stochastic decision free Petri nets. ~IEEE Trans. Auto. Cont. 37, 1905-1920,
• 9: ~BACCELLI, F., AND MAKOWSKI, A. 1989. Queueing models for systems with synchronization ~constraints. Proc. {EEL' 77, (Jan.), 138-161.
• 10: François Baccelli , William A. Massey , Don Towsley, Acyclic fork-join queuing networks, Journal of the ACM (JACM), v.36 n.3, p.615-642, July 1989 [doi>10.1145/65950.65957]
• 11: ~BHARGAVA, i., KUROSE, J. F., TOWSLEY, D., AND VANLEEMPUT, G. 1988. Performance compari- ~son of error control schemes in high speed computer communication networks. IEEE J. Sel. ~Areas Commun. 6, 9 (Dec.), 1565-1575.
• 12: ~CASEAU, P., AND PUJOLLE, G. 1979. Throughput capacity of a sequence of queues with blocking ~due to finite waiting room. IEEE Trans. Softw. Eng. 5, 631 642.
• 13: ~COMMONER, F., HOLT, i. W., EVEN, 8., AND PNUELLY, A. 1971. Marked directed graphs. J. ~Comput. Syst. Set. 5, 511-523.
• 14: Yves Dallery , Stanley B. Gershwin, Manufacturing flow line systems: a review of models and analytical results, Queueing Systems: Theory and Applications, v.12 n.1-2, p.3-94, Dec. 1992 [doi>10.1007/BF01158636]
• 15: ~DALLERY, Y., AND TOWSLEY, D. 1991. Symmetry property of the throughput in closed tandem ~queueing networks with finite buffers. Oper. Res. Lett. 10, 9 (Dec.), 541-547.
• 16: ~DALLERY, Y., LlW, Z., AND TOWSLEY, D. 1992. Properties of fork/join queueing networks with ~blocking under various operating mechanisms. Tech. Rep. COINS 92-39. Univ. Massachusetts ~at Amherst, Amherst, Mass., May.
• 17: ~DIMASCOLO, M., DAVID, R., AND DALLER~, Y. 1991. Modeling and analysis of assembly systems ~with unreliable machines and finite buffers, lie Trans. 23, 4, 315-330.
• 18: ~FDIDA, S., PERROS, H. G., AND WlLK, A. 1990. Semaphore queues: Modelling multllayered ~window flow control mechanisms. IEEE Trans. Comnum. 38, 3, 309-317.
• 19: ~GAVER, D. P, 1962. A waiting line with interrupted service, including priorities. J.R. Stat Soc., ~Set. B 24, 73-90.
• 20: ~GERSHW1N, S. B. 1988/1989. Assembly/disassembly systems: An efficient decomposition algo- ~rithm for tree-structured network. MIT Lab. for Manufacturing and Productivity Report, ~LMP-88-007.
• 21: ~GORDON, W. J., AND NEWELL, G. F. 1967. Cyclic queueing systems with restricted length queues, ~Oper. Res. 15, 266-278.
• 22: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 23: ~KELLY, F. P. 1979. Reuersibi{tty and Stochastic Networl~'. Wiley, New York.
• 24: ~KINGM&N, J. F. C- 1968. The ergodic theory of subadditive processes. J. Royal Statist. Soc., Ser. B ~30, 499-510.
• 25: ~MEgSTER, L. E., AND SHANTHIKUMAR, J. G. 1990. Concavity of the throughput of tandem ~queueing systems with finite buffer storage space. Adv. Appl. ,Prob. 22,764-767.
• 26: Benjamin Melamed, A note on the reversibility and duality of some tandem blocking queueing systems, Management Science, v.32 n.12, p.1648-1650, Dec. 1986
• 27: ~MURATA, T. 1989. Petri nets: Properties, analysis and applications. Prec. IEISE 77, 4 (Apr.), ~541-579.
• 28: ~MUTH, E. G. 1079. The reversibility property of production lines. 3latzage Scz. 25, 2, 152-158.
• 29: 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 ]
• 30: ~NEUTS, M. 1981, Matrix-Geometric Sohtttotls z~z Stocha,stw Models. Johns Hopkins, Baltimore, Md.
• 31: V F Nicola, A single server queue with mixed types of interruptions, Acta Informatica, v.23 n.4, p.465-486, July 1986 [doi>10.1007/BF00267867]
• 32: ~ONVURAL, R, O., AND PERROS, H. G. 1987. Throughput analysis of cyclic queuemg networks ~with finite buffers. Fech. Rep. CS Dept. 87-03. NCSU, Raleigh, N.C.
• 33: James Lyle Peterson, Petri Net Theory and the Modeling of Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1981
• 34: ~PLRROS, H. G. 1989. Approximation algorithms for open queuemg networks w~th blocking In ~Stochastzc Analysts oj Computer wid Commutucatto~t 5)'stems, H Takagi, ed. North-Holland, ~Amsterdam, The Netherlands.
• 35: P5 kE, I. C. 1981. The Ada Program,ttng Language. Prentice-Hall International, London. ~RAMAMOORTHY, C. V., AND He, G. S. 1980. Performance evaluation of asynchronous concurrent ~systems using Petri nets. IEEE Trans SQ/tw. Etzg. SE-6, 440-449
• 36: ~SHANTH/KUMAR, J G., AND YAO. W. W 1989. Monotonicity and concavity properties in cyclic ~queueing networks with finite buffers. In Qtteuebtg Networks wtth Blocking, H. G Perros, and T. ~Altiok. eds. North-Holland. 325-344.
• 37: ~SEVAST'~ANOV, B. h. 1962. Influence of storage bin capacity on the average standstill time of a ~production line. TheeO' Prob. AptvL 7, 4, 429 438.
• 38: ~WAkV, AND, J. 1988. Air lntroductlo~l to Queuetng Networks. Prentice-Hail, Englewood Cliffs, N.J.
• 39: ~YAMAZAKI, G., KAWASHIHA, T., AND 8AKASEGAWA, H. 1985. Reversibihty of tandem blocking ~queueing systems, Manage. Sc'l 31, 1, 78-83.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

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

General Terms:
Performance

Keywords:
Fork-Join queuing networks, blocking before service, concavity, duality, equivalence, marked graphs, queuing theory, symmetry, throughput