Синий (алгоритм управления очередью)
Blue — это дисциплина планирования для сетевого планировщика, разработанная аспирантом У-чан Фэном для профессора Канга Г. Шина из Мичиганского университета и других специалистов в Исследовательском центре Томаса Дж. Уотсона в IBM 1999 году. [1]
Функционирование [ править ]
Как и случайное раннее обнаружение (RED), Blue действует путем случайного отбрасывания или маркировки пакета явной меткой уведомления о перегрузке до того, как буфер передачи контроллера сетевого интерфейса переполнится. Однако, в отличие от RED, он практически не требует настройки со стороны сетевого администратора. Синяя очередь поддерживает вероятность удаления/маркировки p и удаляет/маркирует пакеты с вероятностью p при их поступлении в очередь. Всякий раз, когда очередь переполняется, p увеличивается на небольшую константу p i , а всякий раз, когда очередь пуста, p уменьшается на константу p d < p i .
Если состав трафика на интерфейсе не изменится, p будет медленно сходиться к значению, которое удерживает очередь в пределах ее границ с полным использованием канала.
ярмарка Blue Стохастическая
Главный недостаток Blue, который он разделяет с большинством дисциплин очередей с одной очередью , заключается в том, что он не различает потоки трафика , а рассматривает все потоки как единый агрегат. Таким образом, один агрессивный поток может вытолкнуть пакеты из очереди, принадлежащей другим, более управляемым потокам.
Stochastic fair Blue (SFB) — это стохастически справедливый вариант Blue, который хэширует потоки и поддерживает различную вероятность отметки/отбрасывания для каждого значения хеш-функции. При отсутствии хэш-коллизий SFB может предоставить достаточную долю буферного пространства для каждого потока. При наличии коллизий хэшей SFB справедлив только стохастически. [2]
В отличие от других стохастически справедливых дисциплин организации очередей, таких как SFQ ( Stochastic Fairness Queuing ), SFB может быть реализован с использованием фильтра Блума , а не хеш-таблицы , что значительно снижает требования к объему хранилища при большом количестве потоков.Когда вероятность падения/отметки потока достигает 1, было показано, что поток не реагирует на признаки перегрузки из сети. Такой неэластичный поток помещается в « штрафную скамью » и ограничивается по скорости.
Устойчивая стохастическая ярмарка Blue [ править ]
Многие алгоритмы планирования, в том числе ориентированные на справедливость, особенно уязвимы для подмены типа «отказ в обслуживании» распределенных атак (DDoS). В 2009 году был предложен устойчивый стохастический алгоритм Fair Blue (RSFB) для защиты от поддельных DDoS-атак. Основная идея RSFB заключается в записи реагирующих обычных потоков TCP и восстановлении отброшенных пакетов. Алгоритм RSFB эффективен для сохранения пропускной способности TCP при наличии поддельных DDoS-атак. [3]
Реализации [ править ]
Реализация Blue является частью ALTQ , сетевого планировщика для BSD Unix. [4]
Реализация SFB для Linux была включена в ядро Linux в версии 2.6.39. [5] [6] [7]
Ссылки [ править ]
- ^ У-чан Фэн; Дилип Д. Кандлур; Дебанжан Саха; Кан Г. Шин (апрель 1999 г.). «СИНИЙ: новый класс алгоритмов активного управления очередью» (PDF) . Технический отчет по информатике (CSE–TR–387–99). Мичиганский университет . Проверено 8 июня 2013 г.
- ^ У-Чанг Фэн; Дилип Д. Кандлур; Дебанжан Саха; Кан Г. Шин (апрель 2001 г.). «Стохастический справедливый синий: алгоритм управления очередями для обеспечения справедливости». Материалы IEEE INFOCOM 2001. Конференция по компьютерным коммуникациям. Двадцатая ежегодная совместная конференция Общества компьютеров и коммуникаций IEEE (кат. № 01CH37213) (PDF) . Том. 3. С. 1520–1529. CiteSeerX 10.1.1.11.4235 . дои : 10.1109/INFCOM.2001.916648 . ISBN 978-0-7803-7016-6 . S2CID 5902623 . Проверено 8 июня 2013 г.
- ^ Чангван Чжан; Цзяньпин Инь и Чжипин Цай (2009). RSFB: устойчивый алгоритм Stochastic Fair Blue против поддельных DDoS-атак (PDF) . стр. 1566–1567. ISBN 978-1-4244-4521-9 . Проверено 8 июня 2013 г.
{{cite book}}:|journal=игнорируется ( помощь ) Аннотация - ^ У-чан Фэн. "Синий" . Веб-страница . Проверено 8 июня 2013 г.
- ^ Новички в ядре - Linux 2.6.39 - Сеть
- ^ «Модуль сетевого планировщика ядра SFB Linux» . ядро.орг . Проверено 7 сентября 2013 г.
- ^ Юлиуш Хробочек. «Stochastic Fair Blue для ядра Linux» . Проверено 8 июня 2013 г.