Случайное раннее обнаружение ( RED ), также известное как случайное раннее отбрасывание или случайное раннее отбрасывание , представляет собой дисциплину очередности для сетевого планировщика , подходящую для предотвращения перегрузки . [1]
В обычном алгоритме отбрасывания хвоста маршрутизатор или другой сетевой компонент буферизует столько пакетов, сколько может, и просто отбрасывает те, которые не может буферизовать. Если буферы постоянно заполнены, сеть перегружена . Отбрасывание хвоста распределяет буферное пространство несправедливо между потоками трафика. Отбрасывание хвоста также может привести к глобальной синхронизации TCP, поскольку все соединения TCP одновременно «отстают», а затем одновременно выходят вперед. Сети становятся недоиспользованными и переполненными — попеременно, волнами.
RED решает эти проблемы, заранее отбрасывая пакеты до того, как буфер полностью заполнится. Он использует предиктивные модели для определения того, какие пакеты отбрасывать. Он был изобретен в начале 1990-х годов Салли Флойд и Ван Якобсоном . [2]
RED отслеживает средний размер очереди и отбрасывает (или помечает при использовании совместно с ECN ) пакеты на основе статистических вероятностей . Если буфер почти пуст, то принимаются все входящие пакеты. По мере роста очереди растет и вероятность отбрасывания входящего пакета. Когда буфер заполнен, вероятность достигает 1 и все входящие пакеты отбрасываются.
RED более справедлив, чем tail drop, в том смысле, что он не обладает предвзятостью против всплесков трафика, который использует только небольшую часть полосы пропускания. Чем больше хост передает, тем больше вероятность того, что его пакеты будут потеряны, поскольку вероятность потери пакета хоста пропорциональна объему данных, которые он имеет в очереди. Раннее обнаружение помогает избежать глобальной синхронизации TCP.
По словам Ван Якобсона, «в классическом 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]
{{cite journal}}
: Цитировать журнал требует |journal=
( помощь ){{cite journal}}
: Цитировать журнал требует |journal=
( помощь )