Материал просмотрен 3,950 раз(а)

Что такое алгоритм покрывающего дерева (Spanning Tree)

Для нормальной работы необходимо отсутствие в сетевой архитектуре петель. В маленьких сетях этого не так уж сложно добиться, но в больших сетях необходимо наличие резервных линий связи для повышения надёжности работы сети. А было бы просто прекрасно, если обнаружение вышедших из строя связей происходило автоматически.

Для этих целей был разработан специальный протокол взаимодействия коммутаторов. Закрепившийся в стандарте 802.1D, этот протокол получил название Spanning Tree Algorithm (STA) – алгоритм покрывающего дерева.

Суть алгоритма в том, что в сети создаются резервные связи. Коммутаторы на основе обмена служебными пакетами изучают топологию сети и выбирают оптимальную древовидную конфигурацию сети. Резервные связи, образующие петли, отключаются, путём блокирования соответствующих портов коммутатора. Таким образом, активные петли отсутствуют, и сеть имеет нормальную древовидную архитектуру.

Кроме этого, сеть постоянно тестируется служебными пакетами. Если обнаруживается потерянная связь, то коммутаторы начинают строить оптимальную конфигурацию заново.

Этапы построения оптимальной конфигурации:

  1. Определяется корневой коммутатор (Root Bridge), от которого будет строиться дерево. Корневой коммутатор выбирается на основе наименьшего значения параметра Bridge Identifier, который является комбинацией уникального MAC-адреса устройства и устанавливаемого для устройства приоритета.
  2. Для каждого коммутатора определяется корневой порт (Root Port), имеющий кратчайшее расстояние (Root path cost) до корневого коммутатора.
  3. Определяются порты, через которые подключены другие коммутаторы по кратчайшему пути.
  4. Все остальные порты блокируются.

Конечная стадия работы Spanning Tree Algorythm:

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

2. Root Bridge периодически посылает во все свои порты пакеты с BPDU. Интервал времени, через который происходит посылка, называется Hello Time.

3. В каждом сегменте сети имеется единственный Designated Bridge Port – порт, через который проходит обмен трафиком с Root Bridge. Этот порт имеет наименьшее значение Root Path Cost по сравнению с другими портами в сегменте, либо меньший bridge ID.

4. BPDU принимаются и отправляются STP-совместимым устройством на всех его портах, даже на тех, которые были “выключены” работой STP. Однако BPDU не принимаются на портах, которые были “выключены” администратором.

5. Каждый мост осуществляет пересылку (forwarding) пакетов только между Root Port и портами, которые являются Designated Bridge Port для соответствующего сегмента. Все остальные порты находятся в состоянии “Blocking”.

Для построения алгоритма и тестирования целостности дерева используется специальный пакет данных Bridge Protocol Data Unit (BPDU) – протокол блока данных моста.

Структура пакета BPDU.

Описание

Октеты

Идентификатор протокола 1-2
Идентификатор версии протокола 3
Тип BPDU 4
Флаги 5
Корневой идентификатор 6-13
Стоимость корневого пути 14-17
Идентификатор моста 18-25
Идентификатор порта 26-27
Возраст сообщения 28-29
Максимальный возраст 30-31
Время приветствия 32-33
Задержка рассылки 34-35

Идентификатор протокола – Указывает на алгоритм и протокол Spanning Tree.

Идентификатор версии протокола – Указывает версию протокола.

Тип BPDU – Указывает тип BPDU:

  • 00000000 конфигурация;
  • 10000000 уведомление об изменении топологии.

Для последнего типа последующие поля отсутствуют.

Флаги

Бит 1 является флагом изменения топологии (Topology Change).

Бит 8 является флагом Topology Change Acknowledgement (подтверждение смены топологии).

Корневой идентификатор

Стоимость корневого пути – Беззнаковое целое число, кратное используемой единице стоимости (произвольное значение).

Идентификатор моста – Беззнаковое целое число, используемое для установки уровня приоритета моста (меньшее число указывает на мост с более высоким приоритетом).

Идентификатор порта – Беззнаковое целое число, используемое для установки уровня приоритета порта (меньшее число указывает на порт с более высоким приоритетом).

Возраст сообщения, Максимальный возраст, Время приветствия, Задержка рассылки – Эти 4 таймера задаются 2-байтовыми значениями. Каждое из полей представляет беззнаковое целое число. Единицей измерения для таймеров служит 1/256 доля секунды. Таким образом время может задаваться в диапазоне от 0 до 256 секунд.

P.S. Многие данные взяты из замечательной книжки:

OZON.ru – Книги | Сеть на LINUX. Проектирование, прокладка, эксплуатация | Алексей Старовойтов | Купить книги: интернет-магазин / ISBN 5-94157-687-0