Случайное раннее обнаружение - Random early detection

Алгоритм случайного раннего обнаружения en.svg

Случайное раннее обнаружение (КРАСНЫЙ), также известный как случайный ранний сброс или же случайное раннее выпадение это дисциплина в очереди для сетевой планировщик подходит для предотвращение перегрузки.[1]

В обычном падение хвоста алгоритм, а маршрутизатор или другой сетевой компонент буферизует столько пакетов, сколько может, и просто отбрасывает те, которые не могут буферизовать. Если буферы постоянно заполнены, сеть перегружен. Отбрасывание хвоста несправедливо распределяет буферное пространство между потоками трафика. Опущение хвоста также может привести к Глобальная синхронизация TCP это все TCP соединения "сдерживаются" одновременно, а затем одновременно шагают вперед. Сети становятся недостаточно используемыми и затопляются - поочередно волнами.

RED решает эти проблемы путем упреждающего отбрасывания пакетов до того, как буфер станет полностью заполненным. Он использует модели прогнозирования, чтобы решить, какие пакеты отбрасывать. Он был изобретен в начале 1990-х годов Салли Флойд и Ван Якобсон.[2]

Операция

КРАСНЫЙ отслеживает средний размер очереди и отбрасывает (или отмечает при использовании вместе с ECN ) пакетов на основе статистических вероятности. Если буфер почти пуст, все входящие пакеты принимаются. По мере роста очереди растет и вероятность отбрасывания входящего пакета. Когда буфер заполнен, вероятность достигает 1 и все входящие пакеты отбрасываются.

КРАСНЫЙ более справедлив, чем отбрасывание хвоста, в том смысле, что он не обладает предубеждением против скачкообразного трафика, который использует только небольшую часть полосы пропускания. Чем больше хост передает, тем больше вероятность того, что его пакеты будут отброшены, поскольку вероятность того, что пакет хоста будет отброшен, пропорциональна количеству данных, которые он имеет в очереди. Раннее обнаружение помогает избежать глобальной синхронизации TCP.

Проблемы с классическим RED

По словам Ван Якобсона, «в классическом RED есть не одна, а две ошибки».[3] Были разработаны улучшения алгоритма и черновой вариант[4] был подготовлен, но документ так и не был опубликован, а улучшения не получили широкого распространения или внедрения. Была проведена некоторая работа по завершению исследования и исправлению ошибок.[3]

Pure RED не вмещает качество обслуживания (QoS) дифференциация. Взвешенный КРАСНЫЙ (WRED) и RED с входом и выходом (RIO)[5] обеспечить раннее обнаружение с учетом QoS.

Другие варианты

WRED

Основная статья: Взвешенное случайное раннее обнаружение

В взвешенном RED вы можете иметь разные вероятности для разных приоритетов (Приоритет IP, DSCP ) и / или очереди.[6]

ARED

Адаптивный КРАСНЫЙ или активный КРАСНЫЙ (ARED) алгоритм[7] определяет, следует ли сделать RED более или менее агрессивным, основываясь на наблюдении за средней длиной очереди. Если средняя длина очереди колеблется около мин порог, то раннее обнаружение слишком агрессивно. С другой стороны, если средняя длина очереди колеблется около Максимум порог, то раннее выявление слишком консервативно. Алгоритм изменяет вероятность в зависимости от того, насколько агрессивно он ощущает сброс трафика.

См. Шрикант[8] для углубленного изучения этих методов и их анализа.

КРАСНЫЙ

Основная статья: Надежное раннее случайное обнаружение

Алгоритм надежного случайного раннего обнаружения (RRED) был предложен для повышения пропускной способности TCP против атак типа «отказ в обслуживании» (DoS), в частности Низкий уровень отказа в обслуживании (LDoS) атаки. Эксперименты подтвердили, что существующие алгоритмы, подобные RED, особенно уязвимы для низкоскоростных атак типа «отказ в обслуживании» (LDoS) из-за колеблющегося размера очереди TCP, вызванного атаками.[9] Алгоритм RRED может значительно улучшить производительность TCP при низкоскоростных атаках типа «отказ в обслуживании».[9]

Смотрите также

Рекомендации

  1. ^ Флойд, Салли; Якобсон, Ван (август 1993 г.). «Шлюзы случайного раннего обнаружения (RED) для предотвращения перегрузки». Транзакции IEEE / ACM в сети. 1 (4): 397–413. CiteSeerX  10.1.1.147.3833. Дои:10.1109/90.251892. Получено 2008-03-16.
  2. ^ Хафнер, Кэти (4 сентября 2019 г.). «Салли Флойд, которая помогала вещам работать гладко в Интернете, умерла в возрасте 69 лет» - через NYTimes.com.
  3. ^ а б Геттис, Джим (17 декабря 2010 г.). «КРАСНЫЙ в ином свете». jg's Ramblings. Получено 2010-12-27.
  4. ^ Якобсон, Ван; Николс, Кэти; Подури, Кедар (30 сентября 1999). «КРАСНЫЙ в ином свете». CiteSeerX  10.1.1.22.9406. Цитировать журнал требует | журнал = (помощь)
  5. ^ Кларк, Дэвид Д.; Вроцлавский, Джон (июль 1997 г.). «Подход к размещению услуг в Интернете». IETF. п. 12. Получено 2011-05-27.
  6. ^ Чао, Х. Джонатан (2002). "Frontmatter and Index". Контроль качества обслуживания в высокоскоростных сетях. 605 Третья авеню, Нью-Йорк, штат Нью-Йорк: John Wiley & Sons Inc., стр. I – xvi. Дои:10.1002 / 0471224391.fmatter_indsub. ISBN  978-0-471-00397-7.CS1 maint: location (связь)
  7. ^ Флойд, Салли; Гуммади, Рамакришна; Шенкер, Скотт (2001-08-01). «Adaptive RED: алгоритм повышения устойчивости активного управления очередью RED». Получено 2008-03-16. Цитировать журнал требует | журнал = (помощь)
  8. ^ Срикант, Райадургам (2004). Математика управления перегрузкой в ​​Интернете. Бостон, Массачусетс, США: Birkhäuser. ISBN  978-0-8176-3227-4.
  9. ^ а б Чжан, Чангван; Инь, Цзяньпин; Цай, Чжипин; Чен, Вэйфэн (1 мая 2010 г.). «RRED: надежный алгоритм RED для противодействия низкоскоростным атакам типа« отказ в обслуживании »». Письма по коммуникациям IEEE. 14 (5): 489–491. Дои:10.1109 / LCOMM.2010.05.091407.

внешняя ссылка