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

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

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

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

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

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

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

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

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

строгое ограничение максимального среднего размера очереди;

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

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

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

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

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

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

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

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

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

,

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

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

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

от размера очереди

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