Алгоритм SRB

Свое название мосты SRB получили потому, что они предполагают размещение полного маршрута от источника до пункта назначения во всех межсетевых (LAN) блоках данных, отправляемых источником. SRB хранят и продвигают эти блоки данных в соответствии с указаниями о маршруте, содержащимися в соответствующем поле блока данных. На Рис. 6.5

представлен образец сети SRB.

Рис. 6.5. Sample SRB Network

Предположим, что Хост Х на Рис. 6.5 решила отправить блок данных в Хост Y. Вначале машина Х не знает, где находится машина Y-в той же или в другой LAN. Чтобы определить это, она отправляет тестовый блок данных. Если этот блок данных возвращается к ней без положительного указания о том, что машина Y видела его, то она должна предположить, что машина Y находится в отдаленном сегменте.

Чтобы точно определить местоположение отдаленной машины Y, машина Х отправляет блок данных разведчика (explorer). Каждый мост, получающий этот блок данных (в нашем примере это Мосты 1 и 2), копирует его во все порты отправки сообщений. По мере продвижения блоков данных-разведчиков через объединенную сеть они дополняются маршрутной информацией. Когда блоки данных-разведчики машины Х доходят до машины Y, то машина Y отвечает каждому отдельно, используя накопленную маршрутную информацию. После получения всех ответных блоков данных машина Х может выбрать маршрут, базирующийся на заранее установленном критерии.

В примере, приведенном на Рис. 6.5, результатом этого процесса будут два маршрута:

LAN 1 - Bridge 1 - LAN 3 - Bridge 3 - LAN 2LAN 1 - Bridge 2 - LAN 4 - Bridge 4 - LAN 2

Машина Х должна выбрать один из этих двух маршрутов. Спецификация IEEE 802.5 не назначает критерий, который машина Х должна использовать для выбора маршрута; однако в ней имеется несколько предложений, которые перечислены ниже:

Первый принятый блок данныхОтвет с минимальным числом пересылокОтвет с самым большим разрешенным размером блока данныхРазличные комбинации перечисленных выше критериев

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

После того, как маршрут выбран, он включается в блоки данных, предназначенных для машины Y, в форме поля маршрутной информации (routing information field - RIF). RIF включается только в блоки данных, предназначенных для других LAN. Наличие маршрутной информации в блоке данных указывается путем установки самого значащего бита, называемого битом индикатора маршрутной информации (routing information indicator - RII), в поле адреса источника.

Алгоритм связующего дерева (Spanning-Tree Algoritm) (STA)

Алгоритм был разработан для того, чтобы сохранить преимущества петель, устранив их проблемы. Первоначально алгоритм был документирован корпорацией Digital - основным поставщиком Ethernet. Новый алгоритм, разработанный Digital, был впоследствии пересмотрен комитетом IEEE 802 и опубликован в спецификации IEE 802. 1d в качестве алгоритма STA.

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

STA пользуются выводом из теории графов в качестве базиса для построения свободного от петель подмножества топологии сети. Теория графов утверждает следующее:

Для любого подсоединенного графа, состоящего из узлов и ребер, соединяющих пары узлов, существует связующее дерево из ребер, которое поддерживает связность данного графа, но не содержит петель.

Рис. 6.2 поясняет, каким образом STA устраняет петли. STA требует, чтобы каждому мосту был назначен уникальный идентификатор. Обычно этот идентификатор является одним из адресов МАС данного моста, который дополнен приоритетом. Каждому порту во всех мостах также назначается уникальный (в пределах этого моста) идентификатор (как правило, его собственный адрес МАС). И наконец, каждый порт моста взаимосвязан с затратами какого-нибудь тракта. Затраты тракта представляют собой затраты на передачу какого-нибудь блока данных в одну из локальных сетей через этот порт. На Рис. 6.2 "Сеть ТВ до прогона STA" затраты трактов отмечены на линиях, исходящих из каждого моста. Затраты трактов обычно устaнaвливаются по умолчанию, но могут быть назначены вручную администраторами сети.

Рис. 6.2. TB Network Befor Running STA

Первым шагом при вычислении связующего дерева является выбор корневого моста (root bridge), который представляет собой мост с наименьшим значением идентификатора моста. На Рис. 6.2 корневым мостом является Мост 1. Далее определяется корневой порт (root port) во всех остальных мостах. Корневой порт моста - это порт, через который можно попасть в корневой мост с наименьшими комбинированными затратами тракта. Эта величина (т.е. наименьшие комбинированные затраты тракта до корневого моста) называется затратами корневого тракта (root path cost).

