Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T22:25:48.478Z Has data issue: false hasContentIssue false
  • English
  • Français

Response times in M/M/s fork-join networks

Part of: Special processes

Published online by Cambridge University Press:  01 July 2016

Sung-Seok Ko  and
Richard F. Serfozo
Sung-Seok Ko*
Affiliation:
Samsung SDS
Richard F. Serfozo*
Affiliation:
Georgia Institute of Technology
*
∗ Postal address: Samsung SDS Co. Ltd, 707-719 Yoksam-2 Dong, Kangnam-Gu, Seoul, Korea 135-918. Email address: sungseok@hotmail.com
∗∗ Postal address: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA. Email address: rserfozo@isye.gatech.edu
Get access Rights & Permissions [Opens in a new window]

Abstract

We study a fork-join processing network in which jobs arrive according to a Poisson process and each job splits into m tasks, which are simultaneously assigned to m nodes that operate like M/M/s queueing systems. When all of its tasks are finished, the job is completed. The main result is a closed-form formula for approximating the distribution of the network's response time (the time to complete a job) in equilibrium. We also present an analogous approximation for the distribution of the equilibrium queue length (the number of jobs in the system), when each node has one server. Kolmogorov-Smirnov statistical tests show that these formulae are good fits for the distributions obtained from simulations.

Keywords

Fork-join networkqueueingcommunications networkassembly networkparallel processingsynchronizationsupply chainlittle law for distributions

MSC classification

Primary: 60K20: Applications of Markov renewal processes (reliability, queueing networks, etc.)
Secondary: 60K25: Queueing theory

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 36 , Issue 3 , September 2004 , pp. 854 - 871
Copyright
Copyright © Applied Probability Trust 2004 

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

Article purchase

Temporarily unavailable

References

[1] Ayhan, H. and Seo, D. W. (2001). Laplace transform and moments of waiting times in (max,+) linear systems with Poisson input. Queueing Systems 37, 405–438.Google Scholar
[2] Baccelli, F. and Brémaud, P. (1994). Elements of Queueing Theory. Springer, New York.Google Scholar
[3] Baccelli, F. and Makowski, A. M. (1985). Simple computable bounds for the fork–join queue. In Proc. Johns Hopkins Conf. Inf. Sci., Johns Hopkins University Press, Baltimore, MD.Google Scholar
[4] Baccelli, F., Makowski, A. M. and Shwartz, A. (1989). The fork–join queue and related systems with synchronization constraints: stochastic ordering and computable bounds. Adv. Appl. Prob. 21, 629–660.Google Scholar
[5] Balsamo, S., Donatietllo, L. and Van Dijk, N. M. (1998). Bound performance models of heterogeneous parallel processing systems. IEEE Trans. Parallel Distributed Systems 9, 1041–1056.CrossRefGoogle Scholar
[6] Chen, R. J. (2001). A hybrid solution of fork/join synchronization in parallel queues. IEEE Trans. Parallel Distributed Systems 12, 829–845.CrossRefGoogle Scholar
[7] Flatto, L. (1985). Two parallel queues created by arrivals with two demands II. SIAM J. Appl. Math. 45, 861–878.Google Scholar
[8] Flatto, L. and Hahn, S. (1984). Two parallel queues created by arrivals with two demands I. SIAM J. Appl. Math. 44, 1041–1053. Erratum: 45, 168 (1985).Google Scholar
[9] Haji, R. and Newell, G. F. (1971). A relation between stationary queue and waiting time distributions. J. Appl. Prob. 8, 617–620.Google Scholar
[10] Knessl, C. (1991). On the diffusion approximation to a fork and join queueing model. SIAM J. Appl. Math. 51, 160–171.Google Scholar
[11] Konstantopoulos, P. and Walrand, J. (1989). Stationary and stability of fork–join networks. J. Appl. Prob. 26, 604–614.Google Scholar
[12] Krishnamurthy, A., Suri, R. and Vernon, M. (2004). Analysis of a fork/join synchronization station with inputs from Coxian servers in a closed queueing network. Ann. Operat. Res. 125, 69–94.Google Scholar
[13] Kulkarni, V. G. (1995). Modeling and Analysis of Stochastic Systems. Chapman and Hall, London.Google Scholar
[14] Kumar, A. and Shorey, R. (1993). Performance analysis and scheduling of stochastic fork–join jobs in a multicomputer system. IEEE Trans. Parallel Distributed Systems 4, 1147–1164.Google Scholar
[15] Kushner, H. J. (2001). Heavy Traffic Analysis of Controlled Queueing and Communication Networks (Appl. Math. (New York) 47). Springer, New York.Google Scholar
[16] Law, A. M. and Kelton, W. D. (1991). Simulation Modeling and Analysis. McGraw-Hill, New York.Google Scholar
[17] Nelson, R. and Tantawi, A. N. (1988). Approximation analysis of fork/join synchronization in parallel queues. IEEE Trans. Comput. 37, 739–743.Google Scholar
[18] Nguyen, V. (1993). Processing networks with parallel and sequential tasks: heavy traffic analysis and Brownian limits. Ann. Appl. Prob. 3, 28–55.CrossRefGoogle Scholar
[19] Raghavan, N. R. S. and Viswanadham, N. (2001). Generalized queueing network analysis of integrated supply chains. Internat. J. Production Res. 39, 205–224.Google Scholar
[20] Ross, S. M. (1996). Stochastic Processes, 2nd edn. John Wiley, New York.Google Scholar
[21] Serfozo, R. F. (1999). Introduction to Stochastic Networks (Appl. Math. (New York) 44). Spinger, New York.Google Scholar
[22] Tan, X. and Knessl, C. (1996). A fork–join queueing model: diffusion approximation, integral representations and asymptotics. Queueing Systems 22, 287–322.Google Scholar
[23] Varma, S. and Makowski, A. (1994). Interpolation approximations for symmetric fork–join queues. Perform-ance Evaluation 20, 245–265.Google Scholar
[24] Zhang, Z. (1990). Analytical results for waiting time and system size distributions in two parallel queueing systems. SIAM J. Appl. Math. 50, 1176–1193.Google Scholar