Алгоритм Random early detection

Семейство алгоритмов типа Random early detection (RED).

1 Общая информация

• Random early detection (RED) (Произвольное Раннее Обнаружение)
• Один из типов алгоритмов AQM для управления переполнением очередей маршрутизаторов.
• Предложен Салли Флойд [1].
• Страница Салли Флойд, посвящённая RED: http://www.icir.org/floyd/red.html.

2 Характерные черты алгоритма RED

• Алгоритм крайне простой.
• Алгоритм построен так, чтобы использовать как можно меньше вычислительных ресурсов.
• Основная вычислительная сложность приходится на вычисление функции сброса.
• Не случайно эта функция функция строится из ломаных, как полиномиальное приближение к нелинейной функции сброса.
• Из-за использования в алгоритме скользящего среднего RED хорошо обрабатывает взрывной (burst) трафик.
• В сетях TCP/IP алгоритм RED помогает избавиться от проблемы глобальной синхронизации.
  • Она возникает, когда несколько источников, работающих через один и тот же перегруженный сегмент сети, обнаруживают потери пакетов.
  • Как следствие, эти источники одновременно снижают скорость, а затем (также одновременно) постепенно ее увеличивают, что приводит к новой перегрузке, потере пакетов и повторению всей процедуры.
  • Состояние сети периодически меняется от простоя до перегрузки.
  • RED позволяет избежать глобальной синхронизации, выборочно уничтожая пакеты от определённых источников.

3 Зачем исследовать алгоритмы типа RED

• Математическая модель алгоритмов типа RED достаточно сложная, поэтому обосновать влияние разных элементов алгоритма на качество его работы крайне проблематично.

3.1 Параметры

• Недостатком RED, о котором сообщают многие специалисты, это отсутствие жёсткого алгоритма задания параметров RED [2].
• Параметры задают:
  • пороги;
  • форму функции сброса;
  • размер буфера.
• Изменение одних параметров тут же сказывается на других.

3.2 Функция сброса

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

3.3 Пути исследования

• Необходимо придумать такую функцию сброса, чтобы она вела себя нужным образом при конфигурации по умолчанию.
• Можно с помощью задания нескольких порогов задать разные функции на разных сегментах.
• Поскольку подобных функций можно задать достаточно много (с минимальным приложением усилий), а адекватной математической модели пока нет, исследования по улучшению RED будут продолжаться бесконечно.

4 Принципы работы

• RED отслеживает средний размер очереди и отбрасываемых пакетов, основываясь на статистической вероятности.
• Также RED может использовать отслеживание пометок ECN.
• Если буфер практически пуст, то все пакеты пропускаются в обычном режиме.
• Когда очередь начинает расти, то вероятность отбрасывания пакетов также начинает расти.
• Когда буфер полностью заполняется, вероятность становится равной единице и все входящие пакеты отбрасываются.
• Можно сказать, что когда заполненность буфера маршрутизатора превышает какое-либо пороговое значение, вероятность отбрасывания входящего пакета зависит от степени превышения этого порогового значения.

Литература