Systems and Means of Informatics

2023, Volume 33, Issue 3, pp 29-47

DISPATCHING IN NONOBSERVABLE PARALLEL QUEUES WITH FINITE CAPACITIES

M. G. Konovalov
R. V. Razumchik

Abstract

Consideration is given to the problem of optimal centralized routing in one simple model of volunteer computer systems. The model consists of the finite number of parallel finite-capacity FIFO (first in, first out) queues, each with a single server, and a single dispatcher. Homogeneous jobs arrive one-by-one in a stochastic manner to the dispatcher which must instantly make a routing decision based solely on its previous routing decisions and, possibly, the time instants at which those decisions were made. Although no feedback from the queues is available, the dispatcher knows the maximum queues' capacities, all service rates, the distribution of job sizes, and the inter-arrival time distribution. The new algorithm for generating routing decisions "on the fly" which optimizes the given cost function of the stationary mean sojourn time and the loss probability is proposed.

[+] References (23)

Konovalov, M., and R. Razumchik. 2019. Kompleksnoe upravlenie v odnom klasse sistem s parallel'nym obsluzhivaniem [Mixed policies for online job allocation in one class of systems with parallel service]. Informatika i ee Primeneniya - Inform. Appl. 13(4):54-59. doi: 10.14357/19922264190409.
Sokolov, A. E., and I. A. Ushakov. 1978. Matematicheskie metody modelirovaniya pri sozdanii sistem svyazi [Mathematical modeling methods for creating communication systems]. Tekhnika sredstv svyazi. Ser. ASU [Communication Technology. Automatic Control Systems Series] 2:3-11.
Mengistu, T. M., and D. Che. 2019. Survey and taxonomy of volunteer computing. ACM Comput. Surv. 52(3):59. 35 p. doi: 10.1145/3320073.
Nikitina, N., M. Manzyuk, C. Podlipnik, and M. Jukic. 2021. Volunteer computing project SiDock@home for virtual drug screening against SARS-CoV-2. Computer science protecting human society against epidemics. Eds. A. Byrski, T. Czachorski, E. Gelenbe, K. Grochla, and Y. Murayama. IFIP advances in information and communication technology book ser. Cham: Springer. 616:23-34. doi: 10.1007/9783-030-86582-5-3.
Kurochkin, 1.1., K.V. Grigoriev, E. U. Korlyakova, A.M. Shilina, E.P. Urasova, and V. N. Yakimets. 2022. Issledovanie sposobov privlecheniya dobrovol'tsev v proekty dobrovol'nykh raspredelennykh vychisleniy [Study of methods to attract volunteers in voluntary distributed computing projects]. Informatsionnoye obshchestvo: obrazovanie, nauka, kul'tura i tekhnologii budushchego [The information society: Education, science, culture, and future technologies] 6:49-61. doi: 10.17586/2587-8557-2022-6-49-61.
Lakshmi, L. 2022. Resource and history-aware IoT task scheduling in volunteer assisted fog computing. Conference (International) on Smart Applications, Communications and Networking. Piscataway, NJ: IEEE. 9993995. 6 p. doi: 10.1109/ SmartNets55823.2022.9993995.
BOINC computing power. Available at: https://boinc.berkeley.edu/computing.php (accessed September 20, 2023).
Mizin, I. A., and A. P. Kuleshov. 1986. Seti EVM [Computer networks]. Itogi nauki i tekhniki. Ser. Tekhicheskaya kibernetika [Technical cybernetics. Results of science and technology ser]. Moscow: VINITI. 20:3-134.
Durrani, M.N., and J.A. Shamsi. 2014. Volunteer computing: Requirements, challenges, and solutions. J. Netw. Comput. Appl. 39(1):369-380. doi: 10.1016/j.jnca. 2013.07.006.
Tapparello, C., C. Funai, S. Hijazi, A. Aquino, B. Karaoglu, H. Ba, J. Shi, and W. Heinzelman. 2015. Volunteer computing on mobile devices: State of the art and future research directions. Enabling real-time mobile cloud computing through emerging technologies. Hershey, PA: IGI Global. 153-181. doi: 10.4018/978-1-4666- 8662-5.ch005.
Konovalov, M., and R. Razumchik. 2017. Using inter-arrival times for scheduling in non-observable queues. 31st ECMS Conference (International) on Modelling and Simulation Proceedings. Budapest, Hungary: ECMS. 667-672. doi: 10.7148/20170667.
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 Prime- neniya - Inform. Appl. 9(4):56-67. doi: 10.14357/1992264150406.
Hordijk, A., and D.A. van der Laan. 2004. Periodic routing to parallel queues and billiard sequences. Math. Method. Oper. Res. 59(2): 173-192. doi: 10.1007/ s001860300322.
Konovalov, M., and R. Razumchik. 2021. Minimizing mean response time in batch- arrival non-observable systems with single-server FIFO queues operating in parallel. Communications ECMS 35(1):272-278. doi: 10.7148/2021-0272.
Konovalov, M., and R. Razumchik. 2016. O razmeshchenii zadaniy na dvukh serverakh pri nepolnom nablyudenii [Dispatching to two parallel nonobservable queues using only static information]. Informatika i ee Primeneniya - Inform. Appl. 10(4):57-67. doi: 10.14357/19922264160406.
Konovalov, M., and R. Razumchik. 2018. Improving routing decisions in parallel nonobservable queues. Computing 100(10): 1059-1079. doi: 10.1007/s00607-018-0598-5.
Semchedine, F., L. Bouallouche-Medjkoune, and D. Aissani. 2011. Task assignment policies in distributed server systems: A survey. J. Netw. Comput. Appl. 34(4): 1123- 1130. doi: 10.1016/j.jnca.2011.01.011.
Hordijk, W., A. Hordijk, and B. Heidergott. 2015. A genetic algorithm for finding good balanced sequences in a customer assignment problem with no state information. Asia Pac. J. Oper. Res. 32(3):1550015. 20 p. doi: 10.1142/S0217595915500153.
Nazin, A.V., and A. S. Poznyak. 1986. Adaptivnyy vybor variantov: rekurrentnye algoritmy [Adaptive option selection: Recursive algorithms]. Moscow: Nauka. 288 p.
Konovalov, M. G. 2007. Metody adaptivnoy obrabotki informatsii i ikh prilozheniya [Methods of adaptive information processing and their applications]. Moscow: IPI RAN. 212 p.
Zaikin, O. S., M. A. Posypkin, A. A. Semenov, and N. P. Khrapov. 2012. Opyt organizatsii dobrovol'nykh vychisleniy na primere proektov optima@home i sat@home [Experience in organizing voluntary computing on the example of the optima@home and sat@home projects]. Vestnik Nizhegorodskogo universiteta im. N.I. Lobachevskogo [Bulletin of the Lobachevsky University of Nizhni Novgorod] 5-2:340-347. EDN: PZKQIZ.
Javadi, B., D. Kondo, J.-M. Vincent, and D. P. Anderson. 2011. Discovering statistical models of availability in large distributed systems: An empirical study of seti@home. IEEE T. Parall. Distr. 22(11):1896-1903. doi: 10.1109/TPDS.2011.50.
Tijms, H. 1992. Heuristics for finite-bufferqueues. Probab. Eng. Inform. Sc. 6(3):277- 285. doi: 10.1017/S0269964800002540.

[+] About this article