Leaky Bucket

Leaky Bucket (с англ. — «дырявое ведро») — это алгоритм управления трафиком в компьютерных сетях и телекоммуникационных системах, предназначенный для контроля скорости передачи данных и сглаживания пульсаций (burstiness) входящего потока. Алгоритм реализует механизм, при котором пакеты или данные поступают в буфер (ведро), а затем «вытекают» из него с фиксированной, заранее заданной скоростью, независимо от интенсивности входящего трафика. Если входящий поток превышает пропускную способность «ведра» или размер буфера, избыточные пакеты отбрасываются. Leaky Bucket является одним из базовых методов формирования трафика (traffic shaping) и обеспечения качества обслуживания (Quality of Service, QoS).

История и происхождение

Концепция «дырявого ведра» была впервые предложена в 1986 году в работе Джона Тёрнера (John Turner) «New Directions in Communications (or Which Way to the Information Age?)», опубликованной в журнале IEEE Communications Magazine. Изначально алгоритм разрабатывался для управления трафиком в сетях с асинхронным режимом передачи (ATM), где требовалось строгое соблюдение параметров качества обслуживания, таких как задержка и джиттер. Впоследствии Leaky Bucket нашёл применение в протоколах IP-сетей, в том числе в механизмах DiffServ (Differentiated Services) и IntServ (Integrated Services), а также в системах пакетной обработки данных, таких как очереди в маршрутизаторах и коммутаторах.

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

Алгоритм Leaky Bucket моделирует поведение ведра с отверстием в дне. Входящие данные (пакеты, байты или биты) поступают в ведро, которое имеет фиксированную ёмкость (максимальный размер буфера). Из ведра данные «вытекают» с постоянной скоростью, определяемой пропускной способностью канала или заданным параметром. Если ведро переполняется (поступает больше данных, чем может вытечь или вместить буфер), избыточные данные отбрасываются.

Основные параметры

• Скорость вытекания (leak rate) — максимальная скорость, с которой данные могут покидать ведро. Измеряется в битах в секунду (bps) или пакетах в секунду (pps).
• Размер ведра (bucket size) — максимальный объём данных, который может быть накоплен в буфере. Измеряется в байтах или пакетах.
• Текущий уровень заполнения — количество данных, находящихся в ведре в данный момент времени.

Алгоритм

1. При поступлении нового пакета проверяется текущий уровень заполнения ведра.
2. Если уровень заполнения плюс размер пакета не превышает размер ведра, пакет помещается в буфер, а уровень заполнения увеличивается на размер пакета.
3. Если уровень заполнения превышает размер ведра, пакет отбрасывается (или помечается как несоответствующий).
4. Ведро «вытекает» с постоянной скоростью: через каждый интервал времени уровень заполнения уменьшается на величину, равную произведению скорости вытекания на длительность интервала.

Виды и модификации

Leaky Bucket с отбрасыванием пакетов

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

Leaky Bucket с буферизацией

Вместо отбрасывания пакетов они могут помещаться в очередь (буфер) и ожидать своей очереди на отправку. Однако если очередь переполняется, пакеты всё равно отбрасываются. Эта модификация используется в маршрутизаторах с очередями типа FIFO (First In, First Out).

Leaky Bucket с маркировкой

В некоторых реализациях (например, в механизмах DiffServ) пакеты, превышающие порог, не отбрасываются, а помечаются как «out-of-profile» (вне профиля). Такие пакеты могут быть отброшены позже при перегрузке сети, но в обычных условиях передаются.

Сравнение с Token Bucket

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

Применение

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

Leaky Bucket используется для ограничения скорости передачи данных на уровне сетевых устройств (маршрутизаторов, коммутаторов). Например, в протоколе ATM он применялся для контроля параметров трафика (PCR — Peak Cell Rate, SCR — Sustainable Cell Rate). В IP-сетях алгоритм реализован в механизмах policing (полицейский контроль) и shaping (формирование трафика) в рамках QoS.

Системы потоковой передачи данных

В видеосервисах и аудиопотоках Leaky Bucket позволяет сглаживать пульсации битрейта, обеспечивая равномерную загрузку канала и предотвращая перегрузки. Например, в кодеках H.264 и H.265 используется модель Leaky Bucket для расчёта размера буфера декодера.

Очереди в операционных системах

Алгоритм применяется в планировщиках задач (schedulers) для ограничения скорости обработки запросов. Например, в ядре Linux механизм net/sched/sch_tbf.c (Token Bucket Filter) реализует как Leaky Bucket, так и Token Bucket.

Системы управления доступом к ресурсам

В веб-серверах и API-шлюзах Leaky Bucket используется для rate limiting (ограничения частоты запросов). Например, сервер может ограничивать количество запросов от одного IP-адреса до 100 запросов в секунду, отбрасывая избыточные.

Преимущества и недостатки

Преимущества

• Простота реализации — алгоритм легко реализуется как в аппаратном, так и в программном обеспечении.
• Предсказуемость — фиксированная скорость вытекания гарантирует стабильную задержку и отсутствие джиттера.
• Сглаживание пульсаций — эффективно устраняет кратковременные всплески трафика.

Недостатки

• Жёсткость — не допускает кратковременных превышений скорости, даже если средняя скорость ниже номинальной. Это может приводить к избыточным потерям пакетов при неравномерном трафике.
• Неэффективность при низкой загрузке — если входящий трафик ниже скорости вытекания, ведро остаётся пустым, и пропускная способность канала недоиспользуется.
• Зависимость от размера буфера — при малом размере ведра увеличивается вероятность отбрасывания пакетов, при большом — возрастает задержка.

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

• Название «дырявое ведро» происходит от метафоры: вода (данные) наливается в ведро, но вытекает через отверстие в дне. Если наливать слишком быстро, ведро переполняется.
• В сетях ATM алгоритм Leaky Bucket использовался для реализации параметров трафика, таких как SCR (Sustainable Cell Rate) и MBS (Maximum Burst Size).
• В современных IP-сетях Leaky Bucket часто применяется вместе с Token Bucket в рамках единой системы управления трафиком, например, в механизме srTCM (Single Rate Three Color Marker) и trTCM (Two Rate Three Color Marker).

Источники

• Turner, J. S. (1986). «New Directions in Communications (or Which Way to the Information Age?)». IEEE Communications Magazine, 24(10), 8–15.
• Tanenbaum, A. S., Wetherall, D. J. (2011). «Computer Networks» (5th ed.). Pearson.
• Kurose, J. F., Ross, K. W. (2017). «Computer Networking: A Top-Down Approach» (7th ed.). Pearson.
• RFC 2211 — Specification of the Controlled-Load Network Element Service. IETF, 1997.
• RFC 2697 — A Single Rate Three Color Marker. IETF, 1999.