logo search
Учебник проектирование и внедрение компьютерных

Алгоритм связующего дерева

Для реализации мостов и функционирующей на них системы проверок в сетях, имеющих несколько мостов, используется алгоритм связующего дерева (spanning tree algorithm). Этот алгоритм описан в стандарте IEEE 802. Id. Он призван решить две задачи. Во-первых, необходимо, чтобы фреймы не зацикливались в сети. Если мосты связывают множество сетевых сегментов, возможна ситуация, когда фреймы начинают передаваться по замкнутым Маршрутам и, следовательно, никогда не достигнут точки назначения. Как Минимум, при этом упадет пропускная способность сети. Большое же количество зациклившихся фреймов может создать слишком большой трафик, Провоцирующий широковещательный шторм (broadcast storm). Широковещательный шторм – состояние, когда используется вся пропускная способность сети. Это может быть вызвано чрезмерным количеством запросов на передачу данных от сетевых устройств, что создает эффект полного бездействия сети.

Во-вторых, алгоритм связующего дерева определяет наиболее эффективный маршрут для передачи фреймов. При этом эффективность оценивается по двум критериям: по расстоянию, проходимому фреймом, и по степени использования кабельной системы. Алгоритм формирует для фреймов однонаправленный сетевой путь. Все мосты, имеющиеся в сети, взаимодействуй друг с другом и определяют направление, по которому передаются фреймы в цепочке мостов. При этом выбирается так называемый корневой мост (root bridge). Каждый мост получает уникальный идентификатор и уровень приоритета. Наивысший приоритет имеет корневой мост. Протокол алгоритма связующего дерева позволяет мостам взаимодействовать при помощи специальных широковещательных фреймов, называемых блоками данных протокола моста (bridge protocol data unit, BPDU). Эти блоки данных позволяют мостам получать сведения о других мостах. Формат фрейма BPDU показан на рис.6.

Рисунок 6. Побайтовое представление фрейма BPDU.

Значения полей фрейма:

Первым шагом при создании сети с мостами является определение моста с наивысшим приоритетом. Такой приоритет получает мост, имеющий самый маленький МАС-адрес, он и становится корневым мостом. Другие мосты получают приоритеты в соответствии со своими МАС-адресами (в соответствии с алгоритмом связующего дерева – чем меньше МАС-адрес моста, тем выше его приоритет).

Мост, назначенный корневым (его порты называют "назначенными" портами), сразу же рассылает корневые фреймы BPDU для обнаружения замкнутых маршрутов. Другие мосты переводят выбранные порты в заблокированное (однонаправленное) состояние, чтобы замкнутые маршруты стали невозможными. Фрейм не может обойти весь связанный мостами путь более одного раза, в противном случае он превышает допустимое количество пересылок (hop) и уничтожается. Каждому порту назначается некоторое значение стоимости пути, которое либо выбирается по умолчанию, либо устанавливается администратором сети. Стоимость пути к корневому мосту определяется с учетом скорости линии и расстояния. Линия Т-1, работающая со скоростью 1,544 Мбит/с, имеет более высокую скорость, чем линия Мбит/с Ethernet. Мост, находящийся дальше от корневого моста, заблокирует свои порты из-за более высокой стоимости передачи (т. е. из-за более длинного пути к корневому мосту).

Как только определена структура сети связующего дерева, корневой мост начинает каждые несколько секунд передавать фреймы BPDU типа Hello. Если другие мосты сети не получают этот фрейм в течение определенного промежутка времени (по умолчанию 20 секунд), предполагается, что корневой мост отключен или неисправен. Мост, который первым обнаружит это, для выбора нового корневого моста генерирует конфигурационный BPDU-фрейм, сообщающий об изменении топологии сети.

В сетях Ethernet расчеты стоимости пути позволяют также обеспечить целостность переданного фрейма. Нередко администраторы сети устанавливая предельную стоимость, например, указывают, что в линейном маршруте между двумя узлами может быть более восьми мостов. При превышении этого числа алгоритмы CSMA/CD могут давать ошибки синхронизации фреймов. Хотя это ограничение на применение алгоритма связующего дерева не закреплено официально в стандарте, добросовестные сетевые администраторы придерживаются его.

Алгоритм связующего дерева может показаться сложным, однако можно выделить некоторые важные задачи, которые он решает, упрощая управление сетевым трафиком.

Рисунок 7. Возможные физические маршруты в сравнении с логическим маршрутом, установленным с помощью алгоритма связующего дерева.