 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
 |
 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
 |
 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
 |
 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Исследование влияния параметров алгоритма WRED на качество обслуживания при передаче данных по перегруженным каналамГончаров А.А. (ИТЭФ), Семенов Ю.А. (ИТЭФ/МФТИ) Рассмотрен метод оптимального подбора параметров для алгоритма WRED при передаче данных по каналам Интернет в условиях перегрузки. 1. ВведениеЭффективность использования полосы пропускания канала всегда была актуальной задачей, но её важность возросла в последние годы в связи с появлением всё более жестких требований к качеству обслуживания (QoS). К числу параметров качества обслуживания следует отнести доступную полосу пропускания, вероятность потери пакета, разброс времени доставки и само время доставки пакета от отправителя к получателю. Все эти параметры зависят от алгоритмов формирования и обслуживания очередей пакетов в сетевых устройствах (переключателях и маршрутизаторах). В современных сетевых устройствах реализуются алгоритмы RED/WRED, PQ, WFQ, LLQ, CBWFQ и т.д.. Ниже рассматривается поведение очередей в случае использования алгоритма WRED [1, 2]. Особенностью этого алгоритма является то, что решение о постановке пакета в очередь принимается по-разному, в зависимости от уровня заполнения буфера (длины очереди). Механизм WRED использует следующие параметры: wq - весовой коэффициент усреднения; TH_MIN - нижний порог средневзвешенной длины очереди; TH_MAX - верхний порог средневзвешенной длины очереди; pc - максимальное значение вероятности отбрасывания пакетов для области между TH_MIN и TH_MAX. В алгоритме WRED устанавливаются два порога TH_MIN и TH_MAX. Пока усреднённая длина очереди ниже TH_MIN, любой входящий пакет поступает в буфер. В области между TH_MIN и TH_MAX вероятность отбрасывания пакета линейно растёт от 0 до значения pc (см. рис.1).  Рис. 1. После достижения порога TH_MAX все поступающие пакеты отбрасываются. (см рис.1) Усреднение длины очереди производится согласно формуле.  (1) здесь  Рис. 2. 2. Экспериментальная частьЗадачей данной работы было экспериментальное определение области параметров алгоритма WRED, в которой осцилляции длины очереди минимальны, и сравнение полученных результатов с данными моделирования, выполненного нами в работе [1]. Нами передавались потоки UDP пакетов через тестовый канал, показанный на рис. 2. Помимо указанных выше параметров WRED важную роль играют значения входного потока и квоты полосы пропускания на выходе буфера. Комбинацию этих параметров можно характеризовать безразмерным коэффициентом перегрузки канала l/m. Здесь l[бит/сек] - поток на входе буфера, а m[бит/сек] – полоса пропускания на выходе буфера. В случае перегрузки l>m, коэффициент перегрузки l/m определяет время переполнения буфера маршрутизатора и время выхода маршрутизатора на стационарный режим работы. Варьируя этот параметр можно воспроизводить разные ситуации перегрузок в сети. К сожалению, на практике параметр l/m обычно не выбирается, но он больше всех остальных параметров влияет на поведение системы. В отличие от модельного исследования параметров WRED [1], в реальном оборудовании мы не можем отслеживать изменение средневзвешенной длины очереди от времени, изменение текущей длины очереди от времени. О длине очереди можно судить косвенно, по задержке пакета в маршрутизаторе. 2.1 Исследование влияния параметра pc на поведение алгоритма WREDВ первом эксперименте исследовалось влияние параметра pc на проходящие через алгоритм WRED потоки. При моделировании в статье [1] можно было плавно менять значение параметра pc, но в маршрутизаторах параметр pc задается как дробь 1/k, где целое значение k лежит в диапазоне <1-65535>. Через тестовый канал передавалось 3 потока, параметры которых представлены в таблице 1. Таблица 1.
