Numerical Analysis of the Control Problem for a Queuing System with a Small Parameter on a Non-Uniform Grid Scheme
Abstract
The shortest queue problem (SQP) is widely applied for load-balancing procedure in telecommunication systems. Now SQP is one of the most intensively studied and many investigators give full consideration to the SQP research for large-scale queueing systems (LSQS) with a huge number of identical devices because of the integration of 5G/6G networks is carried out at a very high speed. In this work we apply the high-order non-uniform grid numerical scheme for the investigation of the LSQS dynamics with identical single-service devices under the optimal control. We assume that identical services provide by devices with exponentially distributed service time and there is a Poisson incoming flow of requests for LSQS services with finite intensity. LSQS implements the service discipline so that each input request provides a random selection from any m-set devices such device that has the s-th shortest (or equivalently, the (m-s)-th longest) queue size. The evolution dynamics LSQS can be considered using the solutions analysis, where the solutions can be obtained by solving a system of differential equations of infinite degree which can be found with the use of the Markov chains method. We consider the control problem for LSQS, which is formulated in the form of the boundary value problem (BVP) for this system of differential equations with a small parameter. We use the truncation procedure for this singularly perturbed BVP and investigate BVP for the finite order system of differential equations. We apply the high-order non-uniform grid scheme for numerical solving of the truncated BVP. The grid scheme demonstrates good convergence of solutions of the singularly perturbed BVP when a small parameter tend to zero. The results of the LSQS dynamics simulation demonstrate that this LSQS with the control capable of serving a huge number of input requests.
References
2. Sidorov S., Faizliev A., Balash V., Balash O., Krylova M., Fomenko A. Extended innovation diffusion models and their empirical performance on real propagation data. Journal of Marketing Analytics. 2021;(9):99-110. https://doi.org/10.1057/s41270-021-00106-x
3. Yarkina N., Correia L.M., Moltchanov D., Gaidamaka Y., Samouylov K. Multi-tenant resource sharing with equitable-priority-based performance isolation of slices for 5G cellular systems. Computer Communications. 2022;(188):39-51. https://doi.org/10.1016/j.comcom.2022.02.019
4. Beliakov G., Divakov D.V. Aggregation with dependencies: Capacities and fuzzy integrals. Fuzzy Sets and Systemsthis. 2022;(446):222-232. https://doi.org/10.1016/j.fss.2021.03.009
5. Sevastianov L.A., Lovetskiy K.P., Kulyabov D.S. Multistage collocation pseudo-spectral method for the solution of the first order linear ODE. In: 2022 VIII International Conference on Information Technology and Nanotechnology (ITNT). Samara, Russian Federation: IEEE Computer Society; 2022. p. 1-6. https://doi.org/10.1109/ITNT55410.2022.9848731
6. Tiutiunnik A.A., Divakov D.V., Lovetskiy K.P., Sevastianov A.L. Single-mode propagation of adiabatic guided mode in a smooth transition between planar waveguides. Proceedings of SPIE. 2022. Vol. 12193. Article number: 1219305. https://doi.org/10.1117/12.2626384
7. van Houdt B. Global Attraction of ODE-based Mean Field Models with Hyperexponential Job Sizes. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 2019;3(2):23. https://doi.org/10.1145/3341617.3326137
8. Bu Q.H., Liu L.W., Tang J.S., Zhao Y.Q. Approximations for a Queueing Game Model with Join-the-Shortest-Queue Strategy. Journal of the Operations Research Society of China. 2023;11(3):489-504. https://doi.org/10.1007/s40305-021-00382-5
9. Liu X., Gong K., Ying L. Steady-state analysis of load balancing with Coxian-2 distributed service times. Naval Research Logistics. 2022;69(1):57-75. https://doi.org/10.1002/nav.21986
10. Zhou X., Shroff N., Wierman A. Asymptotically optimal load balancing in large-scale heterogeneous systems with multiple dispatchers. Performance Evaluation. 2021;(145):102146. https://doi.org/10.1016/j.peva.2020.102146
11. Zhu L., Casale G., Perez I. Fluid approximation of closed queueing networks with discriminatory processor sharing. Performance Evaluation. 2020;139:102094. https://doi.org/10.1016/j.peva.2020.102094
12. Qiu B., Chen X.Q., Wu Q. A key design to prolong lifetime of wireless sensor network. Chaos, Solitons & Fractals. 2016;89:491-496. https://doi.org/10.1016/j.chaos.2016.02.025
13. Chen H., Wang Z. Optimal control for parallel queues with a single batch server. Operations Research Letters. 2022;50(4):377-383. https://doi.org/10.1016/j.orl.2022.04.004
14. Haviv M., Ravner L. A survey of queueing systems with strategic timing of arrivals. Queueing System. 2021;(99):163-198. https://doi.org/10.1007/s11134-021-09717-8
15. Banerjee S., Budhiraja A., Puha A.L. Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions. The Annals of Applied Probability. 2022;32(4):2587-2651. https://doi.org/10.1214/21-AAP1741
16. van der Boor M., Borst S.C., van Leeuwaarden J.S., Johan S.H., Mukherjee D. Scalable load balancing in networked systems: A survey of recent advances. SIAM Review. 2022;64(3):554-622. https://doi.org/10.1137/20M1323746
17. Alnawayseh S.E.A., Al-Sit W.T., Ghazal T.M. Smart Congestion Control in 5G/6G Networks Using Hybrid Deep Learning Techniques. Complexity. 2022;2022(1):1781952. https://doi.org/10.1155/2022/1781952
18. Bushkova T., Moiseeva S., Moiseev A., Sztrik J., Lisovskaya E., Pankratova E. Using Infinite-server Resource Queue with Splitting of Requests for Modeling Two-channel Data Transmission. Methodology and Computing in Applied Probability. 2022;(24):1753-1772. https://doi.org/10.1007/s11009-021-09890-6
19. Nazarov A., Dudin A., Moiseev A. Pseudo Steady-State Period in Non-Stationary Infinite-Server Queue with State Dependent Arrival Intensity. Mathematics. 2022;10(15):2661. https://doi.org/10.3390/math10152661
20. Nazarov A., Phung-Duc T., Izmailova Y. Asymptotic-Diffusion Analysis of Multiserver Retrial Queueing System with Priority Customers. In: Dudin A., Nazarov A., Moiseev A. (eds.) Information Technologies and Mathematical Modelling. Queueing Theory and Applications. ITMM 2020. Communications in Computer and Information Science. Vol. 1391. Cham: Springer; 2021. p. 236-250. https://doi.org/10.1007/978-3-030-72247-0_18
21. Kumar S., Sumit S., Vigo-Aguiar J. A high order convergent numerical method for singularly perturbed time dependent problems using mesh equidistribution. Mathematics and Computers in Simulation. 2022;(199):287-306. https://doi.org/10.1016/j.matcom.2022.03.025
22. Negero N.T. A uniformly convergent numerical scheme for two parameters singularly perturbed parabolic convection diffusion problems with a large temporal lag. Results in Applied Mathematics. 2022;(16);100338. https://doi.org/10.1016/j.rinam.2022.100338
23. Ranjan K.R., Gowrisankar S. Uniformly convergent NIPG method for singularly perturbed convection diffusion problem on Shishkin type meshes. Applied Numerical Mathematics. 2022;(179):125-148. https://doi.org/10.1016/j.apnum.2022.04.015
24. Vasilyev S.A., Bouatta M.A., Tsareva G.O. High-Order Non-uniform Grid Scheme for Numerical Analysis of Queueing System with a Small Parameter. In: Silhavy R., Silhavy P., Prokopova Z. (eds.) Data Science and Algorithms in Systems. CoMeSySo 2022. Lecture Notes in Networks and Systems. Vol. 597. Cham: Springer; 2023. p. 785-797. https://doi.org/10.1007/978-3-031-21438-7_66
25. Vasilyev S.A., Bouatta M.A., Kanzitdinov S.K., Tsareva G.O. High-Order Non-uniform Grid Scheme for Numerical Analysis of Shortest Queue Control Problem with a Small Parameter. In: Silhavy R., Silhavy P. (eds.) Networks and Systems in Cybernetics. CSOC 2023. Lecture Notes in Networks and Systems. Vol. 723. Cham: Springer; 2023. p. 639-653. https://doi.org/10.1007/978-3-031-35317-8_58
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
