Формирование необходимого числа остовных деревьев

Демичев Максим Сергеевич Инженер-конструктор по защите информации, Акционерное общество «Научно-производственное предприятие «Радиосвязь» 660000, Россия, Красноярский край, г. Красноярск, ул. Красноярский Рабочий, 31 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 Другие публикации этого автора     Гаипов Константин Эдуардович кандидат технических наук доцент, Сибирский государственный университет науки и технологий им. академика М.Ф. Решетнёва 660000, Россия, Красноярский край, г. Красноярск, ул. Красноярский Рабочий, 31 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 Другие публикации этого автора     Королев Евгений Михайлович старший преподаватель, Сибирский государственный университет науки и технологий имени академика М.Ф. Решетнева 660037, Россия, Красноярский край, г. Красноярск, пр. Красноярский Рабочий, 31 Korolev Evgenii Mikhailovich Senior Lecturer, Department of Military Training Center, Reshetnev Siberian State University of Science and Technology 660037, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Pr. Krasnoyarskii Rabochii, 31 boxkem@mail.ru Другие публикации этого автора     Демичева Алёна Алексеевна студент, Сибирский государственный университет науки и технологий им. академика М.Ф. Решетнёва 660031, Россия, Красноярский край, г. Красноярск, ул. Красноярский Рабочий, 31 Demicheva Alena Alekseevna Student, the department of Security of Information Technologies, Reshetnev Siberian State University of Science and Technology 660031, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Krasnoyarskii Rabochii, 31 DemichevaAlena@yandex.ru Другие публикации этого автора

Нарожный Артём Игоревич студент, Сибирский государственный университет науки и технологий им. академика М.Ф. Решетнёва 660000, Россия, Красноярский край, г. Красноярск, ул. Красноярский Рабочий, 31 Narozhnyi Artem Igorevich Student, Department of Information Technology Security, Reshetnev Siberian State University of Science and Technology 660000, Russia, Krasnoyarskii krai, g. Krasnoyarsk, ul. Krasnoyarskii Rabochii, 31 artem_narozhnyi@mail.ru Другие публикации этого автора

Введение

В процессе эксплуатирования телекоммуникационной сети, как правило, возникаю вопросы, связанные с выбором оптимальных маршрутов по тому или иному критерию, задача глобальной оптимизации, решенная в ^{[2, стр. 454 – 466]}, позволяет определить оптимальные маршруты по критерию минимальной суммарной задержки в каждом канале связи. Результатом такой оптимизации является набор маршрутов между каждой парой источник-приемник. Существующие технологии маршрутизации и коммутации накладывают ряд ограничений на возможные маршруты, которые, как правило, связаны с работой протоколов маршрутизации или на канальном уровне с протоколами группы STP (spanning tree protocol – протокол покрывающего дерева) ^[4]. Если же на сетевом уровне можно обойти ограничения связанные с тем, что маршруты от источника до приемников должны проходить только по дереву наикратчайшей стоимости, с помощью статической маршрутизации или применяя механизмы MPLS-TE (multiprotocol label switching traffic engineering – управление трафиком многопротокольной коммутацией по меткам) ^[6], то на канальном уровне единственной стандартной схемой управления трафиком является совместное использование техники виртуальных локальных сетей и протокола STP. Таким образом, можно сделать вывод, что для достижения оптимального распределения трафика необходимо не только знать сами маршруты, но и определить конфигурационные параметры протоколов, отвечающих за маршрутизации. В данной статье приводится описания алгоритма выбора необходимого числа деревьев минимальной стоимости, распространяясь по которым трафик будет проходить по оптимальным маршрутам.

Постановка задачи

Пусть имеется маршруты прохождения трафика заданы матрицей R размерностью w на t, где w - количество маршрутов, t – количество ребер графа, которым описывается сеть, если элемент r_wt=1 то ребро входит в маршрут если 0 то не входит. Необходимо определить требуемое количество деревьев Т, так что бы маршруты получаемые с помощью данного множества деревьев обеспечивали прохождение трафика по маршрутам, определенных в матрице R.

Ход работы

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

Для решения поставленной задачи необходимо решить следующие этапы алгоритма:

1. Алгоритм построения матрицы маршрутов и циклов М;

