Дырявое ведро - Leaky bucket
Дырявое ведро представляет собой алгоритм , основанный на аналогии того , как ковш с постоянной утечкой будет переполнением , если либо средняя скорость , с которой вода заливается в превышает скорость , с которой протекает ведро или , если больше воды , чем емкость ковша залил все сразу. Он может быть использован , чтобы определить , является ли некоторая последовательность дискретных событий Соответствия норм в определенные пределы на их средних и пиковые скоростях или частотах, например , ограничить действия , связанные с этими событиями по этим ставкам или задержать их , пока они не действительно соответствуют ставкам. Его также можно использовать для проверки соответствия или ограничения только средней скорости, т. Е. Удаления любых отклонений от средней.
Он используется в пакетной коммутации компьютерных сетей и телекоммуникационных сетей в обоих трафика полицейских и формирования трафика по передаче данных , в виде пакетов , в определенных пределах по полосе пропускания и пакетирования (мера неравномерности или вариаций в трафика потока) . Его также можно использовать в качестве алгоритма планирования для определения времени передачи, которое будет соответствовать ограничениям, установленным для полосы пропускания и пакетной передачи, применяемым сетью: см. Сетевой планировщик . Версия «дырявого ведра», общий алгоритм скорости передачи ячеек , рекомендуется для сетей с асинхронным режимом передачи (ATM) в управлении использованием / параметрами сети на пользовательско-сетевых интерфейсах или межсетевых интерфейсах или межсетевых интерфейсах для защиты сети. от чрезмерных уровней трафика на маршрутизируемых через него соединениях. Общий алгоритм скорости передачи ячеек или его эквивалент может также использоваться для формирования передач с помощью сетевой интерфейсной карты в сеть ATM (т. Е. На стороне пользователя пользовательско-сетевого интерфейса), например, до уровней ниже уровней, установленных для использования / Управление параметрами сети в сети, чтобы предотвратить дальнейшее ограничение этого соединения. Алгоритм дырявого ведра также используется в счетчиках дырявого ведра, например, для обнаружения того, когда средняя или пиковая скорость случайных или стохастических событий или стохастических процессов , таких как сбои или отказы, превышает определенные пределы.
По крайней мере, некоторые реализации дырявого ведра являются зеркальным отражением алгоритма Token Bucket и при заданных эквивалентных параметрах определяют точно такую же последовательность событий, чтобы соответствовать или не соответствовать тем же ограничениям. Однако есть как минимум два разных описания дырявого ведра, которые могут вызвать путаницу.
Обзор
В литературе описаны два различных метода применения этой аналогии с дырявым ведром. Они дают то, что кажется двумя разными алгоритмами, оба из которых называются алгоритмом дырявого ведра и, как правило, без ссылки на другой метод. Это привело к путанице в отношении того, что такое алгоритм дырявого ведра и каковы его свойства.
В одном из вариантов применения аналогии аналог ведра - это счетчик или переменная, отдельная от потока трафика или планирования событий. Этот счетчик используется только для проверки того, что трафик или события соответствуют ограничениям: счетчик увеличивается, когда каждый пакет прибывает в точку, где выполняется проверка или происходит событие, что эквивалентно способу, которым вода периодически добавляется в ведро. Счетчик также уменьшается с фиксированной скоростью, эквивалентной тому, как вода вытекает из ведра. В результате значение счетчика представляет собой уровень воды в аналогичном ведре. Если значение счетчика остается ниже заданного предельного значения, когда приходит пакет или происходит событие, т. Е. Сегмент не переполняется, это указывает на его соответствие ограничениям полосы пропускания и пакетной передачи или ограничениям для событий средней и пиковой скорости. Таким образом, в этой версии аналог воды переносится пакетами или событиями, добавляется в ведро при их прибытии или возникновении, а затем утекает. Этот вариант здесь именуется дырявым ведром как счетчик .
Во втором варианте аналог ведра - очередь в потоке трафика. Эта очередь используется для непосредственного управления этим потоком: пакеты помещаются в очередь по мере их поступления, что эквивалентно добавлению воды в ведро. Затем эти пакеты удаляются из очереди ( первым пришел - первым обслужен ), обычно с фиксированной скоростью, например, для дальнейшей передачи, что эквивалентно утечке воды из ведра. В результате скорость, с которой обслуживается очередь, напрямую контролирует скорость дальнейшей передачи трафика. Таким образом, он налагает соответствие, а не его проверку, и если очередь обслуживается с фиксированной скоростью (и где все пакеты имеют одинаковую длину), результирующий поток трафика обязательно лишен пакетности или дрожания. Так что в этой версии сам трафик является аналогом воды, проходящей через ведро. Неясно, как эту версию применения аналогии можно использовать для проверки частоты дискретных событий. Эта версия упоминается здесь как дырявое ведро как очередь .
Дырявое ведро как счетчик в точности эквивалентно (зеркальному отображению) алгоритму ведра токенов , то есть процесс добавления воды в дырявое ведро точно отражает процесс удаления токенов из ведра токенов, когда приходит соответствующий пакет, процесс Утечка воды из дырявого ведра точно соответствует тому, что происходит при регулярном добавлении жетонов в ведро для жетонов, а проверка того, что протекающее ведро не переполняется, является зеркалом проверки того, что ведро для жетонов содержит достаточно жетонов и не будет «переполнено». Таким образом, при заданных эквивалентных параметрах два алгоритма будут рассматривать один и тот же трафик как соответствующий или несоответствующий. Дырявое ведро как очередь можно рассматривать как частный случай дырявого ведра как счетчика.
Как метр
Джонатану С. Тернеру приписывают первоначальное описание алгоритма дырявого ведра, и он описывает его следующим образом: «Счетчик, связанный с каждым пользователем, выполняющим передачу по соединению, увеличивается каждый раз, когда пользователь отправляет пакет, и периодически уменьшается. После увеличения порога сеть отбрасывает пакет. Пользователь указывает скорость уменьшения счетчика (это определяет среднюю полосу пропускания) и значение порога (мера пакетности) ». Бакет (аналог счетчика) в этом случае используется как счетчик для проверки соответствия пакетов, а не как очередь для непосредственного управления ими.
Другое описание того, что по сути является той же версией алгоритма счетчика, общего алгоритма скорости ячеек , дано ITU-T в рекомендации I.371 и в спецификации UNI форума ATM . Описание, в котором термин ячейка эквивалентен пакету в описании Тернера, дано ITU-T следующим образом: «Дырявое ведро с непрерывным состоянием можно рассматривать как ведро с конечной емкостью, реальное содержание которого истекает с непрерывной скорость 1 единица содержимого в единицу времени, и содержимое которой увеличивается на приращение T для каждой соответствующей ячейки ... Если при поступлении ячейки содержимое корзины меньше или равно предельному значению τ , тогда ячейка соответствует; в противном случае ячейка не соответствует требованиям. Вместимость корзины (верхняя граница счетчика) равна ( T + τ ) ". В этих спецификациях также указано, что из-за его конечной емкости, если содержимое корзины на момент проверки соответствия превышает предельное значение, и, следовательно, ячейка не соответствует требованиям, то корзина остается неизменной; то есть вода просто не добавляется, если это приведет к переполнению ведра.
Дэвид Э. МакДайсан и Даррел Л. Спон комментируют описание, данное Форумом ITU-T / ATM. В этом они заявляют: «В аналогии с дырявым ведром ячейки [банкомата] на самом деле не протекают через ведро; это происходит только при проверке на соответствие допуску». Однако, что нечасто в описаниях в литературе, МакДайсан и Спон также называют алгоритм дырявого ведра очередью, продолжая: «Обратите внимание, что одна из реализаций формирования трафика состоит в том, чтобы фактически обеспечить прохождение ячеек через ведро».
При описании работы версии алгоритма ITU-T МакДайсан и Спон ссылаются на «понятие вымышленного« гремлина », обычно используемое в теории очередей ». Этот гремлин проверяет уровень в ведре и предпринимает действия, если уровень выше предельного значения τ : при контроле (рис. 2) он открывает люк, что приводит к отбрасыванию прибывающего пакета и предотвращает попадание воды в него. ведро; при формировании (рис. 3) он толкает вверх заслонку, которая задерживает прибывающий пакет и не дает ему доставить воду до тех пор, пока уровень воды в ведре не упадет ниже τ .
Разница между описаниями, данными Тернером и форумом ITU-T / ATM, заключается в том, что Тернер относится к контролю трафика , тогда как форум ITU-T / ATM применим как к контролю трафика, так и к формированию трафика. Кроме того, Тернер не утверждает, что на содержимое счетчика должны влиять только соответствующие пакеты, и должно увеличиваться только тогда, когда это не приведет к превышению лимита, т.е. Тернер не указывает явно, что емкость корзины или максимальное значение счетчика конечно. Чтобы описание Тернера было четко согласовано с ITU-T, утверждение «Если счетчик превышает пороговое значение при увеличении, сеть отбрасывает пакет», необходимо изменить на что-то вроде «Если счетчик превысит порог [эквивалентный глубина сегмента, 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 может использоваться для определения того, когда средняя или пиковая частота событий превышает некоторый допустимый фоновый уровень, то есть когда ведро переполняется. Однако события, которые не вызывают переполнения, т.е. имеют достаточно низкие скорости и хорошо распределены во времени, можно игнорировать. Например, такой счетчик дырявого ведра можно использовать для обнаружения внезапного всплеска исправимых ошибок памяти или постепенного, но значительного увеличения средней скорости, что может указывать на надвигающийся отказ и т. Д.
Использование алгоритма дырявого ведра в счетчике дырявого ведра аналогично таковому в управлении трафиком в том смысле, что он используется в качестве счетчика. По сути, события заменяют пакеты в описании, при этом каждое событие вызывает добавление воды в ведро. Если ведро переполнится в результате события, то событие должно инициировать действие, связанное с событием выхода за пределы. Некоторые реализации кажутся параллельными описанию Тернера, поскольку нет явного ограничения на максимальное значение, которое может принимать счетчик, подразумевая, что после того, как счетчик превысил пороговое значение, он не может вернуться в свое предыдущее состояние до тех пор, пока период, значительно превышающий эквивалент интервала выбросов пройден, который может быть увеличен за счет событий, которые в противном случае были бы соответствующими. Однако другие реализации могут не увеличивать счетчик, когда он переполнен, что позволяет ему правильно определять, соответствуют ли следующие события или нет.
Параметры
В случае алгоритма дырявого ведра в качестве счетчика ограничениями трафика могут быть полоса пропускания и периодичность вывода.
Предел пропускной способности и предел пакетной передачи для соединения могут быть указаны в контракте на трафик . Предел полосы пропускания может быть указан как частота пакетов или кадров, скорость передачи байтов или битов , или как интервал передачи между пакетами. Предел пакетной передачи может быть определен как допуск отклонения дрожания или задержки или как максимальный размер пакета (MBS).
Несколько наборов параметров контракта могут применяться одновременно к соединению с использованием нескольких экземпляров алгоритма дырявого ведра, каждый из которых может принимать полосу пропускания и предел пакетной передачи: см. Контроллер двойного дырявого ведра .
Интервал выброса
Скорость, с которой происходит утечка из ведра, будет определять предел ширины полосы, который Тернер называет средней скоростью, а обратная величина - интервалом излучения в 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 , однако, намного больше, чем 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 ; максимальный допуск джиттера, τ ; и время, необходимое для передачи / приема пакета, δ , как указано ниже:
Точно так же минимальное значение допуска джиттера τ, которое дает конкретный MBS, может быть вычислено из MBS следующим образом:
В случае ATM, где технически MBS относится только к допуску SCR, в приведенном выше уравнении время, необходимое для доставки каждого пакета, δ , представляет собой интервал излучения для ячеек в PCR T PCR , а интервал излучения T , - интервал излучения для SCR T SCR . Если MBS должно быть количеством ячеек, необходимых для транспортировки сегментированного пакета, предельное значение в приведенном выше, τ , должно быть таким же, как и для SCR τ SCR . Однако в UNI или NNI, где ячейки в PCR будут подвергаться изменению задержки, это должно быть предельное значение для SCR плюс значение для PCR τ SCR + τ PCR .
Для пакетов переменной длины максимальный размер пакета будет зависеть от длины пакетов в пакете, и нет единого значения для максимального размера пакета. Однако можно указать общую длину пакета в байтах, исходя из байтовой скорости входящего потока, эквивалентной байтовой скорости утечки и глубины сегмента.
Сравнение с алгоритмом token bucket
Алгоритм дырявого ведра иногда противопоставляется алгоритму маркерного ведра . Однако изложенную выше концепцию работы с дырявым ведром в качестве счетчика можно напрямую сравнить с алгоритмом маркерного ведра, описание которого приводится в этой статье следующим образом:
- Токен добавляется в корзину каждые 1 / r секунд.
- В ведре может храниться не более b жетонов. Если жетон приходит, когда ведро заполнено, он сбрасывается.
- Если доступно менее n токенов, токены не удаляются из корзины, и пакет считается несоответствующим.
Это можно сравнить с концепцией работы, повторенной сверху:
- Корзина фиксированной емкости, связанная с каждым виртуальным подключением или пользователем, протекает с фиксированной скоростью.
- Если ведро пустое, оно перестанет протекать.
- Чтобы пакет соответствовал требованиям, должна быть возможность добавить определенное количество воды в ведро: конкретное количество, добавляемое соответствующим пакетом, может быть одинаковым для всех пакетов или может быть пропорционально длине пакета.
- Если такое количество воды приведет к превышению емкости ведра, значит, пакет не соответствует требованиям, и вода в ведре останется неизменной.
Как можно видеть, эти два описания, по сути, являются зеркальным отображением друг друга: одно регулярно что-то добавляет в корзину и что-то убирает для согласования пакетов до нулевого предела; другой регулярно убирает и добавляет для согласованных пакетов до предела емкости корзины. Итак, является ли реализация, которая добавляет токены для соответствующего пакета и удаляет их с фиксированной скоростью, реализацией дырявого ведра или маркерного ведра? Аналогично, какой алгоритм используется в реализации, которая удаляет воду из соответствующего пакета и добавляет воду с фиксированной скоростью? Фактически, оба они фактически одинаковы, то есть реализации как дырявого ведра, так и маркерного ведра, поскольку это один и тот же базовый алгоритм, описанный по-разному. Это объясняет, почему при заданных эквивалентных параметрах два алгоритма будут видеть одни и те же пакеты как соответствующие или несоответствующие. Таким образом, различия в свойствах и производительности реализаций алгоритмов дырявых и токен-бакетов полностью связаны с различиями в реализациях, то есть они не связаны с различиями в базовых алгоритмах.
Следует отметить, что алгоритм дырявого ведра, когда он используется в качестве счетчика, может разрешить соответствующий выходной поток пакетов с джиттером или пакетностью, может использоваться как в контроле трафика, так и в формировании, и может быть реализован для пакетов переменной длины.
Как очередь
Дырявое ведро как очередь - это, по сути, способ описания простого буфера или очереди FIFO, которая обслуживается с фиксированной скоростью для устранения скачкообразия или дрожания. Его описание дано Эндрю С. Таненбаумом в (более старой версии) его книги « Компьютерные сети »: «Дырявое ведро состоит из конечной очереди. Когда приходит пакет, если в очереди есть место, он добавляется к очередь; в противном случае он отбрасывается. При каждом такте часов передается один пакет (если очередь не пуста) ". Таким образом, реализация дырявого ведра в виде очереди всегда является формой функции формирования трафика.
Как можно видеть, эта реализация ограничена тем, что пакеты всегда передаются только с фиксированной скоростью. Чтобы подчеркнуть это, Таненбаум также заявляет, что «Алгоритм дырявого ведра обеспечивает жесткую схему вывода со средней скоростью, независимо от того, насколько импульсным является [входной] трафик». Однако это утверждение строго верно только до тех пор, пока очередь не становится пустой: если средняя скорость поступления меньше, чем частота тактов часов, или если входной сигнал достаточно прерывистый, чтобы потери привели к тому, что скорость остатка была ниже тактовая частота (т.е. промежутки во входном потоке достаточно велики, а очередь достаточно мала, чтобы она могла стать пустой), в выходном потоке будут промежутки.
Еще одно ограничение состоит в том, что дырявое ведро как функция формирования трафика очереди передает пакеты только в тактах; следовательно, если он используется в сети, что эквивалентно UPC и NPC , он также накладывает фиксированную фазу на дальнейшую передачу пакетов. Принимая во внимание, что при использовании счетчика дырявого ведра для управления дальнейшей передачей пакет передается, как только он соответствует, то есть относительно предыдущего или, если он уже соответствует, времени его прибытия; не по каким-то произвольным местным часам. И наоборот, в контексте задержки передачи это наложение фиксированной фазы, которая может со временем отличаться от фазы входящего потока пакетов, в остальном согласованного, составляет изменение задержки и, следовательно, дрожание. Джиттер, вызванный этим конкретным образом, может наблюдаться только тогда, когда задержка измеряется как время прохождения между двумя отдельными точками измерения, одна с каждой стороны дырявого ведра, как функция формирования очереди. Однако в контексте передачи данных в реальном времени именно эта сквозная задержка определяет задержку полученных данных. Следовательно, дырявое ведро в качестве очереди не подходит для передачи в реальном времени с формированием трафика.
Ограничение пакетов переменной длины с использованием алгоритма дырявого ведра в качестве очереди значительно сложнее, чем для пакетов фиксированной длины. Таненбаум дает следующее описание дырявого ведра «подсчета байтов» для пакетов переменной длины: «В каждом такте счетчик инициализируется равным n. Если первый пакет в очереди имеет меньше байтов, чем текущее значение счетчика, он передается, и счетчик уменьшается на это количество байтов. Дополнительные пакеты также могут быть отправлены, если счетчик достаточно высок. Когда счетчик падает ниже длины следующего пакета в очереди, передача прекращается до тех пор, пока следующий тик, при котором остаточный счетчик байтов сбрасывается [до n], и поток может продолжаться ». Как и версия для пакетов фиксированной длины, эта реализация сильно влияет на фазу передачи, что приводит к переменным сквозным задержкам и непригодности для формирования трафика в реальном времени.
Использует
Дырявое ведро в качестве очереди можно использовать только для формирования трафика в соответствии с указанной полосой пропускания без джиттера на выходе. Его можно использовать в сети, например, как часть управления полосой пропускания, но он больше подходит для формирования трафика в сетевых интерфейсах хостов. Алгоритм «дырявого ведра» используется в модуле Nginx ngx_http_limit_conn_module для ограничения количества одновременных подключений, исходящих с одного IP-адреса .
Параметры
В случае алгоритма дырявого ведра в качестве очереди единственным определенным пределом для этого алгоритма является пропускная способность его вывода.
Ограничение полосы пропускания для соединения может быть указано в договоре трафика . Предел полосы пропускания может быть указан как частота пакетов или кадров, скорость передачи байтов или битов , или как интервал передачи между пакетами.
Неэффективность
Реализация дырявого ведра в виде очереди не позволяет эффективно использовать доступные сетевые ресурсы. Поскольку он передает пакеты только с фиксированными интервалами, во многих случаях объем трафика будет очень низким и большие части сетевых ресурсов (в частности, полоса пропускания) не будут использоваться. Поэтому в реализации дырявого ведра в виде очереди не существует механизма, который позволял бы отдельным потокам разгоняться до скорости порта, эффективно потребляя сетевые ресурсы в то время, когда в сети не было бы конкуренции за ресурсы. Однако реализация token bucket и дырявого ведра в качестве счетчика позволяет выходным потокам трафика иметь скачкообразные характеристики.
Сравнение двух версий
Анализ двух версий алгоритма дырявого ведра показывает, что версия как очередь является частным случаем версии как счетчика.
Представьте себе функцию формирования трафика для пакетов фиксированной длины, которая реализуется с использованием очереди фиксированной длины, формируя элемент задержки, который обслуживается с использованием дырявого ведра в качестве счетчика. Представьте также, что ковш в этом счетчике имеет глубину, равную количеству, добавленному пакетом, то есть имеет нулевое предельное значение τ . Однако проверка на соответствие выполняется только с интервалами интервала передачи, когда передается пакет в начале очереди и в него добавляется вода. Эта вода затем просачивается во время следующего интервала выбросов (или удаляется непосредственно перед выполнением следующего теста на соответствие), позволяя следующему пакету соответствовать тогда или в некотором последующем интервале выбросов. Функцию обслуживания можно также рассматривать с точки зрения корзины с токенами той же глубины, где добавляется достаточно токенов для одного пакета (если корзина не заполнена) с интервалами эмиссии. Эта реализация затем будет принимать пакеты с импульсным шаблоном прибытия (ограниченным глубиной очереди) и передавать их с интервалами, которые всегда являются точными (целыми) кратными интервалу передачи.
Однако реализация дырявого ведра как счетчика (или маркерного ведра) в функции формирования трафика, описанной выше, является точным эквивалентом описания дырявого ведра как очереди: элемент задержки версии измерителя является ведром версия очереди; ведро версии счетчика - это процесс, обслуживающий очередь, а утечка такова, что интервал выбросов совпадает с интервалом тактов. Поэтому для пакетов фиксированной длины реализация дырявого ведра в виде очереди является частным случаем функции формирования трафика с использованием дырявого ведра (или маркерного ведра) в качестве счетчика, в котором предельное значение τ равно нулю, а процесс проверки соответствия выполняется с минимально возможной скоростью.
Дырявое ведро как очередь для пакетов переменной длины также можно описать как эквивалент особого случая дырявого ведра как счетчика. Предлагаемая реализация, как и реализация фиксированной длины, может рассматриваться как функция формирования трафика, в которой очередь является элементом задержки, а не корзиной, а функция, обслуживающая очередь, в этом случае явно указывается как корзина токенов. : он уменьшается для соответствующих пакетов и увеличивается с фиксированной скоростью. Следовательно, поскольку дырявое ведро как счетчик и маркерное ведро эквивалентны, дырявое ведро как очередь для пакетов переменной длины также является частным случаем функции формирования трафика, использующей дырявое ведро (или ведро токена) в качестве счетчика.
Интересное последствие видения дырявого ведра как очереди для пакетов переменной длины как конкретной реализации маркерного ведра или дырявого ведра как счетчика при формировании трафика. Это значит, что сегмент счетчика имеет глубину n, и, как всегда бывает с сегментом токенов, эта глубина определяет пакетность выходного трафика (возможно, по отношению к среднему или минимальному количеству токенов, необходимых для пакеты). Следовательно, можно количественно измерить пакетность выходных данных этого дырявого ведра "подсчета байтов" в виде метра, если только все пакеты не имеют максимальной длины, когда это становится бессмысленным. Однако эта способность определять прерывистость вывода находится в прямом противоречии с утверждением о том, что дырявое ведро (как очередь) обязательно дает вывод с жесткой скоростью, независимо от того, насколько скачкообразно ввод.