stringtranslate.com

Случайное раннее обнаружение

Случайное раннее обнаружение ( RED ), также известное как случайное раннее отбрасывание или случайное раннее отбрасывание , представляет собой дисциплину очередности для сетевого планировщика , подходящую для предотвращения перегрузки . [1]

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

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

Операция

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

RED более справедлив, чем tail drop, в том смысле, что он не обладает предвзятостью против всплесков трафика, который использует только небольшую часть полосы пропускания. Чем больше хост передает, тем больше вероятность того, что его пакеты будут потеряны, поскольку вероятность потери пакета хоста пропорциональна объему данных, которые он имеет в очереди. Раннее обнаружение помогает избежать глобальной синхронизации TCP.

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

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

Чистый RED не учитывает дифференциацию качества обслуживания (QoS). Взвешенный RED (WRED) и RED с In и Out (RIO) [5] обеспечивают раннее обнаружение с учетом QoS.

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

ВРЕД

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

АРЕД

Алгоритм адаптивного RED или активного RED (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 . doi :10.1109/90.251892. S2CID  221977646. Получено 16.03.2008 .
  2. ^ Хафнер, Кэти (4 сентября 2019 г.). «Салли Флойд, которая помогла всему гладко пройти в Интернете, умерла в возрасте 69 лет». The New York Times .
  3. ^ ab Gettys, Jim (2010-12-17). "RED in a Different Light". jg's Ramblings . Получено 2010-12-27 .
  4. ^ Якобсон, Ван; Николс, Кэти; Подури, Кедар (30.09.1999). «КРАСНЫЙ в ином свете». CiteSeerX 10.1.1.22.9406 .  {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  5. ^ Кларк, Дэвид Д.; Вроцлавски, Джон (июль 1997 г.). «Подход к распределению услуг в Интернете». Ietf Datatracker . IETF. стр. 12. Получено 27.05.2011 .
  6. ^ Чао, Х. Джонатан (2002). «Frontmatter and Index». Качество управления обслуживанием в высокоскоростных сетях . Нью-Йорк: John Wiley & Sons Inc. стр. i–xvi. doi :10.1002/0471224391.fmatter_indsub. ISBN 978-0-471-00397-7.
  7. ^ Флойд, Салли; Гуммади, Рамакришна; Шенкер, Скотт (2001-08-01). "Адаптивный RED: алгоритм повышения надежности активного управления очередями RED" . Получено 16.03.2008 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  8. ^ Шрикант, Райадургам (2004). Математика управления перегрузкой Интернета. Бостон, Массачусетс, США: Birkhäuser. ISBN 978-0-8176-3227-4.
  9. ^ ab Zhang, Changwang; Yin, Jianping; Cai, Zhiping; Chen, Weifeng (1 мая 2010 г.). «RRED: надежный алгоритм RED для противодействия низкоскоростным атакам типа «отказ в обслуживании». IEEE Communications Letters . 14 (5): 489–491. doi :10.1109/LCOMM.2010.05.091407. S2CID  1121461.

Внешние ссылки