Компьютерные сети. 6-е изд.

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

Здесь уместно прояснить разницу между понятиями «контроль перегрузок» (congestion control), «управление трафиком» (traffic management) и «управление потоком» (flow control). Задача управления трафиком (или регулирования трафика) — гарантировать, что сеть справится с поступающим трафиком. Задача может решаться как устройствами в сети, так и отправителями (часто с использованием механизмов транспортного протокола, называемых методами контроля перегрузок). Управление перегрузками (или контроль перегрузок) касается поведения всех хостов и маршрутизаторов. Управление потоком, наконец, относится к трафику между конкретными отправителями и получателями. С его помощью регулируется скорость отправки данных: она не должна превышать максимально возможную скорость их получения. Задача управления потоком — не допустить потери данных из-за того, что отправитель обладает большей производительностью и его скорость превышает возможности адресата.

Чтобы понять разницу между этими понятиями, представьте сеть из 100-гигабитных оптоволоконных линий. Суперкомпьютер пытается передать большой файл персональному компьютеру, способному принимать данные со скоростью 1 Гбит/с. Хотя перегрузки в данной ситуации не наблюдается, алгоритм управления потоком периодически заставляет отправителя приостанавливать передачу, чтобы получатель успевал принимать трафик.

Приведем другой пример. Рассмотрим сеть из 1000 больших компьютеров, соединенных мегабитными линиями. Половина компьютеров пытается передать файлы остальным со скоростью 100 Кбит/c. Здесь проблема заключается уже не в том, что медленные получатели не успевают принимать данные от быстрых отправителей. Просто сеть не способна пропустить весь предлагаемый трафик.

Причина, по которой контроль перегрузок и управление потоком часто путают, заключается в том, что лучшее решение обеих проблем — добиться более медленной работы хоста. Таким образом, хост может получить просьбу снизить скорость в двух случаях: когда с потоком не справляется получатель или когда с ним не справляется вся сеть. Мы вернемся к этому вопросу в главе 6.

Мы начнем знакомство с управлением перегрузками с рассмотрения подходов, которые могут применяться сетевыми операторами в разных масштабах времени. Затем мы изучим методы предотвращения перегрузки, а также различные алгоритмы борьбы с ее последствиями.

5.3.2. Методы управления трафиком

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

Илл. 5.20. Временные рамки методов управления трафиком и перегрузками

Самый простой способ избежать перегрузки заключается в создании сети с достаточной пропускной способностью для передачи ожидаемого трафика. Если часть пути, по которому обычно пересылаются большие объемы данных, обладает низкой пропускной способностью, вероятность возникновения перегрузки довольно высока. Иногда при перегрузке возможно динамическое добавление ресурсов, например подключение свободных маршрутизаторов или резервных линий (для обеспечения устойчивости к ошибкам) либо же приобретение дополнительной пропускной способности на свободном рынке. Как правило, наиболее загруженные соединения и маршрутизаторы обновляются при первой возможности. Этот процесс называется обеспечением (provisioning) и происходит раз в несколько месяцев, в результате оценки долгосрочной динамики трафика.

Чтобы максимально использовать существующую пропускную способность сети, маршруты могут быть адаптированы к схемам трафика, которые меняются в течение дня, поскольку пользователи сети просыпаются и засыпают в разных часовых поясах. Например, можно обходить загруженные линии, меняя весовые коэффициенты кратчайшего пути. Некоторые радиостанции следят за ситуацией на дорогах с вертолетов и передают полученные сведения радиослушателям, чтобы те могли объехать пробки. Это называется маршрутизацией с учетом состояния трафика (traffic-aware routing). Так же можно разделять трафик, направляя его по разным линиям.

Иногда повысить пропускную способность невозможно, особенно за короткий срок. Тогда единственным выходом является снижение нагрузки.

В сети виртуальных каналов новые соединения отклоняются, если они могут привести к перегрузке сети. Это один из примеров управления допуском (admission control), при котором отправители просто лишаются возможности передавать трафик, если это превышает возможности сети.

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

