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

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

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

• Широковещательные штормы – широковещательные кадры будут бесконечно передаваться по сетям с петлями, используя всю доступную полосу пропускания сети и блокируя передачу других кадров во всех сегментах.

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

Для решения этих проблем и был разработан протокол связующего дерева.

Алгоритм Spanning Tree (STA) позволяет коммутаторам автоматически определять древовидную конфигурацию связей в сети при произвольном соединении портов между собой.

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

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

Пакеты BPDU содержат основную информацию, необходимую для построения топологии сети без петель:

• Идентификатор коммутатора, на основании которого выбирается корневой коммутатор

• Расстояние от коммутатора-источника до корневого коммутатора (стоимость корневого маршрута)

• Идентификатор порта

Пакеты BPDU помещаются в поле данных кадров канального уровня, например, кадров Ethernet. Коммутаторы обмениваются BPDU через равные интервалы времени (обычно 1-4с). В случае отказа коммутатора (что приводит к изменению топологии) соседние коммутаторы, не получив пакет BPDU в течение заданного времени, начинают пересчет связующего дерева.

Современные коммутаторы также поддерживают протокол Rapid STP (IEEE 802.1w), который обладает лучшим временем сходимости по сравнению с STP (меньше 1 секунды). 802.1w обратно совместим с 802.1d.

Сравнение протоколов STP 802.1d и RSTP 802.1w.