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