И наконец, определяются назначенные мосты (designated bridges) и их назначенные порты (designated ports). Назначенный мост - это тот мост каждой локальной сети, который обеспечивает минимальные затраты корневого тракта. Назначенный мост локальной сети является единственным мостом, который позволяет продвигать блоки данных в ту локальную сеть (и из нее), для которой этот мост является назначенным. Назначенный порт локальной сети - это тот порт, который соединяет ее с назначенным мостом.

В некоторых случаях два или более мостов могут иметь одинаковые затраты корневого тракта. Например, на Рис. 6.2 как Мост 4, так и Мост 5 могут достичь Мост 1 (корневой мост) с затратами тракта 10. В этом случае снова используются идентификаторы моста, на этот раз для определения назначеных мостов. При выборе предпочтение отдано порту LAN V Моста 4 перед портом LAN V Моста 5.

При использовании этого процесса устраняются все мосты, непосредственно соединенные с каждой LAN, кроме одного; таким образом, удаляются все петли между двумя LAN. STA также устраняет петли, включающие более двух LAN, в то же время сохраняя связность. На Рис. 6.3 "Сеть ТВ после прогона STA" показаны результаты действия STA в сети, изображенной на Рис. 6.2. На Рис. 6.3 более четко показана топология дерева. Сравнение этого рисунка с рисунком сети до прогона STA показывает, что STA перевел в режим резерва как порты Моста 3 в LAN V, так и порты Moста 5 в LAN V.

Рис. 6.3. TB Network After Running STA

Расчет связующего дерева имеет место при подаче питания на мост и во всех случаях обнаружения изменения топологии. Для расчета необходима связь между мостами связующего дерева, которая осуществляется через сообщения конфигурации (иногда называемые протокольными информационными единицами моста - bridge protocol data units, или BPDU). Сообщения конфигурации содержат информацию, идентифицирующую тот мост, который считается корневым (т.е. идентификатор корневого моста), и расстояние от моста-отправителя до корневого моста (затраты корневого тракта). Сообщения конфигурации также содержат идентификаторы моста и порта моста-отправителя, а также возраст информации, содержащейся в сообщении конфигурации.

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

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

Библиографическая справка

Прозрачные мосты (TB) были впервые разработаны Digital Equipment Corporation в начале 1980 гг. Digital представила свою работу в IEEE, который включил ее в стандарт IEEE 802.1. TB очень популярны в сетях Ethernet/IEEE 802.3.

Библиографическая справка

Алгоритм Source-Route Bridging (SRB) (объединение с помощью мостов "источник-маршрут") был разработан IBM и предложен комитету IEEE 802.1 в качестве средства объединения локальных сетей с помощью мостов. После того, как комитет предпочел другой конкурирующий стандарт (смотри пункт "Прозрачное объединение с помощью мостов" о стандарте ТВ), сторонники SRB предложили его комитету IEEE 802.5, который впоследствии включил его в спецификацию локальной сети IEEE 802.5/Token Ring.

За первым предложением IBM последовало предложение нового стандарта объединения с помощью мостов в комитет IEEE 802: Source-Route Transparent (SRT) (Прозрачное объединение "источник-маршрут") Подробная информация о SRT дается в пункте "Mixed-Media Bridging". SRT полностью устраняет мосты "источник-маршрут" (SRB), предлагая взамен два типа мостов LAN-TB и SRT. Несмотря на то, что SRT получил одобрение, мосты SRB попрежнему широко применяются в сетях.

Библиографическая справка

Прозрачные мосты (transparent bridges - TB) в основном встечаются в сетях Ethernet (смотри пункт "Transparent Bridging"), в то время как мосты SRB встечаются почти исключительно в сетях Token Ring (смотри пункт "Source-Route Bridging"). Оба метода объединения сетей с помощью мостов (ТВ и SRB) популярны, поэтому естественно возникает вопрос о существовании какого-нибудь метода, который позволил бы объединить их. Этот основной вопрос иллюстрируется Рис. 6.7 "объединение с помощью моста доменов ТВ и SRB".

Рис. 6.7. Bridging Between TB and SRB Domains

Библиографическая справка

Рис. 6.7. Bridging Between TB and SRB Domains

Формат блока данных (фрэйма)

Мосты ТВ обмениваются сообщениями конфигурации (configuration messages) и сообщениями об изменении в топологии (topology change). Мосты обмениваются сообщениями конфигурации для установления топологии сети. Сообщения об изменении топологии отправляются после обнаружения какого-нибудь изменения в топологии для указания того, что должен быть произведен повторный прогон STA.

Формат сообщения конфигурации IEEE 802.1d представлен на Рис. 6.4.

