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

Введение. Современные сложные системы с сетевой структурой характеризуются пространственно-временной долговременной зависимостью потоков. Существующие модели теории массового обслуживания, основанные на предположениях о стационарности и взаимной статистической независимости флуктуаций интенсивности входящих потоков, существенно недооценивают реальные задержки.
Цель работы. Разработка усовершенствованной модели оценки задержек агрегированного трафика в высоконагруженных сетях с учетом статистических характеристик взаимосвязей между флуктуациями активности в узлах и каналах сети.
Материалы и методы. Применен суперстатистический подход для аналитической коррекции формулы Кингмана при оценке времени ожидания на основе вычисления коэффициентов вариации интенсивностей поступления и взаимных корреляций между интенсивностями трафика, сформированного различными узлами. Для оценки характеристик агрегированного трафика использованы аналитически полученные аппроксимации плотностей вероятности распределения задержки q-экспоненциальными распределениями, результаты которых подтверждаются данными имитационного моделирования агрегированного трафика. Дополнительно выполнена валидация предложенных оценок на примере анализа эмпирических данных трафика магистральной академической сети MAWI. Длительность анализируемых временных сегментов трафика была адаптирована для адекватного сравнения результатов для модельных и эмпирических данных, при этом интегральные статистики построены на основе результатов анализа нескольких полносуточных записей.
Результаты. Разработана аналитическая модель для оценки задержек в агрегированном трафике, учитывающая коэффициенты вариации интенсивности поступления и взаимные корреляции интенсивностей трафика, исходящего от различных узлов сети. Показано, что аналитическая оценка распределения задержек дает промежуточный результат между оценками, получаемыми при использовании двух схем моделирования. Это обусловлено превалированием ошибок дискретности или конечности выборки данных в зависимости от схемы моделирования.
Заключение. Применение суперстатистического подхода для учета статистических взаимосвязей позволяет уточнить оценки времен запаздывания в высоконагруженных сетях на основе подстановки скорректированных характеристик агрегированного трафика в формулу Кингмана, что позволяет уточнить оценки задержек в сложных технических системах с сетевой структурой. 

1. Erlang A. K. Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges // Elektrotkeknikeren. 1917. Vol. 13. P. 138–155.

2. Pollaczek F. Über Eine Aufgabe der Wahrscheinlichkeitstheorie I // Mathematische Zeitschrift. 1930. Vol. 32, № 1. P. 64–100. doi: 10.1007/BF01194620

3. Хинчин А. Я. Математическая теория стационарной очереди // Мат. сб. 1932. Т. 39, № 4. С. 73–84.

4. Kingman J. F. C. The single server queue in heavy traffic // Mathematical Proc. of the Cambridge Philosophical Society. 1961. Vol. 57, № 04. P. 902–904. doi: 10.1017/S0305004100036094

5. Marchal W. G. An approximate formula for waiting time in single server queues // AIIE Trans. 1976. Vol. 8, № 4. P. 473–474. doi: 10.1080/05695557608975111

6. Krämer W., Langenbach-Belz M. Approximate formulae for the delay in the queueing system GI/G/l // Proc. 8th Intern. Teletraffic Congr. 1976. Vol. 235, № 1. P. 1–8.

7. On the self-similar nature of ethernet traffic (extended version) / W. E. Leland, M. S. Taqqu, W. Willinger, D. V. Wilson // IEEE/ACM Transactions on Networking. 1994. Vol. 2, iss. 1. P. 1–15. doi: 10.1109/90.282603

8. Paxson V., Floyd S. Wide area traffic: the failure of Poisson modeling // IEEE/ACM Transactions on Networking. 1995. Vol. 3, iss. 3. P. 226–244. doi: 10.1109/90.392383

9. The changing nature of network traffic: Scaling phenomena / A. Feldmann, A. C. Gilbert, W. Willinger, T. G. Kurtz // ACM SIGCOMM Comput. Commun. Rev. 1998. Vol. 28, iss. 2. P. 5–29. doi: 10.1145/279345.279346

10. Park K., Willinger W. Self-Similar Network Traffic and Performance Evaluation. John Wiley & Sons, 2000. 558 p. doi: 10.1002/047120644X

11. Universal model for collective access patterns in the Internet traffic dynamics: A superstatistical approach / A. Tamazian, V. Nguyen, O. Markelov, M. Bogachev // EPL. 2016. Vol. 115, № 1. Art. № 10008. doi: 10.1209/0295-5075/115/10008

12. Markelov O., Duc V. N., Bogachev M. Statistical modeling of the Internet traffic dynamics: To which extent do we need long-term correlations? // Physica A: Statistical Mechanics and its Applications. 2017. Vol. 485. P. 48–60. doi: 10.1016/j.physa.2017.05.023

13. Universal rank-size statistics in network traffic: Modeling collective access patterns by Zipf’s law with long-term correlations / V. Nguyen, O. Markelov, A. Serdyuk, A. Vasenev, M. Bogachev // EPL. 2018. Vol. 123, № 5. Art. № 50001. doi: 10.1209/0295-5075/123/50001

