Рис. 5.13. Продвижение по встречному пути: а — сеть; б — входное дерево; в — дерево, построенное методом продвижения по встречному пути

Пример работы алгоритма продвижения по встречному пути показан на рис. 5.13. Слева изображена сеть, посередине — входное дерево для маршрутизатора I этой сети. На первом транзитном участке маршрутизатор I посылает пакеты маршрутизаторам F, H, J и N, являющимся вторым ярусом дерева. Все эти пакеты прибывают к ним по предпочитаемым линиям до I (по пути, совпадающему с входным деревом), что обозначается кружками вокруг символов на рис. 5.13, в. На втором этапе пересылки формируются восемь пакетов — по два каждым маршрутизатором, получившим пакет после первой пересылки. Все восемь пакетов попадают к маршрутизаторам, не получавшим ранее пакетов, а пять из них приходят по предпочитаемым линиям. Из шести пакетов, формируемых на третьем транзитном участке, только три прибывают по предпочитаемым линиям (на маршрутизаторы C, E и K). Остальные оказываются дубликатами. После пяти транзитных участков широковещание заканчивается с общим количеством переданных пакетов, равным 23, тогда как при использовании входного дерева потребовалось бы 4 транзитных участка и 14 пакетов.

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

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

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

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

Передача сообщения членам такой группы называется многоадресной рассылкой (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).