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

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

Для автоматического выполнения перечисленных действий, то есть нахождения и конфигурирования активной древовидной топологии, мониторинга состояния ее связей и перехода к новой древовидной топологии при обнаружении отказа связи в коммутируемых локальных сетях используются алгоритм покрывающего дерева (Spanning Tree Algorithm, STA) и реализующий его протокол покрывающего дерева (Spanning Tree Protocol, STP).

Алгоритм покрывающего дерева, разработанный достаточно давно, в 1983 году, был признан IEEE удачным решением и включен в ту же спецификацию 802.1D, в котороиописывается и сам алгоритм прозрачного моста. Сегодня протокол STP широко применяется в наиболее массовых устройствах современных локальных сетей — коммутаторах. Протокол STP обновлялся несколько раз, последняя его редакция описана в документе 802.1D-2004; новая версия протокола получила название RSTP (Rapid STP, то есть быстрый протокол покрывающего дерева), так как предыдущие версии STP недостаточно быстро находили новую древовидную топологию — на это могло уйти до 50 секунд. Новая версия протокола покрывающего дерева — RSTP — работает значительно быстрее, затрачивая на поиск новой топологи несколько секунд.