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