Рис. 6.4. TB Configuration Message Format

Первым полем сообщения конфигурации ТВ является поле идентификатора протокола (protocol identifier), которое содержит нулевое значение.

Вторым полем в сообщении конфигурации ТВ является поле версии (version), которое содержит нулевое значение.

Третьим полем в сообщении ТВ является поле типа сообщения (message type), которое содержит нулевое значение.

Четвертым полем в сообщении конфигурации ТВ является однобайтовое поле флагов (flags). Бит ТС сигнализирует об изменении в топологии. Бит ТСА устанавливается для подтверждения приема сообщения конфигурации с установленным битом ТС. Другие шесть битов этого байта не используются.

Следующим полем в сообщении конфигурации ТВ является поле идентификатора корневого моста (root ID). Это 8-байтовое поле идентифицирует корневой мост путем перечисления его 2-байтового приоритета, за которым следует его 6-байтовый ID.

За полем ID корневого моста идет поле затрат корневого тракта (root path cost), которое содержит затраты тракта от моста, который отправляет конфигурационное сообщение, до корневого моста.

Далее идет поле идентификатора моста (bridge ID), которое идентифицирует приоритет и ID моста, отправляющего сообщение.

Поле идентификатора порта (port ID) идентифицирует порт, из которого отправлено конфигурационное сообщение. Это поле позволяет обнаруживать и устранять петли, образованные несколькими подключенными мостами.

Поле возраста сообщения (message age) определяет промежуток времени, прошедшего с момента отправки корневым мостом конфигурационного сообщения, на котором базируется текущее конфигурационное сообщение.

Поле максимального возраста (maximum age) указывает, когда текущее конфигурационное сообщение должно быть стерто.

Поле времени приветствия (hello time) обеспечивает период времени между конфигурационными сообщениями корневого моста.

И наконец, поле задержки продвижения (forward delay) обеспечивает промежуток времени, в течение которого мосты должны выжидать, прежде чем перейти в новое состояние после изменения в топологии. Если переходы какого-нибудь моста происходят слишком быстро, то не все каналы сети могут оказаться готовыми для изменения их состояний, в результате чего могут появиться петли.

Сообщения о топологических изменениях состоят всего из 4 байтов. Они включают в себя поле идентификатора протокола (protocol identifier), которое содержит нулевое значение, поле версии (version,), которое содержит нулевое значение и поле типа сообщения (message type), которое содержит значение 128.

Формат блока данных (фрэйма)

Структура IEEE 802.5 RIF представлена на Рис. 6.6.

Рис. 6.6. IEEE 802.5 RIF

Подполе типа (type) в RIF указывает на количество узлов, в которые должен быть отправлен данный блок данных: в один узел, в группу узлов, включающих в себя связующее дерево данной объединенной сети, или во все узлы. Первый тип называется "специально направленным" (specifically routed) блоком данных, второй тип - "разведчиком связующего дерева" (spanning-tree explorer), а третий тип - "разведчиком всех трактов" (all-paths explorer). Разведчик связующего дерева может быть использован в качестве транзитного механизма для блоков данных с многопунктовой адресацией. Он может быть также использован в качестве замены разведчика всех трактов в запросах об исходящих маршрутах. В этом случае пункт назначения в ответ присылает разведчика всех трактов.

Подполе длины (length) обозначает общую длину RIF в байтах.

Бит D указывает направление движения блока данных (прямое или обратное).

Поле "самый большой" (largest) обозначает самый большой блок данных, который может быть обработан вдоль всего этого маршрута.

Полей описателя маршрута (route descriptor) может быть несколько. Каждое из них содержит пару "номер кольца/номер моста", которая определяет какую-нибудь часть маршрута. Таким образом, маршруты представляют собой просто чередующиеся последовательности номеров LAN и мостов, которые начинаются и заканчиваются номерами LAN.

Основы технологии

ТВ названы так потому, что их присутствие и работа являются прозрачными для хостов сети. После подачи питания на ТВ, они узнают о топологии сети путем анализа адреса источника блоков данных, приходящих из всех других подключенных сетей. Например, если мост видит, что какой-нибудь блок данных поступил на линию 1 из Хоста А, он делает вывод, что до Хоста А можно добраться через сеть, подключенную к линии 1. С помощью этого процесса ТВ строят таблицу, приведенную ниже.

Таблица 6.1.

Host addressNetwork number

15	1
17	1
12	2
13	2
18	1
9	1
14	3
.	.
.	.

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