В случае явного отклика маршрутизаторы должны участвовать в цикле обратной связи с отправителями. Чтобы данная схема работала, необходимо тщательно настроить временные параметры. Если каждый раз при одновременном получении двух пакетов маршрутизатор кричит «Стоп!», а простояв без работы 20 мкс, командует «Давай!», система будет находиться в состоянии постоянных незатухающих колебаний. И наоборот, если маршрутизатор для большей надежности станет ждать 30 минут, прежде чем что-либо сообщить, то механизм борьбы с перегрузкой будет реагировать слишком медленно, чтобы приносить хоть какую-то пользу. Своевременная доставка сообщений обратной связи не такая уж простая задача. Дополнительная проблема заключается в том, что маршрутизаторы отправляют больше сообщений, когда сеть уже и так перегружена.

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

Маршрутизация с учетом состояния трафика

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

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

Маршрутизация с учетом состояния трафика использовалась на ранних этапах развития интернета в рамках модели Кханны и Зинки (Khanna and Zinky, 1989). Однако здесь есть небольшая опасность. Рассмотрим сеть на илл. 5.21. Она разделена на две части — восток и запад, соединенные линиями CF и EI. Предположим, что основной трафик между западом и востоком проходит по CF, поэтому она слишком нагружена, что приводит к длительным задержкам. Учет времени ожидания в очереди при вычислении кратчайшего пути сделает линию EI более популярной. После внесения изменений в таблицы маршрутизации большая часть трафика пойдет по EI и слишком нагруженной окажется именно эта линия. При следующем обновлении таблиц кратчайшим путем снова станет CF. В конечном итоге значения в таблицах будут сильно колебаться, что приведет к ошибкам при выборе маршрутов и другим проблемам.

Илл. 5.21. Сеть, в которой восточная и западная части соединены двумя линиями связи

Если игнорировать нагрузку и учитывать только пропускную способность и задержку распространения, такой проблемы не возникнет. Попытки учесть нагрузку, используя узкий диапазон весовых значений, лишь замедляют колебания маршрутов. Удачное решение проблемы основывается на двух методах. Первый — это маршрутизация, при которой между отправителем и получателем существует несколько путей. В нашем примере это означает, что пакеты можно передавать по обеим линиям между востоком и западом. Второй метод состоит в следующем: схема маршрутизации перемещает трафик по маршрутам настолько медленно, чтобы он конвергировался; так, например, работает схема Галлагера (Gallager, 1977).

С учетом этих трудностей протоколы маршрутизации интернета обычно не корректируют пути на основании уровня нагрузки. Вместо этого операторы сетей настраивают протоколы в более широких временных рамках, плавно меняя конфигурацию и параметры маршрутизации, другими словами, регулируют трафик. Это всегда было трудоемким ручным процессом, чем-то напоминающим черную магию. Несмотря на попытки его формализации, он оставался достаточно примитивным в силу непредсказуемого характера нагрузки в интернете и некоторой громоздкости параметров конфигурации протоколов. С появлением программно-конфигурируемых сетей часть задач была автоматизирована, а распространение по всей сети таких технологий, как MPLS-туннели, предоставило операторам большую гибкость при реализации многих составляющих регулирования трафика.

Управление допуском

Популярный метод предотвращения перегрузки в сетях виртуальных каналов — управление допуском (admission control). Идея проста: не создавать новый виртуальный канал до тех пор, пока сеть не сможет обработать дополнительный трафик без перегрузки. Таким образом, попытка добавить виртуальный канал может закончиться неудачно. Это лучшее решение, так как если позволить дополнительным пользователям подключиться к заполненной сети, ситуация только ухудшится. По аналогии, когда коммутатор в телефонной системе перегружен, вы поднимаете трубку и не слышите гудка.

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

