10.8.3 Алгоритмы сглаживания пульсации графика

10.8.3.1 Алгоритм Leaky Bucket

Алгоритм «дырявое ведро» обеспечивает контроль и, если нужно, сглаживание пульсации трафика. Алгоритм позволяет проверить соблюдение отправителем своих обязательств в отношении средней скорости передачи данных и пульсации этой скорости. Представим себе ведро, в котором накапливаются данные, получаемые от отправителя. В днище ведра имеются отверстия, через которые данные «вытекают» из него для дальнейшей обработки (или передачи). Через определенные интервалы времени подсчитывается объем данных, которые накопились в ведре в течение интервала, предшествовавшего моменту подсчета. Если объем не превышает порога В, всплеск скорости передачи данных внутри этого интервала считается нормальным, и никаких действий не производится. Если объем накопившихся данных превысил порог В, все пакеты, оказавшиеся выше порога, но ниже краев ведра, снабжаются меткой DE (Discard Eligibility), а те, которые не поместились в ведре, отбрасываются. В следующем интервале данные продолжают поступать в ведро и вытекать из него в обычном порядке (независимо от наличия меток), но если ведро переполняется, то отбрасываются не вновь поступающие пакеты, а пакеты с меткой DE, которые еще не успели вытечь. Если при следующем подсчете окажется, что объем данных в ведре ниже порога В, то никаких действий не производится. Если порог превышен, и в числе пакетов, оказавшихся выше порога, имеются пакеты без метки DE, они получают такую метку.

Рис. 10.9 Алгоритм "Leaky Bucket"

Одна из версий этого алгоритма, называемая Generic Cell Rate Algorithm (GCRA), применяется в сетях ATM для контроля некоторых параметров.

10.8.3.2 Алгоритм «Token Bucket»

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

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

Рис. 10.10 Алгоритм "Token Bucket"