Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Software systems and computational methods
Reference:

Search algorithm for loopless routes

Demichev Maksim Sergeevich

Design Engineer of Information Security, JSC Scientific Production Enterprise "Radiosviaz"

660000, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Krasnoyarskii Rabochii, 31

mdemichev@yandex.ru
Other publications by this author
 

 
Gaipov Konstantin Eduardovich

PhD in Technical Science

Docent, the department of Electronic Technology and Telecommunications, Reshetnev Siberian State University of Science and Technology

660000, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Krasnoyarskii Rabochii, 31

cyberjam@yandex.ru
Other publications by this author
 

 

DOI:

10.7256/2454-0714.2020.4.33605

Received:

04-08-2020


Published:

31-12-2020


Abstract: The subject of this research is the search algorithm for loopless routes from transmitter to the recipient of network traffic in the conditions of a known network topology. In designing data transmission network, one of the primary problems is the formation of network traffic routing, due to the fact that heavy traffic often cause the occurrence of bottlenecks in form of the overloaded communication node, which results in speed reduction of data transmission. This article provides the search algorithm for loopless routes from transmitter to the recipient of network traffic; the result is presented as a set of loopless  routes in accordance with the specified network topology. The article also provides the software code of the algorithm written in the C# language, as well as the results of test solutions of the specified topologies. The algorithm was developed via experimental and theoretical methods, on the bases of the available route search algorithms, such as Floyd's algorithm and Dijkstra's algorithm, as well as mechanisms of static and dynamic routing, such as RIP, OSPF, and EIGRP. The novelty of this work consists in elaboration of search algorithm for loopless routes from transmitter to the recipient in the conditions of the available network topology; and in comparison of the acquired results with other methods of formation phase variables. This algorithm allows generating a list of all loopless routes within the indicated network topology between the pair of interacting nodes.


Keywords:

Loopless routes, phase variables, routing, graph algorithms, router, graph, vertex, matrix, array, list


Введение. Решение задачи управления трафиком является одной из ключевых задач телекоммуникационной индустрии, классификация таких задач приведена в [8,9,10]. Управление трафиком охватывает задачу анализа, оптимизации и синтеза телекоммуникационных сетей, что ведет к необходимости получению математической модели сети, которая описывается набором линейно-независимых переменных, выбор того или иного набора переменных будет определять размерность системы уравнений или целевой функции, что в конечном итоге будет определять время, затрачиваемое на решение такой математической модели. Набор линейно-независимых переменных, которым может быть описана телекоммуникационная сеть, являются контурные или узловые интенсивности [1], сложность определения набора таких линейно-независимых переменных определяется сложность алгоритма поиска ранга матрицы (алгоритм Гаусса)[2, стр. 44], количество же самих переменных определяется циклическим или коцеклическим числом направленного графа, которым описывается телекоммуникационная сеть, умноженного на количество источников нагрузки, подключённых к сети. Еще одним способом введение переменных является способ предложенный в [3, 4], в котором предполагается, что переменными будут являться все беспетельные маршруты, при этом алгоритм их нахождения предложен как алгоритм Флойда [5, 6], который обеспечивает поиск не всех беспетельных маршрутов, а всех наикратчайших маршрутов от одной вершины ко всем остальным, таким образом сам алгоритм поиска всех беспетельных маршрутов не предложен, а также не ясна закономерность числа маршрутов в зависимости от количества ребер между узлами графи, поэтому целью данной статьи является разработка такого алгоритма и сравнение количества получаемых маршрутов с количеством лейно-независимых циклов и разрезов.

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

Решение. Для описания алгоритма решения поставленной задачи, введем основные переменные, списки и массивы:

1. Матрица А[i,j] – матрица смежности [7], описывает взаимосвязь узлов связи в топологии сети, где i ∈ – номер передающего узла (номер строки) связи, i [1..N], j – номер (номер столбца) принимающего узла связи, j [1..N].

2. Список Result[k] – список, содержащий беспетельные маршруты от отправителя до получателя, где k – номер записи списка.

Запись в Result[k] k-ого маршрута, рассматривается как массив, то есть записанный k-ый маршрут состоит из номеров узлов связи, имеющие свои индексы записи, таким образом, запись Result[k,m] говорит о k-ой записи и m – номера записи в массиве, где k ∈ [1..K], K – номер последней записи списка Result, m ∈ [1..M] и М – номер последнего индекса массива k-ой записи, само содержимое записи Result[k,m] ∈ [1..N].

3. Список Routes[t] – список, содержащий маршруты, по которым еще будет проводиться поиск беспетельных маршрутов, где t – номер записи списка.

Порядок чтения списка Routes, аналогичен Result, только все ограничения по Routes.

