Heavy-traffic approximations for a layered network with limited resources

• Autorzy: Aveklouris A. , Vlasiou M. , Zhang J. , Zwart B.

Identyfikatory

DOI

10.19195/0208-4147.37.2.15

• Języki publikacji: EN

Abstrakty

EN

Motivated by a web-server model, we present a queueing network consisting of two layers. The first layer incorporates the arrival of customers at a network of two single-server nodes. We assume that the interarrival and the service times have general distributions. Customers are served according to their arrival order at each node and after finishing their service they can re-enter at nodes several times for another service. At the second layer, active servers act as jobs that are served by a single server working at speed one in a processor-sharing fashion. We further assume that the degree of resource sharing is limited by choice, leading to a limited processor-sharing discipline. Our main result is a diffusion approximation for the process describing the number of customers in the system. Assuming a single bottleneck node and studying the system as it approaches heavy traffic, we prove a state-space collapse property.

Słowa kluczowe

EN

layered queueing network; limited processor sharing; fluid model; diffusion approximation; heavy traffic

• Wydawca: Wrocław University of Science and Technology
• Czasopismo: Probability and Mathematical Statistics
• Rocznik: 2017
• Tom: Vol. 37, Fasc. 2
• Strony: 497--532
• Opis fizyczny: Bibliogr. 20 poz., rys., wykr.

Twórcy

autor

Aveklouris A.

• Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

autor

Vlasiou M.

• Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

autor

Zhang J.

• Department of Industrial Engineering and Logistics Management, The Hong Kong University of Science and Technology, Hong Kong S.A.R., China

autor

Zwart B.

• Department of Mathematics and Computer Science, Eindhoven University of Technology, Centrum Wiskunde en Informatica, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

Bibliografia

• [1] M. Bramson, State space collapse with application to heavy traffic limits for multiclass queueing networks, Queueing Syst. 30 (1-2) (1998), pp. 89-140.
• [2] H. Chen and D. D. Yao, Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization, Springer, New York 2001.
• [3] J. L. Dorsman, O. J. Boxma, and M. Vlasiou, Marginal queue length approximations for a two-layered network with correlated queues, Queueing Syst. 75 (1) (2013), pp. 29-63.
• [4] J. L. Dorsman, M. Vlasiou, and B. Zwart, Heavy-traffic asymptotics for networks of parallel queues with Markov-modulated service speeds, Queueing Syst. 79 (3-4) (2015), pp. 293-319.
• [5] R. Durrett, Stochastic Calculus: a Practical Introduction, CRC Press, Boca Raton 1996.
• [6] G. Fayolle, P. J. B. King, and I. Mitrani, The solution of certain two-dimensional Markov models, Adv. in Appl. Probab. 14 (2) (1982), pp. 295-308.
• [7] H. C. Gromoll, Diffusion approximation for a processor sharing queue in heavy traffic, Ann. Appl. Probab. 14 (2) (2004), pp. 555-611.
• [8] J. A. Rolia and K. C. Sevcik, The method of layers, IEEE Trans. Softw. Eng. 21 (8) (1995), pp. 689-700.
• [9] R. D. van der Mei, R. Hariharan, and P. Reeser, Web server performance modeling, Telecommunication Systems 16 (3-4) (2001), pp. 361-378.
• [10] W. van der Weij, S. Bhulai, and R. van der Mei, Dynamic thread assignment in web server performance optimization, Perform. Eval. 66 (6) (2009), pp. 301-310.
• [11] M. Vlasiou, J. Zhang, B. Zwart, and R. D. van der Mei, Separation of timescales in a two-layered network, in: Proceedings of the 24th International Teletraffic Congress, Kraków 2012.
• [12] W. Walter, Ordinary Differential Equations, Springer, New York 1998.
• [13] W. Whitt, Some useful functions for functional limit theorems, Math. Oper. Res. 5 (1) (1980), pp. 67-85.
• [14] R. J. Williams, Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse, Queueing Syst. 30 (1-2) (1998), pp. 27-88.
• [15] M. Woodside, J. E. Neilson, D. C. Petriu, and S. Majumdar, The stochastic rendezvous network model for performance of synchronous client-server-like distributed software, IEEE Trans. Comput. 44 (1) (1995), pp. 20-34.
• [16] H.-Q. Ye, J. Ou, and X.-M. Yuan, Stability of data networks: Stationary and bursty models, Oper. Res. 53 (1) (2005), pp. 107-125.
• [17] H.-Q. Ye and D. D. Yao, A stochastic network under proportional fair resource control: Diffusion limit with multiple bottlenecks, Oper. Res. 60 (3) (2012), pp. 716-738.
• [18] J. Zhang, J. Dai, and B. Zwart, Law of large number limits of limited processor-sharing queues, Math. Oper. Res. 34 (4) (2009), pp. 937-970.
• [19] J. Zhang, J. Dai, and B. Zwart, Diffusion limits of limited processor sharing queues, Ann. Appl. Probab. 21 (2) (2011), pp. 745-799.
• [20] J. Zhang and B. Zwart, Steady state approximations of limited processor sharing queues in heavy traffic, Queueing Syst. 60 (3-4) (2008), pp. 227-246.

Uwagi

The paper is dedicated to Professor Tomasz Rolski.

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).