Значение pc варьировалось в интервале [0.001÷1]. Каждый из трёх потоков имел скорость 1 Мбит/сек. Поле данных пакетов UDP имело длину 1024 байта. Полная полоса PVC (АТМ) канала составляла 2000 кбит/сек. На рисунках 3 и 4 по оси Х значениям {0,1,2,3,4,5,6,7,8,9,10,11} соответствуют значениям параметра рс {1/1000, 1/100, 1/20, 1/10, 1/8, 1/7, 1/6, 1/5, 1/4, 1/3, 1/2, 1}. Красным цветом обозначены значения параметров, соответствующие потоку с DSCP=af11 (см. таблицу 1). Зелёным цветом обозначены значения параметров, соответствующие потоку с DSCP=af12, а синим - значения параметров, соответствующие потоку с DSCP=af13.  Рис. 3. Зависимость процента потерянных пакетов от параметра pc Усреднение проводилось за всё время эксперимента. Параметр рс влияет лишь на время переходного процесса, который возникает при перегрузке канала. Из рисунка видно, что значения pc<0.25 вызывают одинаковый отклик системы. Зависимости процента потерянных пакетов в единицу времени для разных значений рс практически одинаковы. Следовательно, при данном значении wq разумно использовать значения pc>0.25. Видно, что процент потери пакетов в двух крайних случаях отличается менее чем на 3%. Параметр рс очень слабо влияет на процент потери пакетов в случае перегрузки канала. Настройка параметра pc влияет на продолжительность начального переходного процесса, но не влияет на характеристики передачи потока пакетов при продолжительной постоянной перегрузке. На рисунке 4 приведена временная зависимость задержки при передаче пакета через перегруженный канал. После возрастания задержки до 4 секунд, его значение выходит на постоянный средний уровень ~1.8сек. Всплеск задержки доставки пакетов возникает, когда текущая длина очереди WRED растёт, а средневзвешенная длина очереди ещё не достигла порога TH_MAX. Когда средневзвешенная длина очереди достигает верхнего порога, текущая длина очереди начинает быстро сокращаться, т.к. все пакеты поступающие на вход отбрасываются. Для разных значений рс длительность и высота перехода будут отличаться. Но конечное стационарное состояние системы одинаково для всех значений параметра рс. Параметр рс важен в случае кратковременных перегрузок, когда система не успевает выйти на стационарный режим работы. Далее под словами: «характеристика измерена н а плато» буде подразумеваться, что измерения выполнялись, когда процесс находился в стационарном режиме.  Рис. 4. Зависимость задержки доставки пакетов от времени На рис. 4 представлена зависимость задержки доставки пакетов от времени с момента начала перегрузки. По оси Y отложена задержка доставки пакета. По оси Х - время с момента начала перегрузки (pc=1, DSCP=AF11). Здесь и на последующих рисунках, время по оси Х отсчитывается с начала эксперимента. В области 0-10 секунд происходит линейный рост задержки доставки пакетов. Это связано с процессом заполнения буфера маршрутизатора, в момент 10 секунд значение средневзвешенной длины очереди превысило ТН_МАХ, и рост длины очереди остановился, очередь начала быстро опорожняться. С 13 до 37 секунд, задержка остаётся постоянной, это связано с тем, что переходные процессы завершились, и система вышла на стационарный режим. С 37-й по 40-ю секунду виден спад задержки, это обусловлено окончанием передачи потока. Зависимость на рисунке согласуется с результатами моделирования [1]. 2.2 Исследование влияния коэффициента перегрузки l/m на поведение алгоритма WREDПри измерении влияния l/m на параметры QoS через ATM канал передавался один поток UDP пакетов, с длиной поля данных 1024 байта, поток помечался меткой DSCP=AF11. Полоса пропускания ATM канала равнялась m=998000 бит/сек., а скорость источника варьировалась. Параметры настройки алгоритма WRED для этого потока были следующими: TH_MIN=100, TH_MAX=150, pc=1, wq=0.002. Выбор именно этих параметров опирается на результаты моделирования [1]. В области больших значений перегрузок l/m и малой разности (TH_MAX-TH_MIN) было трудно заметить разницу между соседними измерениями. Длительность одного измерения составляла 39 секунд. Отношение l/m варьировалось в пределах от 0,79 до 3,41. Для каждого измерения получена зависимость задержки доставки пакета от времени с начала эксперимента. Была построена зависимость процента потерь от времени с момента начала измерения.  Рис. 5. Зависимость задержки на плато при передаче пакета (ось Y) от l/m (ось X) для pc=1 (зелёный) и pc=0.1 (красный) Из рис. 5 видно, что в начале задержка меняется быстро: до наступления перегрузки (l/m = 0.79) задержка при передаче пакета не менялась и составляла в среднем 0.011-0.012 сек. При значении l/m = 1.02 (слабая перегрузка), задержка выросла до 1.0 – 1.2 секунды (т.е. примерно в сто раз). Далее задержка доставки стабилизируется, так как длина очереди практически остается неизменной.  Рис. 6. Зависимость величины потерь на плато от l/m. pc=1 (зелёный) и pc=0.1 (красный) 2.3 Исследование влияния порогов TH_MIN TH_MAX на параметры качества обслуживанияПороги алгоритма WRED влияют на минимальное и максимальное время задержки пакетов в случае возникновения перегрузки. Во время эксперимента коэффициент перегрузки l/m=1.4 оставался постоянным. Нижний порог алгоритма WRED TH_MIN=100 [пакетов] тоже не менялся. Менялось значение верхнего порога TH_MAX = [110-210] пакетов с шагом 10 пакетов. Не имеет смысл ставить большие значение порога TH_MAX, так как при длительной перегрузке происходит переполнение буфера, отведённого на исходящем интерфейсе маршрутизатора под пакетную очередь. Для двух крайних значений параметра рс получены зависимости значения средней задержки на плато и время выхода системы на плато от значения TH_MAX. (рис. 8, 9), измерена также зависимость максимальной задержки при передаче пакета (рис. 7). Данная задержка возникает во время переходного процесса, размер этой задержки зависит от значения порога TH_MAX и параметра усреднения wq. Условное обозначение точек на графиках приведено в таблице 2. Точкам, отложенным по оси Х с координатами 1, 2, 3 ..., соответствуют значения TH_MAX = 110, 120, 130 …. Таблица 2
 Рис. 7. Зависимость значения максимальной задержки (красный – рс=0.1 зелёный – рс=1) от величины порога TH_MAX  Рис. 8. Зависимость значения задержки на плато от порога TH_MAX. (красный – рс=0.1 зелёный – рс=1) В эксперименте скорость отправки UDP пакетов постоянна и равна l [бит/сек]=const. Обозначим через x(k) – скорость поступления пакетов в буфер маршрутизатора в k-ый временной интервал, а y(k) – скорость передачи пакетов на выходном интерфейсе маршрутизатора. Обозначим