4. Переменная Addresser – узел связи отправителя, Addresser ∈ [1..N].

5. Переменная Destination – узел связи получателя, Destination ∈ [1..N].

Алгоритм поиска всех беспетельных маршрутов от отправителя до получателя:

1. Составляем матрицу смежности А[i,j], согласно ориентированного графа, который описывает введенную топологию сети. Данное заполнение матрицы назовем – исходным состоянием матрицы А[i,j].

2. Добавим в список Routes маршрут, состоящий из узла Addresser. На данном этапе Routes содержит только одну запись.

3. Из списка Routes берем первый маршрут – Routes[1]. В матрице А[i,j], если столбец j = Routes[1,m], где, m∈[1..M-1], то элементы строки j приравниваются нулю.

4. Если А[Routes[1,M], j] = 1, при условии что Routes[1,M] ≠ j, где j ∈ [1..N], а M – последний элемент массива 1 записи, производятся новая запись Routes[1] c добавлением элемента j:

- в Routes[K+1], если j ≠ Destination , тогда запись Routes[1] удаляется;

- в Result[T+1], если j = Destination , Routes[1] удаляется;

если на А[Routes[1,M], j] отсутствуют 1, тогда производится удаление Routes[1] – это считается тупиковым маршрутом.

5. Если в списке Routes есть записи, тогда матрицу А возвращаем в исходное состояние и переходим к шагу 3, иначе конец цикла.

Пример. Пусть имеется произвольное количество узлов связи, которые образуют некоторую топологию сети, согласно Рис. 1. Необходимо рассчитать все беспетельные маршруты от 2-ого узла связи (далее – Addresser) до 5-ого узла связи (далее – Destination ).

1

Рис. 1 Топология сети.

Составляем матрицу смежности А размерности 6 на 6, результат представлен на Рис. 2, где i ∈ [1..6], j ∈ [1..6].

2

Рис. 2 Матрица смежности А[i,j].

Добавим в список Routes первую запись, состоящую из Addresser, результат на Рис. 3.

3

Рис. 3 Список Routes[t].

Согласно алгоритму, необходимо в матрице А[i,j] приравнять нулю все столбцы j, которые равны элементам 1-ой записи списка Routes[t], кроме последнего элемента 1-ой записи списка Routes[t]. На первом шаге всего одна запись, а это значит, что матрица А[i,j] останется в исходном состоянии (Рис. 2).

В матрице А[i,j] на строке 2 находим единицы (Рис. 4). На 2-ой строке видим единицы на пересечении столбца 1, 3 и 4, то есть А[Routes[1,1],1] = А[Routes[1,1],3] = А[Routes[1,1],4] = 1. Тогда в список Routes[t] вводим 3 новые записи и удаляем запись Routes[1], результат на Рис. 5.

4

Рис. 4 Найденные единицы в матрице А[i,j] на 2-ой строке.

5

Рис. 5 Новые добавленные записи списка Routes[t].

Так как список Routes[t] не пуст, тогда согласно алгоритму переходим к шагу 3. Матрица А[i,j] приводится в исходное состояние.

Выбираем запись Routes[1] (из Рис. 5 это – 2-1). В матрице A[i,j] приравниваем нулю столбцы Routes[1,m], m ∈ [1..M-1] , где М – количество элементов 1-ой записи, в нашем случае A[i, 2] = 0, где i ∈ [1..6], результат на Рис. 6.

6

Рис. 6 Матрица A[i,j] с приравненными элементами столбца 2 к нулю.

В матрице А[i,j] (согласно Рис. 6) на строке 1 находим единицы. На 1-ой строке видим единицу на пересечении столбца 4 (А[Routes[1,1],4] = 1). Тогда в список Routes[t] вводим новую запись, удаляем запись Routes[1] и приводим матрицу А[i,j] в исходное состояние. Так как запись Routes[1] будет удалена, то первой записью будет являть маршрут 2-3, аналогично решению маршрута 2-1, проведем для маршрутов 2-3 и 2-4 списка Routes[t], результат решения на Рис. 7, без учета конечных маршрутов, где при решении маршрутов 2-3 и 2-4 получились маршруты, с узлами связи = Destination, таким образом эти маршруты заносятся в список Result[k], Результат на Рис. 8.

7

Рис. 7 Сформированный список Routes[t], согласно решению маршрутов 2-1, 2-3, 2-4.

8

Рис. 8 Сформированный список Result[k], согласно решению маршрутов 2-3 и 2-4.

Далее решение будет аналогично выше представленному примеру, однако наибольший интерес представляет решение маршрута 2-3-6, так как данный маршрут является тупиковым (также как и маршрут 2-4-1).

