В мосте фрейм передается с физического уровня на уровень MAC Ethernet. Здесь фрейм обрабатывается дольше, чем на аналогичном уровне станции. Он передается на ретранслятор, все еще в пределах уровня MAC. Функция ретрансляции в мосте использует только заголовок MAC Ethernet, чтобы определить, как обработать фрейм. В нашем случае фрейм передается порту уровня MAC Ethernet, который связан со станцией D, и продолжает свой путь.

В общем случае ретрансляторы на конкретном уровне могут переписать для него заголовки. Позже будет показано, как это происходит в виртуальных LAN. Мост ни в коем случае не должен проверять содержимое фрейма и выяснять, что в нем находится IP-пакет. Для работы моста это значения не имеет, к тому же это нарушает иерархическое представление протокола. Обратите внимание, что мост, имеющий k портов, также включает k экземпляров MAC-уровня и физического уровня. В нашем простом примере k = 2.

4.7.3. Мосты связующего дерева

Для повышения надежности между мостами устанавливаются резервные соединения. На илл. 4.35 показаны два параллельных канала между В1 и В2. Эта конструкция гарантирует, что при разрыве одного соединения сеть не будет разделена на два набора компьютеров, которые не могут взаимодействовать друг с другом.

Илл. 4.35. Мосты с двумя параллельными соединениями

Впрочем, это создает некоторые дополнительные проблемы, поскольку в топологии возникают циклы. Рассмотрим следующий пример. Станция А отправляет фрейм в ранее неизвестный пункт назначения (илл. 4.35). Каждый мост, действуя по обычным правилам обработки фреймов с неизвестным получателем, использует метод лавинной адресации. Мост В1 получает фрейм от станции А. Обозначим его F0. Мост передает копии этого фрейма через все остальные порты. Мы рассмотрим только те из них, которые соединяют В1 и В2 (хотя фрейм будет отправлен и через другие). Так как между В1 и В2 имеется два соединения, в В2 попадут две копии фрейма. Они обозначены на илл. 4.35 как F1 и F2.

Вскоре после этого мост В2 получает их. Разумеется, он не знает (и не может знать), что это копии, а не два разных фрейма, отправленных друг за другом. Поэтому В2 принимает F1 и F2 и отправляет копии каждого из них со всех остальных портов. Так возникают фреймы F3 и F4, которые по двум соединениям отправляются обратно в В1. Мост В1 видит два новых фрейма с неизвестным адресом назначения и копирует их снова. Этот цикл продолжается бесконечно.

Эта проблема решается установлением связи между мостами и наложением на реальную топологию сети связующего дерева (spanning tree), которое охватывает оба моста. В результате некоторые потенциальные соединения между мостами игнорируются. Это позволяет создать фиктивную незацикленную топологию, которая является подмножеством реальной системы.

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

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

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

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

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

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

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

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