Анализ систем массового обслуживания с пороговым механизмом обновления и инверсионной дисциплиной обслуживания

Обложка

Цитировать

Полный текст

Аннотация

В работе представлено исследование трёх систем массового обслуживания с пороговым механизмом обновления и инверсионной дисциплиной обслуживания. В модели первого типа пороговое значение отвечает только за активацию механизма обновления - механизма вероятностного сброса заявок. Во второй модели пороговое значение не только включает механизм обновления, но и определяет в накопителе границы области, из которой поступившие в систему заявки не могут быть сброшены. В модели третьего типа, обобщающей предыдущие две модели, используются два пороговых значения: одно для активации механизма сброса заявок, второе - для задания безопасной зоны в накопителе. На основе полученных ранее результатов представлены основные вероятностновременные характеристики рассмотренных моделей. С помощью имитационного моделирования проведён анализ и сравнение поведения изученных моделей.

Полный текст

1. Introduction According to [1] the problem of congestion avoidance for communication networks does not have a satisfying solution, so the development and the analysis of new active queue management (AQM) algorithms appears to be the actual task for researches [2]-[13] and practitioners [14]-[24]. In this paper we will consider queuing systems with probabilistic renovation mechanism, which allows to adjust the number of packets in the system by dropping (resetting) them from the queue depending on the ratio of a certain control parameter with specified thresholds [25], [26] at the moment of the end of service on the device (server) [27]-[29] in contrast to standard RED algorithm, when a possible reset occurs at the time of the next packet arrival and the control parameter is an exponentially weighted average queue length [30]-[34]. In our models the renovation mechanism uses one or two thresholds (which determine as the place in the buffer from which the packets are dropped, but also the place to which the reset of packets occurs). The previous works devoted to the analysis of queuing systems with threshold based renovation are [35]-[38]. In [35], [36] some aspects of using the renovation mechanism (different types of renovation, definitions and brief overview were also given) with one or several thresholds as the mathematical models of active queue management mechanisms were considered. Some results of comparing classic RED algorithm with renovation mechanism were presented. In [37] two queuing models with threshold based renovation mechanism were presented: in the first model the threshold value is only responsible for activating the renovation mechanism (the mechanism for probabilistic reset of claims), in the second model the threshold value not only turns on the renovation mechanism, but also determines the boundaries of the area in the queue from which claims that have entered the system cannot be dropped. In [38] the queuing system with two threshold values (one to activate the mechanism for dropping requests, the second - to set a safe zone in the queue) for renovation mechanism was investigated. All three queuing systems have been studied for the service discipline FCFS (First Come First Served), and in this article we will present some results for the discipline LCFS (Last Come First Served). The study will again be carried out using embedded Markov chains. We will not consider in detail the derivation of the stationary distribution of the number of customers (which does not depend on the service discipline and presented in [37], [38]) and will focus only on the service (reset) probabilities and on time characteristics. The structure of the article is following. In the section 2 the results for the queuing model, where the threshold value is only responsible for activating the renovation mechanism, are presented; the section 3 is devoted to the queuing model, in which the threshold value not only turns on the renovation mechanism, but also determines the boundaries of the area in the queue from which claims that have entered the system cannot be dropped. In section 4 the characteristics for the queuing system with two threshold values (one to activate the mechanism for dropping requests, the second - to set a safe zone in the queue) for renovation mechanism are presented. In section 5 the results of GPSS simulation are considered. The last section 6 concludes the paper with the short discussion. 2. The first model Consider the
×

Об авторах

И. С. Зарядов

Российский университет дружбы народов; Институт проблем информатики, Федеральный исследовательский центр «Информатика и управление» РАН

Email: zaryadov-is@rudn.ru
ORCID iD: 0000-0002-7909-6396

Candidate of Physical and Mathematical Sciences, Assistant Professor of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University); Senior Researcher of Institute of Informatics Problems of Federal Research Center “Computer Science and Control” Russian Academy of Sciences

ул. Миклухо-Маклая, д. 6, Москва, 117198, Россия; ул. Вавилова, д. 44, кор. 2, Москва, 119333, Россия

Илкиаш К. К. Виана

Российский университет дружбы народов

Email: hilvianamat1@gmail.com
ул. Миклухо-Маклая, д. 6, Москва, 117198, Россия

Т. А. Милованова

Российский университет дружбы народов

Автор, ответственный за переписку.
Email: milovanova-ta@rudn.ru
ORCID iD: 0000-0002-9388-9499

Candidate of Physical and Mathematical Sciences, Lecturer of Department of Applied Probability and Informatics

ул. Миклухо-Маклая, д. 6, Москва, 117198, Россия

