Delay Estimation in Networks with Cooperative Arrival Dynamics

Introduction. Modern complex systems with a network structure are characterized by spatial and temporal long-term dependence of flows. The existing models of mass service theory based on the assumptions of stationarity and mutual statistical independence of fluctuations in the intensity of incoming flows significantly underestimate real delays.
Aim. Development of an improved model for estimation of aggregated traffic delays in highly loaded networks taking into account statistical characteristics of interrelations between activity fluctuations in nodes and channels of the network.
Materials and methods. A superstatistical approach is applied to analytically correct the Kingman formula for estimating the waiting time based on the calculation of the coefficients of variation of arrival intensities and mutual correlations between the intensities of the traffic generated by different nodes. Analytically obtained approximations of probability densities of delay distribution by q-exponential distributions are used to estimate the characteristics of aggregated traffic, the results of which are confirmed by the data of simulation modeling of aggregated traffic. In addition, the validation of the proposed estimations is performed on the example of analyzing empirical traffic data of the MAWI academic backbone network. The duration of the analyzed time segments of the traffic was adapted to adequately compare the results for model and empirical data, with integral statistics constructed based on the results of the analysis of several full-day records.
Results. An analytical model for estimating delays in aggregated traffic was developed, taking into account the coefficients of variation of arrival intensities and mutual correlations of traffic intensities originating from different nodes in the network. The analytical estimation of delay distribution was shown to give an intermediate result between the estimations obtained by using two modeling schemes, which is caused by the prevalence of errors of discreteness or finiteness of data sampling depending on the modeling scheme.
Conclusion. The application of the superstatistical approach to account for statistical interrelationships allows the estimates of delay times in highly loaded networks to be clarified on the basis of substituting the adjusted characteristics of aggregated traffic into the Kingman formula, thus providing more detailed estimates of delays in complex engineering systems with a network structure.

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. Khintchine A.Ya. Matematicheskaya teoriya statsionarnoi ocheredi [Mathematical Theory of Sta- tionary Queues]. Matem. Sbornik. 1932, vol. 39, no. 4, pp. 73–84. (In Russ.)

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