Token Bucket

Token Bucket (алгоритм «маркерной корзины», «корзина жетонов») — это алгоритм управления трафиком в компьютерных сетях, используемый для контроля скорости передачи данных (traffic shaping) и обеспечения соблюдения согласованной полосы пропускания (policing). Он позволяет регулировать среднюю скорость потока, допуская кратковременные всплески (bursts) трафика до определённого предела, что отличает его от более строгого алгоритма «дырявого ведра» (Leaky Bucket).

История

Концепция Token Bucket была впервые предложена в начале 1990-х годов в контексте развития сетей с интеграцией услуг (ISDN, ATM). Она стала стандартным механизмом в протоколах, требующих гарантий качества обслуживания (QoS), таких как Frame Relay, ATM и, позднее, IP-сети (DiffServ, IntServ). В 1990-е годы алгоритм был формализован в спецификациях Internet Engineering Task Force (IETF), в частности, в RFC 2212 (Specification of Guaranteed Quality of Service) и RFC 2697 (A Single Rate Three Color Marker). Впоследствии Token Bucket лёг в основу многих реализаций в операционных системах (например, в Linux Traffic Control — tbf (Token Bucket Filter)) и сетевом оборудовании (Cisco, Juniper).

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

Алгоритм основан на метафоре корзины, в которую с постоянной скоростью (CIR — Committed Information Rate, согласованная скорость передачи) добавляются маркеры (токены). Каждый маркер даёт право отправить один байт (или один пакет) данных. Если корзина заполняется, избыточные маркеры отбрасываются — это определяет максимальный размер всплеска (Bc — Committed Burst Size). При поступлении пакета данных:

1. Если в корзине есть достаточное количество маркеров (не меньше размера пакета), пакет немедленно отправляется, а соответствующее количество маркеров извлекается.
2. Если маркеров недостаточно, возможны два варианта поведения:

• Traffic Shaping (формирование трафика): Пакет помещается в очередь и ожидает, пока в корзине накопится нужное количество маркеров. Это может вызывать задержки.
• Policing (полицейский контроль): Пакет может быть отброшен (discard) или помечен как «превышающий» (out-of-profile) для последующей обработки с более низким приоритетом (например, при перегрузке сети).

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

• CIR (Committed Information Rate) — средняя скорость добавления маркеров (в бит/с или байт/с). Определяет долгосрочную среднюю скорость потока.
• Bc (Committed Burst Size) — максимальный размер корзины (в байтах или битах). Определяет, какой объём данных может быть передан «всплеском» без потери маркеров.
• Be (Excess Burst Size) — дополнительный размер корзины (в некоторых реализациях, например, в Frame Relay). Позволяет временно превышать Bc, но такие пакеты обычно маркируются как «превышающие» (DE — Discard Eligibility).

Классификация и варианты

По способу обработки избыточных маркеров

• Односкоростной (Single Rate): Используется только один параметр CIR. Маркеры добавляются с одной скоростью. Пример: RFC 2697 (Single Rate Three Color Marker — srTCM).
• Двухскоростной (Two Rate): Используются две скорости: CIR и PIR (Peak Information Rate — пиковая скорость). Маркеры добавляются в две корзины с разными скоростями. Пример: RFC 2698 (Two Rate Three Color Marker — trTCM).

По цветовой маркировке

В современных реализациях (например, в DiffServ) пакеты классифицируются по трём цветам (зелёный, жёлтый, красный) в зависимости от того, какие маркеры были использованы:

• Зелёный (Green): Пакет соответствует согласованной скорости (CIR) и не превышает Bc.
• Жёлтый (Yellow): Пакет превышает Bc, но укладывается в Be (или в PIR в двухскоростном варианте). Такой пакет может быть отброшен при перегрузке с более высокой вероятностью, чем зелёный.
• Красный (Red): Пакет превышает все допустимые лимиты (Bc и Be, или PIR). Он отбрасывается немедленно.

Применение

Управление трафиком в сетях (QoS)

• Формирование трафика (Shaping): Используется на выходных интерфейсах маршрутизаторов для сглаживания всплесков и предотвращения перегрузок. Пример: ограничение скорости загрузки файлов в корпоративной сети.
• Полицейский контроль (Policing): Используется на входных интерфейсах для проверки соответствия трафика контракту. Пример: интернет-провайдеры ограничивают скорость клиента согласно тарифному плану.