Список литературы

  1. F. Baker and G. Fairhurst. “IETF Recommendations Regarding Active Queue Management. RFC 7567”. (Jul. 2015), [Online]. Available: https://tools.ietf.org/html/rfc7567.
  2. K. Nichols and V. Jacobson, “Controlling queue delay”, Communications of the ACM, vol. 55, no. 7, pp. 42-50, May 2012. doi: 10.1145/2209249.2209264.
  3. T. Hoeiland-Joergensen et al. “The flow queue codel packet scheduler and active queue management algorithm. RFC 8290”. (2018), [Online]. Available: https://www.rfc-editor.org/info/rfc8290.
  4. S. Jung, J. Kim, and J.-H. Kim, “Intelligent active queue management for stabilizedQoSguaranteesin5Gmobilenetworks”, IEEE Systems Journal, vol. 15, pp. 4293-4302, 2021. doi: 10.1109/JSYST.2020.3014231.
  5. W.-c. Feng, D. Kandlurz, D. Sahaz, and K. Shin, “BLUE: a new class of active queue management algorithms”, University of Michigan, Tech. Rep., Sep. 2000.
  6. W.-c. Feng, D. Kandlur, and D. Saha, “The BLUE active queue management algorithms”, Networking, IEEE/ACM Transactions on, vol. 10, pp. 513-528, Sep. 2002. doi: 10.1109/TNET.2002.801399.
  7. C. Zhang, J. Yin, and Z. Cai, “RSFB: a resilient stochastic fair blue algorithm against spoofing DDoS attacks”, in 9th International Symposium on Communications and Information Technology, 2009, pp. 1566- 1567. doi: 10.1109/ISCIT.2009.5341033.
  8. T. Hoiland-Jorgensen, D. Taht, and J. Morton, “Piece of CAKE: a comprehensive queue management solution for home gateways”, in IEEE International Symposium on Local and Metropolitan Area Networks (LANMAN), Jun. 2018, pp. 37-42. doi: 10.1109/LANMAN.2018.8475045.
  9. J. Palmei, S. Gupta, P. Imputato, J. Morton, M. Tahiliani, S. Avallone, and D. Taht, “Design and evaluation of COBALT queue discipline”, in IEEE International Symposium on Local and Metropolitan Area Networks (LANMAN), Jul. 2019, pp. 1-6. doi: 10.1109/LANMAN.2019.8847054.
  10. A. Roy, J. L. Pachuau, and A. K. Saha, “An overview of queuing delay and various delay based algorithms in networks”, Computing, vol. 103, pp. 2361-2399, 2021. doi: 10.1007/s00607-021-00973-3.
  11. W. de Morais, C. E. M. Santos, and C. M. Pedroso, “Application of active queue management for real-time adaptive video streaming”, Telecommun Syst, vol. 79, pp. 261-270, 2022. doi: 10.1007/s11235-021-00848-0.
  12. J. George and R. Santhosh, “Congestion control mechanism for unresponsive flows in Internet through active queue management system (AQM)”, Lecture Notes on Data Engineering and Communications Technologies, vol. 68, pp. 765-777, 2022. doi: 10.1007/978-981-16-1866-6_58.
  13. S. Singha, B. Jana, N. K. Mandal, S. Jana, S. Bandyopadhyay, and S. Midya, “Application of dynamic weight with distance to reduce packet loss in RED based algorithm”, Lecture Notes in Networks and Systems, vol. 292, pp. 530-543, 2022. doi: 10.1007/978-981-16-4435-1_52.
  14. R. Adams, “Active queue management: a survey”, Communications Surveys & Tutorials, IEEE, vol. 15, pp. 1425-1476, Jan. 2013. doi: 10.1109/SURV.2012.082212.00018.
  15. M. Menth and S. Veith, “Active queue management based on congestion policing (CP-AQM)”, in Jan. 2018, pp. 173-187. doi: 10.1007/978-3319-74947-1_12.
  16. A. Chydzinski and L. Chrost, “Analysis of AQM queues with queue size based packet dropping”, Applied Mathematics and Computer Science, vol. 21, pp. 567-577, Sep. 2011. doi: 10.2478/v10006-011-0045-7.
  17. A. Chydzinski and P. Mrozowski, “Queues with dropping functions and general arrival processes”, PloS one, vol. 11, e0150702, Mar. 2016. doi: 10.1371/journal.pone.0150702.
  18. M. Konovalov and R. Razumchik, “Numerical analysis of improved access restriction algorithms in a GI/G/1/N system”, Journal of Communications Technology and Electronics, vol. 63, pp. 616-625, Jun. 2018. doi: 10.1134/S1064226918060141.
  19. M. Konovalov and R. Razumchik, “Comparison of two active queue management schemes through the M/D/1/N queue”, Informatika i ee Primeneniya, vol. 12, no. 4, pp. 9-15, 2018, in Russian. doi: 10.14357/19922264180402.
  20. C. SSo-In, R. Jain, and J. Jiang, “Enhanced forward explicit congestion notification (E-FECN) scheme for datacenter Ethernet networks”, in International Symposium on Performance Evaluation of Computer and Telecommunication Systems, 2008, pp. 542-546.
  21. C. Gomez, X. Wang, and A. Shami, “Intelligent active queue management using explicit congestion notification”, in IEEE Global Communications Conference (GLOBECOM), Sep. 2019, pp. 1-6. doi: 10.20944/preprints201909.0077.v1.
  22. S. Shahzad, E.-S. Jung, J. F. Chung M., and R. Kettimuthu, “Enhanced explicit congestion notification (EECN) in TCP with P4 programming”, in International Conference on Green and Human Information Technology (ICGHIT), Feb. 2020. doi: 10.1109/ICGHIT49656.2020.00015.
  23. S. Wang, J. Zhang, T. Huang, T. Pan, J. Liu, and Y. Liu, “A-ECN minimizing queue length for datacenter networks”, IEEE Access, vol. 8, pp. 49100-49111, 2020. doi: 10.1109/ACCESS.2020.2979216.
  24. A. Bashir, E. Machnev, and E. Mokrov, “Queueing model of hysteretic congestion control for cloud wireless sensor networks”, in 13th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 2021, pp. 104-108. doi: 10.1109/ICUMT54235.2021.9631576.
  25. S. Li, Q. Xu, J. Gaber, Z. Dou, and J. Chen, “Congestion control mechanism based on dual threshold DI-RED for WSNs”, Wireless Personal Communications, vol. 115, pp. 2171-2195, 2020. doi: 10.1007/s11277020-07676-6.
  26. S. Singha, B. Jana, S. Jana, and N. K. Mandal, “An innovative active queue management model through threshold adjustment using queue size”, Advances in Intelligent Systems and Computing, vol. 1406, pp. 257- 273, 2022. doi: 10.1007/978-981-16-5207-3_23.
  27. A. Kreinin, “Queueing systems with renovation”, Journal of Applied Mathematics and Stochastic Analysis, vol. 10, pp. 431-443, Jan. 1997. doi: 10.1155/S1048953397000464.
  28. M. Konovalov and R. Razumchik, Queueing systems with renovation vs. queues with red. supplementary material, 2017. arXiv: 1709.01477.
  29. A. V. Gorbunova and A. V. Lebedev, “Queueing system with two input flows, preemptive priority, and stochastic dropping”, Automation and Remote Control, vol. 81, no. 12, pp. 2230-2243, 2020. doi: 10.1134/S0005117920120073.
  30. S. Floyd and V. Jacobson, “Random early detection gateways for congestion avoidance”, IEEE/ACM Transactions on Networking, vol. 1, pp. 397- 413, Sep. 1993. doi: 10.1109/90.251892.
  31. K. Ramakrishnan, S. Floyd, and D. Black. “RFC3168: The Addition of Explicit Congestion Notification (ECN) to IP”. (2001), [Online]. Available: https://tools.ietf.org/html/rfc3168.
  32. S. Floyd, R. Gummadi, and S. Shenker, Adaptive RED: an algorithm for increasing the robustness of RED’s active queue management, Sep. 2001.
  33. A. V. Korolkova, D. S. Kulyabov, and A. I. Chernoivanov, “On the classification of RED algorithms”, Bulletin of Peoples’ Friendship University of Russia, no. 3, pp. 34-46, 2009, in Russian.
  34. W.-C. Feng, “Improving Internet congestion control and queue management algorithms”, The University of Michigan, Tech. Rep., 1999.
  35. H. C. C. Viana, I. Zaryadov, V. Tsurlukov, T. Milovanova, E. Bogdanova, A. Korolkova, and D. Kulyabov, “The general renovation as the active queue management mechanism. Some aspects and results”, Communications in Computer and Information Science, vol. 1141, pp. 488- 502, 2019. doi: 10.1007/978-3-030-36625-4_39.
  36. H. C. C. Viana, I. S. Zaryadov, and T. A. Milovanova, “Queueing systems with different types of renovation mechanism and thresholds as the mathematical models of active queue management mechanism”, Discrete and Continuous Models and Applied Computational Science, vol. 28, no. 4, pp. 305-318, 2020. doi: 10.22363/2658-4670-2020-284-305-318.
  37. H. C. C. Viana, I. S. Zaryadov, and T. A. Milovanova, “Two types of single-server queueing systems with threshold-based renovation mechanism”, Lecture Notes in Computer Science, vol. 13144, pp. 196-210, 2021. doi: 10.1007/978-3-030-92507-9_17.
  38. H. C. C. Viana and I. S. Zaryadov, “Single-server queuing systems with exponential service times and threshold-based renovation”, in 13th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), 2021, pp. 91-97. doi: 10.1109/ICUMT54235.2021.9631585.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Зарядов И.С., Виана И.К., Милованова Т.А., 2022

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.