Дырявое ведро

Эта статья о компьютерном алгоритме. Чтобы узнать о метафоре экономического перераспределения, см. «Дырявое ведро» (экономика) .

Аналогия с дырявым ведром. В ведро можно периодически добавлять воду, которая вытекает с постоянной скоростью, пока не опустеет, а также перельется, когда наполнится.

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

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

Версия дырявого ведра, общего алгоритма скорости передачи данных , рекомендуется для сетей с асинхронным режимом передачи (ATM). в UPC и NPC на интерфейсах пользователь-сеть или межсетевых интерфейсах или интерфейсах сеть-сеть для защиты сети от чрезмерного уровня трафика на соединениях, маршрутизируемых через нее. Общий алгоритм скорости передачи ячеек или его эквивалент также может использоваться для формирования передач сетевой интерфейсной карты в сеть ATM.

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

Обзор

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

В одной версии сегмент представляет собой счетчик или переменную, отдельную от потока трафика или расписания событий. Этот счетчик используется только для проверки соответствия трафика или событий ограничениям: счетчик увеличивается по мере поступления каждого пакета в точку, где выполняется проверка, или при возникновении события, что эквивалентно тому, как периодически добавляется вода в ведро. Счетчик также уменьшается с фиксированной скоростью, аналогично тому, как вода вытекает из ведра. В результате значение счетчика представляет уровень воды в ведре. Если счетчик остается ниже заданного предельного значения при поступлении пакета или возникновении события, т. е. сегмент не переполняется, это указывает на его соответствие ограничениям пропускной способности и пакетной нагрузки или ограничениям событий средней и пиковой скорости. Эта версия упоминается здесь как дырявое ведро в качестве метра .

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

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

Как метр

ГИБДД с дырявым ведром в качестве счетчика

Джонатан С. Тернер указан с исходным описанием алгоритма дырявого ведра и описывает его следующим образом: «Счетчик, связанный с каждым пользователем, передающим по соединению, увеличивается каждый раз, когда пользователь отправляет пакет, и периодически уменьшается. Если счетчик превышает пороговое значение после увеличения, сеть отбрасывает пакет. Пользователь указывает скорость, с которой счетчик уменьшается (это определяет среднюю пропускную способность) и значение порога (мера пакетной активности). Ведро (аналог счетчика) в этом случае используется как счетчик для проверки соответствия пакетов, а не как очередь для их непосредственного контроля.

Другое описание того, что, по сути, является той же версией алгоритма измерителя, общего алгоритма скорости ячейки , дано ITU-T в рекомендации I.371 и в ATM Forum . спецификации UNI Описание, в котором термин « ячейка» эквивалентен пакету в описании Тернера. МСЭ-Т дает следующее: «Дырявое ведро с непрерывным состоянием можно рассматривать как ведро конечной емкости, реальное содержимое которого истощается с непрерывной скоростью 1 единица контента в единицу времени и чье содержимое увеличивается на приращение T для каждой соответствующей ячейки... Если при прибытии ячейки содержимое корзины меньше или равно предельному значению τ , то ячейка является соответствующей. В противном случае ячейка является несоответствующей. ведро (верхняя граница счетчика) равно ( T + τ )». В этих спецификациях также указано, что из-за ее конечной емкости, если содержимое корзины на момент проверки соответствия превышает предельное значение и, следовательно, ячейка не соответствует требованиям, то корзина остается неизменной; то есть воду просто не добавляют, если из-за этого ведро переполнится.

Дэвид Э. Макдайсан и Даррел Л. Спон предоставляют комментарии к описанию, данному Форумом ITU-T/ATM. При этом они заявляют: «В аналогии с дырявым ведром ячейки [ATM] фактически не проходят через ведро; это происходит только при проверке на соответствие допуску». Однако, что необычно в описаниях в литературе, Макдайсан и Спон также называют алгоритм дырявого ведра очередью, продолжая: «Обратите внимание, что одна из реализаций формирования трафика заключается в том, чтобы фактически заставить ячейки проходить через ведро».

Формирование трафика с помощью дырявого ведра в качестве счетчика

Описывая работу версии алгоритма ITU-T, Макдайсан и Спон используют «понятие, обычно используемое в теории массового обслуживания вымышленного гремлина ». Этот гремлин проверяет уровень в ведре и предпринимает действия, если уровень превышает предельное значение τ : при регулировании дорожного движения он открывает люк, что приводит к падению прибывающего пакета и предотвращению попадания его воды в ведро; при формировании трафика он поднимает вверх заслонку, которая задерживает приходящий пакет и не позволяет ему доставить свою воду, пока уровень воды в ведре не упадет ниже τ .

