Компьютерные сети. 6-е изд.

Для примера на илл. 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):

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.7.4. Повторители, концентраторы, мосты, коммутаторы, маршрутизаторы и шлюзы

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