Рассмотрим решение маршрута 2-3-6, с условием, что решение маршрутов 2-1-4 и 2-3-4 выполнено, таким образом Routes[1] = 2-3-6.

Выбираем запись Routes[1]. В матрице A[i,j] приравниваем нулю столбцы Routes[1,m], m ∈ [1..M-1] , где H – количество элементов 1-ой записи, в нашем случае A[i, 2] = A[i, 3] = 0, где i ∈ [1..6], результат на Рис. 9.

В матрице А[i,j] (согласно Рис. 9) на строке 6 наблюдаем отсутствие единиц, значит согласно 3 пункту алгоритма удаляем запись Routes[1] и приводим матрицу А[i,j] в исходное состояние. Таким образом, на данном шаге список Result[k] изменится в связи с допущением решения маршрутов 2-1-4 и 2-3-4, результат представлен на Рис. 10, результат списка Routes[t] представлен на Рис. 11.

9

Рис. 9 Матрица A[i,j] с приравненными элементами столбцов 2 и 3 к нулю.

10

Рис. 10 Сформированный список Result[k], согласно решению маршрутов 2-1-4, 2-3-4 и 2-3-6.

11

Рис. 11 Сформированный список Routes[t], согласно решению маршрутов 2-1-4, 2-3-4 и 2-3-6.

Алгоритм прекращает работу когда список Routes[t] будет пустым. Выше представленное решение рассмотрело все случаи формирования:

- новых маршрутов;

- конечных маршрутов;

- тупиковых маршрутов,

по аналогии решения различных маршрутов, представим результат выполнения алгоритма, Рис. 12.

12

Рис. 12 Результат решения беспетельных маршрутов от узла связи 2 в 5 согласно данной топологии, представленный в списке Result[k].

На основе данного алгоритма был написан программный код на языке C# консольным приложением на целевой рабочей среде .NET Framework 4.7.2. Выполнение кода было выполнено на процессоре Intel(R) Core(TM) i5-7300HQ @ 2.50GHz, на операционной системе Windows10 Prox64, Код расчета алгоритма, а также результаты работы программного кода представлены в Приложении 1.

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

Ниже приведем результаты моделирования для полно связных топологий

Таблица 1. Анализ числа переменных полносвязных топологий

Число узлов

2

3

4

5

6

7

8

9

10

11

12

Число беспетельных маршрутов

1

2

5

16

65

326

1957

13700

109601

986410

9864101

Число фазовых переменных

1

4

9

16

25

36

49

64

81

100

121

Талица 2. Число переменных графов со степенью полуисхода каждого узла равного двум

Число узлов

4

5

6

7

8

9

10

11

12

13

14

Число беспетельных маршрутов (max)

2

2

2

2

2

2

2

2

2

2

2

Число фазовых переменных

5

5

7

8

9

10

11

12

13

14

15

Талица 3. Число переменных графов со степенью полуисхода каждого узла равного трем

Число узлов

6

8

10

12

14

16

18

Число беспетельных маршрутов (max)

9

17

21

25

29

33

37

Число фазовых переменных

13

18

33

64

126

209

441

Талица 4. Число переменных графов со степенью полуисхода каждого узла равного четырем

Число узлов

6

7

8

9

10

11

12

13

14

15

16

Число беспетельных маршрутов (max)

28

48

82

144

240

428

762

1264

2158

3888

6208

Число фазовых переменных

19

22

25

28

31

34

37

40

43

46

49

Талица 5. Число переменных графов со степенью полуисхода каждого узла равного пяти

Число узлов

8

10

12

14

16

18

Число беспетельных маршрутов (max)

274

1214

5442

22925

101667

462033

Число фазовых переменных

33

41

49

57

65

73

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

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

Поскольку работа с готовыми маршрутами удобнее чем с фазовыми переменными такими как система линейно независимыми циклами или разрезами, то необходимо также разработать алгоритм поиска линейно независимых беспетельных маршрутов, что в конечном счете должно еще более сократить число переменных, которым будет описываться математическая модель распределения трафика в телекоммуникационной сети. Возможность поиска линейно-независимых маршрутов обусловлена тем, что маршрут это тот же самый контур при условии, что в сети должна обеспечиваться циркуляция потока между парой отправитель-получатель. Таким образом данный алгоритм может быть использован как алгоритм поиска всех контуров, по которым может быть разложены маршруты распределения трафика, если предположить, что имеется ребро, соединяющее получателя и отправителя. Полученная же матрица маршрутов Result[k] фактически и является матрицей всех контуров.

В приложении к данной статье представлены блок схема разработанного алгоритма, программный код на языке C#, а также представлен пример работы данной программы.

Приложение 1