Часто речь идет о скорости и форме. Возникает вопрос, как описать эти характеристики просто и содержательно. Обычно трафик неравномерен, поэтому нельзя полагаться только на среднюю скорость. Например, гораздо сложнее справиться с колебаниями трафика при поиске в интернете, чем при просмотре потокового видео того же объема, поскольку всплески интернет-трафика с большей вероятностью приводят к перегрузке маршрутизаторов сети. Этот эффект часто называют «дырявым ведром» (leaky bucket) или «маркерным ведром» (token buсket). «Дырявое ведро» обладает двумя параметрами, ведущими к ограничению средней скорости и мгновенному увеличению объема трафика. Поскольку это два наиболее распространенных механизма формирования трафика, мы рассмотрим их более подробно в данном разделе.

Располагая характеристиками трафика, сеть принимает решение о добавлении нового виртуального канала. Чтобы не произошло перегрузки, сеть может, например, зарезервировать часть пропускной способности для каждого виртуального канала. В этом случае характеристика трафика выступает в качестве договора об обслуживании, которое сеть обязуется предоставить пользователю. В разговоре о предотвращении перегрузки мы слишком рано отклонились в сторону смежной темы, QoS; вернемся к ней чуть позже.

Даже если сеть не берет на себя никаких обязательств, она может использовать характеристики трафика для управления доступом. При этом задача сводится к оценке числа виртуальных каналов, достаточного для обеспечения нужной пропускной способности сети и работы без перегрузок. Предположим, что все виртуальные каналы, которые могут передавать трафик со скоростью до 10 Мбит/с, используют один и тот же физический канал с пропускной способностью 100 Мбит/с. Сколько каналов можно использовать? Очевидно, что при 10 каналах нет никакого риска перегрузки, но это неэффективно в обычной ситуации, поскольку вряд ли все они будут одновременно работать в полную силу. В действующих сетях для оценки числа возможных каналов используются статистические данные. Таким образом, за счет допустимого увеличения риска сеть выигрывает в производительности.

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

Илл. 5.22. (а) Перегруженная сеть. (б) Участок сети без перегрузки. Также показан виртуальный канал между A и B

Предположим, что хост, подключенный к маршрутизатору A, хочет установить соединение с хостом, соединенным с B. В других обстоятельствах это соединение прошло бы через один из перегруженных маршрутизаторов. Чтобы этого избежать, сеть усекается, как показано на илл. 5.22 (б). При этом исключаются перегруженные маршрутизаторы и все их линии связи. Пунктиром показан возможный путь виртуального канала в обход перегруженных маршрутизаторов. Подробное описание маршрутизации, чувствительной к нагрузке, можно найти в работе Шейха и др. (Shaikh et al., 1999).

Сброс нагрузки

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

Ключевой вопрос для маршрутизатора, заваленного пакетами, — какой из них исключить. Выбор зависит от типа приложений, использующих данную сеть. При передаче файлов более старые пакеты представляют большую ценность, чем новые. Например, если отбросить пакет 6, но сохранить пакеты 7–10, это заставит получателя выполнить лишнюю работу: поместить в буфер данные, которые он еще не может использовать. Для мультимедийных приложений, работающих в реальном времени, напротив, новый пакет важнее старого, поскольку пакеты становятся ненужными, если не приходят вовремя.

Первую стратегию (старое лучше нового) часто называют винной стратегией (wine), а вторую (новое лучше старого) — молочной стратегией (milk), так как большинство людей предпочтут пить свежее молоко и выдержанное вино, а не наоборот.

Более сложные алгоритмы сброса нагрузки требуют участия отправителей. В качестве примера можно привести пакеты, содержащие сведения о маршрутизации. Они намного важнее обычных пакетов с данными, поскольку устанавливают маршруты; если они будут утеряны, может пострадать связность сети. Другой пример — алгоритмы сжатия видеосигнала (например, MPEG), которые периодически передают полный фрейм, а далее отправляют его измененные версии. В этом случае потеря пакета с изменениями не так страшна, как потеря полного фрейма, так как от него зависят последующие пакеты.

