Алгоритм "token bucket": контроль пропускной способности и неравномерности трафика в сетях. Расписание передач, соответствие лимитам, сетевые планировщики.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритм планирования сетевых передач.
Scheduling algorithm for network transmissions
Токен-бакет – это алгоритм, используемый в сетях с коммутацией пакетов и телекоммуникационных сетях. Он может применяться для проверки соответствия передаваемых данных в виде пакетов заданным ограничениям по пропускной способности и импульсности (мера неравномерности или вариаций в потоке трафика). Также он может использоваться как алгоритм планирования для определения времени отправки передач, соответствующих установленным ограничениям по пропускной способности и импульсности: см. сетевой планировщик.
The token bucket is an algorithm used in packet switched and telecommunications networks. It can be used to check that data transmissions, in the form of packets, conform to defined limits on bandwidth and burstiness (a measure of the unevenness or variations in the traffic flow). It can also be used as a scheduling algorithm to determine the timing of transmissions that will comply with the limits set for the bandwidth and burstiness: see network scheduler.
Обзор
Алгоритм токенов в ведре основан на аналогии с ведром фиксированной емкости, в которое токены, обычно представляющие единицу байтов или один пакет предопределенного размера, добавляются с постоянной скоростью. Когда пакет должен быть проверен на соответствие заданным ограничениям, ведёрко проверяется на наличие достаточного количества токенов в данный момент времени. Если это так, соответствующее количество токенов, например, эквивалентное длине пакета в байтах, изымается ("обналичивается"), и пакет пропускается, например, для передачи. Пакет не соответствует требованиям, если в ведёрке недостаточно токенов, и содержимое ведёрка не изменяется. Пакеты, не соответствующие требованиям, могут обрабатываться различными способами:
The token bucket algorithm is based on an analogy of a fixed capacity bucket into which tokens, normally representing a unit of bytes or a single packet of predetermined size, are added at a fixed rate. When a packet is to be checked for conformance to the defined limits, the bucket is inspected to see if it contains sufficient tokens at that time. If so, the appropriate number of tokens, e. g. equivalent to the length of the packet in bytes, are removed ("cashed in"), and the packet is passed, e. g., for transmission. The packet does not conform if there are insufficient tokens in the bucket, and the contents of the bucket are not changed. Non conformant packets can be treated in various ways:
Они могут быть отброшены. Они могут быть поставлены в очередь для последующей передачи, когда в ведёрке накопится достаточное количество токенов. Они могут быть переданы, но помечены как не соответствующие требованиям, возможно, для последующего отбрасывания в случае перегрузки сети. Соответствующий поток таким образом может содержать трафик со средней скоростью до скорости добавления токенов в ведёрко и иметь импульсность, определяемую глубиной ведёрка. Эта импульсность может быть выражена либо в терминах допустимого джиттера, то есть насколько раньше пакет может соответствовать (например, прибыть или быть переданным), чем ожидалось бы исходя из ограничения средней скорости, либо в терминах допустимого импульса или максимального размера импульса, то есть насколько трафик может превышать средний уровень в течение конечного периода времени.
They may be dropped. They may be enqueued for subsequent transmission when sufficient tokens have accumulated in the bucket. They may be transmitted, but marked as being non conformant, possibly to be dropped subsequently if the network is overloaded. A conforming flow can thus contain traffic with an average rate up to the rate at which tokens are added to the bucket, and have a burstiness determined by the depth of the bucket. This burstiness may be expressed in terms of either a jitter tolerance, i. e. how much sooner a packet might conform (e. g. arrive or be transmitted) than would be expected from the limit on the average rate, or a burst tolerance or maximum burst size, i. e. how much more than the average level of traffic might conform in some finite period.
Вариации
Внедряющие этот алгоритм на платформах с недостаточным разрешением часов для добавления одного токена в корзину каждую секунду, могут рассмотреть альтернативную реализацию. При возможности обновления корзины токенов каждые S миллисекунд, количество токенов для добавления каждые S миллисекунд равно .
Implementers of this algorithm on platforms lacking the clock resolution necessary to add a single token to the bucket every seconds may want to consider an alternative formulation. Given the ability to update the token bucket every S milliseconds, the number of tokens to add every S milliseconds = .
Средняя ставка
В долгосрочной перспективе количество передаваемых конформных пакетов ограничено скоростью генерации токенов, .
Over the long run the output of conformant packets is limited by the token rate, .
Применение
Токен-бакет может использоваться как для формирования трафика, так и для контроля трафика. При контроле трафика некорректные пакеты могут быть отброшены или понижены в приоритете (чтобы последующие функции управления трафиком могли их отбросить при возникновении перегрузки). При формировании трафика пакеты задерживаются до тех пор, пока не станут соответствующими. Контроль и формирование трафика обычно используются для защиты сети от избыточного или резко возрастающего трафика, см. управление пропускной способностью и предотвращение перегрузок. Формирование трафика часто применяется в сетевых интерфейсах хостов для предотвращения отбрасывания передач функциями управления трафиком в сети. Алгоритм токен-бакета также используется для управления потоком ввода-вывода в базах данных.
The token bucket can be used in either traffic shaping or traffic policing. In traffic policing, nonconforming packets may be discarded (dropped) or may be reduced in priority (for downstream traffic management functions to drop if there is congestion). In traffic shaping, packets are delayed until they conform. Traffic policing and traffic shaping are commonly used to protect the network against excess or excessively bursty traffic, see bandwidth management and congestion avoidance. Traffic shaping is commonly used in the network interfaces in hosts to prevent transmissions being discarded by traffic management functions in the network. The token bucket algorithm is also used in controlling database IO flow.