Передача сообщения членам такой группы называется многоадресной рассылкой (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 (отсечь). Так он сообщает о том, что пакеты для данной группы ему больше отправлять не нужно. Такой же ответ может дать маршрутизатор, у которого нет хостов, входящих в группу, если он получил сообщение PRUNE по всем линиям, по которым осуществил многоадресную рассылку. В результате связующее дерево постепенно рекурсивно усекается. Примером протокола многоадресной маршрутизации, работающего по такому принципу, является DVRMP (Distance Vector Multicast Routing Protocol — протокол многоадресной маршрутизации по вектору расстояний) (Вайцман и др.; Waitzman et al., 1988).

Усечение позволяет строить эффективные связующие деревья, состоящие только из тех соединений, которые необходимы для связи с членами группы. Недостаток данного метода в том, что он требует от маршрутизаторов выполнения большого количества операций, особенно в крупных сетях. Предположим, что в сети есть n групп, каждая из которых в среднем состоит из m членов. Каждый маршрутизатор должен хранить m усеченных связующих деревьев для каждой группы, то есть mn деревьев для всей сети. К примеру, на илл. 5.16 (в) изображено связующее дерево, используемое самым левым маршрутизатором для связи с группой 1. Дерево, по которому самый правый маршрутизатор отправляет пакеты группе 1 (оно не показано на рисунке), выглядит по-другому, поскольку пакеты передаются непосредственно членам группы, а не через узлы в левой части графа. Это значит, что выбор направления, в котором маршрутизаторы должны передавать пакеты для группы 1, зависит от того, какой узел является отправителем. При большом количестве групп и отправителей для хранения всех деревьев потребуется много памяти.

Для построения отдельного связующего дерева для группы можно использовать деревья с корнем в ядре (core-based trees) (Балларди и др.; Ballardie et al., 1993). Согласно этому методу все маршрутизаторы выбирают общий корень, также называемый ядром (core) или точкой встречи (rendezvouz point). Чтобы построить дерево, все члены группы передают в этот корень специальный пакет. Конечное дерево формируется из маршрутов, пройденных пакетами. На илл. 5.17 (а) показано дерево с корнем в ядре для группы 1. Для пересылки пакета этой группе отправитель передает сообщение ядру, откуда оно уже рассылается по дереву. Пример работы алгоритма продемонстрирован на илл. 5.17 (б) для отправителя, расположенного в правой части сети. Однако производительность этого метода может быть улучшена. Дело в том, что для многоадресной рассылки не требуется, чтобы пакеты для группы приходили в ядро. Как только пакет достигает дерева, он может быть передан как в направлении корня дерева, так и по любой его ветви. Так алгоритм работает для отправителя, расположенного вверху илл. 5.17 (б).

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