Чтобы реализовать осмысленную стратегию отбрасывания части данных, приложения должны помечать свои пакеты, сообщая сети об их важности. Тогда маршрутизаторы смогут сначала исключить наименее важные пакеты, затем чуть более существенные, и т.д.

Конечно, при отсутствии определенного стимула все будут помечать свои пакеты не иначе как ОЧЕНЬ ВАЖНО — НИ В КОЕМ СЛУЧАЕ НЕ ВЫБРАСЫВАТЬ. Предотвращение неоправданного использования таких меток часто достигается за счет сетевых ресурсов и денежных средств. Например, сеть может разрешить отправителям пересылать пакеты с большей скоростью, чем указано в договоре на предоставление услуг, если пакет будет помечаться как низкоприоритетный. Такая стратегия весьма удачна, поскольку более эффективно распределяет свободные ресурсы: хостам разрешено пользоваться ими, пока это никому не мешает, но это право за ними не закреплено.

Формирование трафика

Чтобы гарантировать пользователю определенную производительность, сеть должна знать примерный объем трафика. В телефонных сетях его оценить легко: обычный звонок (в несжатом формате) требует скорости 64 Кбит/с и одного 8-битного отсчета каждые 125 мкс. Однако в сетях передачи данных трафик неравномерен (bursty). Он может быть неоднородным по трем причинам: непостоянная скорость передачи (например, при видеоконференциях со сжатием), взаимодействие пользователя и приложения (например, просмотр новой веб-страницы) и переключение компьютера между задачами. С неравномерным трафиком работать гораздо сложнее, чем с постоянным, так как при этом может произойти переполнение буферов и, как следствие, утеря пакетов.

Шейпинг трафика (traffic shaping) — способ регулировки средней скорости и равномерности потока входных данных. Приложения должны иметь возможность передавать тот трафик, который им нужен (включая неравномерный); при этом нужен простой и удобный способ описания возможных схем трафика. Когда устанавливается поток, пользователь и сеть (то есть клиент и оператор связи) договариваются об определенной схеме (то есть форме) трафика для данного потока. В результате клиент сообщает провайдеру: «Мой график передачи будет выглядеть следующим образом. Сможете ли вы это обеспечить?»

Иногда такой договор называется соглашением об уровне обслуживания (SLA, Service Level Agreement), особенно если в нем оговариваются комплексные потоки и длительные периоды времени (например, весь трафик для данного клиента). До тех пор пока клиент выполняет свою часть условий соглашения и передает пакеты в пределах установленного графика, провайдер обязуется доставлять их в определенный срок.

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

Шейпинг трафика и его политика не так существенны для однорангового обмена и передач других типов, где используется вся доступная пропускная способность. Но они имеют важное значение для данных в реальном времени (например, при аудио- и видеосоединениях), обладающих строгими требованиями к QoS. Нам уже знаком один способ ограничения объема данных, отправляемого приложениями, — раздвижное окно. С помощью одного параметра он определяет, сколько данных передается в конкретный момент времени, что косвенно сдерживает скорость. Теперь мы обратимся к более общим методам описания трафика и рассмотрим алгоритмы дырявого и маркерного ведра. Хотя эти методы немного отличаются друг от друга, они дают одинаковый результат.

Представьте себе ведро с маленьким отверстием в донышке, как показано на илл. 5.23 (б). Независимо от скорости, с которой вода наливается в ведро, выходной поток обладает постоянной скоростью R, когда в ведре есть вода, и нулевой скоростью, когда оно пустое. Кроме того, когда ведро наполняется и вода занимает весь объем B, вся лишняя вода выливается через край и теряется.

Илл. 5.23. (а) Формирование пакетов. (б) Алгоритм дырявого ведра. (в) Алгоритм маркерного ведра

