Алгоритм связующего дерева (Spanning-Tree Algoritm) (STA)

Алгоритм был разработан для того, чтобы сохранить преимущества петель, устранив их проблемы. Первоначально алгоритм был документирован корпорацией Digital - основным поставщиком Ethernet. Новый алгоритм, разработанный Digital, был впоследствии пересмотрен комитетом IEEE 802 и опубликован в спецификации IEE 802. 1d в качестве алгоритма STA.

STA предусматривает свободное от петель подмножество топологии сети путем размещения таких мостов, которые, если они включены, то образуют петли в резервном (блокирующем) состоянии. Порты блокирующего моста могут быть активированы в случае отказа основного канала, обеспечивая новый тракт через об'единенную сеть.

STA пользуются выводом из теории графов в качестве базиса для построения свободного от петель подмножества топологии сети. Теория графов утверждает следующее:

Для любого подсоединенного графа, состоящего из узлов и ребер, соединяющих пары узлов, существует связующее дерево из ребер, которое поддерживает связность данного графа, но не содержит петель.

Рис. 29-3 поясняет, каким образом STA устраняет петли. STA требует, чтобы каждому мосту был назначен уникальный идентификатор. Обычно этот идентификатор является одним из адресов МАС данного моста, который дополнен приоритетом. Каждому порту во всех мостах также назначается уникальный (в пределах этого моста) идентификатор (как правило, его собственный адрес МАС). И наконец, каждый порт моста взаимосвязан с затратами какого-нибудь тракта. Затраты тракта представляют собой затраты на передачу какого-нибудь блока данных в одну из локальных сетей через этот порт. На Рис. 29-3 "Сеть ТВ до прогона STA" затраты трактов отмечены на линиях, исходящих из каждого моста. Затраты трактов обычно устaнaвливаются по умолчанию, но могут быть назначены вручную администраторами сети.

Первым шагом при вычислении связующего дерева является выбор корневого моста (root bridge), который представляет собой мост с наименьшим значением идентификатора моста. На Рис. 29-3 корневым мостом является Мост 1. Далее определяется корневой порт (root port) во всех остальных мостах. Корневой порт моста - это порт, через который можно попасть в корневой мост с наименьшими комбинированными затратами тракта. Эта величина (т.е. наименьшие комбинированные затраты тракта до корневого моста) называется затратами корневого тракта (root path cost).

И наконец, определяются назначенные мосты (designated bridges) и их назначенные порты (designated ports). Назначенный мост - это тот мост каждой локальной сети, который обеспечивает минимальные затраты корневого тракта. Назначенный мост локальной сети является единственным мостом, который позволяет продвигать блоки данных в ту локальную сеть (и из нее), для которой этот мост является назначенным. Назначенный порт локальной сети - это тот порт, который соединяет ее с назначенным мостом.

В некоторых случаях два или более мостов могут иметь одинаковые затраты корневого тракта. Например, на Рис. 29-3 как Мост 4, так и Мост 5 могут достичь Мост 1 (корневой мост) с затратами тракта 10. В этом случае снова используются идентификаторы моста, на этот раз для определения назначеных мостов. При выборе предпочтение отдано порту LAN V Моста 4 перед портом LAN V Моста 5.

При использовании этого процесса устраняются все мосты, непосредственно соединенные с каждой LAN, кроме одного; таким образом, удаляются все петли между двумя LAN. STA также устраняет петли, включающие более двух LAN, в то же время сохраняя связность. На Рис. 29-4 "Сеть ТВ после прогона STA" показаны результаты действия STA в сети, изображенной на Рис. 29-3. На Рис. 29-4 более четко показана топология дерева. Сравнение этого рисунка с рисунком сети до прогона STA показывает, что STA перевел в режим резерва как порты Моста 3 в LAN V, так и порты Moста 5 в LAN V.

Расчет связующего дерева имеет место при подаче питания на мост и во всех случаях обнаружения изменения топологии. Для расчета необходима связь между мостами связующего дерева, которая осуществляется через сообщения конфигурации (иногда называемые протокольными информационными единицами моста - bridge protocol data units, или BPDU). Сообщения конфигурации содержат информацию, идентифицирующую тот мост, который считается корневым (т.е. идентификатор корневого моста), и расстояние от моста-отправителя до корневого моста (затраты корневого тракта). Сообщения конфигурации также содержат идентификаторы моста и порта моста-отправителя, а также возраст информации, содержащейся в сообщении конфигурации.

Мосты обмениваются сообщениями конфигурации через регулярные интервалы времени (обычно 1-4 сек.). Если какой-нибудь мост отказывает (вызывая изменение в топологии), то соседние мосты вскоре обнаруживают отсутствие сообщений конфигурации и инициируют пересчет связующего дерева.

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