Diffusion Limits for the Queue Length of Jobs in Multiserver Open Queueing Networks

• Autorzy: Edvinas Greičius , Saulius Minkevičius
• Języki publikacji: EN

Abstrakty

EN

A mathematical model of a multiserver open queueing network in heavy traffic is developed. This model is that of a multiserver computer system network in heavy traffic. A limit theorem for the length of the queue has been presented. (original abstract)

Słowa kluczowe

EN

Mathematical models; Computer systems

PL

Modele matematyczne; Systemy komputerowe

• Czasopismo: Operations Research and Decisions
• Rocznik: 2017
• Tom: 27
• Numer: nr 4
• Strony: 71--84

Twórcy

autor

Edvinas Greičius

• Vilnius University, Vilnius, Lithuania

autor

Saulius Minkevičius

• Vilnius University, Vilnius, Lithuania

Bibliografia

• [1] BILLINGSLEY P., Convergence of Probability Measures, Wiley, 1968.
• [2] BOROVKOV A.A., Asymptotic methods in queueing theory, Nauka, Moscow 1980 (in Russian).
• [3] BOROVKOV A.A., Stochastic processes in queueing theory, Nauka, Moscow 1972 (in Russian).
• [4] BOXMA O., On a tandem queueing model with identical service times at both counters, I, II, Adv. Appl. Prob., 1979, 11 (3), 616-643, 644-659.
• [5] BRAMSON M., DAI J.G., Heavy traffic limits for some queueing networks, Ann. Appl. Prob., 2001, 11 (1), 49-90.
• [6] BRAMSON M., State space collapse with application to heavy traffic limits for multiclass queuing networks, Queuing Sys., 1998, 30 (1, 2), 89-140.
• [7] CHEN H., MALDELBAUM A., Stochastic discrete flow networks. Diffusion approximations and bottlenecks, Ann. Appl. Prob., 1991, 19 (4), 1463-1519.
• [8] CHEN H., YAO D.D., Fundamentals of Queueing Networks. Performance, Asymptotics and Optimization, Springer-Verlag, New York 2001.
• [9] CHEN H., ZHANG H., A sufficient condition and a necessary condition for the diffusion approximations of multiclass queueing networks under priority service disciplines, Queing Syst., Theory Appl., 2000, 34 (1-4), 237-268.
• [10] CHEN H., YE H.Q., Existence condition for the diffusion approximations of multiclass priority queueing networks, Queueing Syst., Theory Appl., 2001, 38, 435-470.
• [11] CHEN H., Fluid approximations and stability of multiclass queuing networks: work-conserving disciplines, Ann. Applied Probability., 1995, 5 (3), 637-665.
• [12] DAI J.G., Stability of open multiclass queuing networks via fluid models, F. Kelly, R. Williams (Eds.), Proc. IMA Workshop on Stochastic Networks, Springer-Verlag, New York 2000, 100-121.
• [13] DAI J.G., On positive Harris recurrence of multiclass queueing networks. A unified approach via unified fluid limit models, Ann. Appl. Prob., 1995, 5 (1), 49-77.
• [14] FLORES C., Diffusion approximations for computer communications networks, [In:] B. Gopinath (Ed.), Comp. Comm., Proc. Syrup. Appl. Math., American Mathematical Society, 1985, 83-124.
• [15] GLYNN E.M., Diffusion approximations, [In:] D.P. Heyman, M.J. Sobel (Eds.), Handbooks in Operations Research and Management Science, Vol. 2. Stochastic Models, Elsevier, 1990.
• [16] HARRISON J.M., LEMOINE A.J., A note on networks of infinite-server queues, J. Appl. Prob., 1981, 18, 561-567.
• [17] HARRISON J.M., Brownian Motion and Stochastic Flow Processes, Wiley, New York 1985.
• [18] HARRISON J.M., A broader view of Brownian networks, Ann. Appl. Prob., 2003, 13 (3), 1119-1150.
• [19] HARRISON J.M., NQUYEN V., Brownian models of multiclass queueing networks: current status and open problems, Queueing Syst., Theory Appl., 1993, 13, 5-40.
• [20] IGLEHART D., Weak convergence in queueing theory, Adv. Appl. Prob., 1973, 5, 570-594.
• [21] IGLEHART D., WHITT W., Multiple channel queues in heavy traffic, Adv. Appl. Prob., 1970, 2, 150-177.
• [22] IGLEHART D., WHITT W., Multiple channel queues in heavy traffic. II. Sequences, networks and batches, Adv. Appl. Prob., 1970, 2, 355-369.
• [23] JOHNSON D.P., Diffusion Approximations for Optimal Filtering of Jump Processes and for Queueing Networks, PhD Diss., University of Wisconsin, 1983.
• [24] KANG W.N., KELLY F.P., LEE N.H., WILLIAMS R.J., State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy, Ann. Appl. Probab., 2009, 19 (5), 1719-1780.
• [25] KARPELEVICH F., KREININ A., Heavy traffic limits for multiphase queues, Amer. Math. Soc., Providence, Rhode Island, 1994.
• [26] KINGMAN J., On queues in heavy traffic, J. R. Statist. Soc., 1962, 24, 383-392.
• [27] KINGMAN J., The single server queue in heavy traffic, Proc. Camb. Phil. Soc., 1962, 57, 902-904.
• [28] KOBYASHI H., Application of the diffusion approximation to queueing networks, J. ACM, 1974, 21, 316-328.
• [29] KOLMOGOROV A.N., Foundations of the Theory of Probability, 2nd Ed., Chelsea Publishing Company, New York 1956.
• [30] LEMOINE A.J., Network of queues. A survey of weak convergence results, Manage. Sci., 1978, 24, 1175-1193.
• [31] MANDELBAUM A., STOLYAR A.L., Scheduling flexible servers with convex delay costs: heavy-traffic optimality of the generalized cμ rule, Oper. Res., 2004, 52, 6, 836-855.
• [32] MINKEVIČIUS S., Weak convergence in multiphase queues, Liet. Mat. Rink., 1986, 26, 717-722 (in Russian).
• [33] MINKEVIČIUS S., Complex transient phenomena in multiphase queueing systems, Liet. Mat. Rink., 1999, 39 (3), 343-356 (in Russian).
• [34] MINKEVIČIUS S., On the law of the iterated logarithm in multiserver open queueing networks, Stochastics, 2013, 86 (1), 46-59.
• [35] PROHOROV Y., Transient phenomena in queues, Liet. Mat. Rink., 1963, 3, 199-206 (in Russian).
• [36] REIMAN M., Open queueing networks in heavy traffic, Math. Oper. Res., 1984, 9, 441-459.
• [37] RYBKO A.N., STOLYAR A.L., Ergodicity of stochastic processes describing the operation of open queuing networks, Probl. Peredachi Inf., 1992, 28 (3), 3-26, Probl. Inf. Trans., 1992, 28 (3), 199-220.
• [38] SAKALAUSKAS L., MINKEVIČIUS S., On the law of the iterated logarithm in open queueing networks, Eur. J. Oper. Res., 2000, 120, 632-640.
• [39] STRASSEN V., An invariance principle for the law of the iterated logarithm, Z. Wahrscheinlichkeitstheorie Verwandte Gebiete, 1964, 3, 211-226.
• [40] WHITT W., Heavy traffic limit theorems for queues: a survey, [In:] Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, 1974, 98, 307-350.
• [41] WHITT W., On the heavy-traffic limit theorem for GIG/∞ queues, Adv. Appl. Prob., 1982, 14, 171-190.
• [42] WHITT W., Large fluctuations in a deterministic multiclass network of queues, Manage. Sci., 1993, 39, 1020-1028.

Identyfikatory

DOI

10.5277/ord170404