STP

Spanning Tree Protocol (STP) (протокол кістякового дерева) — мережевий протокол, що працює на другому рівні моделі OSI. Заснований на однойменному алгоритмі, розробником якого є «Мама Інтернету» — Радья Перлман.

Основним завданням STP є приведення мережі Ethernet з множинними зв'язками до деревоподібної топології (кістякове дерево), що виключає передачу пакетів по колу. Відбувається це шляхом автоматичного блокування надлишкових в цей час зв'язків для повної зв'язності портів. Протокол описаний в стандарті IEEE 802.1D.

Принцип дії

1. У мережі вибирається один кореневий міст (англ. Root Bridge).
2. Далі кожен, відмінний від кореневого, міст прораховує найкоротший шлях до кореневого порту. Відповідний порт називається кореневим портом (англ. Root Port). У будь-якого не кореневого комутатора може бути тільки один кореневий порт.
3. Після цього для кожного сегмента мережі прораховується найкоротший шлях до кореневого порту. Міст, через який проходить цей шлях, стає призначеним для цієї мережі (англ. Designated Bridge). Безпосередньо підключений до мережі порт моста — призначеним портом.
4. Далі на всіх мостах блокуються всі порти, які не є кореневими та призначеними. У підсумку виходить деревоподібна структура (математичний граф) з вершиною у вигляді кореневого комутатора.

Основні поняття

• Pathcost- вартість лінка в STP;
• Bpduguard- BPDU-фільтр;
• Rootguard- root-фільтр;
• Bridge ID= Bridge priority + MAC;
• Bridge priority= vlan xxx + 32 768 (default cost);
• Cost- «вартість портів». За замовчуванням дорівнює 32 768 (2 в 15 степені);
• Hello BPDU= root ID + bridge ID + cost;
• Root port(кореневий порт) — це порт, який має найкоротшу відстань до будь-якого порту кореневого комутатора.
• Designated port(призначений порт) — це порт, який має найкоротшу відстань від призначеного комутатора до кореневого комутатора.

Швидкість передачі та вартість шляху

Таблиця знизу показує вартість інтерфейсу в залежності від швидкості передачі.

Швидкість передачі	Вартість (802.1D-1998)	Вартість (802.1t-2001)
4 Mbit/s	250	5000000
10 Mbit/s	100	2000000
16 Mbit/s	62	1250000
100 Mbit/s	19	200000
1 Gbit/s	4	20000
2 Gbit/s	3	10000
10 Gbit/s	2	2000

Важливі правила

1. Кореневим (root-овим) комутатором призначається комутатор з найнижчим BID (Bridge ID)
2. Можливі випадки, коли пріоритет у двох і більше комутаторів буде однаковий, тоді вибір кореневого комутатора (root-а) буде відбувається на підставі MAC-адреси комутатора, де кореневим (root) комутатором стане комутатор з найменшою MAC-адресою.
3. Комутатори, за замовчуванням, не вимірюють стан мережі, а мають заздалегідь прописані налаштування.
4. Кожен порт має свою вартість (cost) з'єднання, встановлену або на заводі-виробнику (за замовчуванням), або вручну.

Алгоритм дії STP (Spanning Tree Protocol)

• Після включення комутаторів в мережу, за замовчуванням кожен (!) Комутатор вважає себе кореневим (root).
• Потім комутатор починає посилати по всіх портах конфігураційні Hello BPDU пакети раз на 2 секунди.
• Виходячи з даних Hello BPDU пакетів, той чи інший комутатор набуває статусу root, тобто кореня.
• Після цього всі порти крім root port і designated port блокуються.
• Відбувається посилка Hello-пакетів раз на 2 секунди, з метою перешкоджання появи петель в мережі.

Порти

• Root Port
• Designated Port
• Non-designated Port
• Disabled Port

Еволюція і розширення

Rapid Spanning Tree Protocol (RSTP)

Докладніше: RSTP

Rapid STP (RSTP) характеризується значними вдосконаленнями STP, серед яких зменшення часу збіжності і вища стійкість. Описаний в стандарті IEEE 802.1w (згодом включено до 802.1D-2004).

Per-VLAN Spanning Tree Protocol (PVSTP)

Per-VLAN STP (PVSTP) відповідно до назви розширює функціонал STP для використання VLAN. У рамках даного протоколу в кожному VLAN працює окремий екземпляр STP. Є пропрієтарним розширенням Cisco, згодом став з незначними обмеженнями підтримуватися іншими виробниками (Juniper^[en], Extreme Networks). Споконвічно протокол PVST працював тільки через ISL-транки, потім було розроблено розширення PVST +, яке дозволяло працювати через набагато поширеніші 802.1Q-транки. Існують реалізації, об'єднуючі властивості PVST + і RSTP, оскільки ці розширення зачіпають незалежні частини протоколу, в результаті виходить (в термінології Cisco) rapid-pvst.
PVST не сумісно з MSTP і при одночасній роботі пристроїв Cisco з цими протоколами викликає проблеми в мережі, зокрема, відключення downlink'ового порту root'ового MSTP-пристрою.
Для блокування PVST на більшості мережевих пристроях інших виробників доводиться створювати MAC фільтр, оскільки в їх BPDU фільтрах пакети PVST невідомі і можуть проходити через ці пристрої навіть при відключених STP.

Multiple Spanning Tree Protocol (MSTP)

Multiple STP (MSTP) є найсучаснішою стандартною реалізацією STP, що враховує всі переваги і недоліки попередніх рішень. Описана в стандарті IEEE 802.1s (згодом включено до 802.1Q-2003). На відміну від PVST +, в якому число примірників сполучного дерева (spanning tree) дорівнює кількості віртуальних мереж, MSTP передбачає конфігурування необхідної кількості примірників незалежно від числа віртуальних мереж (VLAN) на комутаторі. В один примірник MST можуть входити декілька віртуальних мереж. Проте, всі комутатори, які беруть участь у MST, повинні мати однаково сконфігуровані групи VLAN (MST instances), що обмежує гнучкість при зміні конфігурації мережі.

Shortest Path Bridging

Shortest Path Bridging (SPB)або IEEE 802.1aq долає обмеження блокування.

Історія

Радья Перлман що винайшла цей алгоритм, також написала короткий вірш що пояснює принципи його роботи^[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.

Примітки

1. An Algorithm for Distributed Computation of a Spanning Tree in an Extended LAN [Архівовано 19 квітня 2015 у Wayback Machine.] Radia Perlman, 1985

Посилання

• IEEE Std 802.1D™- 2004 [Архівовано 31 жовтня 2017 у Wayback Machine.] (англ.)
• IEEE Std 802.1Q™- 2005 [Архівовано 6 липня 2010 у Wayback Machine.] (англ.)
• Understanding Spanning-Tree Protocol [Архівовано 18 грудня 2008 у Wayback Machine.] (англ.)
• PVST+ Explained — CCIE Blog (англ.)
• Differences between PVST and PVST+ [Архівовано 16 вересня 2011 у Wayback Machine.] (англ.)