Дефицитный циклический робин
Алгоритм планирования для сетевого планировщика

Deficit Round Robin ( DRR ), также Deficit Weighted Round Robin ( DWRR ), является алгоритмом планирования для сетевого планировщика . DRR, как и Weighted Fair Queuing (WFQ), является пакетной реализацией идеальной политики Generalized Processor Sharing (GPS). Он был предложен M. Shreedhar и G. Varghese в 1995 году как эффективный (со сложностью O(1) ) и справедливый алгоритм. [1]

Подробности

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

Алгоритм

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

Переменные и константы const integer N // Nb очередей const целое число Q[1..N] // на такт очереди целое число DC[1..N] // Счетчик дефицита на очередь очередь очередь[1..N] // Очереди
Цикл планирования while true do  for i in 1..N do  if not queue[i].empty() then ДК[i]:= ДК[i] + Q[i] в то время как ( не queue[i].empty() и DC[i] ≥ queue[i].head().size() ) делают DC[i] := DC[i] − очередь[i].head().size() отправить( очередь[i].head() ) очередь[i].dequeue() конец пока  если очередь[i].empty() тогда ДК[i] := 0 конец если  конец если  конец для конца пока

Показатели: справедливость, сложность и задержка

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

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

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

Реализации

Реализация алгоритма дефицитного циклического перебора была написана Патриком Макхарди для ядра Linux [4] и опубликована под лицензией GNU General Public License .

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

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

Примечания

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

Ссылки

  1. ^ Шридхар, М.; Варгезе, Г. (октябрь 1995 г.). «Эффективная справедливая организация очередей с использованием дефицитного циклического алгоритма». ACM SIGCOMM Computer Communication Review . 25 (4): 231. doi :10.1145/217391.217453. ISSN  0146-4833.
  2. ^ Lenzini, L.; Mingozzi, E.; Stea, G. (2002). "Aliquem: новая реализация DRR для достижения лучшей задержки и справедливости при сложности O(1)". IEEE 2002 Tenth IEEE International Workshop on Quality of Service (Cat. No.02EX564) . стр.  77–86 . doi :10.1109/IWQoS.2002.1006576. ISBN 978-0-7803-7426-3. S2CID  62158653.
  3. ^ Табатабаи, Сейед Мохаммадхоссейн; Ле Будек, Жан-Ив (май 2021 г.). «Deficit Round-Robin: A Second Network Calculus Analysis». 2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS) (PDF) . Нэшвилл, Теннесси, США: IEEE. стр.  171–183 . doi :10.1109/RTAS52030.2021.00022. ISBN 978-1-6654-0386-3. S2CID  235294011.
  4. ^ "Модуль сетевого планировщика ядра DRR Linux". kernel.org . Получено 2013-09-07 .
  5. ^ Lenzini, Luciano; Mingozzi, Enzo; Stea, Giovanni (2007). «Анализ производительности модифицированных планировщиков с дефицитом циклического алгоритма». IOS Journal of High Speed ​​Networks . 16 (4): 399–422 .
  6. ^ Ленцини, Лучано; Мингоцци, Энцо; Стеа, Джованни (2006). Анализ производительности модифицированных планировщиков циклического обслуживания дефицита (Технический отчет). Dipartimento di Ingegneria della Informazione, Пизанский университет.
  • Лекция EE122 Калифорнийского университета в Беркли: Эффективная справедливая организация очередей с использованием дефицитного циклического обслуживания
Взято с "https://en.wikipedia.org/w/index.php?title=Deficit_round_robin&oldid=1236798513"