Системы массового обслуживания с различными видами обновления и порогами как математические модели алгоритмов активного управления очередями

Обложка

Цитировать

Полный текст

Аннотация

Работа посвящена некоторым аспектам использования механизма обновления (различные варианты обновления рассмотрены, определения и краткий обзор представлены) с одним или несколькими порогами в качестве математических моделей механизмов активного управления очередями. Описаны системы массового обслуживания, в которых реализован механизм обновления с порогами, позволяющий управлять числом заявок в системе путем их сброса из накопителя в зависимости от значения некоторого управляющего параметра и пороговых значений. Сброс заявок из накопителя происходит в момент окончания обслуживания заявки на приборе, что отличает данный механизм сброса от RED-подобных алгоритмов, для которых сброс возможен в момент поступления в систему. Представлены модели с одним, двумя или тремя порогами. В этих моделях пороговые значения определяют не только место, с которого в накопителе начинается сброс заявок, но и до какой позиции заявки могут быть сброшены. Для некоторых из описываемых моделей уже получены аналитические и численные результаты (ссылки на работы представлены), но большая часть моделей находится в процессе изучения, поэтому представлены только описания и некоторые текущие данные. Приведены некоторые результаты сравнения классического алгоритма RED с механизмом обновления.

Об авторах

Илкиаш Виана Карвалью Кравид

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

Автор, ответственный за переписку.
Email: hilvianamat1@gmail.com

post-graduate student of Department of Applied Probability and Informatics

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

Иван С. Зарядов

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

Email: zaryadov-is@rudn.ru

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

ул. Вавилова, д. 44, корп. 2, Москва, 119333, Россия

Татьяна А. Милованова

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

