Алгоритм Spanning Tree

Алгоритм покрывающего дерева — Spanning Tree Algorithm (STA) позволяет мостам автоматически определять древовидную конфигурацию связей в сети при произвольном соединения портов между собой.

Алгоритм Spanning Tree определяет активную конфигурацию сети за три этапа.

· Сначала в сети определяется корневой мост (root switch), от которого строится дерево. Корневой мост может быть выбран автоматически или назначен администратором. При автоматическом выборе корневым становится мост с меньшим значением МАС-адреса его блока управления.

· Затем, на втором этапе, для каждого моста определяется корневой порт (root port) — это порт, который имеет по сети кратчайшее расстояние до кор­невого моста (точнее, до любого из портов корневого моста).

· На третьем этапе для каждого сегмента сети выбирается так называемый назначенный порт (designated port) — это порт, который имеет кратчайшее
расстояние от данного сегмента до корневого моста.

После определения корневых и назначенных портов каждый мост блокирует остальные порты, которые не попали в эти два класса портов.

Понятие расстояния играет важную роль в построении покрывающего дерева. Именно по этому критерию выбирается единственный порт, соединяющий каж­дый мост с корневым мостом, и единственный порт, соединяющий каждый сегмент сети с корневым мостом.

На рис.2.17 показан пример построения конфигурации покрывающего дерева для сети, состоящей из 5 сегментов и 5 мостов. Корневые порты закрашены темным цветом, назначенные порты не закрашены, а заблокированные порты пере­черкнуты. В активной конфигурации мосты 2 и 4 не имеют портов, переда­ющих кадры данных, поэтому они закрашены как резервные.

Рис.2.17. Построение покрывающего дерева сети по алгоритму STA

Расстояние до корня определяется как суммарное условное время на передачу одного бита данных от порта данного моста до порта корневого моста. При этом считается, что время внутренних передач данных (с порта на порт) мостом пренебрежимо мало, а учитывается только время на передачу дан­ных по сегментам сети, соединяющим мосты. Условное время сегмента рас­считывается как время, затрачиваемое на передачу одного бита информации в 10 наносекундных единицах между непосредственно связанными по сегменту сети портами. Так, для сегмента Ethernet это время равно 10 условным единицам, а для сегмента Token Ring 16 Мбит/с — 6,25. (Алгоритм STA не связан с каким-либо определенным стандартом канального уровня, он может применяться к мостам, соединяющим сети различных технологий.)

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

Для автоматического определения начальной активной конфигурации дерева все мосты сети после их инициализации начинают периодически обмени­ваться специальными пакетами, называемыми протокольными блоками данных мо­ста — BPDU (Bridge Protocol Data Unit), что отражает факт первоначальной разработки алгоритма STA для мостов.

Пакеты BPDU помещаются в поле данных кадров канального уровня, напри­мер кадров Ethernet или FDDI. Желательно, чтобы все мосты поддерживали общий групповой адрес, с помощью которого кадры, содержащие пакеты BPDU, моли бы одновременно передаваться всем мостам сети. Иначе пакеты BPDU «ссылаются широковещательно.

Идентификаторы мостов состоят из 8 байт, причем младшие 6 являются МАС-адресом блока управления моста. Старшие 2 байта в исходном состо­янии заполнены нулями, но администратор может изменить значение этих байтов, тем самым назначив определенный мост корневым.

После инициализации каждый мост сначала считает себя корневым. Поэтому он начинает через интервал hello генерировать через все свои порты сооб­щения BPDU конфигурационного типа. В них он указывает свой идентификатор в качестве идентификатора корневого моста (и в качестве идентификатора данного моста также), расстояние до корня устанавливается в 0, а в каче­стве идентификатора порта указывается идентификатор того порта, через который передается BPDU. Как только мост получает BPDU, в котором имеется идентификатор корневого моста, со значением, меньшим его собственного, он перестает генерировать свои собственные кадры BPDU, а начинает ретрансли­ровать только кадры нового претендента на звание корневого моста. На рис. у моста 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 конфигурационного типа, в результате чего устанавливается новая активная конфигурация.