Spanning Tree Protocol ( STP , протокол остовного дерева ) — канальный протокол. Основной задачей STP является устранение петель в топологии произвольной сети Ethernet , в которой есть один или более сетевых мостов , связанных избыточными соединениями. STP решает эту задачу, автоматически блокируя соединения, которые в данный момент для полной связности коммутаторов являются избыточными.

Необходимость устранения топологических петель в сети Ethernet следует из того, что их наличие в реальной сети Ethernet с коммутатором с высокой вероятностью приводит к бесконечным повторам передачи одних и тех же кадров Ethernet одним и более коммутатором, отчего пропускная способность сети оказывается почти полностью занятой этими бесполезными повторами; в этих условиях, хотя формально сеть может продолжать работать, на практике её производительность становится настолько низкой, что может выглядеть как полный отказ сети.

STP относится ко второму уровню модели OSI . Протокол описан в стандарте IEEE 802.1D, выработанном рабочей группой IEEE 802.1 по межсетевому взаимодействию. Основан на одноимённом алгоритме , который разработала Радья Перлман ( англ. Radia Perlman ).

Если в сети с мостовыми подключениями (в сегменте сети из коммутаторов) имеется несколько путей, могут образоваться циклические маршруты, и следование простым правилам пересылки данных через мост (коммутатор) приведёт к тому, что один и тот же пакет будет бесконечно передаваться с одного моста на другой (передаваться по кольцу из коммутаторов).

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

Описание

Алгоритм остовного дерева является основой протокола, динамически отключающего избыточные связи в сети стандарта Ethernet (для образования древовидной топологии). STP стандартизован IEEE и поддерживается многими моделями управляемых коммутаторов, в частности, включён по умолчанию на всех коммутаторах Cisco .

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

В коммутаторах Cisco с поддержкой VLAN протокол STP по умолчанию выполняется независимо для каждой виртуальной сети.

Кроме STP, в коммутаторах могут применяться другие методики обнаружения и устранения петель — например, сравнением таблиц коммутации (списков MAC-адресов) разных портов, или сравнением контрольных сумм проходящих пакетов (совпадение указывает на одинаковые пакеты, которые появляются из-за петель). По сравнению с описанными методами, случайным образом (или основываясь на каких-то догадках) блокирующими «дублирующие» порты, протокол STP обеспечивает древовидную структуру всего сегмента, при любом количестве резервных линий между произвольными коммутаторами, поддерживающими STP.

Принцип действия

1. Выбирается один корневой мост ( англ. Root Bridge ).
2. Далее каждый коммутатор просчитывает кратчайший путь к корневому. Соответствующий порт называется корневым портом ( англ. Root Port ). У любого некорневого коммутатора может быть только один корневой порт.
3. После этого для каждого сегмента сети, к которому присоединён более чем один мост (или несколько портов одного моста), просчитывается кратчайший путь к корневому мосту(порту). Мост, через который проходит этот путь, становится назначенным для этой сети ( англ. Designated Bridge ), а соответствующий порт — назначенным портом ( англ. Designated port ).
4. Далее во всех сегментах, с которыми соединено более одного порта моста, все мосты блокируют все порты, не являющиеся корневыми и назначенными. В итоге получается древовидная структура (математический граф ) с вершиной в виде корневого коммутатора.

Основные понятия

• Bridge ID = Bridge priority + MAC;
• Bridge priority = vlan xxx + 4096xN, N-множитель, назначается администратором сети (4096х8=32768 default cost);
• Cost — «стоимость портов»;
• Pathcost — стоимость линка в STP;
• Hello BPDU = root ID + bridge ID + cost; ( англ. Bridge Protocol Data Unit )
• Root port (корневой порт) — это порт, который имеет минимальную стоимость до любого порта корневого коммутатора;
• Designated port (назначенный порт) — это порт, который имеет кратчайшее расстояние от назначенного коммутатора до корневого коммутатора.

Скорость передачи и стоимость пути

