Blue (алгоритм управления очередью)
Blue — это дисциплина управления очередями (англ. scheduling discipline) в сетевом планировщике, разработанная аспирантом У-чан Фэном (Wu-chang Feng) совместно с профессором Кан Ги Шином (Kang G. Shin) в Мичиганском университете (англ. University of Michigan) и сотрудниками исследовательского центра имени Томаса Дж. Уотсона компании IBM (англ. Thomas J. Watson Research Center) в 1999 году[1].
Принципы работы
Подобно механизму случайного раннего обнаружения перегрузки (англ. random early detection, RED), Blue работает путём случайного сбрасывания или маркирования пакетов с использованием явных уведомлений о перегрузке (англ. explicit congestion notification) до того, как буфер передачи сетевого интерфейса (англ. network interface controller) переполнится. В отличие от RED, Blue практически не требует настройки со стороны сетевого администратора. Очередь Blue поддерживает вероятность сброса/маркировки p и сбрасывает или маркирует пакеты с вероятностью p по мере их поступления в очередь. Каждый раз при переполнении очереди значение p увеличивается на небольшую постоянную величину pi, а при опустошении очереди — уменьшается на постоянную pd < pi.
Если характер трафика на интерфейсе не меняется, p постепенно стремится к такому значению, при котором очередь поддерживается в допустимых границах при полной загрузке канала.
Основной недостаток Blue, как и большинства дисциплин обслуживания с одной очередью, заключается в том, что она не различает отдельные потоки трафика, а обрабатывает их как единый агрегат. Поэтому агрессивный поток может вытеснить из очереди пакеты других, менее агрессивных, потоков.
Стохастическая справедливая Blue (англ. stochastic fair Blue, SFB) — модификация Blue, обеспечивающая стохастическую справедливость за счёт хеширования потоков и поддержания для каждого значения хеша собственной вероятности маркировки/сброса. При отсутствии коллизий хеша SFB позволяет каждому потоку получать равную долю буферного пространства. При наличии коллизий справедливость обеспечивается лишь стохастически[2].
В отличие от других стохастических справедливых дисциплин очередей, таких как SFQ (англ. Stochastic Fairness Queuing), SFB может быть реализована с использованием блум-фильтра (англ. bloom filter) вместо хеш-таблицы, что существенно снижает требования к памяти при большом числе потоков. Если вероятность сброса/маркировки потока достигает 1, это свидетельствует о неэффективном (неэластичном) отклике потока на сигналы перегрузки сети. Такой поток помещается в «камеру штрафников» (англ. penalty box) и ограничивается по скорости.
Многие алгоритмы планирования, включая направленные на справедливость, уязвимы для атак с подделкой исходного адреса при распределённых атаках отказа в обслуживании (DDoS). В 2009 году был предложен алгоритм устойчивого стохастического справедливого Blue (RSFB, англ. Resilient Stochastic Fair Blue) для противодействия таким атакам. Его основная идея заключается в сохранении записей о корректных TCP-потоках и восстановлении теряемых ими пакетов. Алгоритм RSFB эффективен для поддержания пропускной способности TCP при наличии DDoS-атак с подделкой исходных адресов[3].