В общем случае, ретрансляторы на некотором уровне могут переписать заголовки для этого уровня. ВЛВС вскоре обеспечит пример. Мост ни в коем случае не должен смотреть внутрь кадра и узнавать, что он переносит IP-пакет; это не важно для обработки мостом и нарушило бы иерархическое представление протокола. Также отметьте, что мост, имеющий k портов, будет иметь k экземпляров MAC-уровней и физических уровней. В нашем простом примере k = 2.
4.8.3. Мосты связующего дерева
Для повышения надежности между мостами можно использовать избыточные соединения. На рис. 4.40 показаны два параллельных соединения между двумя мостами. Эта конструкция гарантирует, что, если одно соединение нарушено, сеть не будет разделена в два набора компьютеров, которые не могут говорить друг с другом.
Рис. 4.40. Мосты с двумя параллельными соединениями
Такое решение, впрочем, создает некоторые дополнительные проблемы, поскольку в топологии образуются кольца. В качестве примера, иллюстрирующего указанные проблемы, рассмотрим кадр, отправленный А с ранее неизвестным адресом назначения (рис. 4.40). Каждый мост, действуя по обычным правилам обработки кадров с неизвестным получателем, использует метод заливки. В данном примере это означает, что кадр из А попадает к мосту В1, F0 . Мост посылает копии этого кадра во все остальные свои порты. Мы рассмотрим только порты, соединяющие В1 и В2 (хотя кадр будет послан и в другие). Так как из В1 в В2 есть два соединения, в В2 попадут две копии кадра. Они показаны на рис. 4.40 как F1 и F2 .
Вскоре после этого мост В1 получает эти кадры. Разумеется, он не знает (и не может знать), что это копии одного кадра, а не два разных кадра, посланных один за другим. Поэтому мост В2 отправляет копии кадра F1 во все свои порты. Так возникают F3 и F4, которые по двум соединениям отправляются обратно в В1. Мост В1 видит два новых кадра с неизвестным адресом назначения и копирует их снова. Этот цикл продолжается вечно.
Решение данной проблемы заключается в установлении связи между мостами и наложении на реальную топологию сети связующего дерева (spanning tree), до-
стигающего каждого моста. В результате некоторые возможные соединения между мостами игнорируются с целью создания фиктивной бескольцевой топологии, которая является подмножеством реальной топологии.
Например, на рис. 4.41 показаны пять мостов, которые связаны и имеют соединенные с ними станции. Каждая станция соединяется только с одним мостом. Есть некоторые избыточные соединения между мостами, так что если будут использоваться все соединения, кадры будут отправлены в циклы.
Эта система может быть представлена в виде графа с мостами в качестве узлов и соединениеми между ними —в качестве ребер. Такой граф можно редуцировать до связующего дерева, которое по определению не имеет циклов, удалив из него соединения, изображенные на рис. 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). Наконец, формируется кадр, который спускается на физический уровень и может быть передан, например, по ЛВС.
