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

Второй метод, использующийся для повышения отказоустойчивости компьютерной сети, это Spanning Tree Protocol. Разработанный достаточно давно, в 1983 г., он до сих пор остается актуальным. В сетях Ethernet, коммутаторы поддерживают только древовидные, т. е. не содержащие петель связи. Это означает, что для организации альтернативных каналов требуются особые протоколы и технологии, выходящие за рамки базовых, к которым относится Ethernet.

Можно положиться на сетевого администратора, который должен исключить возможность образования петель в сети, но такое решение крайне нежелательно. Даже если администратор имеет время и желание для предотвращения таких вещей, он не застрахован от ошибок. Используя алгоритм покрывающего дерева, администратор сети может не заботиться о возникновении петель, мосты сами об этом позаботятся. Алгоритм Spanning Tree (STA) позволяет коммутаторам автоматически определять древовидную конфигурацию связей в сети при произвольном соединения портов между собой. Коммутаторы, поддерживающие протокол STP автоматически создают древовидную конфигурацию связей без петель в компьютерной сети. Такая конфигурация называется покрывающим деревом - Spanning Tree (иногда ее называют остовным деревом). Конфигурация покрывающего дерева строится коммутаторами автоматически с использованием обмена служебными пакетами.

Рассмотрим подробно работу протокола STP:

1. Для построения древовидной структуры сети без петель в сети должен быть определен корневой коммутатор (root switch), от которого и строится это дерево. В качестве корневого коммутатора выбирается коммутатор с наименьшим значением идентификатора. Идентификатор коммутатора - это число длиной восемь байт, шесть младших байтов которого составляет МАС-адрес его блока управления, а два старших байта конфигурируются вручную. Это позволяет администратору сети влиять на процесс выбора корневого коммутатора. Если администратор не вмешается в этот процесс, корневой коммутатор будет выбран случайным образом - им станет устройство с минимальным MAC-адресом блока управления. Такой выбор может оказаться далеко не рациональным. Поэтому следует выбрать корневой коммутатор, исходя из имеющейся топологии сети, и назначить ему вручную наименьший идентификатор. При автоматическом выборе корневым становится коммутатор с меньшим значением МАС-адреса его блока управления.

2. Далее, для каждого коммутатора определяется корневой порт (root port) - это порт, который имеет по сети кратчайшее расстояние до корневого коммутатора. Он у каждого коммутатора только один!

3. После этого для каждого сегмента сети просчитывается кратчайший путь к корневому коммутатору. Коммутатор, через который проходит этот путь, становиться назначенным для этой сети (Designated Bridge). Непосредственно подключенный к сети порт коммутатора – назначенным портом. Назначенный порт сегмента имеет наименьшее расстояние до корневого моста, среди всех портов, подключенных к данному сегменту.

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