Разработка процедуры двунаправленного поиска для решения задачи маршрутизации в транспортных программно-конфигурируемых сетей


DOI: 10.34759/trd-2021-118-07

Авторы

Волков А. С.1*, Баскаков А. Е.2**

1. Национальный исследовательский университет «МИЭТ», 124498, Москва, Зеленоград, пл. Шокина, д. 1
2. Национальный исследовательский университет «Московский институт электронной техники», площадь Шокина, 1, Москва, Зеленоград, 124498, Россия

*e-mail: leshvol@mail.ru
**e-mail: 79999924816@ya.ru

Аннотация

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

Программно-конфигурируемые сети связи, как правило, функционируют на базе установленных протоколов, описывающих процедуры взаимодействия ПКС-коммутаторов и контроллера, например, протокол OpenFlow. Так, контроллер имеет актуальную информацию о сети связи, ее топологии и отдельных устройства, а значит, сеть связи может быть представлена в виде неориентированного взвешенного графа, что сводит задачу маршрутизации к задаче поиска множества путей на графе.

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

Ключевые слова:

программно-конфигурируемые сети, управление ресурсами транспортной сети, двунаправленный поиск путей передачи

Библиографический список

  1. Hou A. et al. Bandwidth scheduling for big data transfer using multiple fixed node-disjoint paths // Journal of Network and Computer Applications, 2017, vol. 85, pp. 47 — 55. DOI: 10.1016/j.jnca.2016.12.011

  2. Srinivasan S.M., Truong-Huu T., Gurusamy M. Flexible bandwidth allocation for big data transfer with deadline constraints // 2017 IEEE Symposium on Computers and Communications (ISCC), IEEE, 2017, pp. 347 — 352. DOI:10.1109/ISCC.2017.8024554

  3. Aleksieva V., Haka A. Modified scheduler for traffic prioritization in lte networks // International Conference on Intelligent Information Technologies for Industry, Springer, Cham, 2017, pp. 228 — 238. DOI:10.1007/978-3-319-68324-9_25

  4. Yamada Y. et al. Feature-selection based data prioritization in mobile traffic prediction using machine learning // 2018 IEEE Global Communications Conference (GLOBECOM), IEEE, 2018. DOI:10.1109/GLOCOM.2018.8647627

  5. Barakabitze A.A. et al. 5G network slicing using SDN and NFV: A survey of taxonomy, architectures and future challenges // Computer Networks, 2020, vol. 167, pp. 106984. DOI:10.1016/j.comnet.2019.106984

  6. Alsaeedi M., Mohamad M.M., Al-Roubaiey A.A. Toward adaptive and scalable OpenFlow-SDN flow control: A survey // IEEE Access, 2019, vol. 7, pp. 107346 — 107379. DOI:10.1109/ACCESS.2019.2932422

  7. Priya A.V., Radhika N. Performance comparison of SDN OpenFlow controllers // International Journal of Computer Aided Engineering and Technology, 2019, vol. 11, no. 4-5, pp. 467 — 479. DOI: 10.1504/IJCAET.2019.100444

  8. Gopi D., Cheng S., Huck R. Comparative analysis of SDN and conventional networks using routing protocols // 2017 International Conference on Computer, Information and Telecommunication Systems (CITS), IEEE, 2017, pp. 108 — 112. DOI:10.1109/CITS.2017.8035305

  9. Waleed S. et al. Demonstration of single link failure recovery using Bellman Ford and Dijikstra algorithm in SDN // 2017 International Conference on Innovations in Electrical Engineering and Computational Technologies (ICIEECT), IEEE, 2017, DOI:10.1109/ICIEECT.2017.7916533

  10. Wang X. Y. L. SDN load balancing method based on K-Dijkstra // International Journal of Performability Engineering, 2018, vol. 14, no. 4, pp. 709. DOI:10.23940/ijpe.18.04.p14.709716

  11. Dong K. et al. Auxiliary graph based routing, wavelength, and time-slot assignment in metro quantum optical networks with a novel node structure // Optics express, 2020, vol. 28, no. 5, pp. 5936 — 5952. DOI:10.23919/PS.2019.8817743

  12. Бородин В.В., Петраков А.М., Шевцов В.А. Анализ алгоритмов маршрутизации в сети связи группировки беспилотных летательных аппаратов // Труды МАИ. 2016. № 87. URL: http://trudymai.ru/published.php?ID=69735

  13. Бородин В.В., Петраков А.М., Шевцов В.А. Имитационная модель для исследования адаптивных сенсорных сетей // Труды МАИ. 2018. № 100. URL: http://trudymai.ru/published.php?ID=93398

  14. Tripp-Barba C. et al. Survey on routing protocols for vehicular ad hoc networks based on multimetrics // Electronics, 2019, vol. 8, no. 10, pp. 1177. DOI:10.3390/electronics8101177

  15. Borodin V., Shevtsov V., Petrakov A., Shevgunov T. Characteristics of Updating Route Information of Networks with Variable Topology // Proceedings of the Computational Methods in Systems and Software. Springer, Cham, 2019, pp. 376 — 384. DOI:10.1007/978-3-030-30329-7_33

  16. Шевцов В.А., Бородин В.В., Крылов М.А. Построение совмещенной сети сотовой связи и самоорганизующейся сети с динамической структурой // Труды МАИ. 2016. № 85. URL: http://trudymai.ru/published.php?ID=66417

  17. Моршинин А.В. Об одной задаче кластеризации графа // Вестник Омского университета. 2018. Т. 23. № 1. C. 4 — 9. DOI: 10.25513/1812-3996.2018.23(1).4-9

  18. Курносов А.Д. О нижней оценке числа связного доминирования в графах с фиксированной степенной последовательностью // Труды МФТИ. 2020. Т. 12. № 2. С. 40 — 54.

  19. Баранский В.А., Сеньчонок Т.А. О максимальных графических разбиениях, ближайших к заданному графическому разбиению // Сибирские электронные математические известия. 2020. Т. 17. С. 338 — 363.

  20. Dragan F.F., Köhler E., Leitert A. Line-distortion, bandwidth and path-length of a graph // Algorithmica, 2017, vol. 77, no. 3, pp. 686 — 713. DOI:10.1007/978-3-319-08404-6_14


    Скачать статью

mai.ru — информационный портал Московского авиационного института

© МАИ, 2000—2024

 Вход