Скорость передачи	Стоимость (802.1D-1998)	Стоимость ( 802.1W-2001 )
4 Мбит/с	250	5 000 000
10 Мбит/с	100	2 000 000
16 Мбит/с	62	1 250 000
100 Мбит/с	19	200 000
1 Гбит/с	4	20 000
2 Гбит/с	3	10 000
10 Гбит/с	2	2 000

Важные правила

1. Корневым (root) портом назначается порт с самой низкой стоимостью пути (path cost).
2. Возможны случаи, когда стоимость пути по двум и более портам коммутатора будет одинакова, тогда выбор корневого (root) порта будет происходить на основании полученных от соседей приоритета и порядкового номера порта (Lowest Sender Port ID) , например fa0/1 , fa0/2, fa0/3 и корневым (root) станет порт с наименьшим номером.
3. Коммутаторы, по умолчанию, не измеряют состояние загрузки сети в реальном времени и работают в соответствии со стоимостью (cost) интерфейсов в момент построения дерева STP.
4. Каждый порт имеет свою стоимость (cost), обратно пропорциональную пропускной способности (bandwidth) порта и которую можно настраивать вручную.
5. Все порты в STP последовательно проходят 4 состояния: blocking (прослушивают BPDU без передачи данных), listening (прослушивают и ретранслируют BPDU), learning (получают данные, обновляют MAC-таблицы), forwarding (рабочее состояние порта). С интервалами по умолчанию работа порта (forwarding) начинается через 30 сек.

Алгоритм действия STP (Spanning Tree Protocol)

• После включения коммутаторов в сеть по умолчанию каждый коммутатор считает себя корневым (root).
• Каждый коммутатор начинает посылать по всем портам конфигурационные Hello BPDU пакеты раз в 2 секунды.
• Если мост получает BPDU с идентификатором моста (Bridge ID) меньшим, чем свой собственный, он прекращает генерировать свои BPDU и начинает ретранслировать BPDU с этим идентификатором. Таким образом, в конце концов в этой сети Ethernet остаётся только один мост, который продолжает генерировать и передавать собственные BPDU. Он и становится корневым мостом (root bridge).
• Остальные мосты ретранслируют BPDU корневого моста, добавляя в них собственный идентификатор и увеличивая счётчик стоимости пути (path cost).
• Для каждого сегмента сети, к которому присоединено два и более портов мостов, происходит определение designated port — порта, через который BPDU, приходящие от корневого моста, попадают в этот сегмент.
• После этого все порты в сегментах, к которым присоединено 2 и более портов моста, блокируются за исключением root port и designated port.
• Корневой мост продолжает посылать свои Hello BPDU раз в 2 секунды.

Порты

Каждый порт, задействованный в STP, может работать в одном из следующих режимов (ролей):

• Root Port (корневой) — порт для передачи трафика корневому коммутатору. Каждый некорневой коммутатор имеет только один корневой порт, выбранный из соображений минимальной стоимости пути.
• Designated Port (назначенный) — некорневой порт моста между сегментами сети, принимающий трафик из соответствующего сегмента. Сам мост также называется назначенным. В каждом сегменте сети может быть только один назначенный порт. У корневого коммутатора все порты — назначенные.
• Non-designated Port (неназначенный) — порт, не являющийся корневым, или назначенным. Передача фреймов данных через такой порт запрещена.
• Disabled Port (отключённый) — порт, не участвующий в STP, либо выключенный административно (командой shutdown).

Эволюция и расширения

Rapid Spanning Tree Protocol (RSTP)

Rapid STP (RSTP) является значительным усовершенствованием STP. В первую очередь необходимо отметить уменьшение времени сходимости и более высокую устойчивость. В немалой степени это достигнуто за счет идей, использованных Cisco Systems в качестве проприетарных расширений STP. RSTP описан в стандарте IEEE 802.1w (впоследствии включён в 802.1D-2004).