14. Service delays in strongly linked network communities / M. Bogachev, N. Pyko, S. Pyko, A. Vasenev // J. of Physics: Conf. Ser. 2019. Vol. 1352, iss. 1. Art. № 012006. doi: 10.1088/1742-6596/1352/1/012006

15. Liu Y., Whitt W. Stabilizing performance in networks of queues with time-varying arrival rates // Probability in the Engineering and Informational Sciences. 2014. Vol. 28, № 4. P. 419–449. doi: 10.1017/S0269964814000084

16. Pender J., Rand R. H., Wesson E. An analysis of queues with delayed information and time-varying arrival rates // Nonlinear Dyn. 2018. Vol. 91, № 4. P. 2411–2427. doi: 10.1007/s11071-017-4021-0

17. Whitt W. Time-varying queues. Queueing Models Serv. Manag. 2018. Vol. 1, № 2. P. 79–164.

18. Dudin A., Klimenok V. I., Vishnevsky V. M. The Theory of Queuing Systems with Correlated Flows. Cham: Springer, 2020. 410 p. doi: 10.1007/978-3-030-32072-0

19. An approximate mean queue length formula for queueing systems with varying service rate / J. Zhang, T. T. Lee, T. Ye, L. Huang // J. of Industrial and Management Optimization. 2021. Vol. 17, iss. 1. P. 185–204. doi: 10.3934/jimo.2019106

20. Bogachev M., Eichner J., Bunde A. The effects of multifractality on the statistics of return intervals // The European Physical J. Special Topics. 2008. Vol. 161, № 1. P. 181–193. doi: 10.1140/epjst/e2008-00760-5

21. Bogachev M. I., Eichner J. F., Bunde A. On the occurrence of extreme events in long-term correlated and multifractal data sets // Pure and Applied Geophysics. 2008. Vol. 165. P. 1195–1207. doi: 10.1007/s00024-008-0353-5

22. Podobnik B., Stanley H. E. Detrended crosscorrelation analysis: A new method for analyzing two nonstationary time series // Phys. Rev. Let. 2008. Vol. 100, № 8. Art. № 084102. doi: 10.1103/PhysRevLett.100.084102

23. Detrended partial cross-correlation analysis of two nonstationary time series influenced by common external forces / X.-Y. Qian, Y.-M. Liu, Z.-Q. Jiang, B. Podobnik, W.-X. Zhou, H. E. Stanley // Phys. Rev. E. 2015. Vol. 91, № 6. Art. № 062816. doi:10.1103/PhysRevE.91.062816

24. Detrended partial-cross-correlation analysis: A new method for analyzing correlations in complex system / N. Yuan, Z. Fu, H. Zhang, L. Piao, E. Xoplaki, J. Luterbacher // Scientific Reports. 2015. Vol. 5, № 1. P. 1–7. Art. № 8143. doi: 10.1038/srep08143

25. Bogachev M., Bunde A. On the occurrence and predictability of overloads in telecommunication networks // EPL. 2009. Vol. 86, № 6. Art. № 66002. doi: 10.1209/0295-5075/86/66002

26. Approximate waiting times for queuing systems with variable long-term correlated arrival rates / M. I. Bogachev, A. V. Kuzmenko, O. A. Markelov, N. S. Pyko, S. A. Pyko // Physica A: Statistical Mechanics and its Applications. 2023. Vol. 614. Art. № 128513. doi: 10.1016/j.physa.2023.128513

27. Approximate waiting times for queuing systems with variable cross-correlated arrival rates / M. I. Bogachev, N. S. Pyko, N. S. Tymchenko, S. A. Pyko, O. A. Markelov // Physica A: Statistical Mechanics and its Applications. 2024. Vol. 654. Art. № 130152. doi: 10.1016/j.physa.2024.130152

28. Kendall D. G. Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain // The Annals of Mathematical Statistics. 1953. Vol. 24, iss. 3. P. 338–354. doi: 10.1214/aoms/1177728975

29. IoT network model with multimodal node distribution and data-collecting mechanism using mobile clustering nodes / D. Vorobyova, A. Muthanna, A. Paramonov, O. A. Markelov, A. Koucheryavy, G. Ali, E. L. M. Affendi, A. A. Abd El-Latif // Electronics. 2023. Vol. 12, № 6. Art. № 1410. doi: 10.3390/electronics12061410

30. Little J. D. A proof for the queuing formula: L = λW // Operations Research. 1961. Vol. 9, № 3. P. 383–387. doi: 10.1287/opre.9.3.383

31. Oliver R. M. An alternate derivation of the Pollaczek-Khintchine formula // Oper. Res. 1964. Vol. 12, № 1. P. 158–159. doi: 10.1287/opre.12.1.158

32. Cohen J. E. Sum of a random number of correlated random variables that depend on the number of summands // The American Statistician. 2019. Vol. 73, iss. 1. P. 56–60. doi: 10.1080/00031305.2017.1311283