Александр Филимонов

Сети ЭВМ и телекоммуникации




Начало > Локальные сети

Особенности практической реализации алгоритма Spanning Tree в сети мостов

На практике алгоритм Spanning Tree реализуется распределенным образом каждым мостом в отдельности. Для обеспечения информационного обмена в процессе выполнения этого алгоритма мосты посылают друг другу специальные сообщения, которые называются BPDU(bridge protocol data units). Сообщения BPDU размещаются в поле полезной нагрузки блоков данных канального уровня – кадров Ethernet или Token Ring. Структура кадра Ethernet, который используется для переноса сообщения BPDU, приведена в таблице:

Destination Address Source Address Type Length SAP BPDU
6 6 2 3 8

При выполнении процедуры Spanning Tree используются два типа сообщений:

  • Сообщения типа Configuration BPDU
  • Сообщениям типа Topology Change Notification BPDU

Сообщения первого типа формируются корневым мостом и используются для определения структуры Spanning Tree. Сообщения второго типа могут быть сформированы любым мостом.

Структура сообщения типа Configuration BPDU рассмотрена в последующем разделе.

Структура и состав BPDU

Protocol Identifier Version Message Type Flag Root ID Root path cost Bridge ID Port ID Message age Maximum age Hello time Forward delay
2 1 1 1 8 4 8 2 2 2 2 2

Поле Protocol identifier

Данное поле занимает 2 байта в BPDU и формируется значением 00000000

Поле Version

Это поле занимает 1 байт в BPDU. Существующей в настоящий момент версии алгоритма STA соответствует значение 0000 данного поля.

Поле Message type

В этом поле BPDU размещается признак, с помощью которого различаются сообщения алгоритма STA:

  • Сообщениям типа Configuration BPDU соответствует значение 0х00 поля Message type
  • Сообщениям типа Topology Change Notification BPDU соответствует значение 0х80 поля Message type

Поле Flags

два бита этого поля TC(topology change) и Topology Change Acknowledgment (TCA) используются для того, чтобы  обеспечить информационный обмен на этапе изменения установленной конфигурации структуры Spanning Tree.

Поле Root ID

В этом поле BPDU размещается идентификатор корневого моста. Первые два байта представляют собой приоритет данного моста, который может быть установлен системным администратором. Последующие 6 байтов представляют собой МАС- адрес корневого моста.

Поле Root path cost

Это поле занимает 4 байта в кадре BPDU и представляет стоимость кратчайшего пути от того моста, который является источником сообщения до корневого моста.

Поле Bridge ID(BID)

В этом поле BPDU размещается идентификатор моста, который является источником данного сообщения.

Поле Port ID

В этом поле сообщения BPDU размещается идентификатор порта, через который было передано данное сообщение.

Поле Message age

Поле Message age (возраст сообщения) занимает два байта в сообщении BPDU и предназначено для фиксирования времени существования сообщения в сети. Каждый мост при прохождении через него сообщения модифицирует содержимое этого поля путем добавления к нему значения задержки, которая соответствует данному каналу. Значение этого и всех последующих интервалов времени определяются с точностью 1/256 доли секунды.

Поле Maximum age

Поле age(Максимальный возраст сообщения) устанавливает максимальное время существования данного сообщения в сети. В том случае, если значение поля Message age у полученного сообщения превышает значение Maximum age, такое сообщение не принимается к рассмотрению и не передается далее.

Поле Hello time

Значение этого поля сообщения BPDU определяет период следования конфигурационных сообщений. Обычно это значение соответствует интервалу времени от 1 до 4 секунд.

Поле Forward delay

Значение этого поля определяет величину интервала времени, который должен предшествовать переходу моста в новое состояние при изменении конфигурации системы. Эта задержка предназначена для исключения возникновения циклических маршрутов во время переходных процессов в сети.

Выполнение процедуры Spanning Tree

Для того, чтобы принимать участие в выполнении процедуры Spanning Tree, каждый мост должен определять и сохранять значения следующих параметров системы:

  • Идентификатор корневого моста (Root bridge Identifier RBI)
  • Стоимость кратчайшего пути до корневого моста (Root Path Cost)
  • Идентификатор ближайшего моста, через который проходит этот путь
  • Идентификатор порта данного моста, через который проходит этот путь

Формирование структуры Spanning Tree производится в ходе процесса самоорганизации замкнутой системы. Во время протекания этого процесса компоненты этой системы – мосты обмениваются конфигурационными сообщениями и в ходе этого обмена определяют указанные выше значения. Определение всех параметров производится одновременно путем постепенного приближения к истинному значению.

Определение значения идентификатора корневого моста

