Корзина токенов

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

Обзор

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

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

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

Алгоритм

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

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

Вариации

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

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

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

В долгосрочной перспективе вывод соответствующих пакетов ограничивается скоростью токена. $r$ .

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

Позволять $M$ — максимально возможная скорость передачи в байтах/секунду.

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

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

Использование

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

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

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

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

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

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

Иерархический сегмент токенов

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

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

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

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

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

См. также

Ссылки

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

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

Джон Эванс, Кларенс Филсфилс (2007). Развертывание QoS IP и MPLS для мультисервисных сетей: теория и практика . Морган Кауфманн. ISBN 978-0-12-370549-5 .
Фергюсон П., Хьюстон Г. (1998). Качество обслуживания: обеспечение качества обслуживания в Интернете и в корпоративных сетях . Джон Уайли и сыновья, Inc. ISBN 0-471-24358-2 .

[Scylla_IO_sched-1] «Реализация нового алгоритма планировщика ввода-вывода для смешанных рабочих нагрузок чтения/записи» . 3 августа 2022 г. Проверено 4 августа 2022 г.

[Turner-2] Тернер, Дж., Новые направления в коммуникациях (или путь к веку информации?) . Журнал IEEE Communications 24 (10): 8–15. ISSN 0163-6804 , 1986.

[Tanenbaum-lbaq-3] Перейти обратно: ^а ^б Эндрю С. Таненбаум, Компьютерные сети, четвертое издание , ISBN 0-13-166836-6 , PTR Prentice Hall, 2003 г., стр. 401.

[ATMF-GCRA-4] Форум ATM, Пользовательский сетевой интерфейс (UNI), версия 3.1, ISBN 0-13-393828-X , PTR Прентис-Холл, 1995.

[ITU-T-GCRA-5] ITU-T, Управление трафиком и контроль перегрузок в B ISDN , Рекомендация I.371, Международный союз электросвязи, 2004 г., Приложение A, стр. 87.

[Linux_HTB-6] «Домашняя страница Linux HTB» . Проверено 30 ноября 2013 г.

[1]

[2]

[3]

[4]

[5]

[6]