Systems and Means of Informatics
2024, Volume 34, Issue 4, pp 31-47
OPTIMIZATION OF THE THRESHOLD PARAMETER OF A RED-LIKE QUEUE MANAGEMENT ALGORITHM FORA G/M/1 QUEUE
Abstract
The article considers the problem of calculating the optimal threshold value of a RED-like algorithm by a threshold value for a G/M/1 queue with incomplete queue renovation and probabilistic clients reset. The RED-like algorithm uses a single-threshold mechanism for probabilistic reset of clients from the queue, according to which at each moment of release of the service device, some clients are removed from the queue with a given probability. Customers queue in the order of arrival and those whose queue number exceeds the specified threshold at the time of release of the service device (they are in the “congestion zone”) are reset with a given probability. It is assumed that the “congestion zone” has a limited number of seats and if there are no empty seats in the “congestion zone” at the time of arrival of the customer, the customer is reset. The objective function is a weighted sum of the average customer delay time, the average number of customers dropped from the queue per unit of time, the average number of customers rejected at the entrance per unit of time, the average downtime of the device, and customer service payment. The mathematical problem of optimizing the objective function by a threshold value at a fixed size of the “overload zone” is formulated. The proofs of some relations between the characteristics of the queuing system and the unimodality of the objective function in terms of the threshold value are presented. A simple algorithm for the guaranteed solution of the formulated problem is proposed.
[+] References (22)
- Floyd, S., and V. Jacobson. 1993. Random early detection gateways for congestion avoidance. IEEE ACM T. Network. 1:397-413. doi: 10.1109/90.251892.
- Viana, C. C. H., I. S. Zaryadov, and T. A. Milovanova. 2020. Queueing systems with different types of renovation mechanism and thresholds as the mathematical models of active queue management mechanism. Discrete Continuous Models Applied Computational Science 28(4):305-318. doi: 10.22363/2658-4670-2020-28-4-305-318.
- Kabra, M., S. Saha, and B. Lin. 2006. Fast buffer memory with deterministic packet departures. 14th Symposium on High-Performance Interconnects Proceedings. Piscataway, NJ: IEEE. 67-72. doi: 10.1109/HOTI.2006.13.
- Zheng, B., and M. Atiquzzaman. 2008. A framework to determine the optimal weight parameter of RED in next-generation Internet routers. Int. J. Commun. Syst. 21:9871008.
- Reddy, T.B., A. Ahammed, and R. Banu. 2009. Performance comparison of active queue management techniques. Int. J. Computer Science Network Security 9(2):405- 408.
- Lin, D., and R. Morris. 1997. Dynamics of random early detection. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication Proceedings. New York, NY: ACM. 127-137. doi: 10.1145/263109.26315.
- Feng, W.-C., K. G. Shin, D. D. Kandlur, and D. Saha. 2002. The BLUE active queue management algorithms. IEEE ACM T. Network. 10(4):513-528. doi: 10.1109/ TNET.2002.801399.
- Feng, W.-C., D. D. Kandlur, D. Saha, and K. G. Shin. 2001. Stochastic Fair Blue: A queue management algorithm for enforcing fairness. 20th Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings. Piscataway, NJ: IEEE. 3:1520-1529. doi: 10.1109/INFCOM.2001.916648.
- Parris, M., K. Jeffay, and F. D. Smith. 1999. Lightweight active router-queue management for multimedia networking. Proc. SPIE3654:162-174. doi: 10.1117/12.333807.
- Pan, R., B. Prabhakar, and K. Psounis. 2000. CHOKe: A stateless active queue management scheme for approximating fair bandwidth allocation. 19th Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings. Piscat- away, NJ: IEEE. 2:942-951.
- Korolkova, A. V., D. S. Kulyabov, and A. I. Tchernoivanov. 2009. K voprosu o klassifikatsii algoritmov RED [On the classification of RED algorithms]. Vestnik RUDN. Ser. Matematika. Informatika. Fizika [Bulletin of Russian Peoples’ Friendship University. Series Mathematics, Information Sciences and Physics] 3:34-46. EDN: KXIRXN.
- Zaryadov, I. S., A. V. Korolkova, and R. V. Razumchik. 2012. Matematicheskie modeli rascheta i analiza kharakteristik sistem aktivnogo upravleniya ocheredyami s dvumya vkhodyashchimi potokami i razlichnymi prioritetami [Mathematical models of active queue management systems analysis based on queueing system with two types of traffic and different priorities]. T-Comm 6(7): 107-111. EDN: PWXFSB.
- Gaidamaka, Yu.V., and A. G. Maslennikov. 2013. Ob odnoy sisteme massovogo obsluzhivaniya s aktivnym upravleniem ochered’yu [On a queuing system with an active queue management]. Vestnik RUDN. Ser. Matematika. Informatika. Fizika [Bulletin of Russian Peoples’ Friendship University. Series Mathematics, Information Sciences and Physics] 4:56-64. EDN: RCKTSD.
- Konovalov, M., and R. Razumchik. 2017. Queueing systems with renovation vs. queues with RED. Cornell University. arXiv.org. 10 p. Available at: https://arxiv. org/abs/1709.01477/ (accessed October 16, 2024).
- Konovalov, M., and R. Razumchik. 2018. Comparison of two active queue management schemes through the M/D/1/N queue. Informatika i ee Primeneniya — Inform. Appl. 12(4):9-15. doi: 10.14357/19922264180402. EDN: VOGJOZ.
- Konovalov, M. G., and R. V. Razumchik. 2018. Numerical analysis of improved access restriction algorithms in a GI/G/l/N system. J. Commun. Technol. El. 63(6):616-625. doi: 10.1134/S1064226918060141.
- Lie, A., O. M. Aamo, and L.A. Rpnningen. 2004. Optimization of active queue management based on proportional control system. Conference (International) on Communications, Internet, and Information Technology Proceedings. St. Thomas, U.S. Virgin Islands: IASTED/ACTA Press. 6 p.
- Baldi, S., E.B. Kosmatopoulos, A. Pitsillides, M. Lestas, P. A. Ioannou, and Y. Wan. 2016. Adaptive optimization for active queue management supporting TCP flows. P. Amer. Contr. Conf. Piscataway, NJ: IEEE. 751-756. doi: 10.1109/ ACC.2016.7525004.
- Agalarov, Ya. M. 2023. Ob optimizatsii raboty rezervnogo pribora v mnogolineynoy sisteme massovogo obsluzhivaniya [Optimization of a queue-length dependent additional server in the multiserver queue]. Informatika i ee Primeneniya — Inform. Appl. 17(1):89-95. doi: 10.14357/19922264230112. EDN: FCYDUT.
- Agalarov, Ya. M. 2024. Ob odnoporogovom upravlenii ochered’yu v sisteme massovogo obsluzhivaniya s neterpelivymi zayavkami [On single-threshold queue management in a queuing system with impatient customers]. Informatika i ee Primeneniya — Inform. Appl. 18(2):40-46. doi: 10.14357/19922264240206. EDN: JZHAKU.
- Karlin, S. 1968. A first course in stochastic processes. New York-London: Academic Press. 502 p.
- Agalarov, Ya. M. 2019. Priznak unimodal’nosti tselochislennoy funktsii odnoy peremennoy [A sign of unimodality of an integer function of one variable]. Obozrenie prikladnoy i promyshlennoy matematiki [Surveys Applied and Industrial Mathematics] 26(1):65-66. EDN: EBHBDB.
[+] About this article
Title
OPTIMIZATION OF THE THRESHOLD PARAMETER OF A RED-LIKE QUEUE MANAGEMENT ALGORITHM FORA G/M/1 QUEUE
Journal
Systems and Means of Informatics
Volume 34, Issue 4, pp 31-47
Cover Date
2024-12-10
DOI
10.14357/08696527240403
Print ISSN
0869-6527
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
queue management; queue renovation; threshold parameter
Authors
Ya. M. Agalarov 
Author Affiliations
Federal Research Center "Computer Science and Control", Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
|