STP

Не слід плутати з Straight-through processing.

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

Необхідність усунення топологічних петель в мережі Ethernet випливає з того, що їх наявність в реальній мережі Ethernet з комутатором з високою ймовірністю призводить до нескінченних повторів передачі одних і тих же кадрів Ethernet одним і більше комутатором, отчого пропускна здатність мережі виявляється майже повністю зайнятою цими марними повторами; в цих умовах, хоча формально мережа може продовжувати працювати, на практиці її продуктивність стає настільки низькою , що може виглядати як повна відмова мережі.

STP відноситься до другого рівня моделі OSI. Протокол описаний в стандарті IEEE 802.1d. STP заснований на однойменному алгоритмі, який розробила Радья Перлман ( англ. Radia Perlman ).

Приклад мережі. Квадратами позначені комутатори, цифри в квадратах - ідентифікатори мостів (Bridge ID). Хмари з латинськими літерами позначають сегменти мережі

1. Принцип дії

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

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

  • Bridge ID = Bridge priority + MAC;
  • Bridge priority = vlan xxx + 32768 (default cost);
  • Cost - "вартість портів";
  • Pathcost - вартість лінка в STP;
  • Hello BPDU = root ID + bridge ID + cost;
  • Root port (кореневої порт) - це порт, який має мінімальну вартість до будь-якого порту кореневого комутатора.
  • Designated port (призначений порт) - це порт, який має найкоротша відстань від призначеного комутатора до кореневого комутатора.

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

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

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

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

  1. Кореневим (root) портом призначається порт з найнижчою вартістю шляху (path cost).
  2. Можливі випадки, коли вартість шляху з двох і більше портів комутатора буде однакова, тоді вибір кореневого (root) порту буде відбуватися на підставі порядкового номера порту, наприклад fa0 / 1, fa0 / 2, fa0 / 3 і кореневим (root) стане порт з найменшим номером.
  3. Комутатори, за замовчуванням, не вимірюють стан завантаження мережі в реальному часі і працюють у відповідності з вартістю (cost) інтерфейсів в момент побудови дерева STP.
  4. Кожен порт має свою вартість (cost), назад пропорційну пропускної здатності (bandwidth) порту і яку можна налаштовувати вручну.

4. Алгоритм дії 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 секунди.

5. Порти

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

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

6.1. 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.


6.2. 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.


6.3. 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). В один примірник MST можуть входити кілька віртуальних мереж, за умови, що їх топологія однакова (в сенсі входять до VLAN комутаторів і з'єднань між ними). Мінімальна кількість екземплярів MSTP відповідає кількості унікальних топологічно груп VLAN в домені другого рівня (знову ж на рівні комутаторів і з'єднань між ними). MSTP накладає важливе обмеження: всі комутатори, які беруть участь у MSTP, повинні мати однаково сконфігуровані групи VLAN (MST instances), що обмежує гнучкість при зміні конфігурації мережі.

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


6.4. Shortest Path Bridging (SPB)

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

7. Цікаві факти

Алгоритм, закладений в основу STP, був розроблений в 1985 році Радіей Перлман. Їй дали 1 тиждень на розробку алгоритму. Вона зробила це за 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


Примітки