Email: milovanova-ta@rudn.ru

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

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

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

  1. F. Baker and G. Fairhurst. (Jul. 2015). “IETF Recommendations Regarding Active Queue Management. RFC 7567.,” [Online]. Available: https://tools.ietf.org/html/rfc7567.
  2. M. Menth and S. Veith, “Active Queue Management Based on Congestion Policing (CP-AQM),” in. Jan. 2018, pp. 173-187. doi: 10.1007/9783-319-74947-1_12.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. M. Konovalov and R. Razumchik, “Comparison of two active queue management schemes through the M/D/1/N queue,” Informatika i ee Primeneniya (Informatics and Applications), vol. 12, no. 4, pp. 9-15, 2018. doi: 10.14357/19922264180402.
  8. 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.
  9. K. Ramakrishnan, S. Floyd, and D. Black. (2001). “RFC3168: The Addition of Explicit Congestion Notification (ECN) to IP,” [Online]. Available: https://tools.ietf.org/html/rfc3168.
  10. S. Floyd, R. Gummadi, and S. Shenker, “Adaptive RED: An Algorithm for Increasing the Robustness of RED’s Active Queue Management,” Sep. 2001.
  11. M. Konovalov and R. Razumchik. (2017). “Queueing systems with renovation vs. queues with RED. Supplementary Material.” arXiv: 1709. 01477, [Online]. Available: https://arxiv.org/abs/1709.01477.
  12. I. Zaryadov and A. Korolkova, “The Application of model with general renovation to the analysis of characteristics of active queue management with random early detection (RED) [Primeneniye modeli s obobshchennym obnovleniyem k analizu kharakteristik sistem aktivnogo upravleniya ocheredyami tipa Random Early Detection (RED)],” T-Comm, no. 7, pp. 84-88, 2011, In Russian.
  13. H. Viana Carvalho Cravid et al., “The General Renovation as the Active Queue Management Mechanism. Some Aspects and Results,” in Communications in Computer and Information Science. 2019, vol. 1141, pp. 488-502. doi: 10.1007/978-3-030-36625-4_39.
  14. V. Jacobson, K. Nichols, and K. Poduri, “RED in a Different Light,” Tech. Rep., 1999.
  15. G. Fairhurst and M. Welzl. (2017). “The Benefits of Using Explicit Congestion Notification (ECN). RFC 8087,” [Online]. Available: https: //tools.ietf.org/html/rfc3168.
  16. C. So-In, R. Jain, and J. Jiang, “Enhanced Forward Explicit Congestion Notification (E-FECN) scheme for datacenter Ethernet networks,” in 2008 International Symposium on Performance Evaluation of Computer and Telecommunication Systems, 2008, pp. 542-546.
  17. C. Gomez, X. Wang, and A. Shami, “Intelligent active queue management using explicit congestion notification,” in 2019 IEEE Global Communications Conference (GLOBECOM), Sep. 2019, pp. 1-6. doi: 10.20944/preprints201909.0077.v1.
  18. S. Shahzad, E.-S. Jung, J. F. Chung M., and R. Kettimuthu, “Enhanced Explicit Congestion Notification (EECN) in TCP with P4 Programming,” in 2020 International Conference on Green and Human Information Technology (ICGHIT), Feb. 2020. doi: 10.1109/ICGHIT49656.2020. 00015.
  19. 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. 49 100-49 111, 2020. doi: 10.1109/ACCESS.2020.2979216.
  20. K. Nichols and V. Jacobson, “Controlling queue delay,” Communications of The ACM - CACM, vol. 55, pp. 42-50, May 2012. DOI: 10.1145/ 2209249.2209264.
  21. T. Hoeiland-Joergensen et al. (2018). “The Flow Queue CoDel Packet Scheduler and Active Queue Management Algorithm. RFC 8290,” [Online]. Available: https://www.rfc-editor.org/info/rfc8290.
  22. S. Jung, J. Kim, and J.-H. Kim, “Intelligent active queue management for stabilized QoS guarantees in 5G mobile networks,” IEEE Systems Journal, vol. PP, pp. 1-10, Aug. 2020. doi: 10.1109/JSYST.2020.3014231.
  23. W.-C. Feng, D. Kandlur, D. Saha, and K. Shin, “BLUE: a new class of active queue management algorithms,” University of Michigan, Tech. Rep., Sep. 2000. doi: 10.1109/TNET.2002.801399.
  24. 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.
  25. C. Zhang, J. Yin, and Z. Cai, “RSFB: a Resilient Stochastic Fair Blue algorithm against spoofing DDoS attacks,” in 2009 9th International Symposium on Communications and Information Technology, 2009, pp. 1566- 1567. doi: 10.1109/ISCIT.2009.5341033.
  26. G. Da-gang, “A New Adaptive BLUE Algorithm,” in 2010 International Conference on Electrical and Control Engineering, 2010, pp. 2601-2605. doi: 10.1109/iCECE.2010.638.
  27. T. Hoiland-Jorgensen, D. Taht, and J. Morton, “Piece of CAKE: A Comprehensive Queue Management Solution for Home Gateways,” in 2018 IEEE International Symposium on Local and Metropolitan Area Networks (LANMAN), Jun. 2018, pp. 37-42. doi: 10.1109/LANMAN.2018. 8475045.
  28. J. Palmei, S. Gupta, P. Imputato, J. Morton, M. Tahiliani, S. Avallone, and D. Taht, “Design and Evaluation of COBALT Queue Discipline,” in 2019 IEEE International Symposium on Local and Metropolitan Area Networks (LANMAN), Jul. 2019, pp. 1-6. doi: 10.1109/LANMAN.2019. 8847054.
  29. W.-C. Feng, “Improving Internet Congestion Control and Queue Management Algorithms,” Ph.D. dissertation, The University of Michigan, 1999.
  30. A. V. Korolkova, D. S. Kulyabov, and A. I. Chernoivanov, “On the classification of RED algorithms,” Bulletin of Peoples’ Friendship University of Russia. Series Mathematics. Information Sciences. Physics, no. 3, pp. 34-46, 2009, In Russian.
  31. A. Kreinin, “Queueing systems with renovation,” Journal of Applied Mathematics and Stochastic Analysis, vol. 10, pp. 431-443, Jan. 1997. doi: 10.1155/S1048953397000464.
  32. P. P. Bocharov and I. S. Zaryadov, “Probability Distribution in Queueing Systems with Renovation,” Bulletin of Peoples’ Friendship University of Russia. Series Mathematics. Information Sciences. Physics, pp. 15-25, 2007.
  33. E. Bogdanova et al., “Characteristics of lost and served packets for retrial queueing system with general renovation and recurrent input flow,” Communications in Computer and Information Science, vol. 919, pp. 327-340, 2018. doi: 10.1007/978-3-319-99447-5_28.
  34. I. Zaryadov, E. Bogdanova, T. Milovanova, S. Matushenko, and D. Pyatkina, “Stationary Characteristics of the GI/M/1 Queue with General Renovation and Feedback,” in 10th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), Nov. 2018, pp. 1-6. doi: 10.1109/ICUMT.2018.8631244.
  35. I. Zaryadov and A. Pechinkin, “Stationary time characteristics of the GI/M/n/oo system with some variants of the generalized renovation discipline,” Automation and Remote Control, vol. 70, pp. 2085-2097, Dec. 2009. doi: 10.1134/S0005117909120157.
  36. I. Zaryadov, “Queueing systems with general renovation,” in International Conference on Ultra Modern Telecommunications and Workshops, Oct. 2009, pp. 1-4. doi: 10.1109/ICUMT.2009.5345382.
  37. I. Zaryadov, R. Razumchik, and T. Milovanova, “Stationary waiting time distribution in G|M|n|r with random renovation policy,” in Communications in Computer and Information Science, vol. 678, Feb. 2016, pp. 349-360. doi: 10.1007/978-3-319-51917-3_31.
  38. E. V. Bogdanova, T. A. Milovanova, and I. S. Zaryadov, “The analysis of queuing system with general service distribution and renovation,” RUDN Journal of Mathematics, Information Sciences and Physics, vol. 25, no. 1, pp. 3-8, 2017. doi: 10.22363/2312-9735-2017-25-1-3-8.
  39. I. S. Zaryadov, E. V. Bogdanova, and T. A. Milovanova, “Probabilitytime characteristics of M|G|1|1 queueing system with renovation,” in CEUR Workshop Proceedings, vol. 1995, 2017, pp. 125-131.

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

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

Данный сайт использует cookie-файлы

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, которые обеспечивают правильную работу сайта.

О куки-файлах