×

Weak convergence limits for sojourn times in cyclic queues under heavy traffic conditions. (English) Zbl 1151.60040

The paper studies the behaviour of cyclic networks of exponential single-server queues when a fixed number of nodes is filled with an ever increasing population. There are essentially two different cases. In the first case all servers have the same load and the total population in the system is shared equally by all nodes up to random fluctuations. In the second case differently loaded servers exist and bottlenecks occur, which in the simplest case with exactly one slowest server means that almost the whole population is queued up at this slowest server. The main interest of the paper is in detailed travel-time behaviour of individual customers in the second case.
The paper is organized as follows. In Section 2 the authors describe the model and collect the necessary results on sojourn time distribution. In Section 3 they recall Boxma’s result on the influence of the slowest server on the total cycle time and add an invariance property for the conditional sojourn time distribution. In Section 4 they prove the central limit theorem for the overall cycle time when the population size grows unboundedly. The asymptotic behaviour of the joint vector of sojourn times is derived in Section 5. The limiting picture is a composition of a central limit theorem for the bottleneck node and an exponential limit for the unscaled sequences of sojourn times for the nonbottleneck nodes.

MSC:

60K25 Queueing theory (aspects of probability theory)
60F05 Central limit and other weak theorems
90B22 Queues and service in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berger, A., Bregman, L. and Kogan, Y. (1999). Bottleneck analysis in multiclass closed queueing networks and its application. Queueing Systems 31 , 217–237. · Zbl 0934.90013 · doi:10.1023/A:1019110314687
[2] Billingsley, P. (1968). Convergence of Probability Measures . John Wiley, New York. · Zbl 0172.21201
[3] Boxma, O. J. (1988). Sojourn times in cyclic queues – the influence of the slowest server. Comput. Performance Reliab. 13–24.
[4] Boxma, O. J., Kelly, F. P. and Konheim, A. G. (1984). The product form for sojourn time distributions in cyclic exponential queues. J. Assoc. Comput. Mach. 31 , 128–133. · Zbl 0642.60073 · doi:10.1145/2422.322419
[5] Chen, H. and Yao, D. D. (2001). Fundamentals of Queueing Networks . Springer, New York. · Zbl 0992.60003
[6] Chow, W. M. (1980). The cycle time distribution of exponential cyclic queues. J. Assoc. Comput. Mach. 27 , 281–286. · Zbl 0432.68032 · doi:10.1145/322186.322193
[7] Daduna, H. and Szekli, R. (2002). Conditional job observer property for multitype closed queueing networks. J. Appl. Prob. 39 , 865–881. · Zbl 1027.60095 · doi:10.1239/jap/1037816025
[8] Gordon, W. J. and Newell, G. F. (1967). Closed queueing networks with exponential servers. Operat. Res. 15 , 254–265. · Zbl 0168.16603 · doi:10.1287/opre.15.2.254
[9] Harrison, P. G. (1985). On normalizing constants in queueing networks. Operat. Res. 33 , 464–468. · Zbl 0564.60087 · doi:10.1287/opre.33.2.464
[10] Kallenberg, O. (2002). Foundations of Modern Probability , 2nd edn. Springer, New York. · Zbl 0996.60001
[11] Kelly, F. P. (1984). The dependence of sojourn times in closed queueing networks. In Mathematical Computer Performance and Reliability , eds G. Iazeolla \et, North-Holland, Amsterdam, pp. 111–121.
[12] Kushner, H. J. (2001). Heavy Traffic Analysis of Controlled Queueing Networks and Communication Networks . Springer, New York. · Zbl 0988.90004
[13] Lemoine, A. J. (1978). Networks of queues – a survey of weak convergence results. Manag. Sci. 24 , 1175–1193. · Zbl 0396.60088 · doi:10.1287/mnsc.24.11.1175
[14] Malchin, C. and Daduna, H. (2005). An invariance property of sojourn times in cyclic networks. Operat. Res. Lett. 33 , 1–8. · Zbl 1076.90015 · doi:10.1016/j.orl.2004.03.006
[15] Morrison, J. A. (1987). Conditioned response-time distribution for a large closed processor-sharing system in very heavy usage. SIAM J. Appl. Math. 47 , 1117–1129. JSTOR: · Zbl 0627.60096 · doi:10.1137/0147074
[16] Reiman, M. I. (1982). The heavy traffic diffusion approximation for sojourn times in Jackson networks. In Applied Probability – Computer Sciences: The Interface , eds R. L. Disney and T. J. Ott, Vol. II, Birkhäuser, Boston, MA, pp. 409–421. · Zbl 0647.60099
[17] Reiman, M. I. (1984). Some diffusion approximations with state space collapse. In Proc. Internat. Sem. Modeling Performance Eval. Methodol. , eds F. Baccelli and G. Fayolle, Springer, New York, pp. 20–240. · Zbl 0545.60089 · doi:10.1007/BFb0005175
[18] Schassberger, R. and Daduna, H. (1983). The time for a roundtrip in a cycle of exponential queues. J. Assoc. Comput. Mach. 30 , 146–150. · Zbl 0508.68022 · doi:10.1145/322358.322369
[19] Williams, R. J. (1996). On the approximation of queueing networks in heavy traffic. In Stochastic Networks – Theory and Applications , eds F. P. Kelly \et, Clarendon Press, Oxford, pp. 35–56. · Zbl 0855.60083
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.