Три этапа построения дерева

На рис. 1 приведен пример сети из стандарта 802.1D-2004, который иллюстрирует работу протокола STP. Мы также будем использовать этот пример в своем описании.

В этом примере сеть построена на восьми коммутаторах, которые имеют идентификаторысо значениями от 111 до 888 (для удобства записи здесь используются сокращенные до 3-х разрядов значения МАС-адресов коммутаторов). Все коммутаторы соединены друг с другом двухточечными связями, которые образуют сегменты A-N. Порты 3 и 4 коммутаторов с 555 по 888 соединены с конечными узлами сети, то есть компьютерами (на рисунке не показаны). Все связи в сети — это связи со скоростью 100 Мбит/с (Fast Ethernet).

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

Первый этап — определение корневого коммутатора, от которого строится дерево. В качестве корневого коммутатора выбирается коммутатор с наименьшим значением идентификатора. В исходном состоянии каждый коммутатор считает себя корневым, поэтому он генерирует и передает своим соседям сообщения Hello, в которых помещает свой идентификатор в качестве идентификатора корневого коммутатора. Как только коммутатор получает от соседа сообщение Hello, в котором содержится идентификатор корневого коммутатора, меньший его собственного, он перестает считать себя корневым коммутатором и генерировать свои сообщения Hello, но начинает ретранслировать сообщения Hello, получаемые от соседей.

Рис. 2. Пример сети, иллюстрирующей работу STP

Если администратор не вмешается в этот процесс, корневой коммутатор выбирается достаточно случайным образом — им станет устройство с минимальным МАС-адресом блока управления. Очевидно, что такой выбор может оказаться далеко не рациональным.

Например, при выборе коммутатора 555 в качестве корневого значительная часть трафика проходила бы через большое количество транзитных сегментов и коммутаторов. Поэтому пускать данный процесс «на самотек» администратору не стоит — лучше в него вмешаться и назначить корневой коммутатор осознанно (путем соответствующего конфигурирования старших байтов идентификаторов коммутатора), чтобы выбранный коммутатор действительно занимал центральное место в соединениях сегментов.

В нашем примере мы предполагаем, что администратор не стал менять приоритеты коммутаторов, так что у всех коммутаторов они остались равными значению 32 768 (значение по умолчанию), й корневым коммутатором стал коммутатор с идентификатором 111.

Второй этап — выбор корневого порта для каждого коммутатора. Корневым портом коммутатора является тот порт, расстояние от которого до корневого коммутатора является минимальным. Сам корневой коммутатор корневых портов не имеет.

Для определения корневого порта каждый коммутатор использует пакеты Hello, ретранслируемые ему другими коммутаторами. На основании этих пакетов каждый коммутатор определяет минимальные расстояния от всех своих портов до корневого коммутатора. При ретрансляции сообщения Hello каждый коммутатор увеличивает указанное в сообщении расстояние до корня на метрику того сегмента, из которого принят данный пакет. Тем самым в пакете Hello по мере прохождения через коммутаторы наращивается поле, показывающее расстояние до корневого коммутатора. Например, если считать, что все сегменты в рассматриваемом примере являются сегментами Ethernet со скоростью 100 Мбит/с, то коммутатор 222, приняв из сегмента А пакет Hello со значением расстояния, равным 0, увеличивает его на 200 000 условных единиц (если коммутатор работает с величинами метрики, рекомендованными версией стандарта STP от 2004 года).

Ретранслируя пакеты, каждый коммутатор для каждого своего порта запоминает минимальное расстояние до корня, встретившееся во всех принятых этим портом пакетах Hello. По завершении процедуры определения конфигурации покрывающего дерева каждый коммутатор находит свой корневой порт (с минимальным расстоянием до корня). При равных метриках для разрешения неоднозначности к процедуре выбора минимального расстояния привлекаются значения идентификаторов коммутаторов и портов. Предпочтение отдается портам и коммутаторам с наименьшими идентификаторами. Например, у коммутатора 222 порты 1 и 2 находятся на одинаковом расстоянии до корневого коммутатора 111 — оба эти порта непосредственно связаны через сегменты АмВс коммутатором 111, а значит, получают пакеты Hello с метрикой, равной 0. Так как идентификатор порта 1 меньше идентификатора порта 2, то корневым портом коммутатора 222 выбирается порт 1. По аналогичной причине корневым портом коммутатора 555 становится порт 1, а не порт 2. Оба эти порта получают сообщения Hello, генерируемые корневым коммутатором 111, с наименьшим значением метрики 200 000. Порт 1 получает такие сообщения по маршруту: порт 1 коммутатора 111 — сегмент С — порт 1 коммутатора 333 — порт 6 коммутатора 333 — сегмент G, соответственно порт 2 получает их по маршруту: порт 3 коммутатора 111 — сегмент Е — порт 1 коммутатора 444 — порт 6 коммутатора 444 — сегмент I.
Третий этап — выбор назначенных коммутаторов и портов для каждого сегмента сети. Назначенным является тот коммутатор (из числа коммутаторов, непосредственно подключенных к данному сегменту), у которого расстояние до корневого моста является минимальным (точнее, расстояние от корневого порта этого коммутатора до корневого коммутатора). Назначенные порты для сегментов исполняют ту же роль, что корневые  порты для коммутаторов — они находятся на кратчайшем пути до корневого коммутатора.

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

