Random early detection

Random early detection (RED) (Произвольное Раннее Обнаружение) — один из алгоритмов AQM для управления переполнением очередей маршрутизаторов.

Общие положения

Недостатки других алгоритмов

В традиционном алгоритме отбрасывания конца очереди (Tail drop), маршрутизатор или другое сетевое оборудование набирает в буфер максимальное количество пакетов, отбрасывая всё, что остается незагруженным. Если буферы постоянно заполнены, сеть становится перегруженной ^[1]

В итоге получается, что Tail drop нерационально использует пространство памяти маршрутизатора. Также в случае множественных коротких TCP сессий в сети наступает перегрузка (когда на маршрутизатор поступает большое количество инициализующих пакетов). Не-TCP программы, не обладающие защитой от перегрузки, также вызывают заторы в сети ^[2].

Решение проблемы

RED отслеживает средний размер очереди и отбрасываемых пакетов, основываясь на статистической вероятности. Также RED может использовать отслеживание пометок ECN.

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

Другими словами, когда заполненность буфера маршрутизатора превышает какое-либо пороговое значение, вероятность отбрасывания входящего пакета зависит от степени превышения этого порогового значения.

RED становится намного эффективнее других алгоритмов в случае малых размеров очередей, а также при «взрывном» характере трафика.

Использование RED делает невозможным разделение по классам качества обслуживания (QoS). Поэтому в случае, когда QoS важно, используются другие варианты алгоритма, такие как Weighted RED (WRED) или RED In/Out (RIO).

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

Взвешенный RED (WRED) позволяет использовать различные вероятности для различных приоритетов (IP precedence, DSCP) или очередей.
Адаптивный / Активный RED (ARED) алгоритм ^[3] решает в каждом отдельном случае, сделать ли RED более или менее агрессивным, основываясь на наблюдениях за средней длиной очереди.

Примечания

↑ Floyd, Sally; Jacobson, Van.: Random Early Detection (RED) gateways for Congestion Avoidance (неопр.) 397–413 (August 1993). doi:10.1109/90.251892. Дата обращения: 26 января 2010. Архивировано из оригинала 15 апреля 2012 года.
↑ Управление трафиком: очереди и шейпинг (неопр.). Дата обращения: 26 января 2010. Архивировано 14 октября 2008 года.
↑ Floyd, Sally; Gummadi, Ramakrishna; Shenker, Scott.: Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management (неопр.) (1 августа 2001). Дата обращения: 26 января 2010. Архивировано из оригинала 15 апреля 2012 года.

Ссылки

[1] Floyd, Sally; Jacobson, Van.: Random Early Detection (RED) gateways for Congestion Avoidance (неопр.) 397–413 (August 1993). doi:10.1109/90.251892. Дата обращения: 26 января 2010. Архивировано из оригинала 15 апреля 2012 года.

[2] Управление трафиком: очереди и шейпинг (неопр.). Дата обращения: 26 января 2010. Архивировано 14 октября 2008 года.

[3] Floyd, Sally; Gummadi, Ramakrishna; Shenker, Scott.: Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management (неопр.) (1 августа 2001). Дата обращения: 26 января 2010. Архивировано из оригинала 15 апреля 2012 года.

[1]

[2]

[3]