Случайное раннее обнаружение ( RED ), также известное как случайное раннее отбрасывание или случайное раннее отбрасывание, представляет собой дисциплину организации очереди для сетевого планировщика, подходящую для предотвращения перегрузки . [1]
В обычном алгоритме отбрасывания хвоста маршрутизатор или другой сетевой компонент буферизует столько пакетов, сколько может, и просто отбрасывает те, которые он не может буферизовать. Если буферы постоянно заполнены, сеть перегружена . Отбрасывание хвоста несправедливо распределяет буферное пространство между потоками трафика. Отбрасывание хвоста также может привести к глобальной синхронизации TCP, так как все TCP- соединения "сдерживаются" одновременно, а затем продвигаются вперед одновременно. Сети становятся недостаточно используемыми и затопляются - поочередно волнами.
RED решает эти проблемы, упреждая отбрасывание пакетов до того, как буфер станет полностью заполненным. Он использует модели прогнозирования, чтобы решить, какие пакеты отбрасывать. Его изобрели в начале 1990-х Салли Флойд и Ван Джейкобсон . [2]
Операция [ править ]
RED отслеживает средний размер очереди и отбрасывает (или маркирует при использовании вместе с ECN ) пакеты на основе статистических вероятностей . Если буфер почти пуст, все входящие пакеты принимаются. По мере роста очереди растет и вероятность отбрасывания входящего пакета. Когда буфер заполнен, вероятность достигает 1, и все входящие пакеты отбрасываются.
КРАСНЫЙ более справедлив, чем отбрасывание хвоста, в том смысле, что он не обладает предубеждением против скачкообразного трафика, который использует только небольшую часть полосы пропускания. Чем больше хост передает, тем более вероятно, что его пакеты будут отброшены, поскольку вероятность того, что пакет хоста будет отброшен, пропорциональна количеству данных, которые он имеет в очереди. Раннее обнаружение помогает избежать глобальной синхронизации TCP.
Проблемы с классическим RED [ править ]
По словам Ван Якобсона, «в классическом RED есть не одна, а две ошибки». [3] Были разработаны усовершенствования алгоритма и подготовлен черновой вариант [4] , но документ так и не был опубликован, а улучшения не получили широкого распространения или внедрения. Была проведена некоторая работа по завершению исследования и исправлению ошибок. [3]
Pure RED не допускает дифференциации качества обслуживания (QoS). Взвешенный КРАСНЫЙ (WRED) и КРАСНЫЙ с входом и выходом (RIO) [5] обеспечивают раннее обнаружение с учетом требований QoS.
Другие варианты [ править ]
WRED [ править ]
В взвешенном RED у вас могут быть разные вероятности для разных приоритетов (приоритет IP , DSCP ) и / или очередей. [6]
ARED [ править ]
Алгоритм адаптивного КРАСНОГО или активного КРАСНОГО (ARED) [7] определяет, следует ли сделать КРАСНЫЙ более или менее агрессивным, на основе наблюдения за средней длиной очереди. Если средняя длина очереди колеблется около минимального порога, раннее обнаружение слишком агрессивно. С другой стороны, если средняя длина очереди колеблется около максимального порога, раннее обнаружение является слишком консервативным. Алгоритм изменяет вероятность в зависимости от того, насколько агрессивно он считает, что отбрасывает трафик.
См. Подробное описание этих методов и их анализа в Srikant [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 . DOI : 10.1109 / 90.251892 . Проверено 16 марта 2008 . CS1 maint: обескураженный параметр ( ссылка )
- ↑ Хафнер, Кэти (4 сентября 2019 г.). «Салли Флойд, которая помогала вещам работать гладко в Интернете, умирает в возрасте 69 лет» - через NYTimes.com.
- ^ a b Геттис, Джим (17 декабря 2010 г.). «КРАСНЫЙ в ином свете» . jg's Ramblings . Проверено 27 декабря 2010 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Якобсон, Ван; Николс, Кэти; Подури, Кедар (30 сентября 1999). «КРАСНЫЙ в ином свете». CiteSeerX 10.1.1.22.9406 . Цитировать журнал требует
|journal=( помощь ) - ^ Кларк, Дэвид Д .; Вроцлавский, Джон (июль 1997 г.). «Подход к размещению услуг в Интернете» . IETF. п. 12 . Проверено 27 мая 2011 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Чао, Х. Джонатан (2002). "Frontmatter and Index". Контроль качества обслуживания в высокоскоростных сетях . 605 Third Avenue, New York, NY: John Wiley & Sons Inc., стр. I – xvi. DOI : 10.1002 / 0471224391.fmatter_indsub . ISBN 978-0-471-00397-7.CS1 maint: location ( ссылка )
- ^ Флойд, Салли; Гуммади, Рамакришна; Шенкер, Скотт (2001-08-01). «Адаптивный RED: алгоритм повышения устойчивости активного управления очередью RED» . Проверено 16 марта 2008 . Цитировать журнал требует
|journal=( помощь )CS1 maint: обескураженный параметр ( ссылка ) - ^ Srikant, Rayadurgam (2004). Математика управления перегрузкой Интернета . Бостон, Массачусетс, США: Birkhäuser. ISBN 978-0-8176-3227-4.
- ^ а б Чжан, Чангван; Инь, Цзяньпин; Цай, Чжипин; Чен, Вэйфэн (1 мая 2010 г.). «RRED: надежный алгоритм RED для противодействия низкоскоростным атакам типа« отказ в обслуживании »». Письма связи IEEE . 14 (5): 489–491. DOI : 10,1109 / LCOMM.2010.05.091407 .
Внешние ссылки [ править ]
- RED (случайное раннее обнаружение) Управление очередью . Автор: Салли Флойд
- Гудуз - простой симулятор случайного раннего обнаружения (RED)
- Варианты КРАСНОГО . Автор: Хэй Сяо Цзюнь
- Последние публикации в схемах случайного раннего обнаружения (RED)