Разница между описаниями, данными Тернером и Форумом ITU-T/ATM, заключается в том, что описание Тернера относится конкретно к контролю трафика, тогда как описание Форума ITU-T/ATM применимо как к контролю трафика, так и к формированию трафика. Кроме того, Тернер не утверждает, что на содержимое счетчика должны влиять только соответствующие пакеты и его следует увеличивать только в том случае, если это не приведет к превышению предела, т. е. Тернер явно не заявляет, что емкость сегмента или максимальное значение счетчика конечно.

Концепция работы

Описание концепции работы алгоритма дырявого корзины как счетчика, который можно использовать либо при контроле трафика, либо при формировании трафика, можно описать как корзину фиксированной емкости, связанную с каждым виртуальным соединением или пользователем. Ведро протекает с фиксированной скоростью. Если ведро пустое, оно перестает протекать. Чтобы пакет соответствовал требованиям, в ведро должна быть возможность добавлять определенное количество воды. Конкретное количество, добавляемое соответствующим пакетом, может быть одинаковым для всех пакетов или может быть пропорционально длине пакета. Если из-за такого количества воды ведро переполнится, пакет не соответствует требованиям, и вода в ведре останется неизменной.

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

Дырявое ведро в качестве счетчика можно использовать как для формирования трафика, так и для контроля трафика . Например, в сетях ATM в форме общего алгоритма скорости ячейки он используется для сравнения пропускной способности и пакетной нагрузки трафика на виртуальном канале (VC) или виртуальном пути (VP) с указанными ограничениями скорости, на которой Ячейки могут прибывать и иметь максимальный джиттер или изменение интервалов между поступлениями для VC или VP. При контроле трафика ячейки, которые не соответствуют этим ограничениям (несоответствующие ячейки), могут быть отброшены или их приоритет может быть понижен для удаления функций управления нисходящим трафиком в случае перегрузки. При формировании трафика ячейки задерживаются до тех пор, пока не придут в соответствие. Контроль трафика и формирование трафика обычно используются в UPC и NPC для защиты сети от избыточного или чрезмерно пульсирующего трафика. (См. «Управление полосой пропускания и предотвращение перегрузок ».) Формирование трафика обычно используется в сетевых интерфейсах хостов, чтобы предотвратить выход передач за пределы полосы пропускания или джиттера и их отмену функциями управления трафиком в сети. (Видеть планирование (вычисления) и планировщик сети .)

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

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

Параметры

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

К соединению можно одновременно применять несколько наборов параметров контракта с использованием нескольких экземпляров алгоритма дырявого ведра, каждый из которых может иметь предел пропускной способности и пакетной нагрузки: см. Общий алгоритм скорости ячейки § Dual Leaky Bucket Controller .

Интервал выбросов

Скорость, с которой протекает ведро, будет определять предел пропускной способности, который Тернер называет средней скоростью. и обратная величина которого в ITU-T называется интервалом излучения. Проще всего объяснить, что это за интервал, когда пакеты имеют фиксированную длину. Следовательно, первая часть данного описания предполагает это, а последствия переменной длины пакетов рассматриваются отдельно.

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

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

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

Допуск на изменение задержки

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

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

Представьте себе следующую ситуацию: ведро протекает со скоростью 1 единица воды в секунду, поэтому предельное значение τ и количество воды, добавляемой пакетом, T фактически измеряются в секундах. Это ведро изначально пустое, поэтому, когда пакет прибывает в ведро, он не полностью заполняет ведро, добавляя в него воду T , и теперь ведро находится на τ ниже своей вместимости. Таким образом, когда прибывает следующий пакет, ведро должно быть опустошено только за T – τ , чтобы это соответствовало. Таким образом, интервал между этими двумя пакетами может быть на τ меньше T .

