Дефицит по круговой системе

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

Подробности [ править ]

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

Алгоритм [ править ]

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

Переменные и константы 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] ${\ displaystyle Q_ {i}}$

Реализации [ править ]

Реализация алгоритма циклического перебора дефицита была написана Патриком МакХарди для ядра 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 .
^ Лензини, L .; Mingozzi, E .; Стеа, Г. (2002). «Aliquem: новая реализация DRR для достижения большей задержки и справедливости при сложности O (1)». IEEE 2002 Десятый международный семинар IEEE по качеству обслуживания (Кат. № 02EX564) . п. 77. DOI : 10,1109 / IWQoS.2002.1006576 . ISBN 978-0-7803-7426-3.
^ "Модуль сетевого планировщика ядра DRR Linux" . kernel.org . Проверено 7 сентября 2013 .
^ Лензини, Лучано; Мингоцци, Энцо; Стеа, Джованни (2007). «Анализ производительности модифицированных циклических планировщиков дефицита» . Журнал IOS высокоскоростных сетей .
^ Лензини, Лучано; Мингоцци, Энцо; Стеа, Джованни (2006). Анализ производительности модифицированных циклических планировщиков дефицита (Технический отчет). Dipartimento di Ingegneria della Informazione, Пизанский университет.

Внешние ссылки [ править ]

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

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

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

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

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

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

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

[1]