Spanning Tree Protocol (IEEE 802.1d)
Второй метод, использующийся для повышения отказоустойчивости компьютерной сети, это Spanning Tree Protocol. Разработанный достаточно давно, в 1983 г., он до сих пор остается актуальным. В сетях Ethernet, коммутаторы поддерживают только древовидные связи, т.е. которые не содержат петель. Это означает, что для организации альтернативных каналов требуются особые протоколы и технологии, выходящие за рамки базовых, к которым относится Ethernet.
Алгоритм Spanning Tree (STA) позволяет коммутаторам автоматически определять древовидную конфигурацию связей в сети при произвольном соединения портов между собой.
Коммутаторы, поддерживающие протокол STP автоматически создают древовидную конфигурацию связей без петель в компьютерной сети. Такая конфигурация называется покрывающим деревом - Spanning Tree (иногда ее называют остовым деревом). Конфигурация покрывающего дерева строится коммутаторами автоматически с использованием обмена служебными пакетами
Рассмотрим подробно работу протокола STP.
Алгоритм STA требует, чтобы каждому мосту был присвоен идентификатор. Идентификатор моста– 8-байтное поле, которое состоит из 2-х частей: 2-байтного приоритета, назначенного администратором и 6 байтного МАС-адреса его блока управления. Каждому порту также назначается уникальный идентификатор в пределах моста, как правило, это его МАС-адрес. Каждому порту моста ставится в соответствие стоимость маршрута, соответствующая затратам на передачу кадра по локальной сети через данный порт.
Процесс вычисления связующего дерева начинается с выбора корневого моста (root switch), от которого будет строиться дерево. В качестве корневого моста выбирается коммутатор с наименьшим значением идентификатора. Иногда, такой выбор может оказаться далеко не рациональным. Для того чтобы в качестве корневого моста было выбрано определенное устройство (исходя из структуры сети), администратор может повлиять на процесс выборов, присвоив соответствующему коммутатору наименьший идентификатор вручную.
Второй этап работы STP – выбор корневого порта (root port) для каждого из остальных коммутаторов сети.
Корневой порт коммутатора – это порт, который имеет по сети кратчайшее расстояние до корневого коммутатора.
Третий шаг работы STP – определение назначенных портов.
Каждый сегмент в коммутируемой сети имеет один назначенный порт (designated port). Этот порт функционирует как единственный порт моста, т.е. принимает пакеты от сегмента и передает их в направлении корневого моста через корневой порт данного коммутатора. Коммутатор, содержащий назначенный порт для данного сегмента называется назначенным мостом (designated bridge) этого сегмента.Назначенный порт сегмента имеет наименьшее расстояние до корневого моста, среди всех портов, подключенных к данному сегменту. Назначенный порт у сегмента может быть только один. У корневого моста все порты являются назначенными, а их расстояние до корня полагается равным нулю. Корневого порта у корневого моста нет.
При построении покрывающего дерева важную роль играет понятие расстояния. По этому критерию выбирается единственный порт, соединяющий каждый коммутатор с корневым коммутатором, и единственный порт, соединяющий каждый сегмент сети с корневым коммутатором. Все остальные порты переводятся в резервное состояние, то есть такое, при котором они не передают обычные кадры данных. При таком выборе активных портов в сети исключаются петли и оставшиеся связи образуют покрывающее дерево.
В качестве расстояния в STA используется метрика стоимость пути (Path Cost) – она определяется как суммарное условное время на передачу данных от порта данного коммутатора до порта корневого коммутатора Условное время сегмента рассчитывается как время передачи одного бита информации и измеряется в 10-наносекундных единицах. Так, для сегмента Ethernet на 10 Мбит/с условное время равно 10 условным единицам.
Вычисление связующего дерева происходит при включении коммутатора и при изменении топологии. Эти вычисления требуют периодического обмена информацией между коммутаторами связующего дерева, что достигается при помощи специальных пакетов, называемых блоками данных протокола моста - BPDU (Bridge Protocol Data Unit).
Пакеты BPDU содержат основную информацию, необходимую для построения топологии сети без петель:
· Идентификатор коммутатора, на основании которого выбирается корневой коммутатор
· Расстояние от коммутатора-источника до корневого коммутатора (стоимость корневого маршрута)
· Идентификатор порта
Пакеты BPDU помещаются в поле данных кадров канального уровня, например, кадров Ethernet.
Коммутаторы обмениваются BPDU через равные интервалы времени (обычно 1-4с). В случае отказа моста (что приводит к изменению топологии) соседние коммутаторы, не получив 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 уведомления о реконфигурации отсутствуют все поля, кроме двух первых.
Пример работы STP
Для примера рассмотрены 3 коммутатора, подключенные с образованием петли. Т.о., в сети могут возникнуть проблемы с зацикливанием пакетов. Например, пусть какой-либо компьютер в сети LAN1 посылает широковещательный пакет. В соответствии с логикой работы коммутаторов, коммутатор А передаст этот пакет во все подключенные к нему сегменты, за исключением того, из которого он пришел. Коммутатор B получит этот пакет и передаст его коммутатору С. Коммутатор С, также получит широковещательный пакет от коммутатора А и передаст его коммутатору В. Тот в свою очередь, вернет его коммутатору A и так далее. Т.е., пакеты могут ходить по сети бесконечно долго, что может привести к нарушению работоспособности сети. В этом примере с помощью STP блокируется соединение между коммутаторами С и B.
Рисунок. Перед применением Spanning Tree.
Итак, после включения питания и загрузки каждый коммутатор начинает считать себя корневым. Когда он генерирует BPDU (через интервал hello), он помещает свой идентификатор в поле «идентификатор корневого коммутатора», расстояние до корня устанавливается в 0, а в качестве идентификатора порта указывается идентификатор того порта, через который будет передаваться BPDU.
Как только коммутатор получает BPDU, в котором имеется идентификатор корневого коммутатора, меньше его собственного, он перестает генерировать свои собственные кадры BPDU, и начинает ретранслировать только кадры нового претендента на звание корневого коммутатора. При ретрансляции кадров он наращивает расстояние до корня, указанное в пришедшем BPDU, на условное время сегмента, через который принят данный кадр.
При ретрансляции кадров каждый коммутатор для каждого своего порта запоминает минимальное расстояние до корня. При завершении процедуры установления конфигурации покрывающего дерева, каждый коммутатор находит свой корневой порт - это порт, который ближе других портов находится по отношению к корню дерева.
Когда коммутатор A (корневой мост) посылает BPDU’s, они содержат стоимость пути к корневому мосту равную 0. Когда коммутатор B получает эти BPDU, он добавляет стоимость пути Port 1 (4) к стоимости, указанной в полученном BPDU (0). Коммутатор B затем использует значение 4 и посылает BPDU’s со стоимостью пути к корню равной 4 через Port 3 и Port 2.
Когда коммутатор C получает BPDU от коммутатора B, он увеличивает стоимость пути к корню до 23 (4 + 19). Однако коммутатор C также получает BPDU от корневого коммутатора А через Port 1. Стоимость пути к корню в этом BPDU равна 0 и коммутатор C увеличивает ее стоимость до 4 (стоимость его Port 1 равна 4). Теперь коммутатор C должен выбрать единственный корневой порт. Коммутатор C выбирает Port 1 в качестве корневого, поскольку его стоимость пути к корню меньше. После этого коммутатор C начинает объявлять стоимость пути до корня равную 4 нижележащим коммутаторам.
Выборы корневого порта коммутатора В происходят аналогично.
Рисунок. После применения Spanning Tree.
Кроме этого, коммутаторы выбирают для каждого сегмента сети назначенный порт. Для этого они исключают из рассмотрения свой корневой порт, а для всех своих оставшихся портов сравнивают принятые по ним минимальные расстояния до корня с расстоянием до корня своего корневого порта. Если у своего порта это расстояние меньше принятых, то это значит, что он является назначенным портом. Все порты, кроме назначенных переводятся в заблокированное состояние и на этом построение покрывающего дерева заканчивается.
Когда имеется несколько портов с одинаковым кратчайшим расстоянием до корневого коммутатора, выбирается порт с наименьшим идентификатором.
На коммутаторе В назначенным портом становится Port 2. Он имеет наименьшую стоимость пути к корню (19) по сравнению с Port 3 (23). Port 3 на коммутаторе В блокируется. На коммутаторе С назначенным портом становится Port 3 (стоимость пути равна 19), Port 2 –блокируется.
Таким образом, в процессе построения топологии сети каждый порт коммутатора проходит несколько стадий:
· Blocking- При инициализации коммутатора все порты (за исключением отключенных) автоматически переводятся в состояние «Заблокирован». В этом случае порт генерирует, принимает, обрабатывает и ретранслирует только пакеты BPDU. Все остальные пакеты не передаются.
· Listening – В начальный момент работы алгоритма STA порты коммутатора переходят в состояние «Прослушивание». В этот момент пакеты BPDU от других коммутаторов еще не получены и коммутатор считает себя корневым, а все свои порты – назначенными. В том режиме порт может находится до истечения таймера смены состояний (Forwarding Timer). Интервал, выдерживаемый с помощью таймера может изменяться от 4 до 30 с. и нужен он для получения BPDU от всех коммутаторов сети. В этом режиме порт продолжает генерировать, принимать, обрабатывать и ретранслировать BPDU. Если в течение этого времени порт получит BPDU с лучшими параметрами, чем собственные (расстояние, идентификатор коммутатора или порта), то он перейдет в состояние «Заблокирован». В противном случае порт переводится в состояние «Обучение».
· Learning – Обучение – порт начинает принимать пакеты и на основе адресов источника строить таблицу коммутации. Порт в этом состоянии все еще не продвигает пакеты. Порт продолжает участвовать в работе алгоритма STA, и при поступлении BPDU с лучшими параметрами переходит в состояние Blocking «Заблокирован».
· Forwarding – Продвижение - только после двукратной выдержки по таймеру порт переходит в состояние Продвижение и обрабатывает пакеты данных в соответствии с построенной таблицей
· Disable – Отключен – в это состояние порт переводит администратор. Отключенный порт не участвует ни в работе протокола STP, ни в продвижении пакетов данных. Порт можно также вручную включить и он сначала перейдет в состояние Blocking.
В процессе нормальной работы корневой коммутатор продолжает генерировать служебные пакеты BPDU, а остальные коммутаторы продолжают их принимать своими корневыми портами и ретранслировать назначенными. Если по истечении максимального времени жизни сообщения (по умолчанию — 20 с) корневой порт любого коммутатора сети не получит служебный пакет BPDU, то он инициализирует новую процедуру построения покрывающего дерева. При этом на все порты генерируется и передается BPDU, в котором коммутатор указывает себя в качестве корневого.
Коммутаторы D-Link также поддерживают протокол Rapid STP (IEEE 802.1w), который обладает лучшим временем сходимости по сравнению с STP (меньше 1 секунды). 802.1w обратно совместим с 802.1d.