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

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