Search algorithm for loopless routes

Введение. Решение задачи управления трафиком является одной из ключевых задач телекоммуникационной индустрии, классификация таких задач приведена в ^[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 Топология сети.

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

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

Добавим в список Routes первую запись, состоящую из Addresser, результат на Рис. 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 Найденные единицы в матрице А[i,j] на 2-ой строке.

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

Рис. 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 Матрица A[i,j] с приравненными элементами столбцов 2 и 3 к нулю.

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

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

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

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

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

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

по аналогии решения различных маршрутов, представим результат выполнения алгоритма, Рис. 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. Число переменных графов со степенью полуисхода каждого узла равного пяти

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

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

Поскольку работа с готовыми маршрутами удобнее чем с фазовыми переменными такими как система линейно независимыми циклами или разрезами, то необходимо также разработать алгоритм поиска линейно независимых беспетельных маршрутов, что в конечном счете должно еще более сократить число переменных, которым будет описываться математическая модель распределения трафика в телекоммуникационной сети. Возможность поиска линейно-независимых маршрутов обусловлена тем, что маршрут это тот же самый контур при условии, что в сети должна обеспечиваться циркуляция потока между парой отправитель-получатель. Таким образом данный алгоритм может быть использован как алгоритм поиска всех контуров, по которым может быть разложены маршруты распределения трафика, если предположить, что имеется ребро, соединяющее получателя и отправителя. Полученная же матрица маршрутов 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 Блок-схема алгоритма поиска беспетельных маршрутов.

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

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

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

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

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

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