Синий (алгоритм управления очередью)

Blue — это дисциплина планирования для сетевого планировщика, разработанная аспирантом У-чан Фэном для профессора Кан Г. Шина в Мичиганском университете и других в Исследовательском центре Томаса Дж. Уотсона IBM в 1999 году. ^[1]

Как и случайное раннее обнаружение (RED), Blue работает, случайным образом отбрасывая или помечая пакеты явной отметкой уведомления о перегрузке до того, как буфер передачи контроллера сетевого интерфейса переполнится. Однако, в отличие от RED, он требует небольшой настройки или не требует ее вовсе от сетевого администратора. Очередь Blue поддерживает вероятность отбрасывания/отметки p и отбрасывает/помечает пакеты с вероятностью p по мере их поступления в очередь. Всякий раз, когда очередь переполняется, p увеличивается на небольшую константу p _i , а всякий раз, когда очередь пуста, p уменьшается на константу p _d  < p _i .

Если состав трафика на интерфейсе не изменится, p будет медленно стремиться к значению, которое будет удерживать очередь в пределах своих границ при полном использовании канала.

Главный недостаток Blue, который он разделяет с большинством дисциплин очередей с одной очередью , заключается в том, что он не различает потоки трафика , а рассматривает все потоки как единый агрегат. Поэтому один агрессивный поток может выталкивать пакеты из очереди, принадлежащие другим, более хорошо себя ведущим потокам.

Стохастическая справедливость Blue (SFB) — это стохастически справедливая версия Blue, которая хэширует потоки и поддерживает различную вероятность отметки/отбрасывания для каждого значения хэша. При отсутствии коллизий хэша SFB может предоставить справедливую долю буферного пространства для каждого потока. При наличии коллизий хэша SFB является только стохастически справедливым. ^[2]

В отличие от других дисциплин стохастически справедливой очередности, таких как SFQ ( Stochastic Fairness Queuing ), SFB может быть реализована с использованием фильтра Блума, а не хэш-таблицы , что значительно снижает требования к ее хранению, когда число потоков велико. Когда вероятность отбрасывания/отметки потока достигает 1, было показано, что поток не реагирует на сигналы перегрузки от сети. Такой неэластичный поток помещается в « штрафную коробку » и ограничивается по скорости.

Многие алгоритмы планирования, включая ориентированные на справедливость, особенно уязвимы к атакам спуфинга распределенного отказа в обслуживании (DDoS). В 2009 году был предложен устойчивый стохастический справедливый алгоритм Blue (RSFB) против атак спуфинга DDoS. Основная идея RSFB заключается в записи ответных нормальных потоков TCP и восстановлении их потерянных пакетов. Алгоритм RSFB эффективен для сохранения пропускной способности TCP при наличии атак спуфинга DDoS. ^[3]

Реализация Blue является частью ALTQ , сетевого планировщика для BSD Unix. ^[4]

Реализация SFB для Linux была включена в ядро ​​Linux в версии 2.6.39. ^{[5] [6] [7]}