STP
Название	Протокол покрывающего дерева
Уровень (помодели OSI)	Канальный
Создан в	1985
Назначение протокола	Устранение петель в топологии сети
Спецификация	RSTP, MSTP, SPB
Медиафайлы на Викискладе

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

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

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

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

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

Алгоритм остовного дерева является основой протокола, динамически отключающего избыточные связи в сети стандарта 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 (назначенный порт) — это порт, который имеет кратчайшее расстояние отназначенного коммутатора до корневого коммутатора.

1. Корневым (root) портом назначается порт с самой низкой стоимостью пути (path cost).
2. Возможны случаи, когда стоимость пути по двум и более портам коммутатора будет одинакова, тогда выбор корневого (root) порта будет происходить на основании полученных от соседей приоритета и порядкового номера порта (Lowest Sender Port ID)^[2], например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 сек.

• После включения коммутаторов в сеть по умолчанию каждый коммутатор считает себя корневым (root).
• Каждый коммутатор начинает посылать по всем портам конфигурационные HelloBPDU пакеты раз в 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 STP (RSTP) является значительным усовершенствованием STP. В первую очередь необходимо отметить уменьшение времени сходимости и более высокую устойчивость. В немалой степени это достигнуто за счет идей, использованных Cisco Systems в качестве проприетарных расширений STP. RSTP описан в стандартеIEEE 802.1w (впоследствии включён в 802.1D-2004).

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

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.

Вышеописанные вариации протоколов 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) преодолевает ограничения блокировки.

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

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 2010ISBN 1-58714-012-8 (англ.)
• IEEE Std 802.1D™- 2004 (англ.)
• IEEE Std 802.1Q™- 2005Архивная копия от 6 июля 2010 наWayback Machine (англ.)
• Understanding Spanning-Tree ProtocolАрхивная копия от 18 декабря 2008 наWayback Machine (англ.)

В статьене хватаетссылок на источники (см.рекомендации по поиску).

Информация должна бытьпроверяема, иначе она может быть удалена. Вы можетеотредактировать статью, добавив ссылки наавторитетные источники в видесносок.(28 февраля 2019)

• Появились в 1985 году
• Протоколы канального уровня
• Остовное дерево
• Топологии компьютерных сетей

• Википедия:Cite web (не указан язык)
• Википедия:Статьи с нерабочими ссылками
• ПРО:ИТ:Статьи по алфавиту
• ПРО:ИТ:Последняя правка: в текущем месяце
• Википедия:Статьи без ссылок на источники с февраля 2019 года
• Википедия:Статьи без источников (тип: протокол передачи данных)
• Страницы, использующие волшебные ссылки ISBN