Это распространяется на несколько пакетов в последовательности: Представьте себе следующее: Корзина снова пуста, поэтому первый пришедший пакет явно соответствует. Затем корзина становится полностью заполненной после того, как несколько соответствующих пакетов N прибудут за минимально возможное время для их соответствия. Чтобы последний ( N -й) пакет соответствовал требованиям, из ведра должно вылиться достаточное количество воды из предыдущих N – 1 пакетов (( N – 1) × T секунд), чтобы оно достигло точно предельного значения τ. в это время. Следовательно, утечка воды равна ( N – 1) × T – τ , что, поскольку утечка составляет одну единицу в секунду, для утечки потребовалось ровно ( N – 1) × T – τ секунд. Таким образом, кратчайшее время, за которое все N пакетов могут прибыть и соответствовать, составляет ( N – 1) × T – τ секунд, что ровно на τ меньше, чем время, которое потребовалось бы, если бы пакеты прибыли точно в интервал отправки.

Однако пакеты могут приходить с интервалом меньше T только в том случае, если ведро не заполнено предыдущим пакетом. Если оно заполнено, то ведро должно быть опорожнено на полный объем T, прежде чем следующий пакет будет соответствовать требованиям. как только это пространство сегмента будет использовано пакетами, поступающими с интервалом меньше T , последующие кадры должны приходить с интервалом не меньше T. Таким образом , Однако они могут прибывать через большие промежутки времени, когда ведро ими не заполняется. Поскольку ведро перестает протекать, когда оно пусто, всегда существует предел ( τ превышающие T. ) того, какой допуск может быть достигнут за эти интервалы ,

Поскольку предельное значение τ определяет, насколько раньше пакет может прибыть, чем ожидалось, это предел разницы между максимальной и минимальной задержками от источника до точки, где проводится тест на соответствие (при условии, что пакеты генерируются без дрожания). Следовательно, для этого параметра в ATM используется термин «допуск на изменение задержки ячейки» (CDVt).

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

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

Максимальный размер пакета

Предельное значение или допуск на изменение задержки также контролирует, сколько пакетов может прийти в пакете, что определяется превышением глубины сегмента над емкостью, необходимой для одного пакета. Следовательно, MBS также является мерой пульсации или джиттера, и можно указать пакетную пульсацию как MBS и вывести из нее предельное значение τ или указать ее как допуск/предельное значение изменения джиттера/задержки и получить MBS из этот.

Пакет или группа пакетов может прибывать с более высокой скоростью, чем определяется интервалом передачи T . Это может быть скорость линии соединения физического уровня, когда пакеты в пакете будут приходить один за другим. Однако, как и в ATM, допуск может быть применен к более низкой скорости, в этом случае устойчивая скорость передачи ячеек (SCR), и пакет пакетов (ячеек) может достигать более высокой скорости, но меньшей, чем скорость линии связи. физический уровень, в данном случае пиковая скорость передачи данных (PCR). Тогда MBS может представлять собой количество ячеек, необходимых для транспортировки пакета более высокого уровня (см. сегментацию и повторную сборку ), где пакеты передаются с максимальной пропускной способностью, определяемой SCR, а ячейки внутри пакетов передаются в PCR; таким образом позволяя последней ячейке пакета и самому пакету прибыть значительно раньше, чем если бы ячейки были отправлены в SCR: продолжительность передачи = (MBS-1)/PCR, а не (MBS-1)/SCR. Такая пакетная передача в PCR создает значительно более высокую нагрузку на общие ресурсы, например, выходные буферы коммутатора, чем передача в SCR, и, таким образом, с большей вероятностью приведет к переполнению буфера и перегрузке сети. Однако это создает меньшую нагрузку на эти ресурсы, чем передача на SCR с предельным значением. τ _SCR , что позволяет ячейкам MBS передаваться и прибывать последовательно со скоростью линии.

Если предельное значение достаточно велико, то несколько пакетов могут прибыть пакетом и при этом соответствовать: если ведро начинается с пустого, первый прибывший пакет добавит T , но если к моменту прибытия следующего пакета содержимое будет ниже τ это также будет соответствовать. Предполагая, что для прибытия каждого пакета требуется δ , тогда, если τ (выраженное как время, необходимое для опорожнения ведра от предельного значения) равно или превышает интервал отправки за вычетом минимального времени между поступлениями T – δ , второй пакет будет соответствовать, даже если оно придет в виде пакета вместе с первым. Аналогично, если τ равно или больше ( T – δ ) × 2, то пакетом могут прийти 3 пакета и т. д.

Максимальный размер этого всплеска M можно рассчитать по интервалу выбросов T ; максимальная устойчивость к джиттеру, τ ; и время, необходимое для передачи/получения пакета, δ , следующим образом:

