Эндрю Уэзеролл - Компьютерные сети. 5-е издание

Передача сообщения членам такой группы называется многоадресной рассылкой (multicasting), а использующийся при этом алгоритм — многоадресной маршрутизацией (multicast routing). Любая схема многоадресной рассылки предполагает возможность создания и удаления групп и определения списка маршрутизаторов, являющихся членами данной группы. Реализация данных задач, однако, не интересует алгоритм маршрутизации. Пока мы будем считать, что каждая группа определяется адресом рассылки и что каждый маршрутизатор знает, в какие группы он входит. Мы вернемся к вопросу принадлежности к группам, когда будем говорить о сетевом уровне Интернета в разделе 5.6. Схемы многоадресной рассылки основываются на принципах широковещательной маршрутизации, о которой мы уже говорили: пакеты, предназначенные членам группы, пересылаются по связующему дереву, и при этом ставится задача эффективного использования пропускной способности сети. Однако выбор наилучшего связующего дерева зависит от того, является ли группа плотной (когда получатели занимают большую часть всей сети) или разреженной (когда большая часть сети не принадлежит группе). В этом разделе мы рассмотрим оба случая.

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

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

Рис. 5.14. Многоадресная рассылка: а — сеть; б — связующее дерево для самого левого маршрутизатора; в — многоадресное дерево для группы 1; г — многоадресное дерево

для группы 2

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

При маршрутизации по векторам расстояний может быть применена другая стратегия усечения дерева. Для многоадресной рассылки здесь применяется алгоритм продвижения по встречному пути. Когда многоадресное сообщение получает маршрутизатор, у которого нет хостов, входящих в группу, и линий связи с другими маршрутизаторами, принимающими сообщения для данной группы, он может ответить сообщением PRUNE (отсечь), информируя соседа, отправившего сообщение, о том, что сообщения для данной группы ему больше посылать не нужно. Такой же ответ может дать маршрутизатор, у которого нет хостов, входящих в группу, если он получил сообщение PRUNE по всем линиям, по которым он осуществил многоадресную рассылку. В результате связующее дерево постепенно рекурсивно усекается. Примером протокола многоадресной маршрутизации, работающего по такому принципу, является DVRMP( Distance Vector Multicast Routing Protocol— протокол многоадресной маршрутизации по вектору расстояний) (Waitzman и др., 1988).

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

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