Как уже было отмечено выше, конфигурационные сообщения BPDU формирует корневой мост системы. Эти сообщения мост должен посылать постоянно с периодом от 1 до 4 секунд. Когда конфигурационное сообщение поступает на очередной мост, он анализирует соответствие хранимого значения RBI, тому значению, которое пришло в данном сообщении. Установленное на момент включения значение RBI у каждого моста совпадает со значением его собственного идентификатора. В том случае, если это значение меньше, чем значение корневого идентификатора у принятого сообщения, данное сообщение не обрабатывается и далее не передается. Этот аппарат обеспечивает  подавление конфигурационных сообщений от мостов, которые ошибочно посчитали себя корневыми мостами. В том случае, если значение корневого идентификатора у принятого сообщения меньше, чем хранимое значение, мост устанавливает новое значение хранимого идентификатора RBI. Таким образом, через некоторое время все мосты, входящие в систему, устанавливают единое для всех значение идентификатора корневого моста.

Определение корневого порта

Все сообщения, которые поступают на порты моста с корректным значением RBI, мост обрабатывает по специальному алгоритму,  чтобы определить, какой из его портов связан с корневым мостом кратчайшим маршрутом. В качестве критерия оптимальности маршрута мост в данном случае использует значение поля Root path cost принятого сообщения. Стоимость маршрута в алгоритме Spanning Tree пропорциональна задержке при передаче сообщения.  В таблице приведены значения стоимостей, которые соответствуют наиболее популярным значениям скоростей передачи данных в современных локальных вычислительных сетях.

Bandwidth STP Cost Value
4 Mbps 250
10 Mbps 100
16 Mbps 62
45 Mbps 39
100 Mbps 19
155 Mbps 14
622 Mbps 6
1 Gbps 4
10 Gbps 2

У конфигурационных сообщений, которые формирует корневой мост, значения Root path cost устанавливаются равными 0. При передаче корректного конфигурационного сообщения через каждый из своих портов, мост записывает значение своего идентификатора в поле BID и увеличивает значение поля RPC на величину, которая соответствует пропускной способности данного порта. После того, как это сообщение получает очередной мост системы, он должен зафиксировать номер порта, на который это сообщение было принято и значение Root path cost (RPC) у этого сообщения. В том случае, если принятое значение RPC меньше, чем хранимое значение для данного порта, прежнее значение заменяется на новое. Этот алгоритм позволяет определить стоимость кратчайшего пути, который соединяет данный порт с корневым мостом. Порт данного моста, которому соответствует минимальная стоимость корневого маршрута, становится корневым портом.

Определение выделенного моста для сегмента сети

Определение выделенного (designated) порта производится для того, чтобы обеспечить подключение каждого сегмента сети  к корневому пути только одним портом только одного моста. Это, в свою очередь, необходимо для того, чтобы исключить возможность появления кольцевых маршрутов в сети мостов. Для определения моста, который будет использоваться в качестве выделенного для данного сегмента, каждый мост должен анализировать значения RPC у сообщений, поступающих на его порты. На рисунке приведен пример выполнения процедуры Spanning Tree в сети, содержащей 11 мостов.

Корневым мостом в данной сети будет выбран мост, который имеет условный идентификатор 0. Порты, которые в соответствии с алгоритмом будут определены в качестве корневых мостов, помечены на рисунке зелеными точками. При выборе назначенного моста  для сегмента В каждый из подключенных к этому сегменту мостов 1-5 получит как минимум 4 конфигурационных сообщения. Содержание этих сообщений приведено в соответствующей таблице. Сообщения, которые поступят в этот сегмент по маршруту 0-6-4(5) будут представлять путь до корневого моста со стоимостью 38. Сообщения, которые поступят по альтернативному маршруту 0-1(2,3) представляют путь до корневого моста со стоимостью 100. Поэтому в качестве назначенного для данного сегмента будет выбран мост 4, поскольку он имеет меньший идентификатор, чем мост 5, имеющий аналогичную стоимость корневого маршрута.


На рисунке блокированные порты мостов отмечены тонкими черными линиями, а открытые порты – толстыми зелеными линиями.

Реализация процедуры Spanning Tree в современных коммутаторах

В процессе выполнения алгоритма Spanning Tree современные многопортовые мосты – коммутаторы используют несколько таймеров.

Hello Timer

Этот таймер определяет период времени, через который данный компонент сети – мост должен формировать специальные проверочные сообщения.

Forward Delay Timer

Этот таймер определяет интервал времени, который мост должен выдержать после выполнения процедуры  Spanning Tree до перехода в свое основное рабочее состояние - (forwarding).

Maximum Age Timer

