Э. Таненбаум, Д. Уэзеролл - Компьютерные сети, страница 106

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

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

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

Мосты выбирают в качестве корня мост с наименьшимидентификатором. После обмена достаточным числом сообщений, чтобы распространить эту новость, все мосты договорятся, какой мост является корнем. На рис. 4.41мост B1 имеет наименьший идентификатор и становится корнем.Затем создается дерево кратчайших путей от корня до каждого моста. На рис. 4.41мосты B2 и B3 могут быть достигнуты от моста B1 непосредственно, за один шаг, ко-368   Глава 4. Подуровень управления доступом к средеторый является кратчайшим путем. Мост B4 может быть достигнут за два шага, иличерез B2 или через B3. Чтобы разрубить этот узел, выбирается путь через мост с наименьшим идентификатором, таким образом, B4 будет достигнут через B2. Мост B5может быть достигнут за два шага через B3.Чтобы найти эти кратчайшие пути, мосты включают в конфигурационные сообщения расстояние от корня.

Каждый мост помнит кратчайший путь, который он находитк корню. Затем мосты отключают порты, которые не являются частью кратчайшегопути.Хотя дерево охватывает все мосты, но не все соединения (или даже мосты) обязательно присутствуют в дереве. Это происходит, потому что отключение портовликвидирует некоторые соединения в сети, чтобы предотвратить появление циклов.Алгоритм построения дерева продолжает работать постоянно, обнаруживая измененияв топологии и обновляя структуру дерева.Автором распределенного алгоритма построения связующего дерева являетсяРадья Перлман (Radia Perlman).

Ее задачей было решить проблему объединениялокальных сетей без циклов. Ей была дана неделя на решение этой задачи, но она придумала идею алгоритма связующего дерева за один день, так что у нее осталось времяизложить ее в виде стихотворения (Perlman, 1985).I think that I shall never seeA graph more lovely than a tree.A tree whose crucial propertyIs loop-free connectivity.A tree which must be sure to span.So packets can reach every LAN.First the Root must be selectedBy ID it is elected.Least cost paths from Root are tracedIn the tree these paths are placed.A mesh is made by folks like meThen bridges find a spanning tree.Алгоритм связующего дерева стандартизован как IEEE 802.1D и используется ужемного лет.

В 2001 году он был пересмотрен для более быстрого нахождения новогосвязующего дерева после изменения топологии. Для более подробного рассмотрениямостов см. Perlman (2000).4.8.4. Повторители, концентраторы, мосты,коммутаторы, маршрутизаторы и шлюзыМы уже успели в нашей книге рассмотреть множество способов доставки кадров и пакетов из одного компьютера в другой.

Мы упоминали повторители, концентраторы, мосты, маршрутизаторы и шлюзы. Все эти устройства используются очень широко, однаков чем-то они отличаются едва уловимо, а в чем-то весьма существенно. Число их весьмавелико, поэтому лучше рассмотреть их все в совокупности, отмечая сходства и различия.4.8.

Коммутация на канальном уровне  369Чтобы понять, как работают эти устройства, надо осознать, что они работают наразных уровнях, как показано на рис. 4.42, а. Уровень имеет значение, поскольку отэтого зависит, какую часть информации устройство использует для маршрутизации.Типичный сценарий таков: у пользователя появляются какие-то данные, которыенеобходимо отправить на удаленную машину.

Они передаются на транспортный уровень, который добавляет к ним свой заголовок (например, заголовок TCP) и передаетрезультирующую единицу информации на сетевой уровень. Тот, в свою очередь, тожедобавляет свой заголовок, в результате чего формируется пакет сетевого уровня (например, IP-пакет). На рис. 4.42, б IP-пакет выделен серым цветом. Пакет отправляетсяна канальный уровень, где обрастает еще одним заголовком и контрольной суммой(CRC).

Наконец, формируется кадр, который спускается на физический уровеньи может быть передан, например, по ЛВС.Рис. 4.42. Соответствие устройств уровням (а); кадры, пакеты и заголовки (б)Приступим к рассмотрению коммутирующих устройств и взглянем на то, как онисоотносятся с пакетами и кадрами. На самом нижнем, физическом уровне работаютповторители. Это аналоговые устройства, к которым подсоединяются концы двухсегментов кабеля. Сигнал, появляющийся на одном из них, очищается, усиливаетсяповторителем и выдается на второй. Повторители не знают слов «пакет», «кадр» или«заголовок».

Они знают символы, кодирующие биты в напряжение. В классическомEthernet, например, допускается установка четырех повторителей, что усилит сигнал,чтобы увеличить максимальную длину кабеля с 500 до 2500 м.Теперь обратимся к концентраторам. Концентратор имеет несколько входов, объединяемых электрически. Кадры, прибывающие на какой-либо вход, передаются навсе остальные линии.

Если одновременно по разным линиям придут два кадра, онистолкнутся, как в коаксиальном кабеле. Все линии, подсоединяемые к нему, должныработать с одинаковыми скоростями. Концентраторы отличаются от повторителейтем, что они обычно не усиливают входные сигналы, поскольку предназначены не370   Глава 4. Подуровень управления доступом к средедля этого. Их задача — обеспечивать согласованную работу с несколькими входами,к которым подключаются линии с похожими<b>Текст обрезан, так как является слишком большим</b>.