6.5 Протокол покрывающего дерева

«Прозрачность» мостов позволяет создавать составные сети древовидной топологии. Это означает, что между любыми двумя узлами сети должен существовать единственный путь. Множе­ство путей между двумя узлами образует петли, которые являются источниками широковещательных штормов. Сеть с петлями может работать только с мостами, поддерживающими алгоритм маршрутизации от источника. Такие мосты реализуют алгоритм построения покрывающего дерева (spanning tree algorithm - STA). Фактически это алгоритм усечения, с помощью которого сеть с петлями преобразуется в сеть без петель. Алгоритм STA позволяет строить на основе множества линий связи сеть древовидной структуры, в которой связи, образующие дерево, являются основными, а остальные - резервными. Алгоритм STА и протокол взаимо­действия мостов описаны в спецификации IEEE 802.ID.

Мосты определяют покрывающее дерево с помощью обмена служебными пакетами. Для этого в сети определяется корневой мост, от которого строится все дерево. Мост может быть выбран автоматически или назначен администратором. При автоматическом выборе, корневым становится мост с наименьшим значением МАС-адреса. Для каждого моста определяется корневой порт, который имеет кратчайшее расстояние до корневого моста. Для каждого сегмента сети выбирается порт назначения, который имеет кратчайшее расстояние от данного сегмента до корневого моста.

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

Для идентификации, каждый мост, поддерживающий алгоритм STA, имеет уникальный идентификатор, состоящий из двух частей. Младшую часть составляет MAC-адрес моста длиной 6 байт. Старшая часть, длиной 2 байта, содержит приоритет моста, заданный администратором сети. Идентификатор моста играет определяющую роль при выборе корневого моста. Порты внутри моста также имеют свои идентификаторы. Идентификатор порта длиной 2 байта, содержит, назначенный администратором приоритет порта, и порядковый номер порта для данного моста.

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

1. Идентификатор версии протокола;

2. Тип блока данных;

3. Флаг;

4. Идентификатор корневого моста;

5. Расстояние до корневого моста;

6. Идентификатор моста;

7. Идентификатор порта;

8. Время жизни блока;

9. Максимальное время жизни сообщения;

10. Интервал «hello», через который посылаются блоки BPDU;

11. Минимальное время перехода портов в активное состояние.

После инициализации мост сначала считает себя корневым. Поэтому он начинает через интервал «hello» генерировать на все свои порты блоки BPDU конфигурационного типа. В них он указывает свой идентификатор в качестве идентификатора корневого моста, а расстояние до корня устанавливается в нуль. В качестве идентификатора порта указывается идентификатор того порта, через который передается блок BPDU. Если мост получает блок BPDU, в котором имеется идентификатор корневого моста, меньше его собственного, он перестает генерировать свои кадры BPDU, а начинает только ретранслировать кадры нового корневого моста. При этом он увеличивает расстояние до корня, указанное в пришедшем блоке BPDU, на условное время передачи кадра по сегменту от которого был принят кадр. Также при ретрансляции кадров, мост для каждого своего порта запоминает минимальное расстояние до корня, встретившееся во всех принятых этим портом кадрах BPDU. По завершении процедуры конфигурирования покрывающего дерева, мост находит свой корневой порт, который наиболее близок к корню дерева.

Затем мосты выбирают для каждого сегмента сети назначенный порт. Для этого они исключают из рассмотрения свой корневой порт, а для всех остальных портов сравнивают принятые по ним минимальные расстояния до корня с расстоянием до корня своего корневого порта. Если у своего порта это расстояние меньше, чем в принятых блоках, то это значит, что он является портом назначения. Тогда все остальные порты переводятся в заблокированное состояние и построение покрывающего дерева заканчивается.

В процессе работы корневой мост продолжает генерировать служебные кадры, а остальные продолжают их принимать своими корневыми портами и ретранслировать портами назначения. Если у моста нет портов назначения, то он все равно принимает служебные кадры корневым портом. Если по истечении тайм-аута корневой порт не получает служебный кадр, то он инициализирует новую процедуру построения покрывающего дерева.

Мост обрабатывает сообщения BPDU следующим образом. Сначала сравнивает значение идентификатора корневого моста из BPDU с текущим значением идентификатора корневого моста. Если это значение больше текущего значения, то принятый пакет уничтожается, так как он пришел от моста, который не является корневым. Если оно равно текущему значению, то пакет принят от известного корня. Находящееся в пакете расстояние до корня сравнивается с найденным ранее минимальным расстоянием, и если новое значение меньше, то оно переписывается в данную переменную порта. Затем мост наращивает значение поля расстояния на величину условного времени сегмента, по которому пришел пакет, помещает в поле идентификатора моста свой идентификатор и передает этот пакет на все свои порты, кроме того порта, от которого получен пакет. Если же значение идентификатора корневого моста у принятого BPDU меньше текущего, то значит, что обнаружен мост, у которого больше прав претендовать на звание корневого. Его идентификатор фиксируется в специальном поле корневого идентификатора. Затем пакет BPDU обрабатывается таким же образом, как и в предыдущем случае. По мере распространения пакетов BPDU по всей сети, у всех мостов накапливается информация, необходимая для фиксации корневого моста, а также для определения того, какой из портов моста является корневым. После истечения времени установления активной конфигурации, у всех мостов происходит фиксация идентификатора корневого моста. Все порты корневого моста устанавливаются в состояние – «порт назначения».

Алгоритм обеспечивает поддержку резервных связей в сети, и включает процедуру изменения конфигурации при отказах элементов сети. Эта процедура называется процедурой изменения топологии. После установления активной топологии только корневой мост продолжает периодически генерировать пакеты BPDU конфигурационного типа. Остальные мосты продолжают принимать пакеты BPDU на свой корневой порт и распространяют их через свои порты назначения.

Для того чтобы мосты могли обнаружить отказ элемента сети, каждый из них имеет таймер возраста сообщения. При получении пакета BPDU этот таймер устанавливается в исходное состояние. Если какой-либо назначенный мост, его порт или линия связи отказывают, то пакеты BPDU перестают поступать в мосты, которые находятся в поддеревьях отказавшего элемента. Вследствие этого, в этих мостах истекает интервал таймера возраста сообщения и вызывается процедура «установления назначенных портов». После выполнения этой процедуры, аналогичной начальному выбору корневого порта и портов назначения, будут определены новые значения назначенных мостов, корневых портов и портов назначения. Если же отказал корневой мост, то будет выбран новый корневой мост.

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