Эндрю Уэзеролл - Компьютерные сети. 5-е издание

Рис. 5.25.Алгоритмы дырявого и маркерного ведра: а — формирование пакетов; б — дырявое ведро; в — маркерное ведро

С помощью такого ведра можно формировать или приводить в порядок пакеты, поступающие в сеть (рис. 5.25, а). Принцип таков: каждый хост соединяется с сетью через интерфейс, содержащий дырявое ведро. Чтобы пакет можно было отправить в сеть, в ведре должно быть достаточно места для воды. Если в момент поступления пакета ведро заполнено, пакет либо помещается в очередь до тех пор, пока в ведре не освободится достаточно места, либо отвергается. Первый вариант встречается в таких случаях, когда формирование трафика производится операционной системой хоста. Второй вариант имеет место, когда проверка трафика, поступающего в сеть, осуществляется аппаратными средствами в сетевом интерфейсе интернет-провайдера. Этот метод был предложен Тернером (Turner, 1986) и называется алгоритмом дырявого ведра( leaky bucket algorithm).

То же самое можно представить себе по-другому: в виде ведра, которое в данный момент наполняется (рис. 5.25, в). Вода вытекает из крана со скоростью R, а объем ведра, как и в предыдущем случае, равен B . Чтобы отправить пакет, необходимо, чтобы из ведра можно было вылить воду, или маркеры (так обычно называют содержимое ведра), а не налить ее туда. В ведре может содержаться ограниченное число маркеров (не более B); если ведро пустое, для отправки пакета необходимо подождать, пока не появятся новые маркеры. Этот алгоритм называется алгоритмом маркерного ведра ( token bucket algorithm).

Дырявое ведро и маркерное ведро ограничивают постоянную скорость потока, при этом пропуская кратковременные пики трафика (также ограниченные максимальным значением) без искусственных задержек. Чтобы снизить нагрузку на сеть, шейпер (формирователь) трафика сглаживает крупные пики. В качестве примера представьте, что компьютер может производить данные со скоростью 1000 Мбит/с (125 млн байт в секунду) и что первая связь сети также работает на этой скорости. Хост генерирует схему трафика, показанную на рис. 5.26, а . Эта схема является неравномерной. Средняя скорость составляет 200 Мбит/с, хотя хост отправляет пиковый объем трафика в 16 000 Кбайт на максимальной скорости 1000 Мбит/с (за 1/8 секунды).

Рис. 5.26.Схема: а — трафик, передаваемый хостом; б — исходящий трафик, сформированный с помощью маркерного ведра со скоростью 200 Мбит/с и емкостью 9600 Кбайт и в — 0 Кбайт; г — уровень маркерного ведра при формировании трафика со скоростью 200 Мбит/с и емкостью 16 000 Кбайт, д — 9600 Кбайт и е — 0 Кбайт

Теперь предположим, что маршрутизаторы могут принимать данные на максимальной скорости только в течение небольших промежутков времени — до тех пор, пока буфер не заполнится. Размер буфера составляет 9600 Кбайт, что меньше, чем объем пикового трафика. В течение больших промежутков времени маршрутизаторы лучше всего работают, если скорость не превышает 200 Мбит/с (так как именно эта пропускная способность указана в соглашении с клиентом). Из этого следует, что если для передачи используется эта схема, часть трафика будет удалена, так как не поместится в буферы маршрутизаторов.

Чтобы избежать такой утери пакетов, можно сформировать трафик на хосте по методу маркерного ведра. Если скорость R равна 200 Мбит/с, а емкость B равна 9600 Кбайт, трафик попадает в границы возможностей сети. Исходящий трафик такого маркерного ведра показан на рис. 5.26, б. Хост может отправлять трафик на максимальной скорости в 1000 Мбит/с в течение небольшого промежутка времени — до тех пор, пока ведро не станет пустым. Затем он должен будет снизить скорость до 200 Мбит/с и отправить оставшуюся часть трафика. Идея в том, чтобы растянуть время отправки пикового трафика (пачки пакетов), если сеть не в состоянии обработать его в один прием. Уровень маркерного ведра показан на рис. 5.26, д. Вначале ведро наполнено, но после первой порции трафика оно становится пустым. Когда уровень достигает нуля, новые пакеты могут передаваться только с такой скоростью, с которой буфер наполняется; пока ведро снова не наполнится, отправка крупных объемов трафика невозможна. Когда трафик не поступает, ведро постепенно наполняется; пока данные приходят со скоростью заполнения ведра, оно остается пустым.

Чтобы трафик был равномерным, его можно сформировать. На рис. 5.26, в показан исходящий трафик маркерного ведра со скоростью 200 Мбит/с и емкостью 0. Это крайний случай — трафик полностью выровнен. Крупные пачки не принимаются; трафик приходит с постоянной скоростью. Уровень воды в ведре, соответственно, всегда равен нулю (рис. 5.26, е). Трафик помещается в очередь хоста, и в каждый момент времени какой-то пакет ожидает отправки.

Наконец, на рис. 5.26, д показан уровень маркерного ведра со скоростью R = 200 Мбит/с и емкостью B = 16 000 Кбайт. Это самое маленькое маркерное ведро, через которое трафик проходит без изменений. Такое ведро маршрутизатор может использовать для проверки трафика, передаваемого хостом. Такое ведро можно расположить на одном из концов сети; если трафик соответствует маркерному ведру, указанному в соглашении об обслуживании, он сможет через него пройти. Если же хост будет отправлять данные слишком быстро или неравномерно, вода в маркерном ведре закончится, и сеть узнает о том, что трафик не соответствует условиям соглашения. После этого в зависимости от конфигурации сети лишние пакеты будут либо удалены, либо помечены как низкоприоритетные. А в нашем примере ведро становится пустым лишь на короткое время — после получения большого объема трафика. После этого оно восстанавливается и снова готово принять такой трафик.

Дырявое ведро и маркерное ведро просты в реализации. Давайте посмотрим на то, как работает маркерное ведро. Хотя до этого мы говорили о втекающей и вытекающей жидкости, нужно понимать, что на практике сеть имеет дело с дискретными величинами. Реализация алгоритма маркерного ведра подразумевает наличие переменной, считающей маркеры. Счетчик увеличивается на R/AT. В нашем примере счетчик будет увеличиваться на 200 Кбит за 1 мс. Каждый раз при посылке трафика счетчик уменьшается; когда его значение доходит до нуля, передача пакетов останавливается.

Если все пакеты имеют одинаковый объем, уровень ведра можно измерять в пакетах (например, 200 Мбит — это 20 пакетов по 1250 байт). Однако чаще всего используются пакеты разного размера. Тогда уровень ведра исчисляется в байтах. Если число байт в ведре не является достаточным для отправки пакета, пакет вынужден ждать, пока ситуация не изменится (что может произойти не сразу, если скорость заполнения ведра мала).