Другим алгоритмом измерения и контроля нагрузки является Token Bucket, появившийся существенно позднее своего предшественника Leaky Bucket. Хотя иногда в литературе можно встретить утверждения, что оба алгоритма являются практически одинаковыми, автор данной книги придерживается полярного мнения - алгоритмы существенно различаются, поэтому далее обратим на этот факт особое внимание. Token Bucket позволяет применять какие-либо действия (сброс или маркировка) только лишь к пакетам, которые не соответствуют заявленному профилю, при этом пакеты, соответствующие профилю, проходят через Token Bucket без какой-либо дополнительной задержки, связанной с ограниченной интенсивностью исходящей нагрузки, в го время как Leaky Bucket просто является накопителем с детерминированной функцией обслуживания поступающих требований.

Как показано на рис. 2.16 рассматриваемого алгоритма, Token Bucket состоит из двух буферов - для пакетов и жетонов (tokens). Жетоны генерируются автоматически программным обеспечением узла с заданной интенсивностью и помещаются в очередь. Если буфер жетонов полон, то новый жетон теряется. В случае отсутствия жетонов пакеты должны сохраняться в буфере. В связи с тем, что генерация жетонов происходит с определенной интенсивностью, то можно утверждать, что минимальная интенсивность обработки поступающих пакетов равна интенсивности генерации жетонов.

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

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

В соответствии с введенными параметрами определим метакод функционирования Token Bucket, который представлен на рис. 2.17: алгоритм разбивается на две составляющие, функционирующие, в общем-то, несмотря на передачу параметров, независимо.

Метакод алгоритма Token Bucket

Рис. 2.17. Метакод алгоритма Token Bucket

В связи с тем, что на основе алгоритма Token Bucket реализованы механизмы контроля нагрузки в реальных сетях, далее рассмотрим математическое описание режимов его функционирования. Рассмотрим систему, представляющую собой модель узла, в который поступает нагрузка, контроль параметров которой осуществляется при помощи Token Bucket. Обозначим через A(t, t + т) количество нагрузки поступившей в рассматриваемую систему за промежуток времени (t,t + r]. По определению [Parekh92], поток, удовлетворяющий набору параметров (г,Ь,р), где р - пиковая скорость, поступающая в систему нагрузки, имеет функцию поступающей нагрузки следующего вида (где М - максимальный размер пакета):

На рис. 2.18 представлено поведение функции поступающей нагрузки для рассматриваемого алгоритма Token Bucket. Отметим, что на рис. 2.18 функция A(t) отражает наихудший, с точки зрения нагрузки, случай, когда размер поступающих пакетов равен максимально возможному значению М. В соответствии с Parekh92, Cruz91-1] для подобной системы параметры MBS и MBD (Maximum Burst Duration - максимальная длина пачки) могут быть определены следующим образом:

Отметим, что система с реализованным алгоритмом Token Bucket за промежуток времени (M + Z"] может принять количество пакетов не превышающее Ь + tR.

Функционирование алгоритма Token Bucket: поведение функции поступающей нагрузки

Рис. 2.18. Функционирование алгоритма Token Bucket: поведение функции поступающей нагрузки Алгоритм Token Bucket может функционировать, как минимум, в двух режимах - «маркировки или сброса» и «сглаживания». Последний режим подробно рассмотрен в данной главе ниже. Режим «маркировки или сброса» представляет собой вариант функционирования, когда при обнаружении неконформных пакетов они либо сбрасываются, либо маркируются с понижением приоритета. Отличие режима «сглаживания» от «маркировки или сброса» состоит в дополнительной логике алгоритма для буфера пакетов (см. п. 2.4.3.5 данной главы).

На рис. 2.19 представлено поведение функции нагрузки алгоритма Token Bucket в режиме «маркировки или сброса». Как видно из рисунка, для данного режима дополнительно определяется функция неконформной нагрузки A'(i), разность между которой и скоростью обслуживания г определяет количество сброшенных или маркированных пакетов. В [Cruz91-I) определено выражение для подсчета количества маркированных или сброшенных пакетов:

Функционирование алгоритма Token Bucket: режим «маркировки или сброса»

Рис. 2.19. Функционирование алгоритма Token Bucket: режим «маркировки или сброса» Таким образом, алгоритм Token Bucket обладает рядом преимуществ, среди которых необходимо отметить следующие:

• обеспечение точной параметризации конформных и неконформных пакетов;

• ограничение средней скорости контролируемого потока;

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

⇐Алгоритм leaky bucket | Управление трафиком и качество обслужевания в сети | Для архитектуры diffserv: алгоритм trtcm⇒