Компьютерные сети. 6-е изд. - Эндрю Таненбаум

друг с другом.

Илл. 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):

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

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

Чтобы разобраться, как работают упомянутые устройства, надо понять, что они задействованы на разных уровнях, как показано на илл. 4.37 (а). Уровень имеет значение, поскольку от него зависит, какую часть информации устройство использует для маршрутизации. Рассмотрим типичный сценарий. У пользователя появляются данные (User data), которые необходимо отправить на другой компьютер. Они передаются на транспортный уровень, который добавляет к ним свой заголовок (например, TCP header) и передает полученную единицу информации на сетевой уровень. Тот, в свою очередь, тоже добавляет свой заголовок (Packet header), в результате чего формируется пакет сетевого уровня (например, IP-пакет). На илл. 4.37 (б) IP-пакет выделен серым цветом. Пакет отправляется на канальный уровень, где дополняется еще одним заголовком (Frame header) и контрольной суммой (CRC). Наконец, формируется фрейм, который спускается на физический уровень для передачи, например, по LAN.

Приступим к рассмотрению коммутирующих устройств и разберемся, как они соотносятся с пакетами и фреймами. На самом