При маршрутизации по вектору расстояний может применяться другая стратегия усечения дерева. Для многоадресной рассылки здесь используется пересылка в обратном направлении. Когда многоадресное сообщение приходит на маршрутизатор, у которого нет хостов, входящих в группу (или соединений с другими маршрутизаторами, принимающими сообщения для группы), он может ответить сообщением 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 (б) пакет от отправителя в правой части сети достигает правого верхнего участника группы не напрямую, а через ядро, что требует трех переходов. Степень неэффективности зависит от взаимного расположения ядра и отправителей; чаще всего разумно располагать ядро посередине между отправителями. Если источник всего один (как, например, при видеотрансляции), лучше использовать в качестве ядра самого отправителя.
Илл. 5.17. (а) Дерево с корнем в ядре для группы 1. (б) Рассылка для группы 1
Следует отметить, что использование общего дерева позволяет существенно снизить затраты на хранение информации, а также уменьшить число отправленных сообщений и объем вычислений. Для каждой группы маршрутизатор должен хранить не m деревьев, а лишь одно. Кроме того, маршрутизаторы, не являющиеся частью дерева, не участвуют в передаче сообщений группе. Поэтому алгоритмы на основе общих деревьев (в частности, деревьев с корнем в ядре) используются при широковещании для разреженных групп в сети интернет. Они входят в такие популярные протоколы, как PIM (Protocol Independent Multicast — многоадресная рассылка, не зависящая от протокола) (Феннер и др.; Fenner et al., 2006).
5.2.9. Произвольная маршрутизация
До сих пор мы рассматривали модели предоставления информации, в которых источник отправляет сообщение на один адрес (одноадресная рассылка — unicast), на все адреса (широковещание) или группе адресов (многоадресная рассылка). Существует еще одна модель под названием произвольная рассылка (anycast), когда пакет отправляется ближайшему члену группы (Партридж и др.; Partridge et al., 1993). Методы поиска путей в этом случае называются произвольной маршрутизацией (anycast routing).
Зачем нужна произвольная рассылка? Иногда узлы предоставляют услугу (например, сообщают время суток или передают контент), для которой важно одно: чтобы информация была правильной; при этом не имеет значения, какой узел ее предоставил — с этой задачей справится любой из них. Пример использования свободной рассылки в интернете — DNS, о которой мы поговорим в главе 7.
К счастью, нам не придется придумывать новые алгоритмы для произвольной маршрутизации: стандартные методы — маршрутизация по вектору расстояния и маршрутизация с учетом состояния линий — позволяют строить пути для произвольной рассылки. Предположим, что нам нужно передать данные группе 1. Вместо разных адресов все ее участники получат одинаковый адрес — «1». Алгоритм маршрутизации по вектору расстояния распределит векторы обычным способом, и узлы выберут кратчайший путь к адресу 1. В результате узлы отправят данные на ближайшее устройство с таким адресом. Эти пути показаны на илл. 5.18 (а). Данный метод работает, поскольку протокол маршрутизации не знает о существовании нескольких устройств с адресом 1 и считает их одним узлом, как показано в топологии на илл. 5.18 (б).
Илл. 5.18. Произвольная маршрутизация. (а) Маршруты для свободной рассылки. (б) Топология с точки зрения протокола маршрутизации
Такой метод будет работать и для маршрутизации с учетом состояния линий. Но следует отметить, что протокол не обязан находить кажущиеся кратчайшими пути, проходящие через узел 1. Это привело бы к «прыжку через гиперпространство», потому что экземпляры узла 1 на самом деле расположены в различных частях сети. Впрочем, современные протоколы маршрутизации с учетом состояния линий различают маршрутизаторы и хосты (о чем мы не упоминали, поскольку в этом не было необходимости).
5.3. Управление трафиком на сетевом уровне
Слишком большое количество пакетов в любой части сети может в конечном итоге привести к задержке и потере пакетов, что негативно скажется на производительности. Такая ситуация называется перегрузкой (congestion).
5.3.1. Необходимость в управлении трафиком: перегрузка
За борьбу с перегрузкой отвечают сетевой и транспортный уровни. Поскольку она происходит в сети, именно сетевой уровень сталкивается с ней непосредственно и определяет, что делать с лишними пакетами. Самое эффективное решение — уменьшить нагрузку на сеть со стороны транспортного уровня; это значит, что оба уровня должны работать вместе. Сетевой уровень не может автоматически устранить перегрузку. Но операторы сетей могут настроить маршрутизаторы, коммутаторы и другие устройства этого уровня так, чтобы они смягчали ее последствия. Как правило, они заставляют источник снизить скорость отправки или направляют трафик по другим, менее загруженным путям. В этой главе мы рассмотрим вопросы перегрузки, связанные с сетевым уровнем, и механизмы, которые он применяет для борьбы с ней. Для описания функций транспортного уровня в литературе часто используется более общее понятие «контроль перегрузок». Во избежание путаницы здесь мы будем говорить об управлении перегрузками (congestion management) или управлении трафиком (traffic management), понимая под этим методы, применяющиеся на сетевом уровне. В главе 6 мы завершим рассмотрение темы, обсудив механизмы управления перегрузками на транспортном уровне.