В рассматриваемом примере коммутатор 111 при проверке порта 1 обнаруживает, что через этот порт принимаются пакеты с минимальным расстоянием 200 000 (это пакеты от порта 1 коммутатора 222, который ретранслирует через все свои порты сообщения Hello, полученные от коммутатора 1 И, но с измененной метрикой, в частности передает их и коммутатору 111). Так как коммутатор 111 является корневым, то его расстояние до корневого коммутатора равно нулю, то есть меньше, чем у получаемых через порт 1 сообщений. Поэтому коммутатор 1 объявляет свой порт 1 назначенным для сегмента А.

Коммутатор 222 не может объявить свой порт 1 назначенным для сегмента А, так как через него он получает сообщения с минимальной метрикой 0, а у его корневого порта метрика равна 200 000.

На выполнение всех трех этапов коммутаторам сети отводится по умолчанию 15 с. Эта стадия работы портов называется стадией прослушивания (listening), поскольку порты слушают только сообщения BPDU и не передают пользовательских кадров. Считается, что порты находятся в заблокированном состоянии, которое относится только к пользовательским кадрам, в то время как кадры BPDU обрабатываются. Предполагается, что в стадии прослушивания каждый коммутатор получит столько пакетов Hello, сколько потребуется для определения состояния своих портов.

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

Результат работы протокола STP для нашего примера показан на рис. 2. На рисунке корневые порты коммутаторов отмечены символом R, назначенные порты закрашены, а заблокированные зачеркнуты.

После построения покрывающего дерева коммутатор начинает принимать (но не продвигать) пакеты данных и на основе их адресов источника строить таблицу продвижения. Это обычный режим обучения прозрачного моста, который ранее нельзя было активизировать, так как порт не был уверен в том, что он останется корневым или назначенным и будет передавать пакеты данных. Стадия обучения (learning) также выдерживается в течение интервала 15 с. При этом порт продолжает участвовать в работе алгоритма STA, так что поступление пакетов BPDU с лучшими параметрами переводит его в заблокированное состояние.

И только после двукратной выдержки по таймеру порт переходит в стадию продвижения (forwarding) и начинает продвигать пользовательские кадры в соответствии с построенной таблицей (которая продолжает модифицироваться, отражая изменения в структуре сети). Фактически в нашем примере в продвижении пользовательских пакетов после построения активной топологии участвуют только коммутаторы 111,333 и с 555 по 888.

В процессе нормальной работы корневой коммутатор продолжает генерировать пакеты Hello, а остальное коммутаторы получают их через свои корневые порты и ретранслируют через назначенные порты. У коммутатора могут отсутствовать назначенные порты, как у коммутаторов 222 и 444, но он все равно участвует в работе протокола STA, так как корневой порт принимает служебные пакеты BPDU.

Рис. 2. Активная топология, найденная по протоколу STP

Если по истечении максимального времени жизни сообщения (по умолчанию — 10 интервалов Hello, то есть 20 с) корневой порт любого коммутатора сети не получает служебный пакет Hello, то он инициализирует новую процедуру построения покрывающего дерева.

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

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

Использование устаревшей адресной информации может приводить к тому, что некоторое время кадры будут досылаться в неверном направлении и не доходить до адресатов. Для того чтобы сообщить коммутатору о том, что в сети произошло изменение топологии и необходимо удалить старую адресную информацию, по сети распространяются уведомления об изменении конфигурации (это особый тип пакета BPDU).