С помощью такого ведра можно формировать или приводить в порядок пакеты, поступающие в сеть (илл. 5.23 (а)). Принцип следующий: каждый хост соединяется с сетью через интерфейс, содержащий «дырявое ведро». Чтобы пакет можно было отправить в сеть, в ведре должно быть достаточно места для воды. Если в момент поступления пакета ведро заполнено, пакет либо помещается в очередь до тех пор, пока в ведре не освободится достаточно места, либо отвергается. Первый вариант встречается, когда формирование трафика производится операционной системой хоста. Второй — когда проверка трафика, поступающего в сеть, осуществляется аппаратными средствами в сетевом интерфейсе интернет-провайдера. Этот метод был предложен Тернером (Turner, 1986) и называется алгоритмом дырявого ведра (leaky bucket algorithm).

То же самое можно представить по-другому: в виде ведра, которое в данный момент наполняется (см. илл. 5.23 (в)). Вода вытекает из крана со скоростью R, а объем ведра, как и в предыдущем случае, равен B. Чтобы отправить пакет, необходимо, чтобы из ведра можно было вылить воду (или маркеры — так обычно называют содержимое ведра), а не налить ее туда. В ведре может содержаться ограниченное число маркеров (не более B); если ведро пустое, для отправки пакета необходимо подождать, пока не появятся новые маркеры. Данный метод называется алгоритмом маркерного ведра (token bucket algorithm).

Алгоритмы дырявого и маркерного ведра ограничивают постоянную скорость потока, при этом пропуская кратковременные всплески трафика (также ограниченные максимальным значением) без искусственных задержек. Чтобы снизить нагрузку на сеть, шейпер «дырявого ведра» сглаживает крупные всплески трафика. Представьте компьютер, который производит данные со скоростью 1000 Мбит/с (125 млн байт в секунду); первая связь сети работает на той же скорости. Хост генерирует схему трафика, показанную на илл. 5.24 (а). Эта схема является неравномерной. Средняя скорость составляет 200 Мбит/с, хотя хост отправляет пиковый объем трафика в 16 000 Кбайт на максимальной скорости 1000 Мбит/с (за 1/8 с).

Илл. 5.24. (а) Трафик, передаваемый хостом. (б) Исходящий трафик, сформированный с помощью маркерного ведра со скоростью 200 Мбит/с и емкостью 9600 Кбайт. (в) Та же скорость, емкость 0 Кбайт. (г) Уровень маркерного ведра при формировании трафика со скоростью 200 Мбит/с и емкостью 16 000 Кбайт. (д) Та же скорость, емкость 9600 Кбайт. (е) Та же скорость, емкость 0 Кбайт

Теперь предположим, что маршрутизаторы могут принимать данные на максимальной скорости только в течение небольших временных интервалов — до тех пор, пока буфер не заполнится. Размер буфера составляет 9600 Кбайт — это меньше объема пикового трафика. При долгих интервалах маршрутизаторы лучше всего работают, если скорость не превышает 200 Мбит/с (именно такая пропускная способность указана в соглашении с клиентом). Из этого следует, что если для передачи используется эта схема, часть трафика будет удалена, так как не поместится в буферы маршрутизаторов.

Чтобы избежать потери пакетов, можно сформировать трафик на хосте по методу маркерного ведра. Если скорость R равна 200 Мбит/с, а емкость B равна 9600 Кбайт, трафик находится в пределах возможностей сети. Исходящий трафик такого маркерного ведра показан на илл. 5.24 (б). Хост может передавать на максимальной скорости 1000 Мбит/с в течение небольшого промежутка времени — до тех пор, пока ведро не опустеет. Затем он должен будет снизить скорость до 200 Мбит/с и отправить оставшуюся часть трафика. Суть в том, чтобы растянуть время передачи пикового трафика (пачки пакетов), если сеть не в состоянии обработать его в один прием. Уровень маркерного ведра показан на илл. 5.24 (д). Вначале ведро наполнено, но после первой порции трафика оно становится пустым. Когда уровень достигает нуля, новые пакеты могут передаваться только с той скоростью, с какой в буфер поступают маркеры; отправка крупных объемов трафика невозможна, пока ведро снова не будет полным. Оно постепенно наполняется, когда трафик не приходит, и остается пустым, пока данные приходят со скоростью его заполнения.

