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