АссистентНовый вопросИсторияОбласти знаний
Партнёрские проектыСпецпроектыСтать автором
Сменить язык
О РУВИКИ

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, как и большинства дисциплин обслуживания с одной очередью, заключается в том, что она не различает отдельные потоки трафика, а обрабатывает их как единый агрегат. Поэтому агрессивный поток может вытеснить из очереди пакеты других, менее агрессивных, потоков.

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

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

Устойчивый стохастический справедливый Blue

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

Реализации

Реализация Blue входит в состав ALTQ — системы планирования сетевого трафика для BSD Unix[4].

Реализация SFB для Linux появилась в ядре Linux, начиная с версии 2.6.39[5][6][7].

Примечания

  1. ↑ Feng, Wu-chang; Kandlur, Dilip D.; Saha, Debanjan; Shin, Kang G. (апрель 1999). “BLUE: A New Class of Active Queue Management Algorithms” (PDF). Computer Science Technical Report [англ.]. Мичиганский университет (CSE–TR–387–99). Дата обращения 2024-06-17. Проверьте дату в |date= (справка на английском)
  2. ↑ Feng, Wu-Chang. Stochastic fair blue: A queue management algorithm for enforcing fairness // Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213) : [англ.] / Wu-Chang Feng, Dilip D. Kandlur, Debanjan Saha … [et al.]. — апрель 2001. — Vol. 3. — P. 1520–1529. — ISBN 978-0-7803-7016-6. — doi:10.1109/INFCOM.2001.916648.
  3. ↑ Zhang, Changwang. RSFB: a Resilient Stochastic Fair Blue algorithm against spoofing DDoS attacks : [англ.] / Changwang Zhang, Jianping Yin, Zhiping Cai. — 2009. — P. 1566–1567. — ISBN 978-1-4244-4521-9.
  4. ↑ Wu-chang Feng. Blue (англ.). The Fengs. Дата обращения: 17 июня 2024.
  5. ↑ Kernel Newbies — Linux 2.6.39 — Networking (англ.). Kernel Newbies. Дата обращения: 17 июня 2024.
  6. ↑ SFB Linux kernel network scheduler module (англ.). kernel.org. Дата обращения: 17 июня 2024.
  7. ↑ Juliusz Chroboczek. Stochastic Fair Blue for the Linux kernel (англ.). PPS, Университет Париж Дидро. Дата обращения: 17 июня 2024.

Категории