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

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

Последний алгоритм широковещательной маршрутизации выигрывает перед алгоритмом продвижения по встречному пути. Он в явном виде использует входное дерево или любое другое связующее дерево для маршрутизатора, инициировавшего широковещание. Связующее дерево (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 связей, что доказывает его эффективность. Следует обратить внимание на то, что для разных групп используются разные связующие деревья.