Ведро токенов
Алгоритм планирования сетевых передач

Token bucket — это алгоритм, используемый в сетях с коммутацией пакетов и телекоммуникационных сетях . Его можно использовать для проверки того, что передача данных в виде пакетов соответствует определенным ограничениям по полосе пропускания и пульсации (мера неравномерности или вариаций в потоке трафика ). Его также можно использовать в качестве алгоритма планирования для определения времени передач, которые будут соответствовать ограничениям, установленным для полосы пропускания и пульсации: см. сетевой планировщик .

Обзор

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

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

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

Алгоритм

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

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

Вариации

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

Характеристики

Средняя ставка

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

Размер пакета

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

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

Максимальный размер пакета, таким образом, составляет Б макс = Т макс ∗ М {\displaystyle B_{\text{макс}}=T_{\text{макс}}*M}

Использует

Токен-корзина может использоваться как при формировании трафика , так и при управлении трафиком . При управлении трафиком несоответствующие пакеты могут быть отброшены (сброшены) или их приоритет может быть снижен (для того, чтобы функции управления нисходящим трафиком отбрасывали их в случае перегрузки). При управлении трафиком пакеты задерживаются до тех пор, пока они не будут соответствовать. Управление трафиком и управление трафиком обычно используются для защиты сети от избыточного или чрезмерно пульсирующего трафика, см. Управление полосой пропускания и предотвращение перегрузки . Управление трафиком обычно используется в сетевых интерфейсах хостов для предотвращения отбрасывания передач функциями управления трафиком в сети.

Алгоритм token bucket также используется для управления потоком ввода-вывода базы данных. [1] В нем ограничение не применяется ни к IOPS, ни к пропускной способности, а скорее к линейной комбинации того и другого. Определяя токены как нормализованную сумму веса запроса ввода-вывода и его длины, алгоритм гарантирует, что производная по времени вышеупомянутой функции останется ниже необходимого порога.

Сравнение с дырявым ведром

Алгоритм ведра токенов напрямую сопоставим с одной из двух версий алгоритма дырявого ведра , описанных в литературе. [2] [3] [4] [5] Эта сопоставимая версия дырявого ведра описана на соответствующей странице Википедии как алгоритм дырявого ведра как счетчик . Это зеркальное отражение ведра токенов, в котором соответствующие пакеты добавляют жидкость, эквивалентную токенам, удаленным соответствующим пакетом в алгоритме ведра токенов, в ведро конечной емкости, из которого эта жидкость затем сливается с постоянной скоростью, эквивалентной процессу, в котором токены добавляются с фиксированной скоростью.

Однако существует и другая версия алгоритма дырявого ведра [3] , описанная на соответствующей странице Википедии как алгоритм дырявого ведра как очередь . Это особый случай дырявого ведра как счетчика, который можно описать соответствующими пакетами, проходящими через ведро. Дырявое ведро как очередь, таким образом, применимо только к формированию трафика и, в общем случае, не допускает, чтобы поток выходных пакетов был пульсирующим, т. е. он свободен от джиттера. Поэтому он существенно отличается от алгоритма токенового ведра.

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

Иерархическое ведро токенов

Иерархическая корзина токенов (HTB) — это более быстрая замена дисциплины очередей на основе классов (CBQ) в Linux . [6] Она полезна для ограничения скорости загрузки / выгрузки каждого клиента , чтобы ограниченный клиент не мог перегрузить общую полосу пропускания.

Три клиента используют одну и ту же исходящую полосу пропускания.


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

В HTB rate означает гарантированную пропускную способность, доступную для данного класса, а ceil (сокращение от ceiling) указывает максимальную пропускную способность, которую классу разрешено потреблять. Когда класс запрашивает пропускную способность, превышающую гарантированную, он может заимствовать пропускную способность у своего родителя, пока оба ceil не будут достигнуты. Hierarchical Token Bucket реализует механизм очередей классов для системы управления трафиком Linux и предоставляет rate и ceil, чтобы позволить пользователю контролировать абсолютную пропускную способность для определенных классов трафика, а также указывать соотношение распределения пропускной способности, когда становится доступной дополнительная пропускная способность (до ceil).

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

Смотрите также

Ссылки

  1. ^ «Реализация нового алгоритма планировщика ввода-вывода для смешанных рабочих нагрузок чтения/записи». 3 августа 2022 г. Получено 04.08.2022 г.
  2. ^ Тернер, Дж., Новые направления в коммуникациях (или каков путь к информационному веку?) . Журнал IEEE Communications Magazine 24 (10): 8–15. ISSN  0163-6804, 1986.
  3. ^ Эндрю С. Таненбаум, Компьютерные сети, четвертое издание , ISBN 0-13-166836-6 , Prentice Hall PTR, 2003 г., стр. 401. 
  4. ^ ATM Forum, Интерфейс пользовательской сети (UNI), v. 3.1, ISBN 0-13-393828-X , Prentice Hall PTR, 1995. 
  5. ^ МСЭ-Т, Управление трафиком и контроль перегрузки в B ISDN , Рекомендация I.371, Международный союз электросвязи, 2004 г., Приложение A, стр. 87.
  6. ^ "Домашняя страница Linux HTB" . Получено 2013-11-30 .

Дальнейшее чтение

  • Джон Эванс, Кларенс Филсфилс (2007). Развертывание IP и MPLS QoS для мультисервисных сетей: теория и практика . Морган Кауфманн. ISBN 978-0-12-370549-5.
  • Фергюсон П., Хьюстон Г. (1998). Качество обслуживания: предоставление QoS в Интернете и корпоративных сетях . John Wiley & Sons, Inc. ISBN 0-471-24358-2.
Взято с "https://en.wikipedia.org/w/index.php?title=Token_bucket&oldid=1242618301"