Теория сетевого исчисления: современное состояние, приложения и перспективы развития

Представлен обзор современного состояния и нерешенных задач в области теории сетевого исчисления (NC, Network Calculus) – одного из перспективных подходов к анализу сетевых моделей. NC предоставляет особый математический аппарат для получения гарантированных верхних оценок задержек трафика и объема данных в буфере сетевых устройств для обеспечения гарантий качества обслуживания в критически важных системах, таких как промышленные и бортовые сети, системы реального времени и облачные инфраструктуры. Изложены теоретические основы детерминированного NC, включая (min, +)- и (max, +)-алгебры, концепции кривых поступления и обслуживания.
Статья носит проблемно-аналитический характер, так как в ней наряду с описанием методов NC дано их сравнение, указаны недостатки и области применимости. Основное внимание уделено анализу последних достижений и исследований в области NC, включая стохастическое NC, методы анализа с учетом мультиплексирования потоков, интеграцию с методами теории массового обслуживания, а также применение моделей и методов NC в новых областях, таких как сети Ethernet с синхронизацией по времени, мобильные сети 5G/6G, сети с радиоканалами и облачные вычисления. Рассмотрены современные инструменты и вычислительные методы для преодоления сложностей анализа различных сетевых моделей. Обсуждены текущие проблемы и перспективные направления будущих исследований в области NC.

1. Cruz R.L. A calculus for network delay. I. Network elements in isolation // IEEE Trans. Inf. Theory. 1991. V. 37, No 1. P. 114–131. https://doi.org/10.1109/18.61109.

2. Cruz R.L. A calculus for network delay. II. Network analysis // IEEE Trans. Inf. Theory. 1991 . V. 37, No 1. P. 132–141. https://doi.org/10.1109/18.61110.

3. Le Boudec J.-Y., Thiran P. (Eds.) Network Calculus: A Theory of Deterministic Queuing Systems for the Internet. Ser.: Lecture Notes in Computer Science. V. 2050. Berlin, Heidelberg: Springer, 2001. xx, 276 p. https://doi.org/10.1007/3-540-45318-0.

4. Chang C.-S. Performance Guarantees in Communication Networks. Ser.: Telecommunication Networks and Computer Systems. London: Springer, 2000. xx, 392 p. https://doi.org/10.1007/978-1-4471-0459-9.

5. Росляков А.В., Лысиков А.А. Сетевое исчисление (Network Calculus) и его применение для оценки сетевых характеристик. Самара: ПГУТИ, 2019. 222 с.

6. Росляков А.В., Лысиков А.А., Витевский В.Д. Сетевое исчисление Network Calculus. Часть 1. Теоретические основы // Инфоком. технол. 2018. Т. 16, № 1. С. 19–33.

7. Росляков А.В, Герасимов В.В. Применение теории сетевого исчисления для анализа задержек трафика радиоинтерфейса eCPRI в сегменте Fronthaul мобильных сетей 4G/5G // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. 2025. Т. 167, кн. 2. С. 351–366. https://doi.org/10.26907/2541-7746.2025.2.351-366.

8. Ciucu F., Schmitt J.B. Perspectives on network calculus: No free lunch, but still good value // ACM SIGCOMM Comput. Commun. Rev. 2012. V. 42, No 4. P. 311–322. https://doi.org/10.1145/2377677.2377747.

9. Fidler M., Rizk A. A guide to the stochastic network calculus // IEEE Commun. Surv. Tutorials. 2015. V. 17, No 1. P. 92–105. https://doi.org/10.1109/COMST.2014.2337060.

10. Bondorf S., Nikolaus P., Schmitt J.B. Quality and cost of Deterministic Network Calculus: Design and evaluation of an accurate and fast analysis // Proc. ACM Meas. Anal. Comput. Syst. 2017. V. 1, No 1. Art. 16. https://doi.org/10.1145/3084453.

11. Finn N., Thubert P., Varga B., Farkas J. Deterministic Networking Architecture. RFC 8655. IETF, 2019. 38 p. https://doi.org/10.17487/RFC8655.

12. Zhao L., Pop P., Craciunas S.S. Worst-case latency analysis for IEEE 802.1Qbv Time Sensitive Networks using network calculus // IEEE Access. 2018. V. 6. P. 41803–41815. https://doi.org/10.1109/ACCESS.2018.2858767.

