×

A fork-join queueing model: Diffusion approximation, integral representations and asymptotics. (English) Zbl 0860.60078

Summary: We consider two parallel \(M/M/1\) queues which are fed by a single Poisson arrival stream. An arrival splits into two parts, with each part joining a different queue. This is the simplest example of a fork-join model. After the individual parts receive service, they may be joined back together, though we do not consider the join part here. We study this model in the heavy traffic limit, where the service rate in either queue is only slightly larger than the arrival rate. In this limit, we obtain asymptotically the joint steady-state queue length distribution. In the symmetric case, where the two servers are identical, this distribution has a very simple form. In the non-symmetric case, we derive several integral representations for the distribution. We then evaluate these integrals asymptotically, which leads to simple formulas which show the basic qualitative structure of the joint distribution function.

MSC:

60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. Flatto and S. Hahn, Two parallel queues created by arrivals with two demands I, SIAM J. Appl. Math. 44 (1984) 1041-1054. · Zbl 0554.90041 · doi:10.1137/0144074
[2] L. Flatto, Two parallel queues created by arrivals with two demands II, SIAM J. Appl. Math. 45 (1985) 861-878. · Zbl 0579.90033 · doi:10.1137/0145052
[3] Z. Zhang, Analytic results for waiting time and system size distributions in two parallel queueing systems, SIAM J. Appl. Math. 50 (1990) 1176-1193. · Zbl 0701.60090 · doi:10.1137/0150071
[4] F. Baccelli, Two parallel queues created by arrivals with two demands: the M/G/2 symmetrical case, INRIA Report, No. 426, Rocquencourt, Le Chesnay, France (July 1986).
[5] S.J. DeKlein, Two parallel queues with simultaneous service demands, Report No. 360, Department of Mathematics, University of Utrecht, Utrecht, the Netherlands (December 1984).
[6] F. Baccelli and A. Makowski, Simple computable bounds for the fork-join queue,Proc. Johns Hopkins Conf. on Information Science, The Johns Hopkins University, Baltimore, MD (1985) pp. 436-441.
[7] R. Nelson and A.N. Tantawi, Approximate analysis of fork-join synchronization in parallel queues, IEEE Trans. Comput. 37 (1988) 739-743. · doi:10.1109/12.2213
[8] A. Duda and T. Czachorski, Performance evaluation of fork and join synchronization primitives, Acta. Inform. 24 (1987) 525-553. · Zbl 0625.68025 · doi:10.1007/BF00263293
[9] G.J. Foschini, Equilibria for diffusion models for pairs of communicating computers-symmetric case, IEEE Trans. Inform. Theory 28 (1982) 273-284. · Zbl 0476.68030 · doi:10.1109/TIT.1982.1056473
[10] J.A. Morrison, Diffusion approximation for head-of-the-line processor sharing for two parallel queues, SIAM J. Appl. Math. 53 (1993) 471-490. · Zbl 0768.60093 · doi:10.1137/0153028
[11] C. Knessl, On the diffusion approximation to a fork and join queueing model, SIAM J. Appl. Math. 51 (1991) 160-171. · Zbl 0716.60111 · doi:10.1137/0151010
[12] I.S. Gradshteyn and I.M. Ryzhik,Table of Integrals, Series and Products, 5th Ed. (Academic Press, Boston, 1994). · Zbl 0918.65002
[13] F. Baccelli and G. Fayolle, Analysis of models reducible to a class of diffusion processes in the positive quarter plane, SIAM J. Appl. Math. 47 (1987) 1367-1385. · Zbl 0634.60085 · doi:10.1137/0147090
[14] C.M. Bender and S.A. Orszag,Advanced Mathematical Methods for Scientists and Engineers (McGraw-Hill, New York, 1986). · Zbl 0417.34001
[15] N. Bleistein and R.A. Handelsman,Asymptotic Expansions of Integrals (Dover, New York, 1986). · Zbl 0327.41027
[16] R. Nelson, D. Towsley and A.N. Tantawi, Performance analysis of parallel processing systems, IEEE Trans. Software Eng. 14 (1988) 532-540. · Zbl 05113615 · doi:10.1109/32.4676
[17] F. Baccelli, A. Makowski and A. Schwartz, The fork-join queue and related systems with synchronization constraints: stochastic ordering, approximations and computable bounds, Adv. Appl. Probab. 21 (1989) 629-660. · Zbl 0681.60096 · doi:10.2307/1427640
[18] S. Varma, Heavy and light traffic approximations for queues with synchronization constraints, Ph.D. Dissertation, Department of Electrical Engineering, University of Maryland.
[19] V. Nguyen, Processing networks with parallel and sequential tasks: heavy traffic analysis and Brownian limits, Ann. Appl. Prob. 3 (1993) 28-55. · Zbl 0771.60082 · doi:10.1214/aoap/1177005506
[20] P. Wright, Two parallel processors with coupled inputs, Adv. Appl. Prob. 24 (1992) 986-1007. · Zbl 0760.60093 · doi:10.2307/1427722
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.