Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-26T15:18:11.746Z Has data issue: false hasContentIssue false
  • English
  • Français

ON THE PROBABILITY DISTRIBUTION OF JOIN QUEUE LENGTH IN A FORK-JOIN MODEL

Published online by Cambridge University Press:  19 August 2010

Jun Li  and
Yiqiang Q. Zhao
Jun Li
Affiliation:
Communications Research Centre (CRC) Canada, Ottawa, ON, CanadaK2H 8S2 E-mail: [email protected]
Yiqiang Q. Zhao
Affiliation:
School of Mathematics and Statistics, Carleton University, Ottawa, ON, CanadaK1S 5B6 E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this article, we consider the two-node fork-join model with a Poisson arrival process and exponential service times of heterogeneous service rates. Using a mapping from the queue lengths in the parallel nodes to the join queue length, we first derive the probability distribution function of the join queue length in terms of joint probabilities in the parallel nodes and then study the exact tail asymptotics of the join queue length distribution. Although the asymptotics of the joint distribution of the queue lengths in the parallel nodes have three types of characterizations, our results show that the asymptotics of the join queue length distribution are characterized by two scenarios: (1) an exact geometric decay and (2) a geometric decay with the prefactor n−1/2.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 24 , Issue 4 , October 2010 , pp. 473 - 483
Copyright
Copyright © Cambridge University Press 2010

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.)

References

1.Ayhan, H. & Kim, J.K. (2007). A general class of closed fork and join queues with subexponential service times. Stochastic Models 23: 523–535.CrossRefGoogle Scholar
2.Baccelli, F. (1985). Two parallel queues created by arrivals with two demands: The M/G/2 symmetrical case. Technical report 426, INRIA-Rocquencourt.Google Scholar
3.Baccelli, F., Makowski, A.M., & Shwartz, A. (1989). The fork-join queue and related systems with synchronization constraints: stochastic ordering and computable bounds. Advances in Applied Probability 21: 629–660.CrossRefGoogle Scholar
4.Chao, X. & Zheng, S. (2000). Triggered concurrent batch arrivals and batch departures in queueing networks. Discrete Event Dynamic Systems 10: 115–129.CrossRefGoogle Scholar
5.Chen, R.J. (2001). A hybrid solution of fork/join synchronization in parallel queues. IEEE Transactions on Parallel and Distributed Systems 12: 829–845.CrossRefGoogle Scholar
6.Flatto, L. (1985). Two parallel queues created by arrivals with two demands II. SIAM Journal on Applied Mathematics 45: 861–878.CrossRefGoogle Scholar
7.Flatto, L. & Hahn, S. (1984). Two parallel queues created by arrivals with two demands I. SIAM Journal on Applied Mathematics 44: 1041–1053.CrossRefGoogle Scholar
8.Heidelberger, P. & Trivedi, K.S. (1983). Queueing network models for parallel processing with asynchronous tasks. IEEE Transactions on Computers 32: 73–82.CrossRefGoogle Scholar
9.Ko, S.S. & Serfozo, R.F. (2004). Response times in M/M/s fork-join networks. Advances in Applied Probability 36: 854–871.CrossRefGoogle Scholar
10.Nelson, R. & Tantawi, A.N. (1988). Approximate analysis of fork/join synchronization in parallel queues. IEEE Transactions on Computers 37: 739–743.CrossRefGoogle Scholar
11.Nelson, R. & Towsley, D. (1993). A performance evaluation of several priority policies for parallel processing systems. Journal of the ACM 40: 714–740.CrossRefGoogle Scholar
12.Pinotsi, D. & Zazanis, M.A. (2005). Synchronized queues with deterministic arrivals. Operations Research Letters 33: 560–566.CrossRefGoogle Scholar
13.Song, J.S., Xu, S.H., & Liu, B. (1999). Order-fulfillment performance measures in an assemble-to-order system with stochastic leadtimes. Operations Research 47: 131–149.CrossRefGoogle Scholar
14.Shwartz, A. & Weiss, A. (1993). Induced rare events: analysis via large deviations and time reversal. Advances in Applied Probability 25: 667–689.CrossRefGoogle Scholar
15.Tan, X. & Knessl, C. (1996). A fork-join queueing model: Diffusion approximation, integral representations and asymptotics. Queueing Systems 22: 287–322.CrossRefGoogle Scholar
16.Varki, E. (1999). Mean value technique for closed fork-join networks. ACM SIGMETRICS Performance Evaluation Review 27: 103–112.CrossRefGoogle Scholar
17.Varma, S. & Makowski, A.M. (1994). Interpolation approximation for symmetric fork-join queues. Performance Evaluation 20: 245–265.CrossRefGoogle Scholar
18.Wright, P.E. (1992). Two parallel queues with coupled inputs. Advances in Applied Probability 24: 986–1007.CrossRefGoogle Scholar
19.Zhang, Z. (1990). Analytical results for waiting time and system size distributions in two parallel queueing systems. SIAM Journal on Applied Mathematics 50: 1176–1193.CrossRefGoogle Scholar