2. Алгоритм нахождения и определения необходимого количества маршрутов (деревьев);

3. Алгоритм доведения полученных маршрутов до остовного дерева.

Построение матрицы маршрутов и циклов (матрица М)

Для заполнения матрицы М необходимо выполнить поиск в глубину ^{[5, стр. 622 – 626]}, в результате чего получим простые циклы в виде набора ребер. Маршруты, заданные при постановке задач представим в виде набора ребер.

Матрица М имеет размерность q на t, где q – равно сумме количества простых циклов (v) и количества маршрутов (w), t – равно количеству ребер в графе. Также выделяем в матрице М область циклов и область маршрутов. Дополним область циклов сложными циклами:

1. Рассматриваем простые циклы по типу «каждый с каждым». Если хотя бы в одном одноименном столбце цикла b и цикла d располагается 1, то создается новый сложный цикл, элементы которого являются результатом операции «исключающее или» элементов циклов.

2. Рассматриваем сложный цикл с каждым простым циклом (кроме простых циклов, входящих в сумму рассматриваемого сложного цикла). Если хотя бы в одном одноименном столбце сложного цикла и рассматриваемого простого цикла располагается 1, то создается новый сложный цикл, элементы которого являются результатом операции «исключающее или» элементов сложного и простого циклов.

3. Пункт 2 выполняется для каждого сложного цикла, до тех пор, пока существует возможность создания сложного цикла.

4. Выполняем проверку области циклов на совпадение, если элементы циклов совпадают, остается один произвольный цикл, остальные удаляются.

Шаблон матрицы М представлен на рисунке 1.

Заполнение матрицы М осуществляется нулями и единицами, для всех строк области маршрутов и области циклов. Для строки i заполнение происходит следующим образом: если маршрут i содержит ребро j, то значение ячейки mij равно единице, иначе – нулю.

Рисунок 1. Шаблон матрицы М. изменить обозначения

Алгоритм нахождения и определения необходимого количества маршрутов (деревьев).

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

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

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

2. Для маршрута m определяем маски по циклам, где маска равна произведение инверсии элементов маршрута m с циклом. Количество масок равно количеству циклов. В случае наличия одинаковых масок остается одна маска, остальные исключаются.

3. Для каждого маршрута (кроме маршрута m) из матрицы М производится поэлементное умножение на маску, если результат равен маске, то маршрут исключается из дальнейшего рассмотрения, при этом поэлементное умножение для данного (исключенного) маршрута с оставшимися масками выполнять не требуется. Аналогично выполняем данный пункт для оставшихся маршрутов с последующими масками.

4. Не исключенный маршрут с максимальной построчной суммой назовем маршрутом n. В случае наличия нескольких маршрутов n с максимальной построчной суммой, необходимо рассматривать их параллельно. Если в матрице М отсутствуют не исключенные маршруты, тогда переходим в пункт 6, иначе пункт 5.

5. Выполняем поэлементную операцию дизъюнкции между маршрутом m и маршрутом n, а также маршрут m становится равным сумме маршрутов m и n, а маршрут n удаляется из матрицы М, если сумма m и n равна m, тогда маршрут n становится исключенным и переходим в пункт 4, где выбираем новый маршрут n по числу единиц. Переходим в пункт 2, если в матрице М есть не исключенные маршруты, иначе переходим в пункт 6.

6. В список Н записывается маршрут m. При записи маршрута m в список Н, маршрут m удаляется из матрицы М.

7. Удаляем из матрицы М маршрут k, если при поэлементной конъюнкции инверсии маршрута, записанного в список Н, и маршрута k, все полученные элементы равны нулю. Данный пункт выполняется для каждого маршрута матрицы М.

8. Если в матрице М в области маршрутов:

8.1. Не осталось маршрутов, то алгоритм заканчивает свою работу.

8.2. Остался один маршрут, то он вносится в список маршрутов Н, и алгоритм заканчивает свою работу.

8.3. Осталось два и более маршрутов, то переходим в пункт 1.

В случае наличия маршрутов со всеми одинаковыми ребрами, в списке Н остается только один маршрут.

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

