Алгоритм ведра маркеров

Алгоритм ведра маркеров позволяет оценить и ограничить среднюю скорость и величину пульсации потока пакетов. Этот алгоритм основан на сравнении потока пакетов с некоторым эталонным потоком. Эталонный поток представлен маркерами, заполняющими условное ведро маркеров (рис. 204).

Под маркером в данном случае понимается некий абстрактный объект, носитель «порции» информации, используемый для построения эталонного потока. Гене­ратор маркеров периодически с постоянным интервалом w направляет очеред­ной маркер в ведро с ограниченным объемом b байт. Все маркеры имеют одина­ковый объем m байт, а генерация маркеров происходит так, что ведро заполняется со скоростью г бит в секунду. Нетрудно подсчитать, что г ^e 8m/w. Эта скорость г и является максимальной средней скоростью для трафика паке­тов, а объем ведра соответствует максимальному размеру пульсации потока па­кетов. Если ведро заполняется маркерами «до краев» (то есть суммарный объем маркеров в ведре становится равным Ь), то поступление маркеров временно пре­кращается. Фактически ведро маркеров представляет собой счетчик, который наращивается на m каждые w секунд.

Генератор маркеров

При применении алгоритма ведра маркеров профиль трафика определяется сред­ней скоростью г и объемом пульсации Ь.

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

Пакет из бедной очереди продвигаетрй серверам на/выход * томслуч^есяи к мо-, менту его поступления сервер «веди)*' эап^^ммй^ицЕж^!^^^ '

гд^М -r объем пакета. \ V ^ - ^..,,.,... ^ ^v,

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

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

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

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

ПРИМЕЧАНИЕ -----------------------------------------------------------------------------------------------------

Алгоритм ведра маркеров допускает пульсацию трафика в определенных пределах. Пусть пропускная способность выходного интерфейса, который моделируется выходом сервера, равна R. Это значит, что сервер не может передавать данные на выход со скоростью, пре­вышающей R бит/с. Можно показать, что на любом интервале времени t средняя скорость исходящего с сервера потока равна минимуму из двух величин: R и г + b/t. При больших значениях t скорость выходного потока стремится к г — это и говорит о том, что алгоритм обеспечивает желаемую среднюю скорость. В то же время в течение небольшого времени t пакеты могут выходить из сервера со скоростью, большей г. Если г ■+• b/t < R, то они выхо­дят из сервера со скоростью г + b/t, в противном случае интерфейс ограни чивае г эту ско­рость до величины R. Период времени t соответствует пульсации трафика. Эта ситуация наблюдается тогда, когда в течение некоторого времени пакеты не поступали в сервер, так что ведро полностью заполнилось маркерами (то есть времени, большего, чем Ь/г). Если после этого на вход сервера поступит большая последовательность пакетов, следующих один за другим, то эти пакеты будут передаваться на выход со скоростью выходного ин­терфейса R также один за другим, без интервалов. Максимальное время такой пульсации составляет b/(R - г) секунд, после чего обязательно наступит пауза, необходимая для на­полнения опустевшего ведра. Объем пульсации составляет Rb/(R - г) байт. Из приведен­ного соотношения видно, что алгоритм ведра маркеров начинает плохо работать, если средняя скорость г выбирается близкой к пропускной способности выходного интерфейса. В этом случае пульсация может продолжаться очень долго, что обесценивает алгоритм.