Эндрю Уэзеролл - Компьютерные сети. 5-е издание

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

Рис. 4.41. Связующее дерево, соединяющее пять мостов. Пунктирными линиями показаны соединения, которые не входят в связующее дерево

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

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

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

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

Хотя дерево охватывает все мосты, но не все соединения (или даже мосты) обязательно присутствуют в дереве. Это происходит, потому что отключение портов ликвидирует некоторые соединения в сети, чтобы предотвратить появление циклов. Алгоритм построения дерева продолжает работать постоянно, обнаруживая изменения в топологии и обновляя структуру дерева.

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

I think that I shall never see A graph more lovely than a tree.

A tree whose crucial property Is loop-free connectivity.

A tree which must be sure to span.

So packets can reach every LAN.

First the Root must be selected By ID it is elected.

Least cost paths from Root are traced In the tree these paths are placed.

A mesh is made by folks like me Then bridges find a spanning tree.

Алгоритм связующего дерева стандартизован как IEEE 802.1D и используется уже много лет. В 2001 году он был пересмотрен для более быстрого нахождения нового связующего дерева после изменения топологии. Для более подробного рассмотрения мостов см. Perlman (2000).

4.8.4. Повторители, концентраторы, мосты, коммутаторы, маршрутизаторы и шлюзы

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

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

Рис. 4.42. Соответствие устройств уровням (а); кадры, пакеты и заголовки (б)

Приступим к рассмотрению коммутирующих устройств и взглянем на то, как они соотносятся с пакетами и кадрами. На самом нижнем, физическом уровне работают повторители. Это аналоговые устройства, к которым подсоединяются концы двух сегментов кабеля. Сигнал, появляющийся на одном из них, очищается, усиливается повторителем и выдается на второй. Повторители не знают слов «пакет», «кадр» или «заголовок». Они знают символы, кодирующие биты в напряжение. В классическом Ethernet, например, допускается установка четырех повторителей, что усилит сигнал, чтобы увеличить максимальную длину кабеля с 500 до 2500 м.

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

для этого. Их задача — обеспечивать согласованную работу с несколькими входами, к которым подключаются линии с похожими параметрами. Впрочем, во всем остальном хабы не очень отличаются от повторителей. И те и другие являются устройствами физического уровня, они не анализируют адреса уровня каналов и не используют их.