Informatics and Applications

2024, Volume 18, Issue 4, pp 52-58

ON ONE PROBLEM OF LOAD BALANCING IN TWO-PHASE TANDEM QUEUES

M. G. Konovalov
R. V. Razumchik

Abstract

Consideration is given to the dispatching system with a single dispatcher without a queue for storing incoming jobs. There is a finite number of infinite capacity queues running in parallel, each having a single server for serving jobs one-by-one in FIFO (first in, first out) manner. It is assumed that the dispatcher has perfect information about the system upon making a routing decision about the arrived job. Once the decision is made, it is irrevocable but is executed by the job with a random delay. The system is modeled by a two-phase tandem queue, with an infinite-server queue at the first phase and a fixed number of single-server queues at the second phase. Themethod to construct simple dispatching policies bymixing is proposed, which can result in robust rules, having better performance than conventional static and dynamic policies

[+] References (22)

Litvak, N., and U. Yechiali. 2003. Routing in queues with delayed information. Queueing Syst. 43(1/2):147–165.doi: 10.1023/A:1021812816979.
Anselmi, J., and J. Doncel. 2024. Load balancing with job-size testing: Performance improvement or degradation? ACMT ransactions Modeling Performance Evaluation Computing Systems 9(2):8. 27 p. doi: 10.1145/3651154.
Konovalov, M., and R. Razumchik. 2023. Dispetcherizatsiya v chastichno nablyudaemykh stokhasticheskikh sistemakh konechnoy emkosti s parallel’nym obsluzhivaniem [Dispatching in nonobservable parallel queues with finite capacities]. Sistemy i Sredstva Informatiki — Systems and Means of Informatics 33(3):29–47. doi: 10.14357/08696527230303. EDN: XUVVNH.
Konovalov, M. G., and R. V. Razumchik. 2023. Algoritm global’noy optimizatsii nekotorykh statsionarnykh vremennykh kharakteristik zadaniy v chastichno nablyudaemykh stokhasticheskikh sistemakh s parallel’nym obsluzhivaniem [Algorithm for global optimization of time-related stationary characteristics of jobs in nonobservable parallel queues]. Sistemy i Sredstva Informatiki — Systems and Means of Informatics 33(4):50–59. doi: 10.14357/08696527230405. EDN: PQAIRH.
Moiseev, A., and A. Nazarov. 2016. Tandem of infinite server queues with Markovian arrival process. Comm. Com. Inf. Sc. 601:323–333. doi: 10.1007/978-3-319-30843-2_34.
Dudin, A., and A. Nazarov. 2017. On a tandem queue with retrials and losses and state dependent arrival, service and retrial rates. Int. J. Operational Research 29(2):170–182. doi: 10.1504/IJOR.2017.10004611.
Pankratova, E., S. Moiseeva, and M. Farkhadov. 2022. Infinite-server resource queueing systems with different types of Markov-modulated Poisson process and renewal arrivals. Mathematics 10(2962). 16 p. doi: 10.3390/ math10162962.
Fedorova, E., I. Lapatin, O. Lizyura, A. Moiseev, A. Nazarov, and S. Paul. 2023. Queueing system with two phases of service and service rate degradation. Axioms 12(2):104. 19 p. doi: 10.3390/axioms12020104.
Moiseev, A.N., M. Shklennik, and E. Polin. 2023. Infinite-server queueing tandem with Markovian arrival process and service depending on its state. Ann. Oper. Res. 326(1):261–279. doi: 10.1007/s10479-023-05318-1.
Lipshutz, D. 2019. Open problem-load balancing using delayed information. Stochastic Systems 9(3):305–306. doi: 10.1287/stsy.2019.0045.
Hyytia, E., and R. Righter. 2021. Dynamic routing problems with delayed information. Performance evaluation methodologies and tools. Eds. Q. Zhao, and L. Xia. Lecture notes of the Institute forComputer Sciences, Social Informatics and Telecommunications Engineering ser. Cham: Springer. 404:171–184. doi: 10.1007/978-3-030-92511-6_11.
Kitsio, V., and U. Yechiali. 2008. Multi-server queues with intermediate buffer and delayed information on service completions. Stoch. Models 24(2):212–245. doi: 10.1080/15326340802007364.
Randi‚c, M., B. Bla skovi‚c, and S. Dembitz. 2013. Analysis of sojourn times in QBD model of a thread pool. Automatika 54(4):495–506. doi: 10.7305/automatika.54- 4.465.
Sun, Y., and B. Cyr. 2018. Information aging through queues: A mutual information perspective. 19th Workshop (International) on Signal Processing Advances in Wireless Communications Proceedings. Piscataway, NJ: IEEE. Art. 8445873. 5 p. doi: 10.1109/SPAWC.2018.8445873.
Tahir, A., K. Cui, and H. Koeppl. 2023. Learning meanfield control for delayed information load balancing in large queuing systems. 51st Conference (International) on Parallel Processing Proceedings. New York, NY: ACM. Art. 42. 11 p. doi: 10.1145/3545008.3545025.
Konovalov, M. G., and R. V. Razumchik. 2015. Obzor modeley i algoritmov razmeshcheniya zadaniy v sistemakh s parallel’nym obsluzhivaniem [Methods and algorithms for job scheduling in systems with parallel service: A survey]. Informatika i ee Primeneniya — Inform. Appl. 9(4):56–67. doi: 10.14357/1992264150406. EDN: VEABIF.
Itai, A., and Z. Rosberg. 1984. A golden ratio control policy for a multiple-access channel. IEEE T. Automat. Contr. 29(8):712–718. doi: 10.1109/TAC.1984.1103619.
Arian, Y., and Y. Levy. 1992. Algorithms for generalized round Robin routing. Oper. Res. Lett. 12(5):313–319. doi: 10.1016/0167-6377(92)90091-G.
Doncel, J. 2020. Performance balancing size-interval routing policies. INFOR 58(4):635–651. doi: 10.1080/03155986.2020.1743039.
Wang, Y., and D. Down. 2014. On resource pooling in SITA-like parallel server systems. 26th Teletraffic Congress (International) Proceedings. Piscataway, NJ: IEEE. Art. 6932947. 9 p. doi: 10.1109/ITC.2014.6932947.
Hyytia, E. 2013. Lookahead actions in dispatching to parallel queues. Perform. Evaluation 70(10):859–872. doi: 10.1016/j.peva.2013.08.018.
Mishra, A., T. Wen, and K.H. Cheong. 2024. Parrondo’s paradox in network communication: A routing strategy. Physical Review Research 6 :L012037. doi: 10.1103/ PhysRevResearch.6.L012037.

[+] About this article