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

Рисунок 1: Аналогия с дырявым ведром

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

Он используется в пакетной коммутации компьютерных сетей и телекоммуникационных сетей в обоих трафика полицейских и формирования трафика по передаче данных , в виде пакетов , ^{[примечание 1]} до определенных пределов по ширине полосы и пакетирования (мера неравномерности или вариаций трафик поток). Его также можно использовать в качестве алгоритма планирования для определения времени передачи, которое будет соответствовать ограничениям, установленным для полосы пропускания и пакетной передачи, применяемым сетью: см. Сетевой планировщик . ^{[1][2] [3] [4]} Вариант дырявого ведра, в алгоритме общей скорости клеток , рекомендуется для асинхронного режима передачи (АТМ) ^[5] в Использовании / сети управления Параметром при пользователе сетевых интерфейсов или межсетевом интерфейсы или межсетевые интерфейсы для защиты сети от чрезмерных уровней трафика на соединениях, маршрутизируемых через нее. Общий алгоритм скорости передачи ячеек или его эквивалент также может использоваться для формирования передачи с помощью сетевой карты.в сеть ATM (то есть на стороне пользователя пользовательско-сетевого интерфейса), например, до уровней ниже уровней, установленных для управления использованием / параметрами сети в сети, чтобы предотвратить принятие мер по дальнейшему ограничению этого соединения. Алгоритм дырявого ведра также используется в счетчиках дырявого ведра, например, для обнаружения того, когда средняя или пиковая скорость случайных или стохастических событий или стохастических процессов , таких как сбои или отказы, превышает определенные пределы.

По крайней мере, некоторые реализации дырявого ведра являются зеркальным отображением алгоритма Token Bucket и с учетом эквивалентных параметров будут определять точно такую ​​же последовательность событий, чтобы соответствовать или не соответствовать тем же ограничениям. Однако есть как минимум два разных описания дырявого ведра, которые могут вызвать путаницу. ^{[1] [2] [6]}

Обзор [ править ]

В литературе описаны два различных метода применения этой аналогии с дырявым ведром. ^{[1] [2] [3] [4]} Они дают то, что кажется двумя разными алгоритмами, оба из которых называются алгоритмом дырявого ведра и, как правило, без ссылки на другой метод. Это привело к путанице в отношении того, что такое алгоритм дырявого ведра и каковы его свойства.

В одном из вариантов применения аналогии аналог ведра - это счетчик или переменная, отдельная от потока трафика или планирования событий. ^{[1] [3] [4]}Этот счетчик используется только для проверки того, что трафик или события соответствуют ограничениям: счетчик увеличивается, когда каждый пакет прибывает в точку, где выполняется проверка или происходит событие, что эквивалентно способу, которым вода периодически добавляется в ведро. Счетчик также уменьшается с фиксированной скоростью, эквивалентной тому, как вода вытекает из ведра. В результате значение счетчика представляет собой уровень воды в аналогичном ведре. Если значение счетчика остается ниже указанного предельного значения при поступлении пакета или возникновении события, т. Е. Сегмент не переполняется, это указывает на его соответствие ограничениям полосы пропускания и пакетной передачи или ограничениям для событий средней и пиковой скорости. Таким образом, в этой версии аналог воды переносится пакетами или событиями, добавляемыми в ведро при их прибытии или возникновении,а затем утекает. Эта версия упоминается здесь какдырявое ведро как метр .

Во втором варианте аналог ведра - очередь в потоке трафика. ^[2] Эта очередь используется для непосредственного управления этим потоком: пакеты помещаются в очередь по мере их поступления, что эквивалентно добавлению воды в ведро. Затем эти пакеты удаляются из очереди ( первым пришел, первым обслужен.), обычно с фиксированной скоростью, например, для дальнейшей передачи, что эквивалентно утечке воды из ведра. В результате скорость, с которой обслуживается очередь, напрямую контролирует скорость дальнейшей передачи трафика. Таким образом, он налагает соответствие, а не его проверку, и если очередь обслуживается с фиксированной скоростью (и где все пакеты имеют одинаковую длину), результирующий поток трафика обязательно лишен пакетности или дрожания. Таким образом, в этой версии сам трафик является аналогом воды, проходящей через ведро. Непонятно, как эту версию применения аналогии можно использовать для проверки частоты дискретных событий. Эта версия упоминается здесь как дырявое ведро как очередь .

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

