То же самое можно представить по-другому: в виде ведра, которое в данный момент наполняется (см. илл. 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 выходит за пороговый уровень, маршрутизатор узнает о начале перегрузки.