В локальных сетях где реализована функция только первого и второго уровня модели ISO/OSI, проблема реализации альтернативных путей имеет свой характер. Стандартные протоколы могут использовать только древовидные топологии, то есть не содержащие замкнутых контуров.
Алгоритм STA описывает сеть в виде графа, вершинами которого есть сегменты сети и коммутаторы. Это показано на рис.1. Сегмент — часть сети которая не содержит коммутаторов. Сегмент может включать концентраторы/повторители. Алгоритм реализует построение древовидной топологии каналов с единым путем минимальной длины от каждого сегмента и от каждого коммутатора до корневого коммутатора — корня дерева. Единый путь гарантирует отсутствие петель. Метрика — величина расстояния обратно пропорциональная пропускной способности сегмента. Идентификатор коммутатора — эьл 8-байтовое число, где MAC-адрес составляет шесть младших байтов,а два старших остается для администратора который вручную ставит корневой коммутатор для алгоритма. Корневой порт — порт, который использует самый минимальный путь к корневому коммутатору.BPDU — специальные пакеты, которыми обмениваются коммутаторы для определения минимальной метрики.
Рисунок 1
На рис.2 показан пример сети, на котором будет проведет алгоритм покрывающего дерева. Алгоритм STA анализирует активную конфигурацию сети в 3 этапа.
Рисунок 2
Первый этап — определяем корневой коммутатор, где начнется дерево. Обычно если администратор не участвует в процессе, выбирается устройство с минимальным MAC-адресом блока управления. Лучше чтобы администратор принимал участие в процессе, и назначал корневой коммутатор исходя из логики и адекватности выбора. На рисунку корневым коммутатором есть №1.
Второй этап — Выбираем корневой порт для каждого коммутатора. Метрика определяется по пакетам BPDU. На рисунку видно, что коммутатор №2 принимает из сегмента 1 пакет BPDU с метрикой — 0, и увеличивает его на 10 у.е.. Ретранслируя эти пакеты, каждый коммутатор запоминает минимальное число к корню. При равных метриках проверяется идентификаторы портов и коммутаторов. На рисунку видно, что коммутатор №3 выбирает порт №1 в качестве корневого, так как метрика к корню — 10.
Третий этап — выбор назначенных коммутатора и порта. Для каждого сегмента сети выбирается назначенный порт и соответственный порт коммутатора сегмента. остальные порты кроме назначенных и корневых блокируются (на рис. они перечеркнуты). Математически доведено, что при таком алгоритме в сети исключаются петли, и образуется покрывающее дерево. После коммутатор строит таблицу продвижения.
В процессе обычной работы корневой коммутатор генерирует пакеты BPDU с определенным интервалом, а назначенные порты ретранслируют эти пакеты.
Один из основных плюсов данного алгоритма, это то решение о реконфигруции происходит не только с учетом момедних связей, но и связей в отдаленных сегментах сети. К недостаткам можно отнести, что если в сети используется много коммутаторов, то время определения новой активности может быть слишком большим.
Минимальное остовное дерево (или минимальное покрывающее дерево ) в связанном, взвешенном, неориентированном графе - это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер
Пример
Пример минимального остовного дерева в графе. Числа на ребрах обозначают вес ребер.
Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: допустим, есть n городов, которые необходимо соединить дорогами, так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Разрешается строить дороги между заданными парами городов и известна стоимость строительства каждой такой дороги. Требуется решить, какие именно дороги нужно строить, чтобы минимизировать общую стоимость строительства.
Эта задача может быть сформулирована в терминах теории графов как задача о нахождении минимального остовного дерева в графе, вершины которого представляют города, рёбра - это пары городов, между которыми можно проложить прямую дорогу, а вес ребра равен стоимости строительства соответствующей дороги.
Функции канального уровня
Функции протоколов канального уровня различаются в зависимости от того, предназначен ли данный протокол для передачи информации в локальных или в глобальных сетях. Протоколы канального уровня, используемых в локальных сетях, ориентируются на использование разделяемых между компьютерами сети сред передачи данных. Поэтому в этих протоколах имеется подуровень доступа к разделяемой среде. Хотя канальный уровень локальной сети и обеспечивает доставку кадра между любыми двумя узлами локальной сети, он это делает только в сети с совершенно определенной топологией связей, именно той топологией, для которой он был разработан. К таким типовым топологиям, поддерживаемым протоколами канального уровня локальных сетей, относятся общая шина, кольцо и звезда.
Использование разделяемой среды передачи данных делает в локальных сетях ненужными процедуры управления потоком кадров. Локальная сеть базовой топологии не может переполниться кадрами, так как узлы сети не могут начать генерацию нового кадра до приема предыдущего кадра станцией назначения.
Еще одной особенностью протоколов канального уровня локальных сетей является широкое использование дейтаграмнных процедур. Это объясняется хорошим качеством каналов связи, редко искажающим биты в передаваемых кадрах.
Примерами протоколов канального уровня для локальных сетей являются протоколы Token Ring, Ethernet, Fast Ethernet, 100VG-AnyLAN, FDDI.
В глобальных сетях, которые редко обладают регулярной топологией, канальный уровень обеспечивает обмен сообщениями между двумя соседними компьютерами, соединенными индивидуальной линией связи. К таким протоколам типа "точка-точка" относятся протоколы PPP, SLIP, LAP-B, LAP-D. Эти протоколы не используют подуровня доступа к среде, но требуют наличия процедур управления потоком кадров, так как промежуточные коммутаторы могут переполниться при слишком высокой интенсивности трафика по некоторым индивидуальным каналам. Кроме того, из-за высокой степени зашумленности глобальных каналов связи в протоколах этих сетей широко используются методы передачи данных с предварительным установлением соединения и повторными передачами кадров при их искажениях и потерях.
Канальный уровень оперирует единицами данных называемыми кадрами (frame) . В общем случае каждый протокол канального уровня имеет свой особый формат кадра.
В локальных сетях канальный уровень разделяется на два подуровня:
● уровень управления логическим каналом (logical link control, LLC).
● уровень доступа к среде (media access layer, MAC),
Уровень LLC отвечает за достоверную передачу кадров данных между узлами, а также реализует функции интерфейса с прилегающим к нему сетевым уровнем. MAC-уровень лежит ниже LLC-уровня и выполняет функции обеспечения доступа к разделяемой между узлами сети общей среде передачи данных. Стандартные протоколы канального уровня часто различаются реализацией метода доступа к разделяемой среде, в то время как функции LLC-уровня гораздо меньше варьируются от одного стандарта к другому.
Уровень LLC дает более высоким уровням возможность управления качеством услуг, предоставляемых канальным уровнем. Так передача данных на канальном уровне может быть выполнена дейтаграммным способом либо с установлением соединений, с подтверждением правильности приема либо без подтверждения.
Прием кадра из сети и отправка его в сеть связаны с процедурой доступа к среде передачи данных. В локальных сетях используется разделяемая среда передачи данных, поэтому все протоколы канального уровня локальных сетей включают процедуру доступа к среде, которая и является главной функцией МАС-уровня. Кроме того, МАС-уровень должен согласовать дуплексный режим работы уровня LLC с полудуплексным режимом работы физического уровня. Для этого он буферизует кадры с тем, чтобы при получении доступа к среде, передать их по назначению.
Для доступа к разделяемой среде в локальных сетях используется два типа методов доступа:
● методы случайного доступа,
● методы маркерного доступа.
Особенностью всех методов доступа к передающей среде, используемых в локальных сетях, является распределенный характер механизма их реализации, то есть в решении этой задачи участвуют все компьютеры на равных (или почти равных) основаниях. Такая децентрализация делает работу сети более надежной.
Методы случайного доступа основаны на том, что каждая станция сети пытается получить доступ к среде в тот момент времени, когда ей это становится необходимым. Если среда уже занята, то станция повторяет попытки доступа до тех пор, пока очередная попытка не окажется успешной. Хотя принцип случайного доступа допускает различные реализации, широко используется только метод случайного доступа технологии Ethernet.
Методы маркерного доступа основаны на детерминированной передаче от одного узла сети другому специального кадра информации - маркера (токена) доступа. Маркерные методы доступа используются в сетях Token Ring, ArcNet и FDDI. В таких сетях право на доступ к среде передается циклически от станции к станции по логическому кольцу.
Канальный уровень обеспечивает корректность передачи каждого кадра, помещая специальную последовательность бит в начало и конец каждого кадра, чтобы отметить его, а также вычисляет контрольную сумму, суммируя все байты кадра определенным способом и добавляя контрольную сумму к кадру. Когда кадр приходит, получатель снова вычисляет контрольную сумму полученных данных и сравнивает результат с контрольной суммой из кадра. Если они совпадают, кадр считается правильным и принимается. Если же контрольные суммы не совпадают, то фиксируется ошибка.
Функции канального уровня реализуются установленными в компьютерах сетевыми адаптерами и соответствующими им драйверами, а также различным коммуникационным оборудованием: мостами, коммутаторами, маршрутизаторами, шлюзами. В зависимости от того, какой протокол реализует сетевой адаптер, адаптеры делятся на Ethernet-адаптеры, Token Ring-адаптеры, FDDI-адаптеры и т. д. Аналогично, коммутаторы, мосты и машрутизаторы могут иметь порты, поддерживающие различные канальные протоколы.
Все эти устройства могут выполнять следующие действия:
● Формирование кадра - включает размещение данных, поступивших с верхнего уровня, в поле данных кадра, а также формирование заголовка, то есть определение и занесение в соответствующие поля кадра контрольной суммы, MAC-адресов отправителя и получателя, отметки о типе протокола верхнего уровня, пакет которого упакован в поле данных кадра, и возможно некоторой другой информации. Кадры могут быть информационными, содержащими данные конечных пользователей, (они формируются в компьютерах), и служебными, источником которых может быть любое устройство, использующее канальный уровень. Служебные кадры формируются, например, мостами для реализации алгоритма покрывающего дерева, маршрутизаторами при обмене маршрутной информацией, компьютерами при объявлении выполняемых ими сервисов.
● Анализ заголовка кадра и обработка кадра на основании результатов проведенного анализа могут заключаться, например, в уничтожении кадра при несовпадении контрольной суммы, в принятии решения о передаче кадра в сеть при несовпадении адреса назначения с адресом данного узла и т.п.
● Прием кадра из сети и отправка кадра в сеть прежде всего связаны с получением доступа к передающей среде, эта процедура единообразным образом выполняется всеми устройствами сети, построенной с использованием общей базовой сетевой технологии. Как правило, принимаемые кадры помещаются в буфер, а при отправке - выбираются из буфера.
Функции сетевого уровня
Протоколы канального уровня не позволяют строить сети с развитой структурой, например, сети, объединяющие несколько сетей предприятия в единую сеть, или высоконадежные сети, в которых существуют избыточные связи между узлами. Для того, чтобы, с одной стороны, сохранить простоту процедур передачи пакетов для типовых топологий, а с другой стороны, допустить использование произвольных топологий, вводится дополнительный сетевой уровень.
Прежде, чем приступить к рассмотрению функций сетевого уровня, уточним, что понимается под термином "сеть". В протоколах сетевого уровня термин "сеть" означает совокупность компьютеров, соединенных между собой в соответствии с одной из стандартных типовых топологий и использующих для передачи пакетов общую базовую сетевую технологию. Внутри сети сегменты не разделяются маршрутизаторами, иначе это была бы не одна сеть, а несколько сетей. Маршрутизатор соединят несколько сетей в интерсеть.
Основная идея введения сетевого уровня состоит в том, чтобы оставить технологии, используемые в объединяемых сетях в неизменном в виде, но добавить в кадры канального уровня дополнительную информацию - заголовок сетевого уровня , на основании которой можно было бы находить адресата в сети с любой базовой технологией. Заголовок пакета сетевого уровня имеет унифицированный формат, не зависящий от форматов кадров канального уровня тех сетей, которые могут входить в объединенную сеть.
Заголовок сетевого уровня должен содержать адрес назначения и другую информацию, необходимую для успешного перехода пакета из сети одного типа в сеть другого типа. К такой информации может относиться, например:
номер фрагмента пакета, нужный для успешного проведения операций сборки-разборки фрагментов< при соединении сетей с разными максимальными размерами кадров канального уровня,
время жизни пакета, указывающее, как долго он путешествует по интерсети, это время может использоваться для уничтожения "заблудившихся" пакетов,
«Построение сети с помощью алгоритма покрывающего дерева» - страница №1/1
Московский государственный институт электроники и математики
(технический университет)
Информационно-коммуникационные технологии
Расчётно-графическая работа №1 по дисциплине:
«Технические средства сетей ЭВМ»
«Построение сети с помощью алгоритма покрывающего дерева»
Вариант №5
Выполнил: студент гр. C-94
Новиков Р.О.
Преподаватель:
Леохин Ю.Л.
Москва 2008
Содержание
|
1. Введение |
3 |
|
2. Техническое задание |
6 |
|
3. Задача 1 |
7 |
|
4. Задача 2 |
8 |
|
5. Задача 3 |
9 |
|
6. Задача 4 |
10 |
|
Выводы |
11 |
1. Введение
Алгоритм покрывающего дерева - Spanning Tree Algorithm (STA) позволяет коммутаторам автоматически определять древовидную конфигурацию связей в сети при произвольном соединении портов между собой. Как уже отмечалось, для нормальной работы коммутатора требуется отсутствие замкнутых маршрутов в сети. Эти маршруты могут создаваться администратором специально для образования резервных связей или же возникать случайным образом, что вполне возможно, если сеть имеет многочисленные связи, а кабельная система плохо структурирована или документирована.
Поддерживающие алгоритм STA коммутаторы автоматически создают активную древовидную конфигурацию связей (то есть связную конфигурацию без петель) на множестве всех связей сети. Такая конфигурация называется покрывающим деревом - Spanning Tree (иногда ее называют основным деревом), и ее название дало имя всему алгоритму. Алгоритм Spanning Tree описан в стандарте IEEE 802.1D, том же стандарте, который определяет принципы работы прозрачных мостов.
Коммутаторы находят покрывающее дерево адаптивно, с помощью обмена служебными пакетами. Реализация в коммутаторе алгоритма STA очень важна для работы в больших сетях - если коммутатор не поддерживает этот алгоритм, то администратор должен самостоятельно определить, какие порты нужно перевести в заблокированное состояние, чтобы исключить петли. К тому же при отказе какого-либо кабеля, порта или коммутатора администратор должен, во-первых, обнаружить факт отказа, а во-вторых, ликвидировать последствия отказа, переведя резервную связь в рабочий режим путем активизации некоторых портов. При поддержке коммутаторами сети протокола Spanning Tree отказы обнаруживаются автоматически, за счет постоянного тестирования связности сети служебными пакетами. После обнаружения потери связности протокол строит новое покрывающее дерево, если это возможно, и сеть автоматически восстанавливает работоспособность.
Алгоритм Spanning Tree определяет активную конфигурацию сети за три этапа.
Расстояние до корня определяется, как суммарное условное время на передачу одного бита данных от порта данного коммутатора до порта корневого коммутатора. При этом считается, что время внутренних передач данных (с порта на порт) коммутатором пренебрежимо мало, а учитывается только время на передачу данных по сегментам сети, соединяющим коммутаторы. Условное время сегмента рассчитывается как время, затрачиваемое на передачу одного бита информации в 10 наносекундных единицах между непосредственно связанными по сегменту сети портами. Так, для сегмента Ethernet это время равно 10 условным единицам, а для сегмента Token Ring 16 Мбит/с - 6,25. (Алгоритм STA не связан с каким-либо определенным стандартом канального уровня, он может применяться к коммутаторам, соединяющим сети различных технологий.)
В приведенном примере предполагается, что все сегменты работают на одной скорости, поэтому они имеют одинаковые условные расстояния, которые поэтому не показаны на рисунке.
Для автоматического определения начальной активной конфигурации дерева все коммутаторы сети после их инициализации начинают периодически обмениваться специальными пакетами, называемыми протокольными блоками данных моста - BPDU (Bridge Protocol Data Unit), что отражает факт первоначальной разработки алгоритма STA для мостов.
Идентификаторы коммутаторов состоят из 8 байт, причем младшие 6 являются МАС - адресом блока управления коммутатора. Старшие 2 байта в исходном состоянии заполнены нулями, но администратор может изменить значение этих байтов, тем самым назначив определенный коммутатор корневым.
После инициализации каждый коммутатор сначала считает себя корневым. Поэтому он начинает через интервал hello генерировать через все свои порты сообщения BPDU конфигурационного типа. В них он указывает свой идентификатор в качестве идентификатора корневого коммутатора (и в качестве идентификатора данного коммутатора также), расстояние до корня устанавливается в 0, а в качестве идентификатора порта указывается идентификатор того порта, через который передается BPDU. Как только коммутатор получает BPDU, в котором имеется идентификатор корневого коммутатора, со значением, меньшим его собственного, он перестает генерировать свои собственные кадры BPDU, а начинает ретранслировать только кадры нового претендента на звание корневого коммутатора. На рис. 4.38 у коммутатора 1 идентификатор имеет наименьшее значение, раз он стал в результате обмена кадрами корневым.
При ретрансляции кадров каждый коммутатор наращивает расстояние до корня, указанное в пришедшем BPDU, на условное время сегмента, по которому принят данный кадр. Тем самым в кадре BPDU, по мере прохождения через коммутаторы, накапливается расстояние до корневого коммутатора. Если считать, что все сегменты рассматриваемого примера являются сегментами Ethernet, то коммутатор 2, приняв от коммутатора BPDU по сегменту 1 с расстоянием, равным 0, наращивает его на 10 единиц.
Ретранслируя кадры, каждый коммутатор для каждого своего порта запоминает минимальное расстояние до корня, встретившееся во всех принятых этим портом кадрах BPDU. При завершении процедуры установления конфигурации покрывающего дерева (по времени) каждый коммутатор находит свой корневой порт - это порт, для которого минимальное расстояние до корня оказалось меньше, чем у других портов. Так, коммутатор 3 выбирает порт А в качестве корневого, поскольку по порту А минимальное расстояние до корня равно 10 (BPDU с таким расстоянием принят от корневого коммутатора через сегмент 1). Порт В коммутатора 3 обнаружил в принимаемых кадрах минимальное расстояние в 20 единиц - это соответствовало случаю прохождения кадра от порта В корневого моста через сегмент 2, затем через мост 4 и сегмент 3.
Кроме корневого порта коммутаторы распределенным образом выбирают для каждого сегмента сети назначенный порт. Для этого они исключают из рассмотрения свой корневой порт (для сегмента, к которому он подключен, всегда существует другой коммутатор, который ближе расположен к корню), а для всех своих оставшихся портов сравнивают принятые по ним минимальные расстояния до корня с расстоянием до корня своего корневого порта. Если у какого-либо своего порта принятые им расстояния до корня больше, чем расстояние маршрута, пролегающего через свой корневой порт, то это значит, что для сегмента, к которому подключен данный порт, кратчайшее расстояние к корневому коммутатору ведет именно через данный порт. Коммутатор делает все свои порты, у которых такое условие выполняется, назначенными.
Если в процессе выбора корневого порта или назначенного порта несколько портов оказываются равными по критерию кратчайшего расстояния до корневого коммутатора, то выбирается порт с наименьшим идентификатором.
2. Техническое задание
Для сети, состоящей из 5 сегментов Ethernet и 6 мостов, соединенных так, как это показано на рисунке определить корневой мост и корневые порты и назначенные порты у некорневых мостов, используя алгоритм покрывающего дерева.
Условные обозначения:
Корневой порт
Отключенный порт
Назначенный порт
3. Задача 1
Условие
Все мосты и порты имеют равные приоритеты, все сегменты имеют равную пропускную способность и условное время для них = 1.
|
B1.P1 |
B1.P2 |
B1.P3 |
B2.P1 |
B2.P2 |
B3.P1 |
B3.P2 |
|
|
minRPC |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
RPC |
0 |
0 |
0 |
1 |
1 |
1 |
2 |
|
minB |
B1 |
B1 | |||||
|
minP |
P2 |
P1 |
|
B4.P1 |
B4.P2 |
B4.P3 |
B5.P1 |
B5.P2 |
B6.P1 |
B6.P2 |
|
|
minRPC |
0 |
1 |
0 |
0 |
1 |
1 |
∞ |
|
RPC |
1 |
2 |
1 |
1 |
2 |
2 |
∞ |
|
minB |
B1 |
B1 |
B3 | ||||
|
MinP |
P3 |
P3 |
P2 |
Условие
Все параметры те же, что и в случае 1, но мост B1 отказал.
В заданных условиях корневым станет мост B2. Это произойдет в результате выполнения процедуры активной конфигурации, вызванной отказом моста B1.
|
B2.P1 |
B2.P2 |
B3.P1 |
B3.P2 |
B4.P1 |
B4.P2 |
B4.P3 |
B5.P1 |
B5.P2 |
B6.P1 |
B6.P2 |
|
|
minRPC |
0 |
0 |
1 |
1 |
0 |
1 |
2 |
0 |
1 |
1 |
∞ |
|
RPC |
0 |
0 |
2 |
2 |
1 |
2 |
3 |
1 |
2 |
2 | |
|
minB |
B4 |
B2 |
B2 |
B3 | |||||||
|
minP |
P3 |
P2 |
P2 |
P2 |
5. Задача 3
Условие
Все мосты работоспособны, но производительность сегментов S3 и S5 в три раза выше остальных, поэтому условное время остальных сегментов в три раза больше, чем у S3 и S5.
Мост B1 имеет минимальный идентификатор – следовательно, он корневой.
|
B1.P1 |
B1.P2 |
B1.P3 |
B2.P1 |
B2.P2 |
B3.P1 |
B3.P2 |
|
|
minRPC |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
RPC |
0 |
0 |
0 |
3 |
3 |
1 |
6 |
|
minB |
B1 |
B1 | |||||
|
minP |
P2 |
P1 |
|
B4.P1 |
B4.P2 |
B4.P3 |
B5.P1 |
B5.P2 |
B6.P1 |
B6.P2 |
|
|
minRPC |
0 |
1 |
0 |
0 |
1 |
1 |
∞ |
|
RPC |
3 |
6 |
1 |
3 |
6 |
6 |
∞ |
|
minB |
B1 |
B1 |
B3 | ||||
|
minP |
P1 |
P3 |
P2 |
6. Задача 4
Условие
Все сегменты имеют одинаковую производительность, но администратор установил более высокий приоритет для моста B5.
Мост B5 имеет максимальный приоритет – следовательно, он корневой.
|
B1.P1 |
B1.P2 |
B1.P3 |
B2.P1 |
B2.P2 |
B3.P1 |
B3.P2 |
|
|
minRPC |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
|
RPC |
2 |
2 |
1 |
2 |
1 |
2 |
1 |
|
minB |
B5 |
B5 |
B5 |
||||
|
minP |
P1 |
P1 |
P2 |
|
B4.P1 |
B4.P2 |
B4.P3 |
B5.P1 |
B5.P2 |
B6.P1 |
B6.P2 |
|
|
minRPC |
0 |
0 |
1 |
0 |
0 |
0 |
∞ |
|
RPC |
1 |
1 |
2 |
0 |
0 |
1 |
∞ |
|
minB |
B5 |
B5 | |||||
|
minP |
P1 |
P2 |
Выводы
При помощи алгоритма покрывающего дерева для заданной в техническом задании сети были определены корневые мосты и корневые порты. Также были решены поставленные задачи в случае сбоев сети.
Математическая модель вычисления покрывающего дерева сети
Ключевые слова: покрывающее дерево, оптимизация затрат на трафик, нагрузка на рёбра, стоимость использования сети, интенсивность обмена трафиком.
Для произвольной заданной сети строится минимальное покрывающее дерево, учитывающее интенсивность обмена данными для каждой пары узлов исходной сети. Тем самым решается проблема выбора оптимального маршрута для обмена данными между каждой парой вершин заданного графа сети; решается задача выбора минимальных по стоимости провайдеров, обеспечивающего связь между узлами сети. Для этого сеть передачи данных представляется в виде неориентированного графа, для которого строится покрывающее дерево, обеспечивающее минимальные затраты на весь проходящий по сети трафик. Количество переданной информации в единицу времени между каждой парой узлов сети задаётся матрицей интенсивностей обмена данными. Граф сети задаётся матрицей смежности. Стоимость прохождения единицы информации по каждому из рёбер графа сети представляет собой матрицу весов. Для решения поставленной задачи разработан алгоритм и соответствующий программный продукт, строящий покрывающее дерево, которое позволяет передавать заранее заданные объёмы информации между всеми пользователями сети, при этом суммарная стоимость трафика будет минимальной. Помимо построенного покрывающего дерева алгоритм даёт также возможную минимальную стоимость передачи заданного объёма данных между всеми узлами сети. Алгоритм позволяет построить минимальное покрывающее дерево (покрывающее дерево минимального веса), однако для такой цели можно использовать уже имеющиеся алгоритмы, такие как, например, алгоритм Прима или Краскала. Однако с помощью указанных алгоритмов возможно построить лишь минимальное по весу покрывающее дерево. В отличие от них предложенный в работе алгоритм строит дерево с учётом нагрузок на рёбра и вершины исходного графа сети и, вычисляя общую стоимость всего проходящего по сети трафика, минимизирует её.
Анищенко А.А.,
соискатель, кафедра теории вероятностей и математической статистики РУДН, [email protected]
Огромное количество задач может быть смоделировано в виде графа. Это и маршрутизация пакетов в Интернете, и проектирование сетей, и молекулярная биология, и электрические цени, и системы автоматизированного планирования, научные вычисления и много другое. Кроме того, многие проблемы, решенные в рамках теории графов можно перенести на более широкие области. Поэтому использование графовой модели очень эффективно во многих областях сетевых технологий.
Пусть сеть представлена в виде связного неориентированного графа без петель С(У,Е) с множеством вершин V = \;п, и множеством ребер Е. (Здесь и далее используется терминология Харари = \;п- Если та^ = 0- то
вершины не смежные. Для удобства дальнейшего обозначения вводится равносильное обозначение та(!,]) = тЗц ■
Интенсивность передачи данных между узлами задана матрицей Л: Л = {Ху}={Х(ь])}% ¡, ] = \;п, /,У е ¡/(С)I где есть количество информации, переданное за единицу времени из вершины / в вершину /.
Заданы стоимости прохождения единицы трафика по каждому из ребер графа.
Ставится задача построения такого остовного дерева Т(У,ТЕ)> которое позволяет передавать заранее заданные объёмы информации между всеми пользователями сети (матрица Л). При этом суммарная стоимость трафика будет минимальной.
При обеспечении связи между парой вершин более чем одним провайдером (кратные ребра иа графе) рассматривается только ребро с минимальной стоимостью. Данный выбор оправдан, что доказано в ,
Поскольку граф в неориентированный, рёбра < /,} > и < _/,/ > представляют собой одно и то же ребро
и являются равноценными, то есть стоимость за единицу трафика, прошедшего по ним, одинакова.
Стоимость прохождения единицы трафика по каждому из ребер задаётся матрицей стоимостей или матрицей весов \УН = {и"/;7}-{м>г(¿,])}, ¡,] = \:п- Так как граф
С(У,Е) неориентированный, матрица №7? симметрична относительно главной диагонали. Тогда в матрице МБ
Если вершины / и / смежны,еели вершины;и] не смежны
Одной из проблем, возникающих при моделировании реальных систем и сетей, является огромная размерность графа. Анализ такого графа очень затруднителен и может занимать огромное количество времени. Даже многие из элементарных вычислений не представляются возможными при огромном количестве вершин в графе.
Тогда, объединяя вершины в группы, можно добиться такого укрупнения графа С (V .Е"), при котором воз-
можно построение оптимального покрывающего дерева для укрупнённого графа. Л затем при необходимости и для графов, лежащих в вершинах укрупненного графа V. Для этого разбивка на группы записывается в матрицу В = {(¡¡!}, 1-\;т, / = I,/). Где т- количество групп, то есть |К"| =т, \У\ = п;
П,если /е/
V; т V, V/ е V щ =■" J
через узел, но не выходящими из него и не входящими в него.
Тогда для у круп- vifvj =
О, если i £ i
пенного графа С матрица обмена данными Л" вычисляется следующим образом: Л"= RAR1 . Таким образом, при большом количестве вершин поставленную задачу можно свести к меньшей, поэтому предполагается, что в исходном графе п достаточно мало, для того, чтобы были возможны вычисления.
Для решения поставленной задачи:
1. Строится произвольное покрывающее дерево T(V,TE), с матрицей смежности S={sy}={s(i,j)}t
ii j - п и прежней матрицей интенсивностей передачи данных Л.
2. Вычисляется матрица весов полученного дерева WRT = {wrtij } = {wrt(i,j)}: wrty = s„>
3. Для полученного дерева Т вычисляются нагрузки на ребра R = {r.. J = {r(i,j)}, i,j = \;п-
4. Вычисляется суммарная стоимость прохождения трафика по построенному покрывающему дереву
/ftMv S(¡./(¡)Щ y*/fl) Mi.jH)
Mi)+\i(i) -сЫ\) - Ui.f(i))-Mf(i) j) -
YjMftüs \(i. z))+ys ui. zj.fdjj)
MO=ifeff +)=tiWJ)+KW);
5. Полученная стоимость сравнивается с предыдущей наименьшей стоимостью и сохраняется только наименьшая.
6. Строится следующее покрывающее дерево, и алгоритм возвращается к п.2.
Таким образом, перебирая все возможные покрывающие деревья, используя, например, алгоритм Кри-стофидеса } = { f(i)} является на каждом
этапе вектором вершин, смежных с концевыми. (После каждого этапа вектор обнуляется).
dw(i)- «дуговая» нагрузка на i -ю вершину. Для вершины с номером f (i), смежной с концевой вершиной /
Usv(f(i).h),i)+WMfOJA)))
SV -{svy }-{sv(i,j)}> /,7=1,« - матрица, в /-й
строке которой записана последовательность пройденных и удалённых вершин до вершины i;
K = fkj} = {k(i)}, i - \;n - вектор-счётчик количества элементов в строке I матрицы S V .
После того, как вычислены все транзитные нагрузки И>(/) на вершины i = 1/и, можно вычислить и нагрузки на ребра дерева Т:
V/ - й г(/,/(0) - г(/Ш) - Mf) - scMi) + lam(i) -- X \lam(i,sv(i, z) + /am{5v(i, z)ti).
Так как исходный граф G неориентированный и вычисленные нагрузки на ребра r(i, /") являются суммарными нагрузками на ребро < i,j > в обе стороны, то есть из / в / и из / в /, то матрица нагрузок па ребра графа = симметрична.
Блок- схема алгоритма вычисления нагрузок на рёбра покрывающего дерева Т представлена на рис. I.
Задача о нахождении минимального остовного или покрывающего дерева для взвешенного связанного неориентированного графа возникала давно и встречается довольно часто в различных областях. Существует немало алгоритмов реализующих поиск минимального по весу покрывающего дерева для г рафа. Самыми известными из них являются алгоритмы Крас кала. Прима, Бо-рувки . Однако в применении к сетям такие алгоритмы не всегда подходят, поскольку они не учитывают нагрузки на узлы и каналы сети.
Представленный алгоритм учитывает интенсивность обмена трафиком между узлами сети и стоимость прохождения этого трафика по сети и позволяет смоделировать такое покрывающее дерево, которое минимизировало бы затраты на проходящий по сети трафик.
Mathematical model of finding a network spanning tree
Anishchenko AA, Peoples" Friendship University, Moscow, Russia, [email protected]
Abstract. The minimal spanning tree is created for any given network which takes into account the intensity of the data communication for each pair of nodes of the given network. So the problem of choosing the optimal route for the data com-munication between each pair of vertices of the given network graph is solved, the problem of choosing the providers with minimum cost of communication be-tween nodes is solved. For this data network is represented as an undirected graph for which is created a spanning tree with the minimum traffic overhead. Amount of data transmitted per unit of time between each pair of network nodes is represented as a matrix of the data exchange intensity. Graph of the network is given by the adjacency matrix. The cost of a unity of information on each of the edges of the network is a matrix of weights. An algorithm and corresponding software package were developed to solve this problem. Throgh the usage of minimal spanning tree the software allows a user to deliver a known amount of information to all nodes at minimal traffic cost.Besides the constructed spanning tree algorithm computes the minimal cost of transfer a given amount of data between all nodes. In addition algorithm can construct a minimum spanning tree (spanning tree with the lowest total cost), for this is possible use of the existing algorithms such as the Prim"s or Kruskal"s algorithm, for example. But using these algorithms allows building a spanning tree with the lowest total cost. In contrast, the proposed algorithm creates a tree taking into account loads on the edges and vertices of the original network graph and computes and minimizes the total cost of all traffic in the network. Keywords: spanning tee, cost optimization for traffic, load on the edges, the cost of using the network, the data exchange intensity.
В коммутируемых локальных сетях проблема обеспечения надежности сети имеет свою специфику: базовый протокол прозрачного моста корректно работает только в сети с древовидной топологией, в которой между любыми двумя узлами сети существует единственный маршрут. Тем не менее очевидно, что для надежной работы сети необходимо наличие альтернативных маршрутов между узлами, которые можно использовать при отказе основного маршрута. Наиболее простым решением этой проблемы является построение сети с альтернативными маршрутами, ручное нахождение связной древовидной топологии и ручное блокирование (то есть перевод в административное состояние «отключен») всех портов, которые не входят в найденную топологию. В случае отказа сети этот процесс должен повторяться, опять же в ручном режиме. Понятно, что надежность сети в этом случае оказывается не очень высокой, так как время пребывания ее в неработоспособном состоянии будет исчисляться минутами: сначала нужно обнаружить отказ и локализовать его (то есть не только зафиксировать факт, что в сети что-то перестало работать, но и понять, какая именно связь пострадала и требует обхода), затем найти новый работоспособный вариант топологи сети (если он, конечно, существует), а потом его сконфигурировать.
Для автоматического выполнения перечисленных действий, то есть нахождения и конфигурирования активной древовидной топологии, мониторинга состояния ее связей и перехода к новой древовидной топологии при обнаружении отказа связи в коммутируемых локальных сетях используются алгоритм покрывающего дерева (Spanning Tree Algorithm, STA) и реализующий его протокол покрывающего дерева (Spanning Tree Protocol, STP).
Алгоритм покрывающего дерева, разработанный достаточно давно, в 1983 году, был признан IEEE удачным решением и включен в ту же спецификацию 802.1D, в котороиописывается и сам алгоритм прозрачного моста. Сегодня протокол STP широко применяется в наиболее массовых устройствах современных локальных сетей - коммутаторах. Протокол STP обновлялся несколько раз, последняя его редакция описана в документе 802.1D-2004; новая версия протокола получила название RSTP (Rapid STP, то есть быстрый протокол покрывающего дерева), так как предыдущие версии STP недостаточно быстро находили новую древовидную топологию - на это могло уйти до 50 секунд. Новая версия протокола покрывающего дерева - RSTP - работает значительно быстрее, затрачивая на поиск новой топологи несколько секунд.
Алгоритм покрывающего дерева (Spanning Tree Algorithm, STA) описан в стандарте IEEE 802.1D и позволяет ликвидировать петли в сети (если в сети есть кольцевые маршруты, это может привести к неправильной работе мостов и коммутаторов). Алгоритм STA из всех связей, имеющихся в сети, выбирает подмножество, образующее дерево, покрывающее все узлы сети. Алгоритм STA состоит из четырех этапов.
В сети выбирается корневой коммутатор (root switch), который будет считаться корнем дерева. Выбор происходит либо автоматически (корневым становится коммутатор с наименьшим значением MAC-адреса блока управления), либо выполняется администратором.
Для каждого коммутатора определяется корневой порт (root port) – порт, через который проходит самый короткий путь до корневого коммутатора.
Для каждого сегмента сети выбирается назначенный порт (designated port) – порт, через который проходит кратчайший путь от данного сегмента до корневого коммутатора.
Все порты, не вошедшие в корневые и назначенные, блокируются.
При определении кратчайших расстояний рассчитывается суммарное время (в 10-наносекундных единицах) передачи одного бита данных от выбранного порта до корневого коммутатора (учитывается только времена передач по связям между коммутаторами). Например, для Ethernet-сегмента время передачи равно 10, а для Fast Ethernet – 1.
Все коммутаторы периодически обмениваются служебными пакетами – протокольными блоками данных моста (Bridge Protocol Data Unit, BPDU), содержащими идентификатор корневого коммутатора, расстояние до корня, идентификатор коммутатора, выдавшего этот пакет, идентификатор порта, на который был выдан пакет и еще несколько служебных полей. После включения каждый коммутатор считает себя корневым (если иное не задано администратором) и выдает пакеты BPDU со своим идентификатором в поле “идентификатор корневого коммутатора” и расстоянием до корня, равным 0, через все свои порты. Если коммутатор получает BPDU, в котором идентификатор корневого коммутатора меньше его собственного идентификатора, он перестает генерировать свои пакеты, а ретранслирует приходящие пакеты нового корневого коммутатора, увеличивая в них поле “расстояние до корня” на условное время сегмента, по которому пришел этот пакет. При этом коммутатор запоминает для каждого порта минимальное расстояние до корня (из всех пришедших на этот порт пакетов BPDU).
Через заданное время процесс конфигурации заканчивается и корневым портом коммутатор считает тот свой порт, у которого расстояние до корня оказалось минимальным (если таких портов несколько, выбирается порт с наименьшим идентификатором). Затем, он делает назначенными все порты, принятые по которым минимальные расстояния до корня больше, чем расстояние до корня корневого порта. Наконец, все порты, кроме корневого и назначенных, переводятся в заблокированное состояние. В процессе дальнейшей работы корневой коммутатор продолжает генерировать пакеты BPDU, а остальные коммутаторы продолжают их ретранслировать. Если за установленное время тайм-аута корневой порт какого-либо коммутатора не получает BPDU, он инициирует новую процедуру построения
