Продолжение. Часть 11 — здесь.

В русской технической литературе до сих пор не устоялся термин, соответствующий английскому Spanning Tree Algorithm. Кто-то называет его «алгоритмом остовного дерева» (от слова «остов»), кто-то – алгоритмом или протоколом «связующего дерева» и пр. Поэтому поступим, как заправские ИТ-шники и будем использовать английский термин. Заметим лишь, что наилучший перевод этого термина – «алгоритм ветвящегося дерева» – почему-то вообще в литературе не используется.

В теории, если при создании сети Ethernet образуется петля, то любой пакет, у которого адрес назначения не присутствует в таблице маршрутизации ни одного из коммутаторов, будет бесконечно долго в этой сети циркулировать, потребляя её полосу пропускания.

Для устранения этого явления был разработан протокол связи, который создаёт граф набора соединений между коммутаторами, в котором петли отсутствуют. Тем не менее, он обеспечивает доступ к каждому устройству в сети. В теории графов он называется «spanning tree graph» (крона дерева). После создания графа Spanning Tree, те линки и порты сети, которые в него не входят, деактивируются, даже если они могут предоставить кратчайший путь между двумя узлами сети.

В случае отказа какого-то линка Spanning Tree создаётся новое дерево, и тогда отключённые ранее линки, могут быть вновь задействованы.

Может возникнуть вопрос: если между коммутаторами возможен протокол связи Spanning Tree, то, может быть, лучше сделать протокол, который бы создавал в коммутаторах таблицы маршрутизации, не приводящие к появлению петель в исходной топологии? Однако, здесь проблема не в недостатке возможностей координации между коммутаторами, а в функции рассылки Ethernet broadcast. Если в топологии сети есть петли, то пакеты общей рассылки могут в них бесконечно циркулировать. А функция общей рассылки, как мы видели ранее, необходима для работы протокола DHCP.

Алгоритм Spanning Tree работает следующим образом.

Выбирается один корневой коммутатор (мост, Root Bridge). Далее каждый коммутатор прокладывает кратчайший маршрут к корневому коммутатору. Соответствующий порт на каждом коммутаторе называется корневым портом (Root Port). У любого некорневого коммутатора может быть только один корневой порт.

После этого, для каждого сегмента сети, к которому присоединён более чем один коммутатор (или несколько портов одного коммутатора), просчитывается кратчайший путь к корневому коммутатору (порту). Коммутатор, через который проходит этот путь, становится назначенным для этой сети (Designated Bridge), а соответствующий порт — назначенным портом (Designated port).

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

Если какой-то линк (ветвь) отказывает, то граф дерева Spanning Tree изменяет конфигурацию.

Все коммутаторы при работе алгоритма Spanning Tree посылают регулярные сообщения называемые BPDU (Bridge Protocol Data Units) на все интерфейсы. Сообщение BPDU содержит:

• ID данного коммутатора;
• ID коммутатора, который в таблице данного коммутатора значится как корневой;
• «Стоимость маршрута», т.е. число линков (hops).

Эти сообщения распознаются коммутаторами и обрабатываются в каждом коммутаторе, на предмет того, содержится ли в сообщении следующее:

• Наименьший ID из коммутаторов, обнаруженных ранее;
• Наикратчайший путь к корневому коммутатору;
• Маршрут той же длины к корневому коммутатору, но через соседний коммутатор с самым ID меньшим (правило нарушения связи, tie-breaker rule), если маршрутов портов два, то второй обозначается как дополнительный tie-breaker.

В гетерогенной сети Ethernet (состоящей из сегментов с разными стандартами), подразумевается, что все линки должны иметь одинаковую скорость передачи.

Если коммутатор обнаруживает нового кандидата на роль корневого моста, то он посылает сообщения BPDU на все интерфейсы, указывая расстояние. Коммутатор также указывает интерфейс ведущий к корневому коммутатору.

По завершению этого процесса, в каждом коммутаторе будет следующая информация:

• Собственный маршрут от коммутатора к корневому мосту;
• Порт, от которого начинается путь к корневому мосту через другие коммутаторы;
• Для каждого порта – непосредственно подключенные коммутаторы к ним.

Затем, коммутатор деактивирует все интерфейсы, которые не были задействованы в маршруте, по следующим правилам:

1. Активизируется порт, от которого начинается путь к корневому мосту;
2. Активизируются все порты, где подключены коммутаторы, от которых идут маршруты к корневому мосту;
3. Если оставшиеся порты подключены к сегменту сети, к которому подключены другие соседние коммутаторы, то такой порт активируется, если от коммутатора через этот соседний сегмент к корневому мосту идёт путь с наименьшей стоимостью среди всех остальных сегментов, либо, если порт напрямую подключен к коммутатору, с наименьшим ID среди этих соседей (то есть, может служить как запасной порт tie-breaker), а если таких связей – две, то выбирается связь с наименьшим ID. 
4. Если у порта нет напрямую соединенных коммутаторов-соседей, то он подключается к хосту или сегменту и активируется.

Рассмотрим сеть из шести коммутаторов S1 — S6 с топологией, показанной на рисунке.

Топология Spanning Tree формируется при помощи правил 1 и 2. Если от коммутатора S3 идет маршрут к корневому мосту S1 через S2, то по правилу 1, порт S3 в направлении S2 открыт, а по правилу 2 открывается соответствующий порт S2 в направлении S3.

