Random early detection

Random early detection (RED) (Довільне Раннє Виявлення) — один з алгоритмів AQM для управління переповненням черг маршрутизаторів.

Загальні положення

Недоліки інших алгоритмів

У традиційному алгоритмі відкидання кінця черги (Tail drop), маршрутизатор або інше мережеве обладнання набирає в буфер максимальну кількість пакетів, відкидаючи все, що залишається незавантаженим. Якщо буфери постійно заповнені, мережа стає перевантаженої.

У підсумку виходить, що Tail drop нераціонально використовує простір пам'яті маршрутизатора. Також у разі множинних коротких TCP сесій в мережі наступає перевантаження (коли на маршрутизатор надходить велика кількість ініціалізующіх пакетів). Не-TCP програми, що не володіють захистом від перевантаження, також викликають затори в мережі

Рішення проблеми

RED відстежує середній розмір черги і відкидаємо пакетів, грунтуючись на статистичній ймовірності. Також RED може використовувати відстеження позначок Explicit Congestion Notification | ECN.

Якщо буфер практично порожній, то всі пакети пропускаються в звичайному режимі. Коли черга починає рости, то ймовірність відкидання пакетів також починає зростати. Коли буфер повністю заповнюється, ймовірність стає рівною одиниці і всі вхідні пакети відкидаються.

Іншими словами, коли заповнюваність буфера маршрутизатора перевищує будь-яке порогове значення, вірогідність відкидання входить пакету залежить від ступеня перевищення цього граничного значення.

RED стає набагато ефективніше інших алгоритмів у випадку малих розмірів черг, а також при «вибуховий» характер трафіку.

Використання RED робить неможливим поділ за класами якості обслуговування (QoS). Тому у випадку, коли QoS важливо, використовуються інші варіанти алгоритму, такі як Weighted random early detection | Weighted RED (WRED) або RED In / Out (RIO).

Альтернативні варіанти

• Зважений RED (WRED ) дозволяє використовувати різні ймовірності для різних пріоритетів (IP precedence, DSCP) або черг.
• Адаптивний / Активний RED (ARED ) алгоритм вирішує в кожному окремому випадку, чи зробити RED більш-менш агресивним, грунтуючись на спостереженнях за середньою довжиною черги.

Посилання

• The RED web page (англ.)
• Guduz Project (англ.)