Чтобы трафик был равномерным, его можно сформировать. На илл. 5.24 (в) показан исходящий трафик маркерного ведра со скоростью 200 Мбит/с и емкостью 0. Это крайний случай — трафик полностью выровнен. Крупные пачки не принимаются; трафик приходит с постоянной скоростью. Уровень воды в ведре, соответственно, всегда равен нулю (см. илл. 5.24 (е)). Трафик помещается в очередь хоста, и в каждый момент времени какой-то пакет ожидает отправки.

Наконец, на илл. 5.24 (д) показан уровень маркерного ведра со скоростью R = 200 Мбит/с и емкостью B = 16 000 Кбайт. Это самое маленькое маркерное ведро, через которое данные проходят без изменений. Маршрутизатор может использовать его для проверки трафика, передаваемого хостом. Такое ведро можно расположить на одном из концов сети; если трафик будет соответствовать маркерному ведру, указанному в SLA, он сможет пройти через ведро. Если же хост будет отправлять данные слишком быстро или неравномерно, вода в маркерном ведре закончится и сеть узнает о том, что трафик не соответствует условиям договора. Далее в зависимости от конфигурации сети лишние пакеты будут либо удалены, либо помечены как низкоприоритетные. В нашем примере ведро пустеет лишь на короткое время — после пикового трафика. После этого оно восстанавливается и снова готово к новым всплескам.

Методы дырявого и маркерного ведра просты в реализации. Рассмотрим, как работает маркерное ведро. Хотя до этого мы говорили о непрерывно поступающей и вытекающей воде, нужно понимать, что на практике сеть имеет дело с дискретными величинами. Реализация алгоритма маркерного ведра подразу­мевает наличие переменной, считающей маркеры. Счетчик увеличивается на R/∆T. В нашем примере счетчик будет увеличиваться на 200 кбит за 1 мс. Каждый раз при отправке трафика счетчик уменьшается; когда его значение доходит до нуля, передача пакетов останавливается.

Если все пакеты имеют одинаковый объем, уровень ведра можно измерять в них (например, 200 кбит — это 20 пакетов по 1250 байт). Однако чаще всего используются пакеты разного размера. Тогда уровень ведра может исчисляться в байтах. Если байтов в ведре недостаточно для отправки пакета, он вынужден ждать, пока ситуация не изменится (что может произойти не сразу, если скорость заполнения ведра небольшая).

Рассчитывать длительность максимального всплеска (когда ведро пустеет) немного проблематично. Необходимо учитывать, что пока ведро опустошается, появляются новые маркеры. (В силу этого в нашем случае всплеск длится дольше, чем результат деления 9600 Кбайт на 125 Мбайт/с.) При длительности пачки S с, емкости маркерного ведра B байт, скорости появления маркеров R байт/с и максимальной выходной скорости M байт/с очевидно, что максимальное количество переданных байтов в пачке будет равно B + RS байт. Также известно, что количество байтов, переданных в пачке с максимальной скоростью, равно MS. Таким образом,

B + RS = MS.

Решив это уравнение, получим: S = B/(M – R). При наших параметрах B == 9600 Кбайт, M = 125 Мбайт/с и R = 25 Мбайт/с длительность пачки равна приблизительно 94 мс.

