Strong approximations for multiclass feedforward queueing networks. (English) Zbl 1083.60511

Summary: This paper derives the strong approximation for a multiclass queueing network,where jobs after service completion can only move to a downstream service station. Job classes are partitioned into groups. Within a group, jobs are served in the order of arrival; that is, a first-in first-out (FIFO) discipline is in force, and among groups, jobs are served under a preassigned preemptive priority discipline. We obtain the strong approximation for the network through an inductive application of an input/output analysis for a single-station queue. Specifically, we show that if the input data (i.e., the arrival and the service processes) satisfy an approximation (such as the functional law-of-iterated logarithm approximation or the strong approximation), then the output data (i.e., the departure processes) and the performance measures (such as the queue length, the workload and the sojourn time processes) satisfy a similar approximation. Based on the strong approximation, some procedures are proposed to approximate the stationary distribution of various performance measures of the queueing network. Our work extends and complements the existing work of Peterson and Harrison and Williams on the feedforward queueing network. The numeric examples show that strong approximation provides a better approximation than that suggested by a straightforward interpretation of the heavy traffic limit theorem.


60F17 Functional limit theorems; invariance principles
90B22 Queues and service in operations research
60G17 Sample path properties
60J70 Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.)
60K25 Queueing theory (aspects of probability theory)
Full Text: DOI Euclid


[1] Billingsley, P. (1968). Convergence of Probability Measures. Wiley, New York. · Zbl 0172.21201
[2] Chen, H. (1996). A sufficient condition for the positive recurrence of a semimartingale reflecting Brownian motion in an orthant. Ann.Appl.Probab. 6 758-765. · Zbl 0860.60062
[3] Chen, H. and Mandelbaum, A. (1994). Hierarchical modeling of stochastic networks II. Strong approximations. In Stochastic Modeling and Analysis of Manufacturing Systems (D. D. Yao, ed.) 107-131. Springer, Berlin.
[4] Cs örg o, M. and Horváth, L. (1993). Weighted Approximations in Probability and Statistics. Wiley, New York. · Zbl 0770.60038
[5] Dai, J. G. and Harrison, J. M. (1992). Reflected Brownian motion in an orthant: numerical methods for steady-state analysis. Ann.Appl.Probab. 2 65-86. · Zbl 0786.60107
[6] Fendick, K. W., Saksena, V. R. and Whitt, W. (1989). Dependence in packet queues. IEEE Trans. Communications 37 1173-1183.
[7] Glynn, P. W. (1990). Diffusion approximations. In Handbooks in Operations Research and Management Science 2.Stochastic Models (D. P. Heyman and M. J. Sobel, eds.) 145-198. North-Holland, Amsterdam. · Zbl 0703.60072
[8] Harrison, J. M. (1985). Brownian Motion and Stochastic Flow Systems. Wiley, New York. · Zbl 0659.60112
[9] Harrison, J. M. and Nguyen, V. (1993). Brownian models of multiclass queueing networks: current status and open problems. Queueing Systems Theory Appl. 13 5-40. · Zbl 0781.60090
[10] Harrison, J. M. and Williams, R. J. (1992). Brownian models of feedforward queueing networks: quasireversibility and product form solutions. Ann.Appl.Probab.2 263-293. · Zbl 0753.60071
[11] Horváth, L. (1990). Strong approximations of open queueing networks. Math Oper.Res. 17 487-508. · Zbl 0758.60099
[12] Kleinrock, L. (1976). Queueing Systems 2.Computer Applications. Wiley, New York. · Zbl 0361.60082
[13] Lemoine, A. J. (1978). Network of queues-a survey of weak convergence results. Management Sci. 24 1175-1193. · Zbl 0396.60088
[14] Mandelbaum, A. and Massey, W. A. (1995). Strong approximation for time-dependent queues. Math.Oper.Res. 20 33-64. JSTOR: · Zbl 0834.60096
[15] Mandelbaum, A., Massey, W. A. and Reiman, M. (1998). Strong approximation for Markov service networks. Queueing Systems Theory Appl. 30 149-201. · Zbl 0911.90167
[16] Mandelbaum, A. and Pats, G. (1998). Stochastic networks I. Approximations and applications with continuous diffusion limits. Ann.Appl.Probab. 8 569-646. · Zbl 0945.60025
[17] Peterson, W. P. (1991). A heavy trafficlimit theorem for networks of queues with multiple customer types. Math.Oper.Res. 16 90-118. JSTOR: · Zbl 0727.60114
[18] Shen, X. (2000). Performance evaluation of multiclass queueing networks via Brownian motions. Ph.D. thesis, Univ. British Columbia.
[19] Whitt, W. (1974). Heavy traffictheorems for queues: a survey. In Mathematical Methods in Queueing Theory (A. B. Clarke, ed.) 307-350. Springer, New York. · Zbl 0295.60081
[20] Whitt, W. (1980). Some useful functions for functional limit theorems. Math.Oper.Res. 5 67-85. JSTOR: · Zbl 0428.60010
[21] Williams, R. J. (1996). On the approximation of queueing networks in heavy traffic. In Stochastic Networks: Theory and Applications (F. P. Kelly, S. Zachary and I. Ziedins, eds.) 35-56. Oxford Univ. Press. · Zbl 0855.60083
[22] Zhang, H. (1997). Strong approximations for irreducible closed queueing networks. Adv.in Appl. Probab. 29 498-522. JSTOR: · Zbl 0905.60069
[23] Zhang, H., Hsu, G. and Wang, R. (1990). Strong approximations for multiple channel queues in heavy traffic. J.Appl.Probab. 28 658-670. JSTOR: · Zbl 0715.60113
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.