Исследование методов управления трафиком в 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, определяющего часть отбрасываемых пакетов при достижении средним размером очереди максимального порогового значения. Вероятность отбрасывания пакетов:

,

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

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

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

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

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