13. Foukas X., Patounas G., Elmokashfi A., Marina M.K. Network slicing in 5G: Survey and challenges // IEEE Commun. Mag. 2017. V. 55, No 5. P. 94–100. https://doi.org/10.1109/MCOM.2017.1600951.

14. Литвинов Г.Л., Маслов В.П., Соболевский А.Н. Идемпотентная математика и интервальный анализ // Вычисл. технол. 2001. Т. 6, № 6. С. 47–70.

15. Jiang Y., Liu Y. Stochastic Network Calculus. London: Springer, 2008. xix, 232 p. https://doi.org/10.1007/978-1-84800-127-5.

16. Lin C., Deng Y., Jiang Y. On applying stochastic network calculus // Front. Comput. Sci. 2013. V. 7, No 6. P. 924–942. https://doi.org/10.1007/s11704-013-3095-1.

17. Li X., Ni R., Chen J., Lyu Y., Rong Z., Du R. End-to-end network slicing in radio access network, transport network and core network domains // IEEE Access. 2020. V. 8. P. 29525–29537. https://doi.org/10.1109/ACCESS.2020.2972105.

18. Popovski P., Nielsen J.J., Stefanovi´c C., de Carvalho E., Str¨om E., Trillingsgaard K.F., ˇ Bana A.-S., Kim D.M., Kotaba R., Park J., Sørensen R.B. Wireless access for ultra-reliable low-latency communication: Principles and building blocks // IEEE Network. 2018. V. 32, No 2. P. 16–23. https://doi.org/10.1109/MNET.2018.1700258.

19. Finn N., Le Boudec J.-Y., Mohammadpour E., Zhang J., Varga B. Deterministic Networking (DetNet) Bounded Latency. RFC 9320. IETF, 2022. 26 p. https://doi.org/10.17487/RFC9320.

20. Schmitt J.B., Zdarsky F.A. The DISCO Network Calculator – a toolbox for worst case analysis // Proc. 1st Int. Conf. on Performance Evaluation Methodologies and Tools (ValueTools’06). New York, NY: Assoc. Comput. Mach., 2006. Art. 8–es. https://doi.org/10.1145/1190095.1190105.

21. Beck M.A., Schmitt J.B. The DISCO Stochastic Network Calculator version 1.0 – when waiting comes to an end // Proc. 7th Int. Conf. on Performance Evaluation Methodologies and Tools (ValueTools’13). Brussels: ICST, 2013. P. 282–285. https://doi.org/10.4108/icst.valuetools.2013.254378.

22. Bouillard A., Nikolaus P., Schmitt J.B. Unleashing the power of paying multiplexing only once in stochastic network calculus // Proc. ACM Meas. Anal. Comput. Syst. 2022. V. 6, No 2. Art. 31. https://doi.org/10.1145/3530897.

23. Schmitt J.B., Zdarsky F.A., Fidler M. Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch... // Proc. IEEE INFOCOM 2008 – 27th Conf. on Computer Communications. Phoenix, AZ: IEEE, 2008. P. 1669–1677. https://doi.org/10.1109/INFOCOM.2008.228.

24. Fidler M., Schmitt J.B. On the way to a distributed systems calculus: An end-to-end network calculus with data scaling // SIGMETRICS06: Proc. 2006 ACM SIGMETRICS Int. Conf. on Measurement and Modeling of Computer System. Saint Malo: Assoc. Comput. Mach., 2006. P. 287–298. https://doi.org/10.1145/1140277.1140310.

25. Li C., Burchard A., Liebeherr J. A network calculus with effective bandwidth // IEEE/ACM Trans. Networking. 2007. V. 15, No 6. P. 1442–1453. http://dx.doi.org/10.1109/TNET.2007.896501.

26. Zhu J., Wang S. QoS-guaranteed resource allocation in mobile communications: A stochastic network calculus approach // IEEE/ACM Trans. Networking. 2024. V. 32, No 6. P. 5159–5171. https://doi.org/10.1109/TNET.2024.3458922.

27. Specht J., Samii S. Urgency-based scheduler for time-sensitive switched Ethernet networks // Proc. 2016 28th Euromicro Conf. on Real-Time Systems (ECRTS). Toulouse: IEEE, 2016. P. 75–85. https://doi.org/10.1109/ECRTS.2016.27.