На самом деле формула (2) имеет множитель, который в данной качественной оценке опущен (более детальное выражение для p(k) см. в [2]). Скорость поступления пакетов в пакетный буфер маршрутизатора описывается выражением: x(k)= Скорость передачи пакетов из интерфейса маршрутизатора в канал описывается соотношением:
Текущая длина очереди в алгоритме WRED в k–й временной интервал и длина очереди в последующий момент времени связанны соотношением:
где L-максимальный размер пакетного буфера для интерфейса в маршрутизаторе, Dt – приращение времени. Из выражений (1) и (5) можно получить оценку
В результате получаем
Из уравнения 6 следует, что в стационарном режиме, когда колебания средневзвешенной длины очереди затухают, прекращаются и колебания текущей длины очереди. Следовательно, имеем:
В стационарном случае задержка постоянна, она пропорциональна длине текущей очереди. Обозначим длину текущей очереди в стационарном случае - q*(k). Прирост длины текущей очереди в единицу времени равен нулю, запишем это условие: l(1-p(k))-m=0 (8) где p(k) задается из уравнения (2)
Выведена качественная оценка для длины текущей очереди в стационарном случае, при условии что wq <<1. Зависимость на рис. 8 демонстрирует поведение задержки при передаче пакета для разных значений порога TH_MAX. Из рис. 8 видно, что зависимость линейна. Этот результат подтверждается качественной оценкой из уравнения (9).  Рис. 9. Зависимость времени выхода на плато от значения порога TH_MAX (красный – рс=0.1 зелёный – рс=1) Из рис. 9 видно, что продолжительность переходного процесса растёт с ростом величины TH_MAX. Зависимость от параметра pc растёт с ростом TH_MAX. 2.4 Исследование влияния параметра усреднения wq на поведение алгоритма WREDПараметр wq отвечает за амплитуду колебаний длин очередей, а также за время реакции алгоритма WRED на флуктуации перегрузки. Через ATM канал передавался один поток UDP пакетов, с длиной поля данных 1024 байта, поток помечался меткой DSCP=AF11. Отношение l/m в ходе эксперимента оставалось постоянным и равнялось 1,4. Параметры настройки алгоритма WRED для этого потока были следующими: TH_MIN=100, TH_MAX=150, pc=0.1. Ниже приведена таблица с указанием соответствия значения wq и линий на рис. 10. Таблица 3. Соответствие точек на оси Х на рисунке 10 значениям параметра wq.
 Рис. 10. Зависимость задержки при доставке пакета от времени получения пакета для разных значений wq (pc=0.1) Из рисунка 10 видно, что при wq<<1 т.е. wq(N1, N2, N3), см. табл. 3. Алгоритм WRED не успевает отреагировать на перегрузку и происходит максимальное заполнение пакетного буфера маршрутизатора. Это происходит, так как средневзвешенная длина очереди, вычисленная маршрутизатором, практически не меняется, следовательно, не происходит отброса пакетов. Маршрутизатор работает по наихудшей схеме FIFO: для потока выделен весь пакетный буфер (~ 750 пакетов), когда буфер переполняется все пакеты отбрасываются. Для значений wq~1 (N9 и N10, см. табл. 3) WRED мгновенно реагирует на перегрузку, и алгоритм вырождается в схему FIFO c длиной буфера равной TH_MAX=150 пакетов. Эти два случая являются вырожденными и WRED в этих случаях превращается в механизм «tail drops». (Tail drops – в этом механизме при заполнении буфера на исходящем интерфейсе, пакеты, которым не хватило места в буфере, отбрасываются.)  Рис. 11. Зависимость вероятности потери пакетов от времени с начала эксперимента для разных значений wq (pc=0.1) По рис. 11 можно проанализировать процессы, происходящие при разных значениях параметра wq. Фиолетовым цветом (кривая с номером 1) обозначена зависимость с wq=0.000015. В [2] и [10] даётся объяснение того, как разумно выбрать wq. Когда wq слишком мало, то алгоритм WRED перестаёт реагировать на перегрузки. Из уравнения (1) видно, что если wq~0 то средневзвешенная длина очереди не меняется, и WRED не работает. Происходит максимальное заполнение текущей длины очереди, а далее пакеты, которым не хватило места в буфере, будут потеряны. За 12 секунд пакетный буфер заполнился и сразу возникают потери. Случай, когда wq=0.5, выделен красным цветом. В этом случае не происходит запаздывания между ростом длины текущей и средневзвешенной очередей. Они меняются синхронно и их длины равны. Максимально допустимая длина средневзвешенной длины очереди равна TH_MAX.Следовательно, максимальная длина текущей очереди тоже равнялась TH_MAX. Это видно на рис. 11: вблизи 4 секунд система выходит на длину текущей очереди равную TH_MAX, а все пакеты, не поместившиеся в буфер, отбрасываются. На рис. 10 и 11 для кривой №4 (голубого цвета, wq=0.00048) наблюдается всплеск потерь и задержки. После всплеска, кривая выходит на равновесный уровень потерь и задержек. Изначально цель алгоритма WRED была: не дать потоку перегрузить канал за счёт упреждающих потерь пакетов. В случае если происходит непродолжительная перегрузка, и длина текущей очереди сильно возрастает, маршрутизатор не начинает отбрасывать пакеты, пока средневзвешенная длина очереди не достигнет значения TH_MAX. Статья направлена в журнал "Информационные процессы". Ссылки
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
- усредненная длина очереди в (k+1)–й
момент времени, wq -параметр усреднения, 
,
q - усреднённая и текущая длины очереди в k–й момент времени. При малом значении wq
процесс WRED не сразу начинает отбрасывать пакеты при перегрузке, зато продолжит отбрасывание,
даже когда перегрузки уже нет (очередь сократилась ниже TH_MIN). Усреднение длины очереди -
важный компонент при управлении процессом буферизации. Без усреднения процесс буферизации
был бы подвержен сильному влиянию случайных флуктуаций входящего потока пакетов, но именно
усреднение является причиной возникновения осцилляций длины очереди. Зависимость принятия
решения об отбрасывании того или иного пакета определяется значением усреднённой длины очереди,
которое может существенно отличаться от значения текущей длины очереди [1].
(2)
(4)
(5)
для значений wq<<1.
На основе (3), (4) и (1) запишем
(6)
, следовательно 
(7)
, и учитывая (7), получаем:
, (9)