Введем матрицу Т, которая имеет размерность х строк на у столбцов, где х – количество ребер, у – количество циклов + 1. Матрица Т заполняется следующим образом: в позиции tх1 записывается вес ребра х (далее – столбец «Вес»). В позиции t_ху (у≠1) записывается 1, если ребро х включено в цикл под номером у. Будем называть область столбцов от 2-го до у-го – областью циклов.

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

Алгоритм доведения полученных маршрутов до остовного дерева (для описания алгоритма считаем, что наилучшим весом является минимальное значение):

1. Выберем произвольно маршрут (далее – маршрут С), удовлетворяющий условию rb < v – 1, где rb – количество ребер, v – количество вершин в списке Н.

2. Временно исключаем из матрицы Т строку, если соответствующее данной строке ребро присутствует в маршруте С.

3. Если в области циклов существует столбец (исключенные строки из пункта 2 не учитываются), имеющий только одну 1 (ячейка t_ij), то строка i временно исключается. Данный пункт повторяется до тех пор, пока существуют столбцы, имеющие только 1 единицу.

4. Находим минимальное значение в столбце «Вес» (ячейка t_i1). Дописываем ребро i в маршрут С из списка Н. Выполняем алгоритм с пункта 2 с учетом изменения выбранного маршрута С, до тех пор пока все строки не будут исключены, тогда переходим на пункт 5.

5. Выберем следующий маршрут из списка Н (далее – маршрут С), переходим в пункт 2. Выполняем до тех пор, пока алгоритм не применится для всех маршрутов списка Н.

В случае наличия маршрутов со всеми одинаковыми ребрами, в списке Н остается только один маршрут.

Пример

Дана топология сети, представленная на рисунке 2, с пронумерованными вершинами и переименованными ребрами, а также десять маршрутов, представленные в виде набора ребер на рисунке 3.

Рисунок 2. Топология сети

Рисунок 3. Маршруты топологии сети, представленные в виде набора ребер

Для данной топологии найдем простые циклы, алгоритмом поиска в глубину ^{[1, стр. 622 – 626]}. Результат представлен в виде набора ребер на рисунке 4.

Рисунок 4. Простые циклы, в виде набора ребер

Составим матрицу М, стоит отметить, что область циклов дополнилась образованием простых циклов 1+2, 2+3 и 1+2+3, результат представлен на рисунке 5.

Рисунок 5. Матрица М

На данном шаге матрица М пустая. Выделим строку в области маршрутов с максимальным количеством единиц – 10 маршрут.

Определим маски по циклам как произведение инверсии элементов маршрута 10 с каждым циклом, в результате получим 6 масок, рисунок 6.

Рисунок 6. Маски, полученные из 10 маршрута

Выполним поэлементное умножение 1 маски с каждым маршрутом за исключением 10 маршрута. Результат представлен на рисунке 7.

Рисунок 7. Результат умножения 1 маски на маршруты матрицы М

Из рисунка 7, наблюдаем, что произведение 1 маски с 1, 4, 7 и 9 маршрутом в результате равно 1 маски, значит, на данной итерации не будем их учитывать. Умножение 2 маски на маршруты из матрицы М, кроме маршрутов 1, 4, 7, 9 и 10, результат представлен на рисунке 8.

Рисунок 8. Результат умножения 2 маски на маршруты матрицы М, с учетом исключенных маршрутов

Из рисунка 8, видим, что нет результатов равных 2 маске, значит, переходим на умножение 3 маски с маршрутами из матрицы М, кроме маршрутов 1, 4, 7, 9 и 10, результат представлен на рисунке 9.

Рисунок 9. Результат умножения 3 маски на маршруты матрицы М, с учетом исключенных маршрутов

Из рисунка 9, наблюдаем, что произведение 3 маски с 2, 5 и 8 маршрутом в результате равно 3 маски, значит, не будем их учитывать. На данной итерации рассматриваем маршруты 3 и 6. Переходим на умножение 1+2 маски с маршрутами из матрицы М, кроме маршрутов 1, 2, 4, 5, 7, 8, 9, 10, результат представлен на рисунке 10.

Рисунок 10. Результат умножения 1+2 маски на маршруты матрицы М, с учетом исключенных маршрутов

Из рисунка 10, наблюдаем, что произведение 1+2 маски с 6 маршрутом в результате равно 1+2 маски, значит, не будем его учитывать. На данной итерации рассматриваем маршруты 3.