$M=\left\lfloor 1+{\frac {\tau }{T-\delta }}\right\rfloor$

Аналогичным образом, минимальное значение устойчивости к джиттеру τ , которое дает конкретный MBS, может быть рассчитано на основе MBS следующим образом:

$\tau =\left(M-1\right)\left(T-\delta \right)$

В случае ATM, где технически MBS относится только к допуску SCR, в приведенном выше уравнении время, необходимое для прибытия каждого пакета, δ , представляет собой интервал передачи для ячеек в PCR T _PCR , а интервал передачи T , — интервал эмиссии для SCR T _SCR . Если MBS — это количество ячеек, необходимых для транспортировки сегментированного пакета, то предельное значение, указанное выше, τ , должно быть таким же, как для SCR τ _SCR . Однако в UNI или NNI, где ячейки в PCR будут подвергаться изменению задержки, это должно быть предельное значение для SCR плюс значение для PCR τ _SCR + τ _PCR .

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

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

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

• Токен добавляется в корзину каждые 1/ r секунды.

• Ведро может содержать не более b жетонов. Если токен поступает, когда корзина заполнена, он отбрасывается.

• Когда пакет ( PDU сетевого уровня ) [ sic ] поступает «n» байт, n токенов удаляются из корзины и пакет отправляется в сеть.

• Если доступно менее n токенов, ни один токен не удаляется из корзины, и пакет считается несоответствующим.

Это можно сравнить с концепцией операции, повторенной выше:

• В сегменте фиксированной емкости, связанном с каждым виртуальным соединением или пользователем, происходит утечка с фиксированной скоростью.

• Если ведро пустое, оно перестает протекать.

• Чтобы пакет соответствовал требованиям, в ведро должна быть возможность добавить определенное количество воды: конкретное количество, добавляемое соответствующим пакетом, может быть одинаковым для всех пакетов или может быть пропорционально длине пакета.

• Если из-за такого количества воды ведро превысит свою вместимость, пакет не будет соответствовать требованиям, и вода в ведре останется неизменной.

Как можно видеть, эти два описания по сути являются зеркальным отражением друг друга: одно регулярно что-то добавляет в корзину, а что-то забирает для соответствующих пакетов вплоть до нулевого предела; другой регулярно забирает и добавляет соответствующие пакеты до предела емкости ведра. Итак, является ли реализация, которая добавляет токены для соответствующего пакета и удаляет их с фиксированной скоростью, реализацией дырявого ведра или ведра токенов? Аналогично, какой алгоритм используется в реализации, которая удаляет воду из соответствующего пакета и добавляет воду с фиксированной скоростью? Фактически оба они фактически одинаковы, т.е. реализации как дырявого ведра, так и ведра токенов, поскольку это один и тот же базовый алгоритм, описанный по-разному. Это объясняет, почему при эквивалентных параметрах оба алгоритма будут видеть одни и те же пакеты как соответствующие или несоответствующие. Таким образом, различия в свойствах и производительности реализаций алгоритмов дырявого и токен-корзины полностью являются результатом различий в реализациях, т. е. они не вытекают из различий в базовых алгоритмах.

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

Как очередь

«Дырявое» ведро как очередь — это, по сути, способ описания простого буфера или очереди FIFO , который обслуживается с фиксированной скоростью для устранения пульсаций или джиттера. Его описание дано Эндрю С. Таненбаумом в (более старой версии) его книги «Компьютерные сети» следующим образом: «Дырявое ведро состоит из конечной очереди. Когда пакет прибывает, если в очереди есть место, он добавляется к очередь; в противном случае она отбрасывается. На каждом такте передается один пакет (если очередь не пуста). Таким образом, реализация дырявого ведра в виде очереди всегда является формой функции формирования трафика.

Дырявое ведро как очередь

Как можно видеть, эта реализация ограничена тем, что пакеты передаются только с фиксированной скоростью. Чтобы подчеркнуть это, Таненбаум также заявляет, что «Алгоритм дырявого ведра обеспечивает жесткий шаблон вывода на средней скорости, независимо от того, насколько прерывистым является [входной] трафик». Однако это утверждение строго верно только до тех пор, пока очередь не становится пустой: если средняя скорость поступления меньше, чем частота тактов, или если входные данные достаточно импульсивны, так что потери приводят к тому, что скорость остатка становится ниже тактовой частоты (т. е. перерывы во входном потоке достаточно велики, а очередь настолько мала, что может стать пустой), в выходном потоке будут пробелы.

