В коммутируемых локальных сетях проблема обеспечения надежности сети имеет свою специфику: базовый протокол прозрачного моста корректно работает только в сети с древовидной топологией, в которой между любыми двумя узлами сети существует единственный маршрут. Тем не менее очевидно, что для надежной работы сети необходимо наличие альтернативных маршрутов между узлами, которые можно использовать при отказе основного маршрута. Наиболее простым решением этой проблемы является построение сети с альтернативными маршрутами, ручное нахождение связной древовидной топологии и ручное блокирование (то есть перевод в административное состояние «отключен») всех портов, которые не входят в найденную топологию. В случае отказа сети этот процесс должен повторяться, опять же в ручном режиме. Понятно, что надежность сети в этом случае оказывается не очень высокой, так как время пребывания ее в неработоспособном состоянии будет исчисляться минутами: сначала нужно обнаружить отказ и локализовать его (то есть не только зафиксировать факт, что в сети что-то перестало работать, но и понять, какая именно связь пострадала и требует обхода), затем найти новый работоспособный вариант топологи сети (если он, конечно, существует), а потом его сконфигурировать.
Для автоматического выполнения перечисленных действий, то есть нахождения и конфигурирования активной древовидной топологии, мониторинга состояния ее связей и перехода к новой древовидной топологии при обнаружении отказа связи в коммутируемых локальных сетях используются алгоритм покрывающего дерева (Spanning Tree Algorithm, STA) и реализующий его протокол покрывающего дерева (Spanning Tree Protocol, STP).
Алгоритм покрывающего дерева, разработанный достаточно давно, в 1983 году, был признан IEEE удачным решением и включен в ту же спецификацию 802.1D, в котороиописывается и сам алгоритм прозрачного моста. Сегодня протокол STP широко применяется в наиболее массовых устройствах современных локальных сетей - коммутаторах. Протокол STP обновлялся несколько раз, последняя его редакция описана в документе 802.1D-2004; новая версия протокола получила название RSTP (Rapid STP, то есть быстрый протокол покрывающего дерева), так как предыдущие версии STP недостаточно быстро находили новую древовидную топологию - на это могло уйти до 50 секунд. Новая версия протокола покрывающего дерева - RSTP - работает значительно быстрее, затрачивая на поиск новой топологи несколько секунд.
2. Этапы построения покрывающего дерева.
Алгоритм покрывающего дерева (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, он инициирует новую процедуру построения
Алгоритм покрывающего дерева - Spanning Tree Algorithm (STA) позволяет коммутаторам автоматически определять древовидную конфигурацию связей в сети при произвольном соединения портов между собой. Как уже отмечалось, для нормальной работы коммутатора требуется отсутствие замкнутых маршрутов в сети. Эти маршруты могут создаваться администратором специально для образования резервных связей или же возникать случайным образом, что вполне возможно, если сеть имеет многочисленные связи, а кабельная система плохо структурирована или документирована.
Поддерживающие алгоритм STA коммутаторы автоматически создают активную древовидную конфигурацию связей (то есть связную конфигурацию без петель) на множестве всех связей сети. Такая конфигурация называется покрывающим деревом - Spanning Tree (иногда ее называют основным деревом), и ее название дало имя всему алгоритму. Алгоритм Spanning Tree описан в стандарте IEEE 802.1D,"" том же стандарте, который определяет принципы работы прозрачных мостов.
Коммутаторы находят покрывающее дерево адаптивно, с помощью обмена служебными пакетами. Реализация в коммутаторе алгоритма STA очень важна для работы в больших сетях - если коммутатор не поддерживает этот алгоритм, то администратор должен самостоятельно определить, какие порты нужно перевести в заблокированное состояние, чтобы исключить петли. К тому же при отказе какого-либо кабеля, порта или коммутатора администратор должен, во-первых, обнаружить факт отказа, а во-вторых, ликвидировать последствия отказа, переведя резервную связь в рабочий режим путем активизации некоторых портов. При поддержке коммутаторами сети протокола Spanning Tree отказы обнаруживаются автоматически, за счет постоянного тестирования связности сети служебными пакетами. После обнаружения потери связности протокол строит новое покрывающее дерево, если это возможно, и сеть автоматически восстанавливает работоспособность.
Алгоритм Spanning Tree определяет активную конфигурацию сети за три этапа.
Сначала в сети определяется корневой коммутатор (root switch), от которого строится дерево. Корневой коммутатор может быть выбран автоматически или назначен администратором. При автоматическом выборе корневым становится коммутатор с меньшим значением МАС-адреса его блока управления.
Затем, на втором этапе, для каждого коммутатора определяется корневой порт (root port) - это порт, который имеет по сети кратчайшее расстояние до корневого коммутатора (точнее, до любого из портов корневого коммутатора).И наконец, на третьем этапе для каждого сегмента сети выбирается так называемый назначенный порт (designated port) - это порт, который имеет кратчайшее расстояние от данного сегмента до корневого коммутатора. После определения корневых и назначенных портов каждый коммутатор блокирует остальные порты, которые не попали в эти два класса портов. Можно математически доказать,
что при таком выборе активных портов в сети исключаются петли и оставшиеся
связи образуют покрывающее дерево (если оно может быть построено при существующих связях в сети).
Понятие расстояния играет важную роль в построении покрывающего дерева.
Именно по этому критерию выбирается единственный порт, соединяющий каждый коммутатор с корневым коммутатором, и единственный порт, соединяющий каждый сегмент сети с корневым коммутатором.
На рис. 4.38 показан пример построения конфигурации покрывающего дерева для сети, состоящей из 5 сегментов и 5 коммутаторов. Корневые порты закрашены темным цветом, назначенные порты не закрашены, а заблокированные порты перечеркнуты. В активной конфигурации коммутаторы 2 и 4 не имеют портов, передающих кадры данных, поэтому они закрашены как резервные.
Расстояние до корня определяется как суммарное условное время на передачу одного бита данных от порта данного коммутатора до порта корневого коммутатора. При этом считается, что время внутренних передач данных (с порта на порт) коммутатором пренебрежимо мало, а учитывается только время на передачу данных по сегментам сети, соединяющим коммутаторы. Условное время сегмента рассчитывается как время, затрачиваемое на передачу одного бита информации в 10 наносекундных единицах между непосредственно связанными по сегменту сети портами. Так, для сегмента Ethernet это время равно 10 условным единицам, а для сегмента Token Ring 16 Мбит/с - 6,25. (Алгоритм STA не связан с каким-либо определенным стандартом канального уровня, он может применяться к коммутаторам, соединяющим сети различных технологий.)
В приведенном примере предполагается, что все сегменты работают на одной скорости, поэтому они имеют одинаковые условные расстояния, которые поэтому не показаны на рисунке.
Для автоматического определения начальной активной конфигурации дерева все коммутаторы сети после их инициализации начинают периодически обмениваться специальными пакетами, называемыми протокольными блоками данных моста - BPDU(Bridge ProtocolData Unit), что отражает факт первоначальной разработки алгоритма STA для мостов.
Пакеты BPDU помещаются в поле данных кадров канального уровня, например кадров Ethernet или FDDI. Желательно, чтобы все коммутаторы поддерживали общий групповой адрес, с помощью которого кадры, содержащие пакеты BPDU, могли бы одновременно передаваться всем коммутаторам сети. Иначе пакеты BPDU рассылаются широковещательно.
Поля пакета BPDU перечислены ниже.
Идентификатор версии протокола STA - 2 байта. Коммутаторы должны поддерживать одну и ту же версию протокола STA, иначе может установиться активная конфигурация с петлями.
Тип BPDU - 1 байт. Существуют два типа BPDU - конфигурационный BPDU,
то есть заявка на возможность стать корневым коммутатором, на основании
которой происходит определение активной конфигурации, и BPDU уведомления о реконфигурации, которое посылается коммутатором, обнаружившим событие, требующее проведения реконфигурации - отказ линии связи, отказ порта,
изменение приоритетов коммутатора или портов.
Флаги - 1 байт. Один бит содержит флаг изменения конфигурации, второй -
флаг подтверждения изменения конфигурации.
Идентификатор корневого коммутатора - 8 байт.
Расстояние до корня - 2 байта.
Идентификатор коммутатора - 8 байт.
Идентификатор порта - 2 байта.
Время жизни сообщения - 2 байта. Изме^лехся в единицах по 0,5 с, служит для выявления устаревших сообщений. Когда пакет BPDU проходит через коммутатор, тот добавляет ко времени жизни пакета время его задержки данным коммутатором.
Максимальное время жизни сообщения - 2 байта. Если пакет BPDU имеет время жизни, превышающее максимальное, то он игнорируется коммутаторами.
Интервал hello, через который посылаются пакеты BPDU.
Задержка смены состояний - 2 байта. Задержка определяет минимальное время перехода портов коммутатора в активное состояние. Такая задержка необходима, чтобы исключить возможность временного возникновения петель при неодновременной смене состояний портов во время реконфигурации.
У пакета BPDU уведомления о реконфигурации отсутствуют все поля, кроме двух первых.
Идентификаторы коммутаторов состоят из 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 и назначенного порта для сегмента 2. Мост 2 при выборе корневого порта столкнулся с ситуацией, когда порт А и порт В имеют равное расстояние до корня - по 10 единиц (порт А принимает кадры от порта В корневого коммутатора через один промежуточный сегмент - сегмент 1, а порт В принимает кадры от порта А корневого коммутатора также через один промежуточный сегмент - через сегмент 2). Идентификатор А имеет меньшее числовое значение, чем В (в силу упорядоченности кодов символов), поэтому порт А стал корневым портом коммутатора 2.
При проверке порта В на случай, не является ли он назначенным для сегмента 2, коммутатор 2 обнаружил, что через этот порт он принимал кадры с указанным в них минимальным расстоянием 0 (это были кадры от порта В корневого коммутатора 1). Так как собственный корневой порт у коммутатора 2 имеет расстояние до корня 10, то порт В не является назначенным для сегмента 2.
Затем все порты, кроме корневого и назначенных, переводятся каждым коммутатором в заблокированное состояние. На этом построение покрывающего дерева заканчивается.
В процессе нормальной работы корневой коммутатор продолжает генерировать служебные кадры BPDU, а остальные коммутаторы продолжают их принимать своими корневыми портами и ретранслировать назначенными. Если у коммутатора нет назначенных портов, как у коммутаторов 2 и 4, то они все равно продолжают принимать участие в работе протокола Spanning Tree, принимая служебные кадры корневым портом. Если по истечении тайм-аута корневой порт любого коммутатора сети не получает служебный кадр BPDU, то он инициализирует новую процедуру построения покрывающего дерева, оповещая об этом другие коммутаторы BPDU уведомления о реконфигурации. Получив такой кадр, все коммутаторы начинают снова генерировать BDPU конфигурационного типа, в результате чего устанавливается новая активная конфигурация.
Математическая модель вычисления покрывающего дерева сети
Ключевые слова: покрывающее дерево, оптимизация затрат на трафик, нагрузка на рёбра, стоимость использования сети, интенсивность обмена трафиком.
Для произвольной заданной сети строится минимальное покрывающее дерево, учитывающее интенсивность обмена данными для каждой пары узлов исходной сети. Тем самым решается проблема выбора оптимального маршрута для обмена данными между каждой парой вершин заданного графа сети; решается задача выбора минимальных по стоимости провайдеров, обеспечивающего связь между узлами сети. Для этого сеть передачи данных представляется в виде неориентированного графа, для которого строится покрывающее дерево, обеспечивающее минимальные затраты на весь проходящий по сети трафик. Количество переданной информации в единицу времени между каждой парой узлов сети задаётся матрицей интенсивностей обмена данными. Граф сети задаётся матрицей смежности. Стоимость прохождения единицы информации по каждому из рёбер графа сети представляет собой матрицу весов. Для решения поставленной задачи разработан алгоритм и соответствующий программный продукт, строящий покрывающее дерево, которое позволяет передавать заранее заданные объёмы информации между всеми пользователями сети, при этом суммарная стоимость трафика будет минимальной. Помимо построенного покрывающего дерева алгоритм даёт также возможную минимальную стоимость передачи заданного объёма данных между всеми узлами сети. Алгоритм позволяет построить минимальное покрывающее дерево (покрывающее дерево минимального веса), однако для такой цели можно использовать уже имеющиеся алгоритмы, такие как, например, алгоритм Прима или Краскала. Однако с помощью указанных алгоритмов возможно построить лишь минимальное по весу покрывающее дерево. В отличие от них предложенный в работе алгоритм строит дерево с учётом нагрузок на рёбра и вершины исходного графа сети и, вычисляя общую стоимость всего проходящего по сети трафика, минимизирует её.
Анищенко А.А.,
соискатель, кафедра теории вероятностей и математической статистики РУДН, [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.
также оказывает непосредственное влияние на производительность коммутатора. Буферная память используется для временного хранения кадров, в случае если их невозможности немедленной передачи на выходной порт. Основное назначение буферной памяти заключается в сглаживании кратковременных пиковых пульсаций трафика. Такие ситуации могут возникать в случае, если на все порты коммутатора одновременно предаются кадры, и у коммутатора нет возможности передавать принимаемые кадры на порты назначения. Чем больше объем буферной памяти, тем ниже вероятность потери кадров при перегрузках. Размер буферной памяти может указываться как общий, так и в расчете на порт. Для повышения эффективности использования буферной памяти в некоторых моделях коммутаторов память может перераспределяться между портами, так как перегрузки на всех портах маловероятны.
1.3 Алгоритм покрывающего дерева (STA )
Алгоритм покрывающего дерева - Spanning Tree Algorith (STA) позволяет коммутаторам автоматически определять древовидную конфигурацию связей в сети при произвольном соединении портов между собой. Как уже отмечалось, для нормальной работы коммутатора требуется отсутствие замкнутых маршрутов в сети. Эти маршруты могут создаваться администратором специально для образования резервных связей или же возникать случайным образом, что вполне возможно, если сеть имеет многочисленные связи, а кабельная система плохо структурирована или документирована.
Поддерживающие алгоритм STA коммутаторы автоматически создают активную древовидную конфигурацию связей, то есть связную конфигурацию без петель, на множестве всех связей сети. Такая конфигурация называется покрывающим деревом - Spanning Tree (иногда ее называют основным деревом), и ее название дало имя всему алгоритму. Алгоритм Spanning Tree описан в стандарте IEEE 802.1D, том же стандарте, который определяет принципы работы прозрачных мостов.
Коммутаторы находят покрывающее дерево адаптивно, с помощью обмена служебными пакетами. Реализация в коммутаторе алгоритма STA очень важна для работы в больших сетях - если коммутатор не поддерживает этот алгоритм, то администратор должен самостоятельно определить, какие порты нужно перевести в заблокированное состояние, чтобы исключить петли. К тому же при отказе какого-либо кабеля, порта или коммутатора администратор должен, во-первых, обнаружить факт отказа, а во-вторых, ликвидировать последствия отказа, переведя резервную связь в рабочий режим путем активизации некоторых портов. При поддержке коммутаторами сети протокола Spanning Tree отказы обнаруживаются автоматически, за счет постоянного тестирования связности сети служебными пакетами. После обнаружения потери связности протокол строит новое покрывающее дерево, если это возможно, и сеть автоматически восстанавливает работоспособность. Алгоритм Spanning Tree определяет активную конфигурацию сети за три этапа.
Сначала в сети определяется корневой коммутатор (root switch), от которого строится дерево. Корневой коммутатор может быть выбран автоматически или назначен администратором. При автоматическом выборе корневым становится коммутатор с меньшим значением МАС-адреса его блока управления.
Затем, на втором этапе, для каждого коммутатора определяется корневой порт(root port) - это порт, который имеет по сети кратчайшее расстояние до корневого коммутатора (точнее, до любого из портов корневого коммутатора).
И наконец, на третьем этапе для каждого сегмента сети выбирается так называемый назначенный порт (designated port) - это порт, который имеет кратчайшее расстояние от данного сегмента до корневого коммутатора. После определения корневых и назначенных портов каждый коммутатор блокирует остальные порты, которые не попали в эти два класса портов. Можно математически доказать что при таком выборе активных портов в сети исключаются петли и оставшиеся связи образуют покрывающее дерево (если оно может быть построено при существующих связях в сети). Понятие расстояния играет важную роль в построении покрывающего дерева. Именно по этому критерию выбирается единственный порт, соединяющий каждый коммутатор с корневым коммутатором, и единственный порт, соединяющий каждый сегмент сети с корневым коммутатором.
На рис. 4 показан пример построения конфигурации покрывающего дерева для сети, состоящей из 5 сегментов и 5 коммутаторов. Корневые порты закрашены темным цветом, назначенные порты не закрашены, а заблокированные порты перечеркнуты. В активной конфигурации коммутаторы 2 и 4 не имеют портов, передающих кадры данных, поэтому они закрашены как резервные.
Рис.5 Построение покрывающего дерева по алгоритму STA
Расстояние до корня определяется как суммарное условное время на передачу одного бита данных от порта данного коммутатора до порта корневого коммутатора. При этом считается, что время внутренних передач данных (с порта на порт) коммутатором пренебрежимо мало, а учитывается только время на передачу данных по сегментам сети, соединяющим коммутаторы. Условное время сегмента рассчитывается как время, затрачиваемое на передачу одного бита информации в 10 наносекундных единицах между непосредственно связанными по сегменту сети портами. Так, для сегмента Ethernet это время равно 10 условным единицам, а для сегмента Token Ring 16 Мбит/с - 6,25. (Алгоритм STA не связан с каким-либо определенным стандартом канального уровня, он может применяться к коммутаторам, соединяющим сети различных технологий.)
В приведенном примере предполагается, что все сегменты работают на одной скорости, поэтому они имеют одинаковые условные расстояния, которые поэтому не показаны на рисунке.
Для автоматического определения начальной активной конфигурации дерева все коммутаторы сети после их инициализации начинают периодически обмениваться специальными пакетами, называемыми протокольными блоками данных моста - BPDU (Bridge Protocol Data Unit), что отражает факт первоначальной разработки алгоритма STA для мостов.
2 Специальная часть
2.1 Структуризация LAN с помощью мостов
2.1.1 Принципы работы мостов
Прозрачные мосты
Прозрачные мосты незаметны для сетевых адаптеров конечных узлов, так как они строят специальную адресную таблицу, на основании которой можно, передавать пришедший кадр в какой-либо другой сегмент или нет. Сетевые адаптеры при использовании прозрачных мостов работают точно так же, как и в случае их отсутствия, то есть не предпринимают никаких дополнительных действий, чтобы кадр прошел через мост. Алгоритм прозрачного моста не зависит от технологии локальной сети, в которой устанавливается мост, поэтому прозрачные мосты Ethernet работают точно так же, как прозрачные мосты FDDI. Прозрачный мост строит свою адресную таблицу на основании пассивного наблюдения за трафиком, циркулирующим в подключенных к его портам сегментах. При этом мост учитывает адреса источников кадров данных, поступающих на порты моста. По адресу источника кадра мост делает вывод о принадлежности этого хоста тому или иному сегменту сети. На рис.7 проиллюстрирован процесс работы прозрачного моста.
Второй метод, использующийся для повышения отказоустойчивости компьютерной сети, это Spanning Tree Protocol. Разработанный достаточно давно, в 1983 г., он до сих пор остается актуальным. В сетях Ethernet, коммутаторы поддерживают только древовидные, т. е. не содержащие петель связи. Это означает, что для организации альтернативных каналов требуются особые протоколы и технологии, выходящие за рамки базовых, к которым относится Ethernet.
Можно положиться на сетевого администратора, который должен исключить возможность образования петель в сети, но такое решение крайне нежелательно. Даже если администратор имеет время и желание для предотвращения таких вещей, он не застрахован от ошибок. Используя алгоритм покрывающего дерева, администратор сети может не заботиться о возникновении петель, мосты сами об этом позаботятся. Алгоритм Spanning Tree (STA) позволяет коммутаторам автоматически определять древовидную конфигурацию связей в сети при произвольном соединения портов между собой. Коммутаторы, поддерживающие протокол STP автоматически создают древовидную конфигурацию связей без петель в компьютерной сети. Такая конфигурация называется покрывающим деревом - Spanning Tree (иногда ее называют остовным деревом). Конфигурация покрывающего дерева строится коммутаторами автоматически с использованием обмена служебными пакетами.
Рассмотрим подробно работу протокола STP:
1. Для построения древовидной структуры сети без петель в сети должен быть определен корневой коммутатор (root switch), от которого и строится это дерево. В качестве корневого коммутатора выбирается коммутатор с наименьшим значением идентификатора. Идентификатор коммутатора - это число длиной восемь байт, шесть младших байтов которого составляет МАС-адрес его блока управления, а два старших байта конфигурируются вручную. Это позволяет администратору сети влиять на процесс выбора корневого коммутатора. Если администратор не вмешается в этот процесс, корневой коммутатор будет выбран случайным образом - им станет устройство с минимальным MAC-адресом блока управления. Такой выбор может оказаться далеко не рациональным. Поэтому следует выбрать корневой коммутатор, исходя из имеющейся топологии сети, и назначить ему вручную наименьший идентификатор. При автоматическом выборе корневым становится коммутатор с меньшим значением МАС-адреса его блока управления.
2. Далее, для каждого коммутатора определяется корневой порт (root port) - это порт, который имеет по сети кратчайшее расстояние до корневого коммутатора. Он у каждого коммутатора только один!
3. После этого для каждого сегмента сети просчитывается кратчайший путь к корневому коммутатору. Коммутатор, через который проходит этот путь, становиться назначенным для этой сети (Designated Bridge). Непосредственно подключенный к сети порт коммутатора – назначенным портом. Назначенный порт сегмента имеет наименьшее расстояние до корневого моста, среди всех портов, подключенных к данному сегменту.