Правило 3 обеспечивает то, что каждый сегмент сети, который подключен к нескольким коммутаторам, получает уникальный маршрут к коревому мосту. Если S2 и S3 представляют собой граничные коммутаторы соседних сегментов (segment-neighbors), которые подсоединены к сегменту N, то S2 активизирует свой порт к N, а S3 – нет (поскольку 2<3).

Основная сложность здесь – создать маршрут для любого сетевого узла в сегменте N. Коммутаторы S2 и S3 создают свои собственные маршруты по правилам 1 и 2.

Правило 4 обеспечивает, чтобы любые граничные сегменты сохраняли коннективность, и они будут включать все узлы, напрямую подключенные к порту коммутатора.

Пример 1. Только коммутаторы.

Рассмотрим простую сеть (рис. 2), построенную только на коммутаторах, где номер коммутатора представляет собой его ID (хосты и номера интерфейсов не показаны). Каждый порт коммутатора подключается к другому коммутатору или к хосту лишь через один интерфейс (например, к рабочему компьютеру или принтеру).

В этом случае, можно воспользоваться только правилом 3. Любые порты коммутатора, напрямую подключенные к хосту, могут быть идентифицированы, поскольку они «тихие». Коммутатор никогда не получает сообщения BPDU на эти интерфейсы, поскольку хосты их не посылают.

Коммутатор S1 имеет наименьший ID, поэтому он автоматически становится корневым мостом. К S1 напрямую подключены S2 и S4, поэтому они активизируют интерфейсы к S1 по правилу 1, а S1 активизирует свои интерфейсы, через которые к нему могут подключаться S2 и S4 (правило 2).

S3 имеет уникальный маршрут с наименьшей стоимостью к S1, поэтому по правилу 1 он активирует свой интерфейс к S2, в то время как по правилу 2, S2 активизирует свой интерфейс к S3.

У S5 есть два равных по стоимости маршрута к S1 через S2 and S4. Поэтому S5 выбирает соседний коммутатор S2 с наименьшим номером. Его интерфейс к S4 не задействуется. Аналогично, S4 не будет активизировать интерфейс в направлении S5.

Такая же ситуация и с S6, который согласно тем же правилам, выбирает S3.

После того, как эти линки активизированы (строго говоря, активизированы порты, а не линки), то логическая топология сети принимает следующий вид, который и является графом Spanning Tree.

Пример 2. Коммутаторы и сегменты.

В сети могут быть также замкнутые сегменты, которые можно рассматривать целиком, как элементы подобные коммутаторам, через которые могут соединяться отдельные коммутаторы.

Например, в такой сети коммутаторы S1, S2 и S3, являются «соседями» только сегментов, с их общим сегментом В. Как и ранее, номера коммутаторов представляют их ID. Сетевые сегменты, в которых может быть несколько хостов, обозначены буквами. Заметим, что коммутаторы эти хосты обнаруживать не могут, а могут обнаруживать только другие коммутаторы.

Все коммутаторы обнаруживают, что коммутатор S1 является корневым, поскольку его номер – наименьший. Коммутаторы S2, S3 и S4 находятся от него на расстоянии одного линка с сегментом. Коммутаторы S5, S6 и S7 находятся на расстоянии двух линков с двумя сегментами.

По правилу 1, активизируются порт 1 коммутатора S2, порт 1 коммутатора S3, порт 1 коммутатора S4.  По правилу 2, активизируются порты 1, 5 и 4 на S1.

Без алгоритма Spanning Tree, S2 может подключаться к порту S1 через порт 2, а также и через порт 1. Однако, порт 1 имеет меньший номер.

S5 имеет два маршрута до S1 с одинаковой стоимостью: S5 →S4→S1 и S5→S3→S1. S3 – коммутатор с меньшим ID. Поэтому, активизируются порт 2 коммутатора S3 и порт 2 коммутатора S5.

S6 и S7 достигают корневого моста через S2 и S3 соответственно. У коммутатора S6 активизируется порт 1, у S2 – порт 3, а у S3 – порт 3.

На этом этапе, порты 2 и 2 у S1, порт 2 у S2, порты 2 и 3 у S4, порт 1 у S5, порт 2 у S6 и порт 1 у S7 пока не активизированы.

Теперь по правилу 3, в отношении сегментов (и их хостов) делается следующее:

• Порт 2 у S2 не активизируется, потому что у сети В нет прямого соединения с корневым мостом S1.
• Порт 3 коммутатора S4 активизируется, поскольку S4 и S5 через него соединяются, а S4 – ближе к коревому коммутатору. Этим достигается коннективность сети D. Порт 1 коммутатора S5 не активизируется.
• S6 and S7 привязаны к длине маршрута до корневого коммутатора. Однако, у S6 меньше ID, поэтому он активизирует порт 2. У S7 порт 1 не активизируется.

Наконец, по правилу 4 активизируется порт 2 у S4, и таким образом, устанавливается коннективность с хостом J. Также, правило 4 активизирует порт 2 у S1, поскольку сеть F имеет два соединения с S1, а порт 2 у S1 имеет меньший номер.

На этом этапе активизация портов на основе данных, собранных в процессе обнаружения корневого коммутатора завершается. Обмен BPDU продолжается, и при любых изменениях в сети, граф дерева модифицируется, отслеживая изменения в топологии сети.

Продолжение здесь.