Еще одним ограничением является то, что дырявое ведро как функция формирования трафика очереди передает пакеты только по тактам; следовательно, если он используется внутри сети, что эквивалентно UPC и NPC , он также накладывает фиксированную фазу на последующую передачу пакетов. Принимая во внимание, что при использовании счетчика дырявого ведра для управления дальнейшей передачей пакет передается, как только он соответствует, т.е. относительно предыдущего или, если он уже соответствует, времени его прибытия; не по каким-то произвольным местным часам. И наоборот, в контексте задержки передачи такое введение фиксированной фазы, которая со временем может отличаться от фазы соответствующего входного потока пакетов, представляет собой изменение задержки и, следовательно, дрожание. Джиттер, вызванный таким конкретным образом, можно наблюдать только там, где задержка измеряется как время прохождения между двумя отдельными точками измерения, по одной с каждой стороны дырявого ведра, как функция формирования очереди. Однако в контексте передачи данных в реальном времени именно эта сквозная задержка определяет задержку полученных данных. Следовательно, «дырявое» ведро как очередь непригодно для передачи трафика в реальном времени.

Ограничение пакетов переменной длины с использованием алгоритма дырявого ведра в качестве очереди значительно сложнее, чем для пакетов фиксированной длины. Таненбаум дает описание дырявого ведра с «подсчетом байтов» для пакетов переменной длины следующим образом: «На каждом такте счетчик инициализируется значением n. Если первый пакет в очереди имеет меньше байтов, чем текущее значение счетчика, он передается, и счетчик уменьшается на это количество байтов. Также могут быть отправлены дополнительные пакеты, если счетчик достаточно велик. Когда счетчик падает ниже длины следующего пакета в очереди, передача прекращается до тех пор, пока не будет достигнуто значение счетчика. следующий тик, после чего счетчик остаточных байт сбрасывается [на n] и поток может продолжаться». Как и в случае с версией для пакетов фиксированной длины, эта реализация сильно влияет на фазу передачи, что приводит к переменным сквозным задержкам и непригодности для формирования трафика в реальном времени.

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

Дырявое ведро в качестве очереди можно использовать только для формирования трафика до заданной полосы пропускания без дрожания выходного сигнала. Его можно использовать внутри сети, например, как часть управления полосой пропускания, но он больше подходит для формирования трафика в сетевых интерфейсах хостов. Алгоритм дырявого ведра используется в модуле Nginx ngx_http_limit_conn_module для ограничения количества одновременных подключений, исходящих с одного IP-адреса .

Параметры

В случае алгоритма дырявого ведра в виде очереди единственным определенным ограничением для этого алгоритма является пропускная способность его выходных данных.

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

Неэффективность

Реализация дырявого ведра в виде очереди не позволяет эффективно использовать доступные сетевые ресурсы. Поскольку он передает пакеты только через фиксированные интервалы, во многих случаях объем трафика будет очень низким и большая часть сетевых ресурсов (в частности, пропускная способность) не будет использоваться. Поэтому в реализации «дырявого ведра» не существует механизма в виде очереди, который позволял бы отдельным потокам разгоняться до скорости порта, эффективно потребляя сетевые ресурсы в моменты, когда в сети не было бы конкуренции за ресурсы. Однако реализации корзины токенов и дырявой корзины в качестве счетчика позволяют выходным потокам трафика иметь неравномерные характеристики.

Сравнение двух версий

Анализ двух версий алгоритма дырявого ведра показывает, что версия в виде очереди является частным случаем версии в виде счетчика.

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

Однако реализация дырявого ведра в виде счетчика (или токена) в описанной выше функции формирования трафика является точным эквивалентом описания дырявого ведра как очереди: элементом задержки версии счетчика является сегмент версии очереди; ведро версии счетчика — это процесс, обслуживающий очередь, а утечка такова, что интервал эмиссии совпадает с интервалом тиков. Следовательно, для пакетов фиксированной длины реализация дырявого ведра в виде очереди представляет собой частный случай функции формирования трафика, использующей дырявый ведро (или ведро токенов) в качестве счетчика, в котором предельное значение τ равно нулю, а процесс Тестирование на соответствие проводится с минимально возможной скоростью.

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

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

См. также

• Жидкая очередь
• Общий алгоритм скорости передачи данных
• Корзина токенов
• Договор дорожного движения
• СКП и НПС