Круговая система дефицита - Deficit round robin

Дефицит по круговой системе (DRR), также Круговая система, взвешенная по дефициту (DWRR), представляет собой алгоритм планирования для сетевой планировщик. DRR - это вроде взвешенная справедливая очередь (WFQ), пакетная реализация идеального Общий доступ к процессору (GPS) политика. Он был предложен М. Шридхаром и Г. Варгезе в 1995 г. как работоспособный (с О (1) сложность) и честный алгоритм.^[1]

подробности

В DRR планировщик обрабатывает N потоков.^[а] настроен с одним квантом ${ displaystyle Q_ {i}}$ для каждого потока. Эта глобальная идея заключается в том, что в каждом раунде поток ${ displaystyle i}$ могу отправить самое большее ${ displaystyle Q_ {i}}$ байты, а оставшиеся, если есть, сообщаются следующему раунду. Таким образом, поток чисел $я$ достигнет минимальной долгосрочной скорости передачи данных ${ displaystyle { frac {Q_ {i}} {(Q_ {1} + Q_ {2} + ... + Q_ {N})}} R}$ , где ${ displaystyle R}$ скорость ссылки.

Алгоритм

DRR последовательно сканирует все непустые очереди. Когда непустая очередь ${ displaystyle i}$ выбран, его счетчик дефицита увеличивается на его квантовое значение. Тогда значение счетчика дефицита - это максимальное количество байтов, которое может быть отправлено на этом ходу: если счетчик дефицита больше, чем размер пакета в начале очереди (HoQ), этот пакет может быть отправлен, а значение счетчика уменьшается на размер пакета. Затем размер следующего пакета сравнивается со значением счетчика и т. Д. Если очередь пуста или значение счетчика недостаточно, планировщик переходит к следующей очереди. Если очередь пуста, значение счетчика дефицита сбрасывается на 0.

Переменные и константы    const integer N // Nb очередей const integer Q [1..N] // Квантовое целое число для каждой очереди DC [1..N] // Счетчик дефицита очереди queue queue [1..N] // Очереди

Цикл планированияв то время как правда делать    для я в 1..N делать        если не очередь [i] .empty () тогда            DC [i]: = DC [i] + Q [i] в то время как(не queue [i] .empty () и                         DC [i] ≥ queue [i] .head (). Size ()) делать                DC [i]: = DC [i] - queue [i] .head (). Size () send (queue [i] .head ()) queue [i] .dequeue () конец пока             если очередь [i] .empty () тогда                DC [i]: = 0 конец, если        конец, если    конец дляконец пока

Спектакли: честность, сложность

Как и в других алгоритмах планирования, подобных GPS, выбор весов остается на усмотрение администратора сети.

Как и WFQ, DRR предлагает минимальную скорость для каждого потока независимо от размера пакетов. При планировании взвешенного циклического перебора доля используемой полосы пропускания зависит от размеров пакета.

По сравнению с планировщиком WFQ, сложность которого составляет O (журнал (п)) (п количество активных потоки / очереди ) сложность DRR составляет О (1), если квантовая ${ displaystyle Q_ {i}}$ больше максимального размера пакета этого потока. Тем не менее, у этой эффективности есть цена: задержка, т.е. расстояние до идеального GPS в DRR больше, чем в WFQ. ^[2]

Реализации

Реализация алгоритма циклического поиска дефицита была написана Патриком МакХарди для Ядро Linux^[3] и опубликовано под Стандартная общественная лицензия GNU.

В маршрутизаторах Cisco и Juniper реализованы модифицированные версии DRR: поскольку задержка DRR может быть больше для некоторого класса трафика, эти модифицированные версии дают более высокий приоритет некоторым очередям, тогда как другие обслуживаются стандартным алгоритмом DRR.^[4]^[5]

Смотрите также

Заметки

^ Потоки также могут называться очередями, классами или сеансами.

использованная литература

^ Shreedhar, M .; Варгезе, Г. (Октябрь 1995 г.). «Эффективная справедливая организация очередей с использованием кругового алгоритма дефицита». Обзор компьютерных коммуникаций ACM SIGCOMM. 25 (4): 231. Дои:10.1145/217391.217453. ISSN 0146-4833.
^ Лензини, Л .; Mingozzi, E .; Стеа, Г. (2002). «Aliquem: новая реализация DRR для достижения большей задержки и справедливости при сложности O (1)». IEEE 2002 Десятый международный семинар IEEE по качеству обслуживания (Кат. № 02EX564). п. 77. Дои:10.1109 / IWQoS.2002.1006576. ISBN 978-0-7803-7426-3.
^ "Модуль сетевого планировщика ядра DRR Linux". kernel.org. Получено 2013-09-07.
^ Лензини, Лучано; Мингоцци, Энцо; Стеа, Джованни (2007). «Анализ производительности модифицированных циклических планировщиков дефицита». Журнал IOS о высокоскоростных сетях.
^ Лензини, Лучано; Мингоцци, Энцо; Стеа, Джованни (2006). Анализ производительности модифицированных циклических планировщиков дефицита (Технический отчет). Dipartimento di Ingegneria della Informazione, Пизанский университет.

внешние ссылки

Лекция UC Berkeley EE122: Эффективная справедливая организация очередей с использованием циклического алгоритма дефицита

[2] Потоки также могут называться очередями, классами или сеансами.

[shreedhar-1] Shreedhar, M .; Варгезе, Г. (Октябрь 1995 г.). «Эффективная справедливая организация очередей с использованием кругового алгоритма дефицита». Обзор компьютерных коммуникаций ACM SIGCOMM. 25 (4): 231. Дои:10.1145/217391.217453. ISSN 0146-4833.

[Aliquem-DRR-3] Лензини, Л .; Mingozzi, E .; Стеа, Г. (2002). «Aliquem: новая реализация DRR для достижения большей задержки и справедливости при сложности O (1)». IEEE 2002 Десятый международный семинар IEEE по качеству обслуживания (Кат. № 02EX564). п. 77. Дои:10.1109 / IWQoS.2002.1006576. ISBN 978-0-7803-7426-3.

[4] "Модуль сетевого планировщика ядра DRR Linux". kernel.org. Получено 2013-09-07.

[5] Лензини, Лучано; Мингоцци, Энцо; Стеа, Джованни (2007). «Анализ производительности модифицированных циклических планировщиков дефицита». Журнал IOS о высокоскоростных сетях.

[6] Лензини, Лучано; Мингоцци, Энцо; Стеа, Джованни (2006). Анализ производительности модифицированных циклических планировщиков дефицита (Технический отчет). Dipartimento di Ingegneria della Informazione, Пизанский университет.

[1]

[а]

[2]

[3]

[4]

[5]