Rapid STP совместим с STP — если некое устройство использует STP, то RSTP тоже будет использовать STP с этим устройством, но в этом режиме может оказаться, что наличие RSTP на остальных устройствах не дает преимуществ по сравнению с STP.

Per-VLAN Spanning Tree Protocol (PVSTP)

Per-VLAN STP (PVSTP) в соответствии с названием расширяет функциональность STP для использования VLAN . В рамках данного протокола в каждом VLAN работает отдельный экземпляр STP. Является проприетарным расширением Cisco . Изначально протокол PVST работал только через ISL -транки, потом было разработано расширение PVST+, которое позволяло работать через гораздо более распространённые 802.1Q -транки. Существуют реализации, объединяющие свойства PVST+ и RSTP, поскольку эти расширения затрагивают независимые части протокола, в результате получается (в терминологии Cisco) Rapid PVST+. PVST+ совместим с STP и даже коммуницирует «через» коммутаторы, не поддерживающие ни PVST+, ни Rapid PVST+, за счёт использования мультикастовых фреймов. Но Cisco Systems рекомендует не смешивать в одной сети коммутаторы различных производителей, чтобы избежать проблем совместимости разных реализаций и вариаций STP.

Multiple Spanning Tree Protocol (MSTP)

Вышеописанные вариации протоколов STP можно классифицировать по количеству экземпляров STP в случае, когда число VLAN более единицы. Имеются вариации протоколов, у которых на все VLAN приходится единственный экземпляр STP (собственно STP, RSTP), и вариации, у которых каждому VLAN соответствует свой экземпляр STP (PVST, PVST+, Rapid PVST+).

Некоторая избыточность вариаций с отдельным экземпляром STP для каждой VLAN состоит в том, что если топология нескольких VLAN совпадает, то соответствующие им экземпляры STP полностью повторяют работу друг друга. В таком случае в принципе ненужная работа по сути дублирующих друг друга экземпляров STP оборачивается ненужной дополнительной нагрузкой на процессор коммутатора, и в конечном счёте может вынудить конструкторов оборудования для обеспечения его устойчивой работы выбирать более мощный процессор с большим энергопотреблением, что может повлечь за собой дополнительные затраты на электропитание и охлаждение как при изготовлении оборудования, так и эксплуатации.

В этом отношении особняком стоит Multiple STP (MSTP). В один экземпляр MSTP могут входить несколько виртуальных сетей при условии, что их топология одинакова (в смысле входящих в VLAN коммутаторов и соединений между ними). Минимальное количество экземпляров MSTP соответствует количеству топологически уникальных групп VLAN в домене второго уровня (опять же на уровне коммутаторов и соединений между ними). MSTP налагает важное ограничение: все коммутаторы, участвующие в MSTP, должны иметь одинаково сконфигурированные группы VLAN (MST instances), что ограничивает гибкость при изменении конфигурации сети.

MSTP описан в стандарте IEEE 802.1s (впоследствии включён в 802.1Q-2003).

Shortest Path Bridging (SPB)

Shortest Path Bridging (SPB) IEEE 802.1aq преодолевает ограничения блокировки.

История создания

Алгоритм, заложенный в основу STP, был разработан в 1985 году Радией Перлман . Ей дали 1 неделю на разработку алгоритма. Она сделала это за 1 день, а в оставшееся время описала алгоритм в виде стихотворения :

I think that I shall never see
A graph more lovely than a tree.
A tree whose crucial property
Is loop-free connectivity.
A tree that must be sure to span
So packets can reach every LAN.
First, the root must be selected.
By ID, it is elected.
Least-cost paths from root are traced.
In the tree, these paths are placed.
A mesh is made by folks like me,
Then bridges find a spanning tree.

— Radia Joy Perlman

Примечания

Ссылки

• CCNP TSHOOT 642—832 Quick Reference // Brent Steward // Cisco Press 2010 ISBN 1-58714-012-8 (англ.)
• (англ.)
• от 6 июля 2010 на Wayback Machine (англ.)
• от 18 декабря 2008 на Wayback Machine (англ.)