Усечение позволяет строить эффективные связующие деревья, состоящие только из тех соединений, которые необходимы для связи с членами группы. Недостаток данного метода в том, что он требует от маршрутизаторов выполнения большого количества операций, особенно в крупных сетях. Предположим, что в сети есть 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 мы завершим рассмотрение темы, обсудив механизмы управления перегрузками на транспортном уровне.
На илл. 5.19 показано, как начинается перегрузка. Когда количество отправляемых хостами пакетов намного ниже пропускной способности сети, объем доставленного трафика пропорционален объему переданного (в два раза больше отправлено — в два раза больше получено). Но если число пакетов приближается к пределу емкости, при эпизодических всплесках трафика буферы маршрутизаторов переполняются; в итоге некоторые пакеты теряются. Потерянные пакеты расходуют часть пропускной способности, поэтому объем доставленного трафика оказывается ниже идеальной кривой. Таким образом, в сети возникает перегрузка.
Илл. 5.19. Перегрузка ведет к значительному падению производительности: возрастает частота потери пакетов, а также величина задержки, поскольку очереди маршрутизатора заполнены пакетами
В определенный момент может возникнуть коллапс сети из-за перегрузки (congestion collapse), при котором производительность падает, поскольку абонентская нагрузка превышает пропускную способность. Коллапс сети происходит, когда увеличение нагрузки фактически ведет к уменьшению объема успешно доставленного трафика. При этом пакеты настолько задерживаются, что становятся бесполезными к моменту их доставки. Например, на ранних этапах существования интернета время, которое пакет проводил в очереди на отправку (при скорости 56 Кбит/с), зачастую превышало время его пребывания в сети. В результате пакет приходилось удалять. Еще один неприятный сценарий — когда отправители повторно передают сильно задержанные пакеты, полагая, что они утеряны. В этом случае пропускная способность используется неэффективно, поскольку по сети передаются копии одного и того же пакета. Чтобы продемонстрировать влияние этих факторов на производительность, мы отобразили на оси y (см. илл. 5.19) полезную пропускную способность (goodput), то есть скорость, с которой по сети передаются полезные пакеты.
В идеале сеть должна быть устроена так, чтобы перегрузки происходили как можно реже и чтобы в этих ситуациях не возникало коллапсов. К сожалению, в сети с коммутацией пакетов перегрузку невозможно полностью исключить. Если потоки пакетов внезапно начинают прибывать на маршрутизатор сразу по трем или четырем входным линиям и всем им нужна одна и та же выходная линия, то образуется очередь. Если у маршрутизатора заканчивается память для буферизации пакетов, они теряются. Увеличение объема памяти может в какой-то степени помочь, однако Нейгл (Nagle) в 1987 году установил, что при бесконечной памяти маршрутизаторов ситуация с перегрузкой часто не улучшается, а, наоборот, ухудшается. Последние исследования показали, что многие сетевые устройства имеют больше памяти, чем требуется. Это явление получило название излишней сетевой буферизации (bufferbloat). Такие устройства могут снижать производительность сети, чему есть несколько объяснений. Во-первых, за то время, пока пакеты добираются до начала очереди, срок их ожидания истекает (и даже несколько раз) и производится отправка их дубликатов. Во-вторых, отправителей нужно своевременно уведомлять о перегрузках (о чем мы подробнее поговорим в главе 6). Если пакеты не будут удалены, а останутся в буферах маршрутизатора, то отправители продолжат отправку перегружающего сеть трафика. В результате ситуация ухудшится: произойдет коллапс сети. Линии с низкой пропускной способностью или маршрутизаторы, у которых скорость обработки пакетов ниже емкости канала, также могут быть перегружены. Если на других участках сети пропускная способность выше, проблему можно решить, направив туда часть трафика в обход узкого места. Но в конечном итоге увеличение трафика может привести к повсеместной перегрузке. В этом случае операторы сетей могут применить два подхода: сброс нагрузки (то есть игнорирование трафика) или увеличение пропускной способности.