показано, как работает алгоритм пересылки в обратном направлении. На первом транзитном участке маршрутизатор I отсылает пакеты маршрутизаторам F, H, J и N, являющимся вторым ярусом дерева. Все пакеты приходят к ним

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

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

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

Последний алгоритм широковещания, который мы рассмотрим, является развитием предыдущего метода. Он в явном виде использует входное дерево (или любое другое связующее дерево) для маршрутизатора, который начал широковещание. Связующее дерево (spanning tree) представляет собой подмножество сети, в котором находятся все маршрутизаторы и нет замкнутых путей. Если маршрутизатор знает, какие из его линий принадлежат связующему дереву, он может отправить пакет по всем его ветвям (кроме той, по которой пришли данные). Алгоритм обеспечивает отличную пропускную способность, так как для его выполнения требуется генерация абсолютного минимума пакетов. Например, если в качестве связующего дерева использовать входное дерево на илл. 5.15 (б), для рассылки потребуется минимальное число пакетов — 14. Единственный минус — у каждого маршрутизатора должна быть информация о связующем дереве. Иногда эти данные доступны (например, при маршрутизации с учетом состояния линий все маршрутизаторы обладают полными сведениями о топологии сети и могут вычислить связующее дерево), но в некоторых случаях — недоступны (к примеру, при маршрутизации по вектору расстояний).

5.2.8. Многоадресная рассылка

Иногда пакеты отправляются группе получателей, например, в многопользовательских играх или при спортивных трансляциях на несколько точек просмотра. Если группа не слишком мала, передача отдельного пакета на каждый адрес — дорогостоящая операция. С другой стороны, в миллионной сети широковещание на группу из 1000 устройств также нерентабельно, особенно если большинство получателей не заинтересованы в данной информации (или, что еще хуже, заинтересованы, но не должны иметь к ней доступа, как в случае платных спортивных каналов). Таким образом, требуется способ рассылки сообщений строго определенным группам — довольно крупным, но небольшим по сравнению со всей сетью.

Передача сообщения членам такой группы называется многоадресной рассылкой (multicasting), а используемый при этом алгоритм — многоадресной маршрутизацией (multicast routing). Любая схема многоадресной рассылки предполагает возможность создания и удаления групп и определения списка маршрутизаторов, входящих в группу. Для алгоритма не имеет значения, как именно реализуются эти задачи. Пока что мы будем считать, что группа определяется по адресу рассылки, а каждый маршрутизатор знает, в какие группы он входит. Мы еще вернемся к вопросу принадлежности к группам, когда будем говорить о многоадресной интернет-рассылке в разделе 5.7.8.

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

Для плотных групп широковещание подходит — пакет будет успешно отправлен по всей сети. Минус этого алгоритма в том, что пакет получат маршрутизаторы вне группы. Диринг и Черитон (Deering and Cheriton, 1990) предложили удалять из связующего дерева ветви, не ведущие к членам группы. В результате получается эффективное многоадресное связующее дерево.

Для примера рассмотрим две группы, 1 и 2, в сети, изображенной на илл. 5.16 (а). Разные маршрутизаторы подключены к хостам, которые входят в одну или обе группы или не входят ни в одну из них. Связующее дерево для самого левого маршрутизатора показано на илл. 5.16 (б). Это дерево можно использовать для широковещания, однако (как это видно на примере двух усеченных вариантов дерева, приведенных далее) для многоадресной рассылки оно избыточно. На илл. 5.16 (в) удалены все линии, не ведущие к хостам, входящим в группу 1. В результате получается многоадресное связующее дерево, по которому самый левый маршрутизатор может отправлять пакеты группе 1. Пакеты передаются исключительно по нему — этот способ гораздо экономичнее, чем широковещание, так как новое дерево использует 7 соединений вместо 10. На илл. 5.16 (г) показано усеченное многоадресное связующее дерево для группы 2. Оно использует 5 соединений, что также делает его эффективным. Следует обратить внимание на то, что для разных групп используются разные связующие деревья.

Илл. 5.16. Многоадресная рассылка. (а) Сеть. (б) Связующее дерево для самого левого маршрутизатора. (в) Многоадресное дерево для группы 1. (г) Многоадресное дерево для группы 2

Существует несколько способов усечения связующего дерева. Самый простой из них может применяться при маршрутизации с учетом состояния линий, когда каждому маршрутизатору известна полная топология сети, в том числе и состав групп. В этом случае каждый маршрутизатор может построить собственное усеченное связующее дерево для каждого отправителя. Сначала создается обычное входное дерево, а затем из него удаляются все связи, не соединяющие входной (корневой) узел с членами данной группы. Одним из протоколов маршрутизации с учетом состояния линий, работающих по такому принципу, является MOSPF (Multicast OSPF — многоадресный OSPF) (Мой; Moy, 1994).

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