Исследование методов управления трафиком в ip-сетях. Алгоритм red

Цель работы. Изучение реакции механизма профилирования трафика RED (Random Early Detection - случайное раннее обнаружение) на перегрузки сети.

Краткая теоретическая справка. Алгоритм RED представляет собой механизм управления трафиком, разработанный сообществом Интернет для предотвращения перегрузок на магистральных сетях. Этот механизм документирован IETF (Internet Engineering Task Force).

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

Если, несмотря на отбрасывание произвольных пакетов, средний размер очереди будет продолжать увеличиваться, это приведет к линейному росту вероятности отбрасывания. Вероятность отбрасывания пакетов растет прямо пропорционально увеличению среднего размера очереди в диапазоне от минимального до максимального пороговых значений. Средний размер очереди строго ограничен максимальным пороговым значением, поскольку в этом случае вероятность отбрасывания пакетов достигает своего наибольшего значения (100 %). Т. е. главная цель механизма RED заключается в минимизации среднего размера очереди, а значит, и общей задержки трафика на маршрутизаторе.

Если же средний размер очереди весьма невелик и находится ниже минимального порогового значения, механизм RED не вносит каких-либо изменений в процесс обслуживания очереди (область бездействия механизма RED). С другой стороны, при затяжном периоде перегрузки сети поведение механизма RED аналогично поведению классического механизма «отбрасывания хвоста» (drop tail).

 

Основные цели механизма RED:

предотвращение перегрузок.

предотвращение эффекта глобальной синхронизации трафика (следствие работы механизма «отбрасывания хвоста»);

обеспечение непредвзятого обслуживания трафика, характеризующегося кратковременными всплесками (стабилизация работы источников трафика);

минимизация задержки пакетов на узле (маршрутизаторе) путем контроля за средним размером очереди.

Механизм произвольного раннего обнаружения базируется на двух алгоритмах: алгоритм вычисления среднего размера очереди (определяет допустимый уровень всплеска трафика в очереди) и алгоритм вычисления вероятности отбрасывания пакетов (определяет вероятность отбрасывания пакетов для заданного среднего размера очереди).

Алгоритм вычисления среднего размера очереди. При определении вероятности отбрасывания пакетов механизм RED использует не текущий, а экспоненциально взвешенный средний размер очереди. Средний размер очереди на наблюдаемом периоде определяется на основании предыдущего среднего и текущего действительного размера. Использование механизмом RED среднего размера очереди обусловлено необходимостью реагировать только на продолжительную перегрузку сети и не замечать кратковременных всплесков трафика.

Средний размер очереди на периоде наблюдения вычисляется по формуле:

M _ср = М _{ср(t –1)} × (1 – 0,5 ⁿ) + M_t × 0,5 ⁿ,

где M _{ср(t –1)} – предыдущий средний размер очереди, М_t – текущий размер очереди, n - экспоненциальный весовой коэффициент, определяемый пользователем.

Экспоненциальный весовой коэффициент n является ключевым параметром, который определяет относительный вклад предыдущего среднего и текущего размера очереди в новый средний размер очереди. Увеличение экспоненциального весового коэффициента приведет к доминированию предыдущего среднего размера очереди над ее текущим размером в процессе вычисления нового среднего размера очереди. Напротив, уменьшение экспоненциального весового коэффициента приведет к возрастанию значимости текущего размера очереди при вычислении ее нового среднего размера.

Большое значение коэффициента n обусловливает математическую близость нового и предыдущего среднего размера очереди, а также позволяет механизму RED более сдержанно реагировать на моментальные изменения ее текущего размера. Т.е. при увеличении n увеличивается степень сглаживания трафика и, как следствие – повышается стабильность работы источника ТСР-трафика.

Алгоритм вычисления вероятности отбрасывания пакетов. Вероятность отбрасывания пакетов представляет собой функцию, линейно зависящую от среднего размера очереди. Помимо этого, данная функция зависит также от минимального порогового значения M _min, максимального порогового значения M _max и знаменателя граничной вероятности K, определяющего часть отбрасываемых пакетов при достижении средним размером очереди максимального порогового значения. Вероятность отбрасывания пакетов:

 EMBED Microsoft Equation 3.0,

где М _ср – средний размер очереди, М _min, М _max – минимальное и максимальное пороговые значения среднего размера очереди, K – знаменатель граничной вероятности.

Когда средний размер очереди превышает минимальное пороговое значение, механизм RED начинает отбрасывать пакеты. Интенсивность отбрасывания пакетов возрастает прямо пропорционально возрастанию среднего размера очереди до тех пор, пока он не достигнет максимального порогового значения.

Когда средний размер очереди превышает максимальное пороговое значение, механизм RED отбрасывает все пакеты, предназначенные для постановки в очередь (механизм «отбрасывание хвоста»). График вероятности отбрасывания пакетов схематически представлен на рис. 4.1.

 

 EMBED Visio 2000 Drawing

 

Рис.4.1 Зависимость вероятности отбрасывания пакетов

от размера очереди при K = 1 и K = 2

Задание

Исследовать зависимость вероятности отбрасывания пакетов механизмом RED от следующих параметров:

Текущего размера очереди М_t, для чего ввести исходные данные для исследования реакции механизма RED на изменение среднего размера очереди: n, K, M _min, M _max, и необходимое количество значений М_t (вводятся через ENTER, случайным образом в диапазоне около M _max):

 

Таблица 4.1

Варианты заданий к лабораторной работе

Вариант	K	n	М min, пак.	М max, пак.	N
	5 (1; 9)	6	40	213	20
	6 (1; 10)	9	112	375	22
	8 (1; 5)	11	1250	4890	24
	10 (1; 6)	10	388	1292	26
	12 (1; 6)	12	1550	5167	28
	4 (1; 9)	10	990	3654	30
	5 (1; 9)	11	860	2990	28
	8 (1; 12)	9	283	1025	26
	9 (1; 4)	9	450	1480	24
	10 (1; 5)	11	1100	4107	22
	10 (1; 4)	9	512	1520	20

Примечание. N – количество значений текущего размера очереди M_t

 

Знаменателя граничной вероятности K: повторить измерения согласно предыдущему пункту при различных значениях K (значения K 2 и K 3 приведены в табл.1 в скобках).

Экспоненциального весового коэффициента n: М _ср, K, M _min, M _max при n Î[1,10]. Значение М _cр выбрать самостоятельно из диапазона (М _min; M _max).

 

К защите

Знать особенности работы алгоритма RED, цели и области его применения. Уметь объяснить причины возникновения перегрузок в IP-сетях, а также причины возникновения и последствия явления глобальной синхронизации. Иметь представление о механизме медленного старта.

Представить отчет, содержащий таблицы измерений и графики функций P (M_ср | _{K 1, K 2, K 3}), P (n).

Объяснить полученные результаты.