Приведенный программный код на языке C# описывает работу алгоритма согласно алгоритму и блок-схеме (Приложение 2 Рис. 13). Описание переменных осуществлена в комментариях кода. Программный код ввода и вывода информации не представлен, так как реализация ввода и вывода данных осуществляется на собственное усмотрение разработчика.

int addresser, Destination ; // отправитель и получатель соответственно

List result = new List(); // итоговые маршруты

List routes = new List(); // промежуточные маршруты

int[,] matrixA = new int[number, number]; // исходное состояние матрицы смежности А

routes.Add(new List());

routes[0].Add(addresser);

while (routes.Count != 0)

{

int[,] matrixA = new int[number, number]; // Копия матрицы А, в которой происходят изменения, в соответствии с записью routes[0]

Array.Copy(connectivityMatrix, matrixA, number * number);

for (int j = 1; j < routes[0].Count - 1; j++)

{

for (int k = 0; k < number; k++)

{

matrixA[k, routes[0][j]] = 0;

}

}

int a = routes[0][routes[0].Count - 1];

for (int j = 0; j < number; j++)

{

if ((a != j) && (matrixA[a, j] == 1))

{

if (j == Destination )

{

result.Add(new List());

result[result.Count - 1].AddRange(routes[0]);

result[result.Count - 1].Add(j);

}

else

{

routes.Add(new List());

routes[routes.Count - 1].AddRange(routes[0]);

routes[routes.Count - 1].Add(j);

}

}

}

routes.RemoveAt(0);

}

13

Рис. 13 Блок-схема алгоритма поиска беспетельных маршрутов.

Результаты работы программного кода, представлен в тандеме изображений, где первое изображение – схема исследуемой топологии, второе – скриншот результата программного кода в консольном приложении, отображающий отправителя (Addresser), получателя (Description), матрицы смежности (A[i, j]), время расчета, содержание списка Result.

Для более удобного представления в исследуемых топологиях 1, 2, 3, 4 представленных на Рис. 14, 15, 16, 17 двунаправленные связи изображены одинарной линией.

14

Рис. 14 Исследуемая топология 1.

15

Рис. 15 Исследуемая топология 2.

16

Рис. 16 Исследуемая топология 3.

17

Рис. 17 Исследуемая топология 4.

References
1. Gaipov K.E. Invariantnye metody analiza trafika v raspredelennykh sistemakh obrabotki informatsii: dissertatsiya kandidata tekhnicheskikh nauk. [Mesto zashchity: Sib. aerokosm. akad. im. akad. M.F. Reshetneva].-Krasnoyarsk, 2013.-160 s.: il.
2. Kremer N. Sh., 2.3. «Metod Gaussa».
3. Bertsekas D., Gallager R. Seti peredachi dannykh. : Mir 1989 — 544 s., il.
4. Vishnevskii V. M. Teoreticheskie osnovy proektirovaniya komp'yuternykh setei, M.: izd. Tekhnosfera, 2003, 512 s.
5. Levitin A. V. Glava 11. Preodolenie ogranichenii: Metod deleniya popolam // Algoritmy. Vvedenie v razrabotku i analiz — M.: Vil'yams, 2006. — S. 349—353. — 576 s. — ISBN 978-5-8459-0987-9.
6. Belousov A. I., Tkachev S. B. Diskretnaya matematika. — M.: MGTU, 2006. — 744 s. — ISBN 5-7038-2886-4.
7. Kormen, T., Leizerson, Ch., Rivest, R., Shtain, K. Algoritmy: postroenie i analiz / Pod red. I. V. Krasikova. — 2-e izd. — M.: Vil'yams, 2005. — 1296 s. — ISBN 5-8459-0857-4.
8. Gutkovkaya O.L., Ponomarev D.Yu. — Primenenie ortogonal'noi modeli telekommunikatsionnoi seti dlya resheniya zadachi optimal'nogo raspredeleniya trafika // Kibernetika i programmirovanie. – 2017. – № 1. – S. 11 - 29. DOI: 10.7256/2306-4196.2017.1.21810
9. Shuvalov V. P., Varaksina I. Yu. Klassifikatsiya metodov mnogoputevoi marshrutizatsii // T-Comm. 2014. №1 S.29-32.
10. Evseeva O.Yu., Garkusha S.V. Obzor tekhnologicheskikh i teoreticheskikh reshenii v oblasti marshrutizatsii na osnove kachestva obsluzhivaniya // Problemi telekomunіkatsіi. – 2012. – № 3 (8). – S. 24–46 [Elektronnyi resurs]. – Rezhim dostupa: http://pt.journal.kh.ua/2012/3/1/123_evseeva_review.pdf, svobodnyi. Yaz. rus. (data obrashcheniya 08.02.2017)