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

Алгоритм ведра токенов (англ. token bucket algorithm) — это алгоритм контроля трафика, используемый в компьютерных сетях и телекоммуникационных системах для управления скоростью передачи данных и обеспечения соблюдения согласованных параметров трафика (пропускной способности и профиля нагрузки). Относится к классу алгоритмов профилирования трафика и часто применяется совместно с алгоритмом «дырявого ведра» (leaky bucket). Основная функция — ограничение средней скорости передачи данных до заданного значения (committed information rate, CIR) при допустимых кратковременных всплесках (bursts), не превышающих заданный размер «ведра» (bucket size).

Принцип работы

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

Параметры алгоритма

• Скорость пополнения токенов (R) — задаёт среднюю скорость передачи данных (например, 1 Мбит/с). Измеряется в токенах в секунду.
• Размер ведра (B) — максимальное количество токенов, которое может накопиться. Определяет максимальный размер всплеска (burst size), который может быть передан мгновенно. Измеряется в байтах или битах.
• Текущее количество токенов (T) — переменная, изменяющаяся во времени. Начальное значение обычно равно B (ведро полностью заполнено).

Динамика работы

1. Токены добавляются в ведро с постоянной скоростью R токенов в секунду. Если ведро заполнено (T = B), новые токены отбрасываются.
2. При поступлении пакета размером S байт:

• Если T >= S, пакет передаётся, и T уменьшается на S.
• Если T < S, пакет задерживается или отбрасывается (режим «strict policing»), либо может быть передан с пониженным приоритетом (режим «shaping»).

Математическая модель

Изменение количества токенов за время Δt описывается выражением:

T(t + Δt) = min(B, T(t) + R Δt - S N(t))

где N(t) — количество переданных пакетов за время Δt.

Отличие от алгоритма «дырявого ведра»

Оба алгоритма часто путают, но они решают разные задачи:

• Дырявое ведро (leaky bucket) — жёстко ограничивает скорость передачи, сглаживая всплески. Ведро имеет отверстие, через которое «вытекают» данные с постоянной скоростью. Избыточные пакеты отбрасываются или ставятся в очередь. Поток на выходе всегда равномерный.
• Ведро токенов — допускает кратковременные всплески, если в ведре накопились токены. Поток на выходе может быть неравномерным, но средняя скорость не превышает R.

На практике алгоритм ведра токенов часто комбинируют с дырявым ведром для обеспечения как средней скорости, так и сглаживания пиков.

Применение

В компьютерных сетях

• QoS (Quality of Service) — в маршрутизаторах и коммутаторах для ограничения трафика по классам обслуживания. Например, в протоколе DiffServ (Differentiated Services) алгоритм используется для маркировки пакетов (in-profile / out-of-profile) и последующей обработки (отбрасывание, понижение приоритета).
• Traffic shaping — в устройствах, поддерживающих shaping (например, Cisco, Juniper, Linux tc). Позволяет ограничить скорость исходящего трафика, сохраняя возможность кратковременных всплесков.
• Policing — в отличие от shaping, policing отбрасывает избыточные пакеты, не буферизируя их. Часто используется на границе сети (например, у провайдера).

В телекоммуникациях

• ATM (Asynchronous Transfer Mode) — алгоритм ведра токенов (в виде «Generic Cell Rate Algorithm», GCRA) используется для контроля трафика на уровне ячеек (cells). GCRA является стандартом ITU-T (I.371) и ATM Forum.
• Мобильные сети (3G/4G/5G) — для управления скоростью передачи данных абонентов (например, ограничение скорости после превышения лимита).

В облачных и веб-сервисах

• Rate limiting — ограничение количества запросов от одного IP-адреса или пользователя. Например, API-шлюзы (Nginx, Kong, AWS API Gateway) используют алгоритм ведра токенов для реализации политик «100 запросов в минуту, с возможностью пика до 200».
• Аренда ресурсов — в облачных платформах (AWS, Azure) для контроля пропускной способности виртуальных машин и дисковых операций (IOPS).

В операционных системах

• Linux Traffic Control (tc) — реализация алгоритма через дисциплину обслуживания очереди (qdisc) tbf (Token Bucket Filter). Позволяет ограничить скорость передачи данных на сетевом интерфейсе.
• FreeBSD и другие Unix-системы — аналогичные механизмы (dummynet, altq).

Варианты и модификации

Двухскоростное ведро токенов (Two-Rate Token Bucket)

Использует две скорости пополнения:

• Committed Information Rate (CIR) — гарантированная средняя скорость.
• Peak Information Rate (PIR) — максимальная пиковая скорость.

Соответственно, два ведра — для CIR и PIR. Пакеты классифицируются на три категории:

• «Зелёные» — в пределах CIR.
• «Жёлтые» — между CIR и PIR.
• «Красные» — превышают PIR (отбрасываются или маркируются).

Применяется в протоколах MPLS и DiffServ для обеспечения многоуровневого QoS.

Трёхцветное ведро (Three-Color Token Bucket)

Развитие двухскоростного подхода, описанное в RFC 2697 (Single Rate Three Color Marker) и RFC 2698 (Two Rate Three Color Marker). Позволяет маркировать пакеты тремя цветами (зелёный, жёлтый, красный) для последующей обработки.

Реализация в программном обеспечении

Пример на псевдокоде

``` class TokenBucket: def __init__(self, rate, burst): self.rate = rate # токенов в секунду self.burst = burst # максимальное количество токенов self.tokens = burst # текущее количество токенов self.last_time = now() # время последнего обновления

def consume(self, tokens):

Пополнение токенов с момента последнего вызова

elapsed = now() - self.last_time self.tokens = min(self.burst, self.tokens + elapsed * self.rate) self.last_time = now()

if self.tokens >= tokens: self.tokens -= tokens return True # разрешено else: return False # отклонено ```

Реализация в Linux tc (qdisc tbf)

Команда для ограничения скорости до 1 Мбит/с с возможностью всплеска до 10 Кбайт:

`` tc qdisc add dev eth0 root tbf rate 1mbit burst 10kbit latency 50ms ``

Критика и ограничения

• Чувствительность к точности таймера — алгоритм требует точного отсчёта времени для пополнения токенов. В высокоскоростных сетях (10 Гбит/с и выше) погрешности могут привести к неточному ограничению.
• Проблема «голодания» (starvation) — при постоянной высокой нагрузке ведро может опустошаться, и все последующие пакеты будут отбрасываться, пока токены не накопятся. Это может быть проблемой для чувствительных к задержкам приложений (VoIP, видеоконференции).
• Необходимость буферизации — в режиме shaping требуется память для очереди, что может увеличить задержку (jitter).
• Сложность настройки — для эффективной работы требуется правильный подбор параметров R и B в зависимости от характера трафика.

Источники

• Andrew S. Tanenbaum, David J. Wetherall. «Computer Networks» (5th Edition). — Pearson, 2011.
• RFC 2697 — «A Single Rate Three Color Marker».
• RFC 2698 — «A Two Rate Three Color Marker».
• ITU-T Recommendation I.371 — «Traffic control and congestion control in B-ISDN».
• Linux Advanced Routing & Traffic Control HOWTO (LARTC).
• Cisco IOS Quality of Service Solutions Configuration Guide.