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

Более совершенный алгоритм называется многоадресной маршрутизацией (multidestination routing). В каждом пакете содержится либо список адресатов, либо битовая карта с указанием нужных получателей. Когда приходит такой пакет, маршрутизатор проверяет список и определяет набор необходимых исходящих линий. (Линия выбирается, если это оптимальный путь хотя бы к одному адресату из списка.) Маршрутизатор создает копию пакета для каждой выбранной линии. В ней указаны только те адресаты, к которым ведет данный путь. Таким образом, весь список рассылки распределяется между исходящими линиями. После определенного числа передач каждый пакет будет содержать только один адрес назначения, как и обычный пакет. Многоадресная маршрутизация похожа на рассылку индивидуально адресованных пакетов. Разница в том, что в первом случае из нескольких пакетов, следующих по одному маршруту, только один «платит полную стоимость», а остальные «едут бесплатно». Таким образом, пропускная способность используется более эффективно. Однако этот метод все же требует начальных сведений обо всех получателях, а чтобы понять, куда отправить один многоадресный пакет, маршрутизатор должен выполнить столько же действий, сколько и при отправке набора отдельных пакетов.

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

Удивительно простая и изящная концепция пересылки в обратном направлении (reverse path forwarding) была впервые предложена в работе Далала и Меткалфа (Dalal and Metcalfe, 1978). Когда приходит широковещательный пакет, маршрутизатор проверяет, используется ли канал, по которому он прибыл, для обычной передачи данных источнику широковещания. Если это так, то, скорее всего, пакет пришел по наилучшему пути и является первой копией, полученной маршрутизатором. Тогда он рассылает этот пакет по всем линиям (кроме той, по которой он пришел). Но если пакет приходит от того же источника по другому каналу, он отвергается как вероятный дубликат.

Пример работы этого алгоритма представлен на илл. 5.15. Слева (а) изображена сеть, в центре (б) — входное дерево для маршрутизатора I этой сети, а справа (в) показано, как работает алгоритм пересылки в обратном направлении. На первом транзитном участке маршрутизатор I отсылает пакеты маршрутизаторам F, H, J и N, являющимся вторым ярусом дерева. Все пакеты приходят к ним

Илл. 5.15. Продвижение по встречному пути. (а) Сеть. (б) Входное дерево для маршрутизатора I. (в) Дерево, построенное методом пересылки в обратном направлении от маршрутизатора I

по приоритетной линии до I (по маршруту, совпадающему с входным деревом); на рисунке это обозначено буквами в кружках. Затем формируются 8 пакетов — по 2 каждым маршрутизатором, получившим пакет на первом этапе. Все они попадают к маршрутизаторам, еще не получавшим пакеты; 5 из них приходят по приоритетным линиям. Из 6 пакетов, формируемых на третьем транзитном участке, только 3 приходят по приоритетным линиям (на C, E и K). Остальные оказываются дубликатами. После 5 переходов широковещание заканчивается; общее число переданных пакетов — 23. При использовании входного дерева потребовалось бы 4 перехода и 14 пакетов.

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