Как счетчик [ править ]

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

Другое описание того, что по сути является той же версией алгоритма счетчика, общего алгоритма скорости передачи ячеек , дается ITU-T в рекомендации I.371 и в спецификации UNI форума ATM . ^{[3] [4]} Описание, в котором термин ячейка эквивалентен пакету в описании Тернера ^[1] , дается ITU-T следующим образом: «Дырявое ведро с непрерывным состоянием можно рассматривать как ведро с конечной емкостью, Реальный контент истекает с постоянной скоростью 1 единица контента в единицу времени, и чье содержание увеличивается на приращение Tдля каждой соответствующей ячейки ... Если при поступлении ячейки содержимое корзины меньше или равно предельному значению τ , то ячейка соответствует; в противном случае ячейка не соответствует требованиям. Емкость корзины (верхняя граница счетчика) равна ( T + τ ) ". ^{[4] В} этих спецификациях также указывается, что из-за ее конечной емкости, если содержимое корзины на момент проверки соответствия будет больше, чем предельное значение, и, следовательно, ячейка не соответствует требованиям, то ведро остается без изменений; то есть вода просто не добавляется, если это может вызвать переполнение ведра.

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

При описании работы версии алгоритма ITU-T МакДайсан и Спон ссылаются на «понятие вымышленного« гремлина », обычно используемое в теории очередей ». ^[6] Этот гремлин проверяет уровень в ведре и предпринимает действия, если уровень превышает предельное значение τ  : при контроле (рис. 2) он открывает люк, что приводит к отбрасыванию прибывающего пакета и останавливает его воду. от попадания в ведро; при формировании (рис. 3) он толкает вверх заслонку, которая задерживает прибывающий пакет и не дает ему доставить воду до тех пор, пока уровень воды в ведре не упадет ниже τ .

Разница между описаниями, данными Тернером и форумом ITU-T / ATM, состоит в том, что Тернер относится к контролю трафика , тогда как форум ITU-T / ATM применим как к контролю трафика, так и к формированию трафика. Кроме того, Тернер не утверждает, что на содержимое счетчика должны влиять только соответствующие пакеты, и должно увеличиваться только тогда, когда это не приведет к превышению лимита, т.е. Тернер не указывает явно, что емкость корзины или максимальное значение счетчика конечно. Чтобы описание Тернера было четко согласовано с ITU-T, утверждение «Если счетчик превышает пороговое значение при увеличении, сеть отбрасывает пакет» необходимо изменить на что-то вроде «Если счетчик превысит порог [эквивалентный глубина ковша,Т + т, в описании ITU-T] после увеличения сеть отбрасывает пакет, и счетчик не увеличивается », т. е. он увеличивается только тогда, когда он меньше или равен предельному значению τ или, по крайней мере, T меньше чем глубина сегмента в описании ITU-T.

Хотя описание, данное Тернером, не утверждает, что на счетчик должны влиять только соответствующие пакеты, оно дается в терминах функции контроля трафика, где чрезмерное усердие в ограничении соединения, содержащего несоответствующие пакеты, может не быть проблемой. Действительно, в некоторых контекстах, таких как переменный битрейт(VBR), потеря любого одного пакета может привести к повреждению всего сообщения более высокого уровня, например PDU сетевого уровня OSI. В этом случае отбрасывание всех следующих пакетов этого поврежденного PDU снижает ненужную нагрузку на сеть. Однако было бы совершенно неприемлемо при формировании трафика для пакета, который не прошел тест на соответствие, влиять на то, как долго до следующего соответствия может произойти, то есть если акт тестирования последующего пакета на соответствие изменит, как долго пакет, ожидающий соответствия в данный момент, будет ждать. Это именно то, что произошло бы, если бы воду из несоответствующих пакетов добавить в ведро, поскольку любые последующие несоответствующие пакеты поднимут уровень воды и, таким образом, заставят пакет, ожидающий согласования, ждать дольше.