Сетевые протоколы

• ATM (Asynchronous Transfer Mode): Используется для постоянных и виртуальных соединений (CBR, VBR).
• Frame Relay: Используется для контроля Committed Information Rate (CIR) и Excess Information Rate (EIR).
• IP-сети (DiffServ): Реализуется через маркеры (srTCM, trTCM) для классификации и обработки трафика.

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

• Linux Traffic Control (tc): Модуль tbf (Token Bucket Filter) — одна из самых распространённых реализаций. Позволяет ограничивать скорость на сетевых интерфейсах.
• BSD: Реализация через dummynet или pf (packet filter).
• Windows: Встроенные механизмы QoS (Quality of Service) в Windows Server и клиентских версиях.

Промышленные системы и IoT

• Промышленные сети (PROFINET, EtherCAT): Используется для гарантии времени доставки критических данных.
• Системы реального времени: Алгоритм применяется для ограничения частоты отправки сообщений в шинах данных (CAN, Modbus).

Сравнение с другими алгоритмами

Token Bucket vs Leaky Bucket

• Leaky Bucket (дырявое ведро): Алгоритм, который сглаживает трафик до строго постоянной скорости, не допуская всплесков. Пакеты, превышающие скорость, отбрасываются или ставятся в очередь. Token Bucket, в отличие от него, допускает кратковременные всплески, если в корзине есть накопленные маркеры.
• Token Bucket: Более гибкий, так как позволяет использовать накопленные маркеры для передачи данных с пиковой скоростью, что важно для приложений, чувствительных к задержкам (например, VoIP, видеоконференции).

Token Bucket vs Shaping vs Policing

• Shaping (формирование): Использует Token Bucket для буферизации и задержки пакетов, чтобы сгладить всплески. Очередь может быть большой, что увеличивает задержку.
• Policing (полицейский контроль): Использует Token Bucket для немедленного отбрасывания или маркировки пакетов, не создавая очередей. Задержка не увеличивается, но пакеты могут теряться.

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

• Сложность настройки: Требует точного подбора параметров CIR, Bc, Be. Неправильная настройка может привести к неэффективному использованию полосы пропускания или к излишним потерям пакетов.
• Чувствительность к размеру пакетов: Алгоритм может быть несправедлив к потокам с большими пакетами (например, FTP), так как каждый пакет требует количество маркеров, пропорциональное его размеру. Это может приводить к тому, что мелкие пакеты (например, VoIP) получают преимущество.
• Отсутствие адаптивности: Классический Token Bucket не учитывает текущую загрузку сети. В условиях перегрузки он может отбрасывать пакеты, даже если другие потоки не используют свою полосу. Современные реализации (например, в протоколе TCP) используют обратную связь (ECN — Explicit Congestion Notification) для адаптации.
• Проблемы с синхронизацией: В распределённых системах (например, в кластерах) синхронизация маркерных корзин между узлами может быть сложной и приводить к рассогласованию.

Интересные факты

• Алгоритм Token Bucket используется не только в сетях, но и в других областях, где требуется ограничение скорости: например, в системах управления базами данных (ограничение частоты запросов), в API-шлюзах (rate limiting) и в игровых движках (ограничение частоты кадров).
• В операционной системе Linux модуль tbf может работать в двух режимах: «точный» (exact) и «приблизительный» (approximate), что позволяет настраивать производительность и точность.
• В протоколе Frame Relay параметр Be (Excess Burst Size) позволяет временно превышать CIR, но такие пакеты маркируются как DE (Discard Eligibility) и могут быть отброшены при перегрузке сети.

Источники

1. RFC 2212 — Specification of Guaranteed Quality of Service (1997).
2. RFC 2697 — A Single Rate Three Color Marker (1999).
3. RFC 2698 — A Two Rate Three Color Marker (1999).
4. Tanenbaum, A. S., Wetherall, D. J. Computer Networks (5th Edition). — Pearson, 2010. — Глава 5.2.3 (Quality of Service).
5. Kurose, J. F., Ross, K. W. Computer Networking: A Top-Down Approach (7th Edition). — Pearson, 2016. — Глава 7.3 (Traffic Shaping and Policing).
6. Linux Advanced Routing & Traffic Control HOWTO (LARTC). — Раздел «Token Bucket Filter».
7. Cisco IOS Quality of Service Solutions Configuration Guide. — Раздел «Traffic Policing and Shaping».