Недостатком алгоритма маркерного ведра является то, что скорость передачи крупных пачек снижается до постоянного значения R. Часто бывает необходимо уменьшить пиковую скорость, не возвращаясь при этом к постоянному значению скорости (но и не увеличивая его, чтобы не пропустить в сеть дополнительный трафик). Один из способов получения более гладкого трафика состоит во внедрении еще одного маркерного ведра после первого. Скорость второго ведра должна быть гораздо выше. По сути, первое ведро определяет характеристики трафика и фиксирует его скорость, иногда позволяя отправлять крупные объемы данных. Второе ведро уменьшает максимальную скорость, с которой могут передаваться такие пачки. Например, если скорость второго ведра равна 500 Мбит/с, а емкость — 0, первая пачка поступит в сеть с максимальной скоростью 500 Мбит/с. Это меньше, чем предыдущее значение 1000 Мбит/с.

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

Активное управление очередью

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

Рассмотрим несколько подходов к замедлению трафика, применяемых в дейтаграммных сетях и сетях виртуальных каналов. Каждый подход должен решать две проблемы. Во-первых, необходимо, чтобы маршрутизаторы узнавали о перегрузке до того, как она произойдет. Для этого каждый из них должен непрерывно отслеживать ресурсы, которые он задействует, — использование выходных линий, буферизацию очереди пакетов данного маршрутизатора и число пакетов, утерянных вследствие неправильной буферизации. Наиболее эффективным является второй вариант. Средние показатели использования линий не отражают реальной картины при прерывистом трафике. Так, значение 50 % — это мало при сплошном трафике и очень много при переменном. Число утерянных пакетов становится известно слишком поздно: пакеты начинают теряться уже после возникновения перегрузки.

Время ожидания в очереди маршрутизатора точно отражает, как перегрузка сказывается на пакетах. Будучи низким в большинстве случаев, этот показатель должен резко возрастать при скачке трафика, когда увеличивается число непереданных пакетов. Такую оценку времени ожидания в очереди d можно получить с помощью несложных вычислений, периодически замеряя мгновенную длину очереди s и рассчитывая новое значение переменной d по формуле

где константа α определяет, насколько быстро маршрутизатор забывает свою недавнюю историю. Это экспоненциально взвешенное скользящее среднее (Exponentialy Weighted Moving Average, EWMA). Оно сглаживает различные флуктуации и работает как фильтр низких частот. Как только значение d выходит за пороговый уровень, маршрутизатор узнает о начале перегрузки.

Вторая проблема состоит в том, что маршрутизаторы должны вовремя доставлять сообщения обратной связи тем источникам, чей трафик вызывает перегрузку. Хотя перегрузка происходит внутри сети, ее устранение требует участия отправителей, пользующихся сетью. Маршрутизатор должен определить их, а затем аккуратно передать им уведомления, не отправляя лишних пакетов в уже перегруженную сеть. Разные алгоритмы используют различные механизмы обратной связи. О них мы и поговорим далее.

Произвольное раннее обнаружение перегрузки

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

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

Этой ситуацией можно воспользоваться для уменьшения перегрузок. Если заставить маршрутизаторы отбрасывать пакеты еще до того, как ситуация станет безнадежной, то останется время на то, чтобы источник мог предпринять какие-то действия. Популярный алгоритм, реализующий данную идею, называется произвольным ранним обнаружением перегрузки (Random Early Detection, RED) (Флойд и Джейкобсон; Floyd and Jacobson, 1993). Чтобы определить, когда следует удалять пакеты, маршрутизаторы постоянно высчитывают скользящее среднее длин своих очередей. Если средняя длина очереди на каком-либо соединении превышает пороговое значение, эта линия объявляется перегруженной и небольшая часть пакетов удаляется случайным образом. Именно случайный выбор увеличивает вероятность того, что самые быстрые отправители обнаружат утерю пакета. Это наилучший вариант, поскольку маршрутизатор не знает, какой именно источник является самым проблемным в дейтаграммной сети. Отправитель заметит утерю пакета без всяких уведомлений, после чего транспортный протокол замедлит работу. Таким образом, утерянный пакет несет ту же информацию, что и пакет уведомления, но неявно, без отправки маршрутизатором прямого сигнала.

