Илл. 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.
Приступим к рассмотрению коммутирующих устройств и разберемся, как они соотносятся с пакетами и фреймами. На самом нижнем, физическом, уровне находятся повторители. Это аналоговые устройства, которые работают с сигналами, идущими по подключенным к ним кабелям.
Илл. 4.37. (а) Уровни и расположенные на них устройства. (б) Фреймы, пакеты и заголовки
Сигнал, появившийся в одном кабеле, очищается, усиливается повторителем и выдается на второй. Повторители не знают, что такое пакет, фрейм или заголовок. Они знают символы, кодирующие биты в напряжение. В классическом Ethernet, например, допускается установка четырех повторителей для усиления сигнала, чтобы увеличить максимальную длину кабеля с 500 до 2500 м.
Теперь перейдем к концентраторам. Концентратор имеет несколько входных линий, объединяемых с помощью электричества. Фреймы, приходящие на какой-либо вход, передаются на все остальные линии. Если одновременно по разным линиям придут два фрейма, они столкнутся, как в коаксиальном кабеле. Все линии, идущие в концентратор, должны работать с одинаковой скоростью. Концентраторы отличаются от повторителей тем, что, как правило, не усиливают входной сигнал и предназначены для нескольких входных линий. Впрочем, разница между ними незначительна. И те и другие являются устройствами физического уровня; они не анализируют адреса канального уровня и никак не используют их.
Далее мы поднимемся на канальный уровень. Здесь расположены мосты и коммутаторы. Только что мы довольно подробно обсудили мосты, поэтому знаем, что они соединяют две или несколько LAN. Как и в концентраторах, в современных мостах имеются несколько портов, рассчитанных обычно на 4–48 входящих линий определенного типа. В отличие от концентратора, каждый порт изолирован, чтобы быть своей собственной областью коллизий; если у порта есть полнодуплексная двухточечная линия, в алгоритме CSMA/CD нет необходимости. Когда приходит фрейм, мост извлекает из заголовка адрес назначения и анализирует его, сопоставляя с таблицей и определяя, куда нужно его передать. Для Ethernet этот адрес — 48-битный адрес назначения (см. илл. 4.14). Мост только выводит фрейм на нужный порт; он может передавать несколько фреймов одновременно.
Мосты предлагают гораздо более высокую производительность, чем концентраторы, а благодаря изолированным портам входные линии могут работать на разных скоростях и даже с различными типами сетей. Распространенный пример — мост с портами, которые соединяются с 10-, 100 и 1000-Мбит/с Ethernet. Чтобы мост мог принять фрейм на одном порте и передать его на другой, необходима буферизация. Если фреймы приходят быстрее, чем передаются дальше, мост может исчерпать буферное пространство и начать отказываться от фреймов. Например, если Gigabit Ethernet заливает биты в 10-Мбит/с Ethernet на большой скорости, мост должен буферизовать их, надеясь, что памяти хватит. Эта проблема существует, даже если все порты работают на одной и той же скорости, потому что фреймы могут передаваться в порт назначения из нескольких портов.
Первоначально мосты предназначались для того, чтобы соединять разные виды LAN, например Ethernet и Token Ring. Однако из-за отличий между LAN это не сработало. Для фреймов различных форматов необходимо копирование и переформатирование. Это занимает время CPU, требует нового вычисления контрольной суммы и ведет к появлению необнаруженных ошибок из-за поврежденных битов в памяти моста. Еще одна серьезная проблема, не имеющая хорошего решения, — разная максимальная длина фреймов. По сути, слишком длинные для дальнейшей передачи фреймы должны быть отклонены. С идеей прозрачности можно распрощаться.
Еще две сферы, в которых LAN могут различаться, — это безопасность и QoS. У некоторых LAN (например, у 802.11) есть шифрование канального уровня и функции QoS (такие, как приоритеты), у других (например, у Ethernet) этого нет. Следовательно, при обмене между такими LAN трудно обеспечить безопасность или QoS, ожидаемые отправителем. По этой причине современные мосты обычно работают с сетями одного типа, а для соединения разных сетей используются маршрутизаторы, которые мы обсудим позже.
Коммутаторы — это другое название современных мостов. Различия больше связаны с маркетингом, чем с техническими особенностями, но есть несколько важных моментов. Мосты были разработаны, когда использовался классический Ethernet, поэтому они могут соединять относительно небольшое число LAN, а значит, имеют не так много портов. Сегодня чаще употребляется термин «коммутатор». Кроме того, все современные системы используют двухточечные линии, например витую пару. Отдельные компьютеры подключаются непосредственно к коммутатору, поэтому у него, как правило, много портов. Наконец, понятие «коммутатор» также используется в качестве общего термина. Функционал моста понятен. А вот слово «коммутатор» может относиться и к коммутатору Ethernet, и к совершенно другому устройству, принимающему решения о переадресации, например телефонному коммутатору.
Итак, мы кратко обсудили повторители и концентраторы, весьма схожие между собой, а также коммутаторы и мосты, между которыми еще меньше различий. Теперь перейдем к маршрутизаторам. Они существенно отличаются от рассмотренных выше устройств. Когда пакет приходит в маршрутизатор, заголовок и трейлер фрейма удаляются, а сам пакет, расположенный в поле данных (выделены серым на илл. 4.37), передается программному обеспечению маршрутизатора. Далее анализируется заголовок пакета и в соответствии с ним выбирается его дальнейший путь. Если это IP-пакет, то в его заголовке содержится 32-битный (IPv4) или 128-битный (IPv6), но не 48-битный IEEE 802 адрес. ПО маршрутизатора не видит адреса фреймов и даже не знает, как они пришли, по LAN или по двухточечной линии. Более подробно мы изучим маршрутизаторы и принципы маршрутизации в главе 5.