Этот таймер определяет величину временного отрезка, в течение которого сохраняется содержание внутренних запоминающих устройств моста.

Режимы функционирования портов моста

Из-за наличия временных задержек при передаче данных в процессе выполнения алгоритма Spanning Tree, могут возникать нестабильные конфигурации. Поэтому процесс нормального функционирования компонентов сети не может начаться сразу после завершения выполнения процедуры Spanning Tree.

В процессе выполнения процедуры порты моста могут находиться в одном из пяти фиксированных состояний (режимов):

  • Режим блокировки (blocking)
  • Режим прослушивания (Listening)
  • Режим обучения (Learning)
  • Основной режим (Forwarding)
  • Порт выключен (Disabled)

На рисунке приведена последовательность смены состояний порта во время и после выполнения процедуры Spanning Tree.

Режим блокировки

Все порты моста после включения переводятся в режим блокировки. В этом режиме для данного порта мост выполняет следующие действия:

  • Уничтожает информационные кадры, которые поступают на вход заблокированного порта из подключенного сегмента или от других портов данного моста
  • Принимает и обрабатывает конфигурационные сообщения, поступающие на заблокированный порт
  • Не формирует базу данных МАС – адресов для заблокированного порта
  • Не передает конфигурационные сообщения
  • Принимает сообщения от системы управления сетью и отвечает на них

Режим прослушивания

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

  • Уничтожает информационные кадры, которые поступают на вход заблокированного порта из подключенного сегмента или от других портов данного моста
  • Принимает, обрабатывает и формирует конфигурационные сообщения
  • Не формирует базу данных МАС – адресов
  • Принимает сообщения от системы управления сетью и отвечает на них

Режим обучения

При переводе порта в режим прослушивания запускается счетчик времени – forward delay timer. Если к моменту истечения временного интервала, определяемого данным таймером, порт по результатам выполнения процедуры Spanning Tree не будет переведен в блокированное состояние, он автоматически переходит в режим обучения.

В этом режиме для данного порта мост выполняет следующие действия:

  • Уничтожает информационные кадры, которые поступают на вход заблокированного порта из подключенного сегмента или от других портов данного моста
  • Принимает, обрабатывает и формирует конфигурационные сообщения
  • Формирует базу данных МАС – адресов на основании анализа адресов источников из подключенного сегмента
  • Принимает сообщения от системы управления сетью и отвечает на них

Основной режим

Завершение режима обучения производится автоматически после истечения временного интервала forward delay timer. После этого порт переводится в основной режим, который называется forwarding. В этом режиме для данного порта мост выполняет следующие действия:

  • Уничтожает информационные кадры, которые поступают на вход заблокированного порта из подключенного сегмента
  • Обрабатывает информационные кадры, которые поступают на вход данного порта от других портов данного моста
  • Принимает, обрабатывает и формирует конфигурационные сообщения
  • Формирует базу данных МАС – адресов на основании анализа адресов источников из подключенного сегмента
  • Принимает сообщения от системы управления сетью и отвечает на них

Выполнение процедуры Spanning Tree при изменении установленной конфигурации сети

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

В качестве примера можно рассмотреть сеть, которая представлена на рисунке. При разрушении маршрута, который соединял мост 2 с мостом 3, связность сети нарушается. В результате выполнения  процедуры Spanning Tree порт, который связывает мост 1 с мостом 4, переводится в активное состояние. Однако для того, чтобы мост №1 начал передавать пакеты, адресованные станции В по новому маршруту нужно, чтобы была дезавуирована запись, в соответствии с которой кадры адресованные станции В нужно направлять через мост №2. При обычном развитии событий эта запись из таблицы моста №1 исчезнет не раньше, чем истечет временной интервал max age. Для того, чтобы обеспечить более оперативное реагирование компонентов сети на изменение конфигурации применяется специальный механизм, который называется topology change notification.

Суть этого механизма состоит в резком уменьшении времени сохранения записей в информационной базе моста в период изменения конфигурации системы. Мост, который осознает необходимость изменения конфигурации сети, формирует специальное сообщение TCN (topology change notification) и направляет его через свой корневой порт. Назначенный порт подтверждает получение этого сообщения передачей сообщения типа topology change acknowledge. В свою очередь, назначенный мост передает это сообщение далее по инстанции. Когда это сообщение достигает корневого моста, он формирует сообщение topology change, при получении которого все мосты должны уменьшить время жизни своих записей.


< Предыдущая лекция
Принцип построения устройств типа мост (бридж)
Вернуться к оглавлению >


Ссылки по теме:

Поиск

Поиск документов на RFC.net



© 2000— Александр Филимонов
© 2001— Алексей Бусыгин

Top.Mail.Ru