Разделы

Авто
Бизнес
Болезни
Дом
Защита
Здоровье
Интернет
Компьютеры
Медицина
Науки
Обучение
Общество
Питание
Политика
Производство
Промышленность
Спорт
Техника
Экономика

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

Чтобы решить проблему бесконечных циклов и широковещательных штормов в сети с избыточными мостами, Digital Equipment Coiporation разработала алгоритм связующего дерева (SPA, spanningtreealgorithm). Этот алгоритм сохраняет отказоустойчивость, обеспечиваемую избыточными мостами, и устраняет бесконечные циклы. В дальнейшем алгоритм связующего дерева был переработан IEEE и формализован в виде стандарта 802. Id.
Работа алгоритма заключается в выборе одного моста для каждого сегмента с несколькими доступными мостами. На выбранный мост возлагаются все задачи по перенаправлению и фильтрации пакетов для данного сегмента. В это время остальные мосты бездействуют, но остаются в полной готовности на случай отказа выбранного моста.

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

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

В конце концов, в каждом сегменте сети определяется выделенный (отмеченный) мост (designatedbridge), а также выделенный (отмеченный) порт (designatedport) этого моста. Только отмеченному порту выделенного моста разрешено фильтровать и пересылать пакеты для соответствующего сегмента сети. Остальные (избыточные) мосты в данном сегменте остаются работающими на случай выхода из строя выделенного моста, но не активными до тех пор, пока в этом не будет необходимости. Теперь в каждом сегменте функционирует только один мост, и пакеты могут передаваться без возникновения циклов.

Чтобы выполнить все необходимые вычисления, мосты должны обмениваться между собой сообщениями в формате, определенном стандартом 802.Id (рис. 5.7). Эти сообщения называются блоками данных протокола мостов (BPDUs, bridgeprotocoldataunits) и содержат поля, перечисленные ниже.

  • Идентификатор протокола (2 байта). Всегда содержит значение 0.
  • Версия (1 байт). Всегда равна 0.
  • Тип сообщения (1 байт). Всегда содержит значение 0.
  •   Флаги (1 байт). Содержит два 1-битных флага:

Бит 1. Изменение топологии — указывает на то, что сообщение было послано для того, чтобы сигнализировать об изменении в составе сети;

Подпись:

Бит 2. Подтверждение изменения топологии — используется для подтверждения получения сообщения с установленным битом 1.

Идентификатор корня (8 байтов). Идентифицирует корневой мост, то есть указывает присвоенное ему двухбайтовое значение приоритета, следующее за шестибайтовым МАС-адресом.

Стоимость корневого пути (4 байта). Заполняется величиной эффективности пути от моста, пославшего BPDU-сообшение, до корневого моста.
Идентификатор моста (8 байтов). Содержит 6-байтовый аппаратный адрес моста, пославшего сообщение, и 2-байтовое значение заданного этому мосту приоритета.

 Идентификатор порта (2 байта). Определяет порт, через который было отправлено сообщение.

 Возраст сообщения (2 байта). Указывает на время, прошедшее с момента отправки сообщения.

 Максимальный возраст (2 байта). Задает ограничение возраста, по достижении которого сообщение должно быть удалено.

 Интервал приветствия (2 байта). Фиксирует временной интервал между конфигурационными сообщениями корневого моста.

 Задержка передачи (2 байта). Специфицирует промежуток времени, в течение которого мосты должны ожидать завершения работы алгоритма связующего дерева после изменения топологии сети. Если еще не все мосты закончили работу алгоритма, то преждевременные передачи могут вызвать появление циклов.

Сообщения BPDU инкапсулируются стандартными кадрами протокола Канального уровня, использующими значение SAP 01000010 и групповой адрес "всем мостам". Мосты вырабатывают сообщения самостоятельно, но при этом не перенаправляют их в другие сети. Сообщения BPDU пересылаются только в том сетевом сегменте, к которому непосредственно подключены мосты.

Как и процесс заполнения таблицы адресов, алгоритм связующего дерева начинает работать сразу после присоединения мостов к сети и включения их питания. Первоначально каждый мост считает себя корневым, что соответствует стоимости пути, равной 0. По мере приема сообщений BPDU от других мостов сегмента он сравнивает извлеченную из сообщений информацию и определяет, какой из мостов больше подходит для выполнения присущих им функций в данном сегменте. Алгоритм принятия этого решения основан на выстроенных надлежащим образом значениях следующих критериев:

  • идентификатор корня;
  • стоимость корневого пути;
  • идентификатор моста;
  • идентификатор порта.

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

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

Кроме того, корневой мост периодически (через временные промежутки, определяемые значением поля "интервал приветствия") генерирует новые сообщения BPDU со значением поля "возраст сообщения", равным 0. Такие действия вынуждают другие мосты в сети "поддерживать порядок". То есть, если один из мостов сетевого сегмента перестает посылать сообщения BPDU, остальные мосты снова с начала до конца выполняют алгоритм для того, чтобы выбрать для сегмента новый выделенный мост. 4-байтовое сообщение изменения топологии сигнализирует остальным мостам о необходимости повторно запустить алгоритм. Данное сообщение укороченного формата BPDU состоит только из полей идентификатора протокола, версии и типа сообщения, где первые два поля обнулены, а поле "тип сообщения" имеет значение 128.

 

Читайте также:

Дата публикации:2012-10-20

Просмотров:1763

Вернуться в оглавление:

Комментария пока нет...


Имя* (по-русски):
Почта* (e-mail):Не публикуется
Ответить (до 1000 символов):







 

2012-2018 lekcion.ru. За поставленную ссылку спасибо.