stringtranslate.com

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

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

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

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

Операция

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

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

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

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

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

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

ВРЕД

В взвешенном 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 . дои : 10.1109/90.251892. S2CID  221977646 . Проверено 16 марта 2008 г.
  2. ↑ Хафнер, Кэти (4 сентября 2019 г.). «Салли Флойд, которая помогла интернету работать гладко, умерла в возрасте 69 лет» . Нью-Йорк Таймс .
  3. ^ аб Геттис, Джим (17 декабря 2010 г.). «КРАСНЫЙ в ином свете». jg's Ramblings . Проверено 27 декабря 2010 г.
  4. ^ Джейкобсон, Ван; Николс, Кэти; Подури, Кедар (30 сентября 1999 г.). «КРАСНЫЙ в ином свете». CiteSeerX 10.1.1.22.9406 .  {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
  5. ^ Кларк, Дэвид Д.; Вроцлавский, Джон (июль 1997 г.). «Подход к распределению услуг в Интернете». Ietf Datatracker . IETF. п. 12 . Проверено 27 мая 2011 г.
  6. ^ Чао, Х. Джонатан (2002). «Frontmatter и Индекс». Контроль качества обслуживания в высокоскоростных сетях . Нью-Йорк: John Wiley & Sons Inc., стр. i–xvi. doi : 10.1002/0471224391.fmatter_indsub. ISBN 978-0-471-00397-7.
  7. ^ Флойд, Салли; Гуммади, Рамакришна; Шенкер, Скотт (1 августа 2001 г.). «Адаптивный RED: алгоритм повышения устойчивости активного управления очередью RED» . Проверено 16 марта 2008 г. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
  8. ^ Шрикант, Раядургам (2004). Математика контроля перегрузки Интернета. Бостон, Массачусетс, США: Биркхойзер. ISBN 978-0-8176-3227-4.
  9. ^ Аб Чжан, Чанван; Инь, Цзяньпин; Цай, Чжипин; Чен, Вэйфэн (1 мая 2010 г.). «RRED: надежный алгоритм RED для противодействия низкочастотным атакам типа «отказ в обслуживании»». Коммуникационные письма IEEE . 14 (5): 489–491. дои : 10.1109/LCOMM.2010.05.091407. S2CID  1121461.

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