Умножение 2+3 маски с маршрутами и 1+2+3 маски с маршрутами из матрицы М, дают одинаковый результат, представленный на рисунке 11.

Рисунок 11. Результат умножения 1+2 маски на маршруты и маски 1+2+3 на маршруты матрицы М, с учетом исключенных маршрутов

Из рисунка 5 видим, что наибольшее количество единиц содержит 3 маршрут. Выполним поэлементную дизъюнкцию между маршрутом 10 и 3, однако результат равен маршруту 10, значит, маршрут 3 исключаем.

На данный момент не исключенные маршруты отсутствуют, тогда результат запишем в список Н, равный маршруту 10, результат представлен на рисунке 13. Маршрут 10 удалим из матрицы М, которая представлена на рисунке 14 с учетом итерации.

Рисунок 12. Матрица М после первой итерации, с исключенным 10 маршрутом.

Рисунок 13. Список Н, после первой итерации.

Аналогичным образом, согласно алгоритму выполним последующие итерации, результат представлен на рисунке 14.

Рисунок 14. Список Н, после всех итераций.

Из рисунка 14 заметим, что полученное дерево, образованное от маршрута 7 имеет полное совпадение ребер с деревом 1+8, значит, дерево 7 удаляем из списка Н, а также удаляем дерево, образованное от маршрута 3, которое имеет полное совпадение ребер с деревом 10, результат представлен на рисунке 15.

Рисунок 15. Список Н, с учетом сортировки.

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

Рисунок 16. Матрица Т.

Расширим дерево, образуемое от маршрута 2, согласно рисунку 15, до остовного.

Временно исключим из матрицы Т строки a, b, e и g, соответствующие дереву, образованному от маршрута 2, согласно рисунку 15, результат представлен на рисунке 17.

Рисунок 17. Матрица Т с исключенными ребрами a, b, e и g

Так как столбец 1 имеет одну единицу, на пересечении с c строкой (ребром), тогда исключим из матрицы Т строку c результат представлен на рисунке 18.

Рисунок 18. Матрица Т с исключенными ребрами a, b, c, e, и g.

На рисунке 18 находим минимальное значение по столбцу Вес – строка d, таким образом, в список Н, в дерево, образованное от маршрута 2, дописываем ребро d, результат представлен на рисунке 19.

Рисунок 19. Список Н, с учетом внесенных изменений.

Выполним алгоритм для остальных деревьев, в результате получим итоговые остовные деревья, представление на рисунке 20.

Рисунок 20. Список Н, с итоговыми остовными деревьями.

Вывод

Результаты полученные в ходе применения алгоритма к топологии на рисунке 2 говорят о следующем, чтобы обеспечить передачу данных по маршрутам представленным на рисунке 3 необходимо организовать 6 деревьев. Если речь идет о коммутируемой среде Ethernet, то это означает, что должно быть организовано минимум 6 виртуальных локальных сетей в каждой из которой необходимо чтобы протокол STP сформировал дерево согласно рисунку 20, для чего ветвям, которые не должны входить в дерево STP конкретной VLAN (Virtual Local Area Network – виртуальная локальная сеть) ^[4], необходимо назначить достаточно большие веса, а ветвям, которые должны в ходить в дерево, минимально возможные. В качестве веса ребра, которое необходимо исключить из дерева STP, можно использовать любой вес больше чем минимально возможный умноженный на число ветвей, которое вошло в дерево STP.

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

Таким образом, применимость предложенного алгоритма можно отнести к сетям уровня 2 модели OSI (open systems interconnection – базовая эталонная модель взаимодействия открытых систем), в которых трафик должен распространяться только по широковещательным доменам древовидной структуры.

Отметим некоторые ограничения данного алгоритма, в статье не доказывается, что данное число деревьев будет минимально, но сделано все возможное, чтобы число этих деревьев было как можно меньше. Как видно основная сложность алгоритма заключается в подготовке матрицы М, которая содержит все простые циклы графа, размерность такой матрицы может оказаться достаточно большой, в случае если граф будет стремиться к полному графу, но поскольку телекоммуникационные сети представляют собой в основном разреженные графы с числом степени вершины, как правило, не более 3 или 4, так что можно считать, что предложенный алгоритм будет составлять матрицу М за приемлемое время.