28. Guo J., Wang H., Wang Z., Chang Z. Upper bound analysis of TSN end-to-end delay based on network calculus // Proc. 2023 5th Int. Conf. on Natural Language Processing (ICNLP). Guangzhou: IEEE, 2023. P. 394–399. https://doi.org/10.1109/ICNLP58431.2023.00078.

29. Liebeherr J., Burchard A., Ciucu F. Delay bounds in communication networks with heavy-tailed and self-similar traffic // IEEE Trans. Inf. Theory. 2012. V. 58, No 2. P. 1010–1024. https://doi.org/10.1109/TIT.2011.2173713.

30. Fidler M. An end-to-end probabilistic network calculus with moment generating functions // Proc. 2006 14th IEEE Int. Workshop on Quality of Service. New Haven, CT: IEEE, 2006. P. 261–270. https://doi.org/10.1109/IWQOS.2006.250477.

31. Bouet M., Leguay J., Conan V. Cost-based placement of virtualized Deep Packet Inspection functions in SDN // MILCOM 2013 – 2013 IEEE Military Communications Conf. San Diego, CA: IEEE, 2013. P. 992–997. https://doi.org/10.1109/MILCOM.2013.172.

32. Funda C., Herpel T., German R., Hielscher K.-S.J. TBASCEM - Tight Bounds with Arrival and Service Curve Estimation by Measurements // ICPE’24: Proc. 15th ACM/SPEC Int. Conf. on Performance Engineering. London: Assoc. Comput. Mach., 2024. P. 224–235. https://doi.org/10.1145/3629526.3645031.

33. DISCO Network Calculator. 2022. URL: http://disco.informatik.uni-kl.de/index.php/projects/disco-network-calculator.

34. RTaW-Pegase. 2023. URL: https://www.realtimeatwork.com/rtaw-pegase/.

35. Bouillard A., Junier A. Worst-case delay bounds with fixed priorities using network calculus // Proc. 5th Int. ICST Conf. on Performance Evaluation Methodologies and Tools (ValueTools’2011). Brussels: ICST, 2011. P. 381–390. https://doi.org/10.4108/icst.valuetools.2011.245603.

36. Malik A., Roop P. A dynamic Quantized State System execution framework for Hybrid Automata // Nonlinear Anal.: Hybrid Syst. 2020. V. 36. Art. 100870. https://doi.org/10.1016/j.nahs.2020.100870.

37. Craciunas S.S., Oliver R.S., Chmel´ık M., Steiner W. Scheduling real-time communication in IEEE 802.1Qbv time sensitive networks // RTNS’16: Proc. 24th In. Conf. on Real-Time Networks and Systems. New York, NY: Assoc. Comput. Mach., 2016. Р. 183–192. https://doi.org/10.1145/2997465.2997470.

38. Geyer F., Bondorf S. DeepTMA: Predicting effective contention models for network calculus using graph neural networks // Proc. IEEE INFOCOM 2019 - IEEE Conf. on Computer Communications. Paris: IEEE, 2019. P. 1009–1017. https://doi.org/10.1109/INFOCOM.2019.8737496.

39. Promyslov V.G., Semenkov K.V. Assessment of deterministic delay bounds for a DoS-attack prevention device with a static window flow control // IFAC-PapersOnLine. 2020. V. 53, No 2. P. 11089–11093. https://doi.org/10.1016/j.ifacol.2020.12.251.

40. Росляков А.В., Марыков М.В. Описание верхней границы задержки и длины очереди коммутатора в сети SDN // Матер. XXVI Международ. науч.-техн. конф. «Проблемы техники и технологий телекоммуникаций». Самара: ПГУТИ, 2024. С. 142–143.

41. Росляков А.В. Оценка задержек в детерминированных сетях // Матер. XXXII Российск. науч.-техн. конф. «Актуальные проблемы информатики, радиотехники и связи». Самара: ПГУТИ, 2025. С. 65–66.

42. Росляков А.В., Лысиков А.А. Применение теории стохастических сетевых исчислений к анализу характеристик VPN // T-Comm. Телеком. Транспорт. 2013. № 7. С. 106–108. https://doi.org/10.12825/2072-8044-2013-7-106-108.

43. Росляков А.В., Лысиков А.А. Сетевое исчисление Network Calculus. Часть 2. Практическое применение // Инфоком. технол. 2020. Т. 18, № 3. С. 237–248. https://doi.org/10.18469/ikt.2020.18.3.01.