Ни Тернер, ни ITU-T не решают проблему пакетов переменной длины. Однако описание согласно ITU-T предназначено для ячеек ATM, которые представляют собой пакеты фиксированной длины, и Тернер специально не исключает пакеты переменной длины. Следовательно, в обоих случаях, если величина, на которую увеличивается содержимое корзины или счетчик для соответствующего пакета, пропорциональна длине пакета, они оба будут учитывать длину и позволяют алгоритму явно ограничивать полосу пропускания трафика, а не ограничение скорости передачи пакетов. Например, более короткие пакеты добавят меньше в корзину и, следовательно, могут прибыть с меньшими интервалами; тогда как более длинные пакеты добавят больше и, следовательно, должны быть разделены пропорционально большими интервалами для соответствия.

Концепция операции [ править ]

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

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

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

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

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

Использует [ редактировать ]

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

Алгоритм дырявого ведра в качестве счетчика также может использоваться в счетчике дырявого ведра для измерения скорости случайных или случайных процессов . Счетчик Leaky bucket может использоваться для определения того, когда средняя или пиковая частота событий превышает некоторый приемлемый фоновый уровень, то есть когда ведро переполняется. ^[8] Однако события, которые не вызывают переполнения, т. Е. Имеют достаточно низкие скорости и хорошо распределяются во времени, можно игнорировать. Например, такой счетчик дырявого ведра можно использовать для обнаружения внезапного всплеска исправимых ошибок памяти или постепенного, но значительного увеличения средней скорости, что может указывать на надвигающийся отказ ^[9]. и Т. Д.

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

Параметры [ править ]

В случае алгоритма дырявого ведра в качестве счетчика ограничениями трафика могут быть полоса пропускания и периодичность выходных данных. ^{[3] [4] [примечание 2]}

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

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

Интервал выброса [ править ]

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

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

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

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

Допуск изменения задержки [ править ]

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

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 , однако, намного больше, чем T, они могут быть или, тем не менее, многие из них существуют.

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

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

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

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

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

Взрыв или скопление пакетов может прибыть на более высокой скорости , чем определяется излучением интервала Т . Это может быть линейная скорость соединения физического уровня, когда пакеты в пакете будут приходить друг за другом. Однако, как и в 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 ; максимальный допуск джиттера, τ ; и время, необходимое для передачи / приема пакета, δ , как указано ниже: ^[3]

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

Точно так же минимальное значение допуска джиттера τ, которое дает конкретный MBS, может быть вычислено из MBS следующим образом: ^[3]

${\ Displaystyle \ тау = \ влево (М-1 \ вправо) \ влево (Т- \ дельта \ вправо)}$

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

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

Сравнение с алгоритмом token bucket [ править ]

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

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

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

• Когда приходит пакет ( PDU сетевого уровня ) [ sic ] ^{[примечание 1]} из "n" байтов, n маркеров удаляются из корзины, и пакет отправляется в сеть.

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

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

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

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

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

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

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

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

В очереди [ править ]

Дырявое ведро как очередь - это, по сути, способ описания простого буфера FIFO или очереди, которые обслуживаются с фиксированной скоростью для устранения скачков или дрожания. Его описание дано Эндрю С. Таненбаумом в (более старой версии) его книги « Компьютерные сети »: «Дырявое ведро состоит из конечной очереди. Когда приходит пакет, если в очереди есть место, он добавляется к очередь; в противном случае он отбрасывается. При каждом такте часов передается один пакет (если очередь не пуста) ". ^[2] Реализация дырявого ведра в виде очереди всегда является формой функции формирования трафика.

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

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

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

Использует [ редактировать ]

Дырявое ведро в качестве очереди можно использовать только для формирования трафика в соответствии с указанной полосой пропускания без дрожания на выходе. ^[10] Его можно использовать в сети, например, как часть управления полосой пропускания, но он больше подходит для формирования трафика в сетевых интерфейсах хостов.

Параметры [ править ]

В случае алгоритма дырявого ведра в качестве очереди единственным определенным пределом для этого алгоритма является пропускная способность его вывода. ^{[10] [примечание 2]}

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

Неэффективность [ править ]

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

Сравнение двух версий [ править ]

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

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

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

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

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

См. Также [ править ]

• Общий алгоритм скорости передачи ячеек
• UPC и NPC
• Контракт на движение
• Ведро токенов
• Жидкая очередь

Примечания [ править ]

Ссылки [ править ]