Kadiz
Active Member
Алгоритмы дырявого и маркерного ведра
Нам уже знаком один способ ограничения передаваемого приложением объема данных — скользящее окно. Этот метод использует один параметр, который ограничивает данные, передаваемые в определенный момент времени, и косвенно ограничивает скорость. Теперь мы обратимся к более общим методам описания трафика и рассмотрим алгоритмы дырявого ведра и маркерного ведра. Хотя эти алгоритмы немного отличаются друг от друга, они приводят к одинаковому результату.
Представьте себе ведро с маленькой дырочкой в днище, как показано на рис. 5.25, б. Независимо от скорости, с которой вода наливается в ведро, выходной поток обладает постоянной скоростью R, когда в ведре есть вода, и нулевой скоростью, когда ведро пустое. Кроме того, когда ведро наполняется и вода занимает весь объем B, вся лишняя вода выливается через край и теряется.
You must be registered for see images
Рис. 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 секунды).
You must be registered for see images
Рис. 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/ΔT. В нашем примере счетчик будет увеличиваться на 200 Кбит за 1 мс. Каждый раз при посылке трафика счетчик уменьшается; когда его значение доходит до нуля, передача пакетов останавливается. Если все пакеты имеют одинаковый объем, уровень ведра можно измерять в пакетах (например, 200 Мбит — это 20 пакетов по 1250 байт). Однако чаще всего используются пакеты разного размера. Тогда уровень ведра исчисляется в байтах. Если число байт в ведре не является достаточным для отправки пакета, пакет вынужден ждать, пока ситуация не изменится (что может произойти не сразу, если скорость заполнения ведра мала).
При расчете длительности максимальной выходной пачки (до тех пор, пока ведро не станет пустым) нужно учитывать, что пока ведро опорожняется, появляются новые маркеры. При длительности пачки S с, емкости маркерного ведра B байт, скорости появления маркеров R байт/с и максимальной выходной скорости M байт/с очевидно, что максимальное количество переданных байтов в пачке будет равно B + RS байт. Мы также знаем, что количество байтов, переданных в пачке с максимальной скоростью, равно MS. Таким образом,
B + RS = MS.
Решив это уравнение, получим: S = B/(M – R). При наших параметрах B = 9600 Кбайт, M = 125 Мбайт/с и R = 25 Мбайт/с получаем длительность пачки около 94 мс.
Недостатком алгоритма маркерного ведра является то, что скорость передачи крупных пачек снижается до постоянного значения R. Часто бывает желательно уменьшить пиковую скорость, не возвращаясь при этом к постоянному значению скорости (но и не увеличивая это значение, чтобы не пропустить в сеть дополнительный трафик). Один из способов получения более гладкого трафика состоит в помещении еще одного маркерного ведра после первого. Скорость второго ведра должна быть гораздо выше скорости первого. По сути, первое ведро определяет характеристики трафика и фиксирует его скорость, иногда позволяя отправлять крупные объемы данных. Второе ведро уменьшает максимальную скорость, с которой могут передаваться такие пачки. Например, если скорость второго ведра равна 500 Мбит/с, а емкость — 0, первая пачка поступит в сеть с максимальной скоростью 500 Мбит/с. Это меньше, чем наше предыдущее значение 1000 Мбит/с.
Управление такими схемами может оказаться непростым. Когда маркерные ведра используются для формирования трафика на хостах, пакеты вынуждены ждать в очереди до тех пор, пока ведро их не пропустит. Когда они применяются на маршрутизаторах сети для определения трафика, сеть имитирует алгоритм и гарантирует, что пакетов и байтов посылается не больше, чем разрешено. Тем не менее эти методы позволяют формировать сетевой трафик, приводя его к более управляемому виду и обеспечивая тем самым выполнение требований по качеству обслуживания.
