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 більш-менш агресивним, ґрунтуючись на спостереженнях за середньою довжиною черги.

Посилання ред.

http://www.icir.org/floyd/red.html [Архівовано 11 квітня 2003 у Wayback Machine.]
http://code.google.com/p/guduz/ [Архівовано 21 травня 2011 у Wayback Machine.]