Алгоритм текущего ведра

Алгоритм текущего ведра основан на аналогии с ведром фиксированного объёма, куда с постоянной скоростью добавляются токены (жетоны), обычно соответствующие определённому количеству байт или одному пакету оговорённого размера. Когда пакет проверяется на соответствие лимитам, просматривается текущее количество токенов в ведре. Если токенов достаточно, то необходимое количество (например, эквивалентное длине пакета в байтах) «наличными» списывается из ведра, и пакет допускается к передаче. Если токенов недостаточно, содержимое ведра не изменяется и пакет считается несоответствующим. Несоответствующие пакеты могут обрабатываться разными способами:

• они могут быть отброшены;
• они могут быть помещены в очередь для последующей передачи, когда накопится достаточно токенов;
• они могут быть переданы с пометкой о несоответствии (например, для возможного дальнейшего отброса при перегрузке сети).

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

Алгоритм текущего ведра можно описать следующим образом:

• Каждый ${\displaystyle 1/r}$ секунд в ведро добавляется один токен.
• Ведро вмещает не более ${\displaystyle b}$ токенов. Если очередной токен поступает при полном ведре, он отбрасывается.
• Когда поступает пакет (PDU) размером в n байт:
  • если в ведре есть как минимум n токенов, то они списываются, и пакет отправляется в сеть;
  • если токенов меньше, содержимое ведра не меняется, пакет признаётся несоответствующим.

Реализуя алгоритм на платформах с недостаточным разрешением часового устройства для добавления одного токена каждые ${\displaystyle 1/r}$ секунд, возможна альтернативная формулировка: если обновление ведра происходит каждые S миллисекунд, то за это время добавляется ${\displaystyle (r*S)/1000}$ токенов.

В долгосрочной перспективе выходящий поток соответствующих пакетов ограничен скоростью добавления токенов ${\displaystyle r}$.

Пусть ${\displaystyle M}$ — максимальная возможная скорость передачи в байтах в секунду.

Тогда ${\displaystyle T_{\text{max}}={\begin{cases}b/(M-r)&{\text{ если }}r<M\\\infty &{\text{ иначе }}\end{cases}}}$ определяет максимальное время импульса, то есть времени, на которое может быть полностью использована скорость ${\displaystyle M}$.

Максимальный размер импульса: ${\displaystyle B_{\text{max}}=T_{\text{max}}*M}$

Алгоритм текущего ведра может применяться как для формирования трафика (traffic shaping), так и для политики трафика (traffic policing). При политике несоответствующие пакеты могут быть отброшены или понижены в приоритете (чтобы downstream-механизмы могли их отбросить при перегрузках). При формировании трафика пакеты задерживаются до приведения к требованиям. Оба подхода позволяют защищать сеть от избыточного или чрезмерно импульсивного трафика (см. управление пропускной способностью, избежание перегрузки). Формирование трафика обычно реализуется на сетевых интерфейсах конечных устройств, чтобы избежать отбрасывания пакетов сетевыми механизмами.

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

Алгоритм текущего ведра напрямую сопоставим с одной из двух версий алгоритма вытекающего ведра, описанных в литературе. Эта версия описана в статье как вытекающее ведро в роли счётчика: пакеты, проходящие проверку, добавляют «жидкость» в конечное ведро (по смыслу — те же токены, которые списывались бы из ведра в алгоритме текущего ведра). Эта жидкость затем уходит из ведра с постоянной скоростью, как и токены в исходном алгоритме поступают с постоянной скоростью.

Существует также вторая разновидность — вытекающее ведро в роли очереди; она рассматривается как специальный случай предыдущего варианта и подходит только для формирования трафика. Обычно она не допускает импульсивных выбросов на выходе (без дрожания — jitter free), что принципиально отличает её от алгоритма текущего ведра.

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

Иерархический алгоритм текущего ведра (англ. Hierarchical Token Bucket, HTB) — ускоренная альтернатива CBQ (class-based queueing) в качестве дисциплины очереди в Linux. Позволяет ограничивать скорость загрузки/отправки данных для каждого клиента, чтобы ни один абонент не мог полностью занять всё доступное соединение.

В концепции HTB имеется произвольное количество ведер, организованных в иерархию. Основная egress-дисциплина (qdisc) интерфейса — это root qdisc (корневая дисциплина). Она содержит один класс, которому задаются параметры: rate (гарантированная скорость) и ceil (максимально допустимая скорость). Эти значения задаются одинаковыми на верхнем уровне и определяют общий лимит пропускной способности для связи.

В HTB параметр rate обозначает гарантированную скорость для класса, ceil (англ. ceiling — потолок) — максимальную скорость, которую этот класс может потреблять. Если запрошенная скорость превышает гарантированную, класс может «одалживать» пропускную способность у родителя, пока оба потолка не достигнуты. HTB реализует многоуровневую (classful) дисциплину очередей для контроля трафика Linux, позволяя задавать как жесткие лимиты (ceil), так и относительный приоритет между классами, когда доступна дополнительная пропускная способность.

При выборе лимита для корневого класса стоит учитывать, что формирование трафика влияет только на узком месте между локальной сетью и Интернетом, то есть для домашних и офисных сетей, где вся ЛВС выходит, например, через DSL или T1-канал.