Bidirectional search procedure development for solving the the transport software-defined network routing problem


DOI: 10.34759/trd-2021-118-07

Аuthors

Volkov A. S.1*, Baskakov A. E.2**

1. National Research University of Electronic Technology, Bld. 1, Shokin Square, Zelenograd, Moscow, Russia, 124498
2. National Research University of Electronic Technology, 1, sq. Shokina, Moscow, Zelenograd, 124498, Russia

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

Abstract

Modern communication networks represent a complex architectural solution that performs a number of telecommunication tasks, which solution allows the most efficient transmission of large amounts of data through the network. The annual growth in the transmitted traffic volume makes the network technologies application for a long period of time without changes impossible, since the requirements for its processing grow, and increasingly stringent restrictions are being imposed on the network solutions and equipment along with it. One of the most important parameters of data transmission is the end-to-end delay. It represents a set of time values required for an incoming network packet processing and transmitting it through the physical communication channels, as well as the operating time of the network protocols and technologies being employed, in particular, the time spent on of various tables’ construction and operation of algorithms software implementations.

Thus, the solution to the above-said problem can be reduced in the first approximation to the problem of finding a set of routes on a graph describing the a communication network topology.

The existing standard solutions to the problem of searching for the paths on a graph describe, as a rule, the solution to the single route searching per one algorithm iteration, or provide the ability to search for exclusively disjoint data transmission paths, which in some cases is not sufficient for solving the original problem. Application of the routes searching algorithm with the auxiliary graph constructing, allowing find a set of paths, including partially intersecting ones, on the graph from one vertex to another, or from one vertex to set of vertices, may alter the situation. This solution disadvantage consists in critical increase of the algorithm operating time while employing graphs of large dimensionality.

This problem can be solved by applying the bidirectional search method for the above-said algorithm with the auxiliary graph constructing. Thus, the original graph can be conditionally divided into two parts, being the subgraphs from the original graph, connected by the generated paths. A mandatory condition herewith is starting and ending points finding in the constructed subgraphs, then, the auxiliary graphs construction based on them will allow reducing the time complexity by up to two times, depending on the specific software implementation of the algorithm and the methods of the graph writing: adjacency list, incidence list, adjacency matrix etc. The calculated time complexity herewith for the tested network topology containing eight nodes and the connections between them will be 519.23 and 105.95 for the algorithm based on the auxiliary graph and its bidirectional variation, respectively.

Keywords:

software-defined network, transport network resource management, bidirectional transmission paths search

References

  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. Borodin V.V., Petrakov A.M., Shevtsov V.A. Trudy MAI, 2016, no. 87. URL: http://trudymai.ru/eng/published.php?ID=69735

  13. Borodin V.V., Petrakov A.M., Shevtsov V.A. Trudy MAI, 2018, no. 100. URL: http://trudymai.ru/eng/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. Shevtsov V.A., Borodin V.V., Krylov M.A. Trudy MAI, 2016, no. 85. URL: http://trudymai.ru/eng/published.php?ID=66417

  17. Morshinin A.V. Vestnik Omskogo universiteta, 2018, vol. 23, no. 1, pp. 4 — 9. DOI: 10.25513/1812-3996.2018.23(1).4-9

  18. Kurnosov A.D. Trudy MFTI, 2020, vol. 12, no. 2, pp. 40 — 54.

  19. Baranskii V.A., Sen’chonok T.A. Sibirskie elektronnye matematicheskie izvestiya, 2020, vol. 17, pp. 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


    Download

mai.ru — informational site MAI

Copyright © 2000-2024 by MAI

 Вход