RED-маршрутизаторы эффективнее тех, которые удаляют пакеты только при заполнении буфера, хотя и требуют правильной настройки. Например, оптимальное число пакетов на удаление зависит от числа отправителей, которых нужно оповестить о перегрузке. Однако по возможности лучше использовать прямые уведомления. Они работают так же, но передают сообщения в явном виде, а не косвенно через утерю пакета; RED используется в тех случаях, когда хосты не принимают такие уведомления.

Сдерживающие пакеты

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

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

На ранних этапах развития интернета в качестве сдерживающего пакета использовалось сообщение SOURCE QUENCH (Постел; Postel, 1981). Оно не прижилось отчасти потому, что не были четко определены условия и результаты его рассылки. В современном интернете применяется другая схема уведомлений, о которой мы поговорим позже.

Явное уведомление о перегрузке

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

Этот метод называется явным уведомлением о перегрузке (Explicit Congestion Notification, ECN) и используется в интернете (Рамакришнан; Ramakrishnan, 1988). Это усовершенствованный вариант ранних протоколов подобного рода, в частности бинарной схемы обратной связи (Рамакришнан и Джейн; Ramakrishnan and Jain, 1988), применявшейся в архитектуре DECnet. На информацию о перегрузке в заголовке пакета отводится два бита. В момент отправки пакет не имеет метки (илл. 5.25). При проходе через перегруженный маршрутизатор пакет получает отметку о перегрузке. Затем получатель передает эти сведения отправителю, добавив явное уведомление в следующий ответный пакет. На рисунке этот процесс обозначен пунктирной линией, чтобы показать, что он происходит над IP-уровнем (например, на уровне TCP). Далее, как и в случае со сдерживающими пакетами, отправитель должен начать регулировать трафик.

Илл. 5.25. Явное уведомление о перегрузке

Обратное давление на ретрансляционных участках

При высоких скоростях или больших расстояниях до хостов множество новых пакетов может быть передано даже после отправки уведомлений о перегрузке, поскольку реакция на них занимает некоторое время. Рассмотрим, к примеру, хост в Сан-Франциско (маршрутизатор A на илл. 5.26), посылающий поток данных на хост, расположенный в Нью-Йорке (маршрутизатор D на илл. 5.26), со скоростью OC-3 155 Мбит/с. Если у нью-йоркского хоста станет заканчиваться буферная память, сдерживающему пакету потребуется около 40 мс на то, чтобы вернуться обратно в Сан-Франциско и сообщить, что необходимо снизить объем трафика. Явное уведомление о перегрузке займет еще больше времени, поскольку оно доставляется через получателя. На илл. 5.26 (а) распространение сдерживающего пакета схематично показано на второй, третьей и четвертой диаграммах. За те 40 мс, пока пакет движется по сети, в сторону нью-йоркского маршрутизатора передается еще 6,2 Мбит данных, с которыми надо как-то справиться. Только к седьмой диаграмме (илл. 5.26 (а)) маршрутизатор заметит замедление потока.

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

Илл. 5.26. (а) Сдерживающий пакет влияет только на источник. (б) Сдерживающий пакет влияет на все промежуточные участки

точки F, поток данных от F в сторону D должен снизиться. Таким образом, F резервирует для соединения большее количество буферной памяти: источник все еще продолжает заваливать это направление своими данными. Нагрузка на D мгновенно снижается, как головная боль — от таблетки в телевизионной рекламе. На следующем шаге сдерживающий пакет, продолжая свой путь, достигает E и приказывает уменьшить поток в сторону F. В результате точке E приходится выдерживать повышенную нагрузку, но зато F немедленно становится легче. Наконец, победный марш сдерживающего пакета приводит его к источнику всех бед — точке A, и теперь поток снижается по-настоящему.

Результат применения этой схемы — максимально быстрое устранение перегрузки на самом проблемном участке за счет использования большего объема буферной памяти промежуточных маршрутизаторов. Таким образом, проблема решается без потери пакетов. Эта идея обсуждается более подробно в работе Мишры и др. (Mishra et al., 1996).