СНИЖЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ КОНСТРУИРОВАНИЯ ДОПУСТИМЫХ МНОГОМЕРНЫХ МАРШРУТОВ МЕТОДА СОВМЕСТНОЙ ДИНАМИЧЕСКОЙ МАРШРУТИЗАЦИИ
Authors: Винтенкова Ю.С. , Козлов С.В. 
Published: February 2025

В статье проводится сравнительный анализ и синтез вариантов конструирования допустимых многомерных маршрутов метода совместной динамической маршрутизации с точки зрения снижения вычислительной сложности их реализации. Рассматривается вариант использования задачи нахождения максимального независимого множества вершин теории графов для получения многомерных маршрутов максимальной размерности с последующим конструированием допустимых многомерных маршрутов меньших размерностей. Делается вывод о том, что непосредственное использование указанного подхода лишь увеличивает вычислительную сложность конструирования допустимых многомерных маршрутов изза необходимости использования операций сочетания и исключения одинаковых маршрутов, в то время как применение модифицированного алгоритма позволяет снизить вычислительную сложность на 7 .
Introduction. Collective dynamic routing (CDR) method was proposed to increase data throughput of IP networks that operate under the influence of multiuser interferences. CDR method operates in two stages: analysis stage and routing stage. The forming of valid routes set is one of the important objectives of the analysis stage. The objective includes the search for onedimensional routes and the construction of multidimensional routes, which are the combinations of onedimensional routes without using the same channels. Purpose and objectives. The aim of the research is to carry out the analysis and synthesis of computational complexity reduction methods for solving the problem of construction of valid multidimensional routes. To solve this problem, an algorithm of a complete search for one dimensional routes was previously proposed. It ensures that all multidimensional routes will be found, however, like the other methods based on complete search, it has a high computational complexity. Also, the graph theory can be applied to construct multidimensional routes. If a set of onedimensional routes is represented as a graph, then the construction of valid multidimensional route of maximum dimension can be equivalent to the problem of finding the maximum independent set of vertices, for which a large number of algorithms have been developed. Research outcomes allowed to conclude that the use of the BronKerbosch algorithm is appropriate for solving the problem. Findings. Computational complexity comparison for the previously proposed algorithm of complete search and the BronKerbosch algorithm with additional combination operations was carried out on the communication network with the use of the opensource integrated development environment Lazarus. Analysis showed a significant increase in the computational complexity of valid multidimensional routes construction procedure of the BronKerbosch algorithm with combination operations due to the large number of combination operations and the removal of identical valid multidimensional routes. The modified BronKerbosch algorithm was proposed to reduce the computational complexity. The route search procedure was modified in order to construct routes of all dimensions, which allowed to reduce the computational complexity compared to the algorithm of complete search for onedimensional routes. Conclusions. The application of modified BronKerbosch algorithm allowed to reduce computational complexity of valid multidimensional routes construction procedure by 7 in comparison to complete search algorithm.