Алгоритм покрывающего дерева

 

Алгоритм покрывающего дерева (Spanning Tree Algorithm, STA) описан в стандарте IEEE 802.1D и позволяет ликвидировать петли в сети (если в сети есть кольцевые маршруты, это может привести к неправильной работе мостов и коммутаторов). Алгоритм STA из всех связей, имеющихся в сети, выбирает подмножество, образующее дерево, покрывающее все узлы сети. Алгоритм STA состоит из четырех этапов.

 

1. В сети выбирается корневой коммутатор (root switch), который будет считаться корнем дерева. Выбор происходит либо автоматически (корневым становится коммутатор с наименьшим значением MAC-адреса блока управления), либо выполняется администратором.

2. Для каждого коммутатора определяется корневой порт (root port) – порт, через который проходит самый короткий путь до корневого коммутатора.

3. Для каждого сегмента сети выбирается назначенный порт (designated port) – порт, через который проходит кратчайший путь от данного сегмента до корневого коммутатора.

4. Все порты, не вошедшие в корневые и назначенные, блокируются.

 

При определении кратчайших расстояний рассчитывается суммарное время (в 10-наносекундных единицах) передачи одного бита данных от выбранного порта до корневого коммутатора (учитывается только времена передач по связям между коммутаторами). Например, для Ethernet-сегмента время передачи равно 10, а для Fast Ethernet – 1.

Все коммутаторы периодически обмениваются служебными пакетами – протокольными блоками данных моста (Bridge Protocol Data Unit, BPDU), содержащими идентификатор корневого коммутатора, расстояние до корня, идентификатор коммутатора, выдавшего этот пакет, идентификатор порта, на который был выдан пакет и еще несколько служебных полей. После включения каждый коммутатор считает себя корневым (если иное не задано администратором) и выдает пакеты BPDU со своим идентификатором в поле “идентификатор корневого коммутатора” и расстоянием до корня, равным 0, через все свои порты. Если коммутатор получает BPDU, в котором идентификатор корневого коммутатора меньше его собственного идентификатора, он перестает генерировать свои пакеты, а ретранслирует приходящие пакеты нового корневого коммутатора, увеличивая в них поле “расстояние до корня” на условное время сегмента, по которому пришел этот пакет. При этом коммутатор запоминает для каждого порта минимальное расстояние до корня (из всех пришедших на этот порт пакетов BPDU).

Через заданное время процесс конфигурации заканчивается и корневым портом коммутатор считает тот свой порт, у которого расстояние до корня оказалось минимальным (если таких портов несколько, выбирается порт с наименьшим идентификатором). Затем, он делает назначенными все порты, принятые по которым минимальные расстояния до корня больше, чем расстояние до корня корневого порта. Наконец, все порты, кроме корневого и назначенных, переводятся в заблокированное состояние.

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

 

Список литературы

 

1. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы (учебник для ВУЗ’ов). —СПб.: Питер, 2011. —944 c.

2. Смелянский Р.Л. Компьютерные сети (в 2 томах). —M.: Академия, 2011 (том 1: Системы передачи данных, —304 c.; том 2: Сети ЭВМ, —240 с.).

3. Э.Таненбаум, Д.Уэзеролл. Компьютерные сети. —СПб.: Питер, 2012. —960 c.

4. Новожилов Е.О., Новожилов О.П.. Компьютерные сети. —M.: Академия, 2011. —304 с.

5. Кузин А.В. Компьютерные сети. —M.: Форум, Инфра-М, 2011. —192 c.

6. Виснадул Б.Д., Лупин С.А., Сидоров С.В., Чумаченко П.Ю.. Основы компьютерных сетей. —M.: Форум, Инфра-М, 2009. —272 c.

7. Дж.Скотт Хогдал. Анализ и диагностика компьютерных сетей. —M.: Лори, 2007. —364 c.

 

 

 

 

Учебное издание