ТВ успешно изолирует внутрисегментный трафик, тем самым сокращая трафик, видимый в каждом отдельном сегменте. Это обычно улучшает время реакции сети, видимое пользователю. Степень сокращения трафика и улучшения времени реакции зависят от объема межсегментного трафика относительно общего трафика, а также от объема широковещательного и многопунктового трафика.

Основы технологии

Трансляционное объединение с помощью мостов (Translational bridging - TLB) обеспечивает относительно недорогое решение некоторых из многочисленных проблем, связанных с объединением с помощью моста доменов ТВ и SRB. TLB впервые появился в середине-конце 1980 гг., но ни одна из организаций по стандартам не стала заниматься им. В результате многие аспекты TLB предоставлены для решения тому, кто реализует его.

В 1990 г. IBM устранила некоторые из недостатков TLB путем введения "Прозрачного объединения с помощью моста "источник-маршрут" (Source-Route Transparent-SRT). SRT может продвигать трафик из конечных узлов сети как с прозрачным объединением, так и с объединением "источник-маршрут", и образовывать общее связующее дерево с мостами TB, позволяя тем самым конечным станциям каждого типа сообщаться с конечными станциями такого же типа в сети с произвольной топологией.

В конечном итоге, целью объединения доменов ТВ и SRB является возможность сообщения между конечными станциями ТВ и SRB. В данной главе описываются технические проблемы, которые должны быть решены алгоритмами, пытающимися сделать это, а также представлены два возможных решения: TLB и SRT.

Основы технологии

Таблица 6.1.

Host addressNetwork number

15	1
17	1
12	2
13	2
18	1
9	1
14	3
.	.
.	.

Основы технологии

Трансляционное объединение с помощью мостов (TLB)

Поскольку порядок связи между двумя типами носителя не был по-настоящему стандартизован, нет ни одной реализации TLB, которую можно назвать точной. Ниже дается описание нескольких популярных методов реализации TLB.

При трансляции между Ethernet и Token Ring протокол TLB переупорядочивает биты адреса источника и пункта назначения. Проблема встроенных адресов МАС может быть решена путем программирования моста таким образом, чтобы он проверял адреса МАС разных типов; однако это техническое решение должно адаптироваться к каждому новому типу встроенных адресов МАС. В некоторых решениях TLB просто проверяются наиболее популярные встроенные адреса МАС. Если программное обеспечение TLB работает в роутере с несколькими протоколами, то этот роутер может успешно назначать тракты для этих протоколов и полностью решить эту проблему.

Поле RIF имеет подполе, которое указывает размер самого большого блока данных, который может быть принят конкретной реализацией SRB. TLB, отправляющие блоки данных из домена ТВ в домен SRB, обычно устанавливают значение поля размера MTU равным 1500 для того, чтобы ограничить размер блоков данных Token Ring, входящих в домен ТВ. Некоторые хосты не могут точно обрабатывать это поле; в этом случае TLB вынуждены просто игнорировать те блоки данных, которые превышают размер MTU Еthernet.

Биты, представляющие функции Token Ring, не имеющие следствия в Ethernet, обычно отбрасываются протоколами TLB. Например, отбрасываются биты приоритета, резервирования и монитора Token Ring. Что касается битов состояния блоков данных Token Ring, то они обрабатываются по-разному в зависимости от изготовителя TLB. Некоторые изготовители TLB просто игнорируют эти биты. Другие обеспечивают установку в мостах бита С, но не обеспечивают бит А. В первом случае узел источника Token Ring не имеет возможности установить, потерян или нет отправленный им блок данных. Сторонники этого метода считают, что механизмы надежности, такие, как отслеживание потерянных блоков данных, лучше реализовать в уровне 4 модели ОSI. Защитники "метода установки бита С" утверждают, что этот бит должен быть задан для отслеживания потерянных блоков данных, но бит А не может быть установлен, т.к. мост не является конечным пунктом назначения.

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

При объединении с помощью моста доменов SRB и ТВ информация SRB удаляется. RIF обычно сохраняются в кэш для использования последующим возвратным трафиком. При объединении с помощью моста доменов ТВ и SRB, TLB может проверить блок данных, чтобы узнать, имеет ли он назначение многопунктовой адресации. Если блок данных имеет многопунктовое или широковещательное назначение, он отправляется в домен SRB в качестве разведчика связующего дерева. Если блок данных имеет однопунктовый адрес, то TLB ищет пункт назначения в кэш RIF. Если тракт найден, то он будет использован, а информация RIF включается в блок данных; в противном случае этот блок данных отправляется в качестве разведчика связующего дерева. Т.к. две этих реализации связующего дерева несовместимы, то, как правило, не разрешаются несколько трактов между доменами SRB и ТВ.