Круговой алгоритм дефицита ( DRR ), а также циклический алгоритм, взвешенный по дефициту ( DWRR ), представляет собой алгоритм планирования для сетевого планировщика . DRR, как и взвешенная справедливая организация очереди (WFQ), представляет собой пакетную реализацию идеальной политики общего доступа к процессору (GPS). Он был предложен М. Шридхаром и Дж. Варгезом в 1995 г. как эффективный (со сложностью O (1) ) и справедливый алгоритм. [1]
Подробности
В DRR планировщик, обрабатывающий N потоков [a] , настроен с одним квантомдля каждого потока. Эта глобальная идея заключается в том, что в каждом раунде поток могу отправить самое большее байты, а оставшиеся, если они есть, сообщаются следующему раунду. Таким образом, поток числа i достигнет минимальной долгосрочной скорости передачи данных, где скорость ссылки.
Алгоритм
DRR последовательно сканирует все непустые очереди. Когда непустая очередьвыбран, его счетчик дефицита увеличивается на его квантовое значение. Тогда значение счетчика дефицита - это максимальное количество байтов, которое может быть отправлено на этом этапе: если счетчик дефицита больше, чем размер пакета в начале очереди (HoQ), этот пакет может быть отправлен, а значение счетчика уменьшается на размер пакета. Затем размер следующего пакета сравнивается со значением счетчика и т. Д. Если очередь пуста или значение счетчика недостаточно, планировщик переходит к следующей очереди. Если очередь пуста, значение счетчика дефицита сбрасывается на 0.
Переменные и константы const integer N // Кол-во очередей const integer Q [1..N] // На квант очереди integer DC [1..N] // Счетчик дефицита на каждую очередь queue queue [1..N] // очереди
Цикл планирования при истинном значении do for i in 1..N do if not queue [i] .empty () then DC [i]: = DC [i] + Q [i] while (not queue [i] .empty () и DC [i] ≥ queue [i] .head (). size ()) делать DC [i]: = DC [i] - queue [i] .head (). Size () отправить (очередь [i] .head ()) очередь [i] .dequeue () end while if queue [i] .empty () тогда DC [i]: = 0 конец если конец если конец за конец пока
Спектакли: честность, сложность
Как и в случае других алгоритмов планирования, подобных GPS, выбор весов остается на усмотрение администратора сети.
Как и WFQ, DRR предлагает минимальную скорость для каждого потока независимо от размера пакетов. При взвешенном циклическом планировании доля используемой полосы пропускания зависит от размеров пакета.
По сравнению с планировщиком WFQ, который имеет сложность O (log (n)) ( n - количество активных потоков / очередей ), сложность DRR составляет O (1) , если квантбольше максимального размера пакета этого потока. Тем не менее, эта эффективность имеет свою цену: задержка, то есть расстояние до идеального GPS, больше в DRR, чем в WFQ. [2]
Реализации
Реализация алгоритма циклического перебора дефицита была написана Патриком МакХарди для ядра Linux [3] и опубликована под лицензией GNU General Public License .
В маршрутизаторах Cisco и Juniper реализованы модифицированные версии DRR: поскольку задержка DRR может быть больше для некоторых классов трафика, эти модифицированные версии дают более высокий приоритет некоторым очередям, тогда как другие обслуживаются стандартным алгоритмом DRR. [4] [5]
Смотрите также
Заметки
- ^ Потоки также могут называться очередями, классами или сеансами.
Рекомендации
- ^ Shreedhar, M .; Варгезе, Г. (Октябрь 1995 г.). «Эффективная честная организация очередей с использованием кругового алгоритма дефицита» . Обзор компьютерных коммуникаций ACM SIGCOMM . 25 (4): 231. DOI : 10,1145 / 217391,217453 . ISSN 0146-4833 .
- ^ Лензини, Л .; Mingozzi, E .; Стеа, Г. (2002). «Aliquem: новая реализация DRR для достижения большей задержки и справедливости при сложности O (1)». IEEE 2002 Десятый международный семинар IEEE по качеству обслуживания (Кат. № 02EX564) . п. 77. DOI : 10,1109 / IWQoS.2002.1006576 . ISBN 978-0-7803-7426-3. S2CID 62158653 .
- ^ "Модуль сетевого планировщика ядра DRR Linux" . kernel.org . Проверено 7 сентября 2013 .
- ^ Лензини, Лучано; Мингоцци, Энцо; Стеа, Джованни (2007). «Анализ производительности модифицированных циклических планировщиков дефицита» . Журнал IOS высокоскоростных сетей .
- ^ Лензини, Лучано; Мингоцци, Энцо; Стеа, Джованни (2006). Анализ производительности модифицированных циклических планировщиков дефицита (Технический отчет). Dipartimento di Ingegneria della Informazione, Пизанский университет.