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

Размещено на http://www.allbest.ru/

3

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

Демичев Максим Сергеевич

студент, Сибирский государственный университет науки и технологии им. М.Ф. Решетнева

Гаипов Константин Эдуардович

кандидат технических наук

доцент, Сибирский государственный университет науки и технологий им. академика М.Ф. Решетнёва

Королев Евгений Михайлович

старший преподаватель, Сибирский государственный университет науки и технологий имени академика М.Ф. Решетнева



Аннотация

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

Ключевые слова: остовное дерево, маршрут, матрица, алгоритм, цикл, маршрутизация, коммутация, топология сети, протокол, трафик

The subject of the study is to obtain spanning trees for propagating traffic over broadcast channels using the known network topology and known routes. To solve this problem, a mathematical model is constructed in which the network topology is regarded as an undirected graph, but the described solution is also suitable for an oriented graph, where a separate direction is represented by a separate edge. The proposed solution does not require flexible scalability of the network, therefore, when changing the initial input parameters, it is necessary to repeatedly execute the sequence of algorithms described in the article. The development of the algorithm was carried out by an experimental-theoretical method using the mathematical model of a graph constructed from the known topology of the network and the compilation of spanning trees on its basis. The result of the presented work is in determining the necessary number of spanning trees for the optimal solution of the network routing problem. The novelty of this research is the possibility of applying the developed solution in the link-layer networks according to the OSI reference model, exclusively for broadcasting traffic of a given network topology.

Keywords:

network topology, switching, routing, cycle, algorithm, matrix, route, spanning tree, protocol, traffic

трафик топология сети неориентированный граф



Введение

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



Библиография

1.Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика. Графы, матроиды, алгоритмы (2001) с 288

2.Бертсекас, Димитри. Сети передачи данных / Д. Бертсекас, Р. Галлагер; Перевод с англ. Н. Б. Лиханова и др.; Под ред. Б. С. Цыбакова.-М. : Мир, 1989.-544 с. : ил.

3.Гольдштейн А.Б., Гольдштейн Б.С.Технология и протоколы MPLS,. СПб.: БХВ -- Санкт-Петербург, 2005. -- 304 с.: ил. ISBN 5-8206-0126-2

4.Кларк К., Гамильтон К. Принципы коммутации в локальных сетях Cisco.-М.: Издательский дом "Вильямс", 2003.-976 с. -- ISBN 5-8459-0464-1.

5.Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. -- 2-е изд. -- М.: Вильямс, 2005. -- 1296 с. -- ISBN 5-8459-0857-4.

6.Олвейн В. Структура и реализация современной технологии MPLS.-М.: Издательский дом "Вильямс", 2004.-480 с. -- ISBN 5-8459-0633-4

7.Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. - СПб.: Питер, 2000.

8.Смирнова Е.В., Пролетарский А.В., Баскаков И.В., Федотов Р.А. Управление коммутируемой средой. - М.: РУСАКИ, 2011. - 335 с.

9.Смирнова Е. В., Пролетарский А. В.. Технологии коммутации и маршрутизации в локальных компьютерных сетях : учеб. пособие - М.: Изд-во МГТУ им. Н.Э. Баумана, 2013. - 389, с. : ил. - (Компьютерные системы и сети).

10.Уилсон Р. -- Введение в теорию графов, 1977 год, 208 с. Издатель: Мир, Город печати: Москва

Размещено на Allbest.ru