Круговой цикл дефицита

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

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

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

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

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

Variables and Constants
    const integer N             // Nb of queues
    const integer Q[1..N]       // Per queue quantum 
    integer DC[1..N]            // Per queue deficit counter
    queue queue[1..N]           // The queues

Scheduling Loop
while true do
    for i in 1..N do
        if not queue[i].empty() then
            DC[i]:= DC[i] + Q[i]
            while( not queue[i].empty() and
                         DC[i] ≥ queue[i].head().size() ) do
                DC[i] := DC[i] − queue[i].head().size()
                send( queue[i].head() )
                queue[i].dequeue()
            end while 
            if queue[i].empty() then
                DC[i] := 0
            end if
        end if
    end for
end while

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

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

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

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

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

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

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

См. также [ править ]

Примечания [ править ]

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

Ссылки [ править ]

^ Шридхар, М.; Варгезе, Г. (октябрь 1995 г.). «Эффективная справедливая организация очередей с использованием циклического алгоритма дефицита» . Обзор компьютерных коммуникаций ACM SIGCOMM . 25 (4): 231. дои : 10.1145/217391.217453 . ISSN 0146-4833 .
^ Лензини, Л.; Мингоцци, Э.; Стеа, Г. (2002). «Aliquem: новая реализация DRR для достижения лучшей задержки и справедливости при сложности O (1)». IEEE 2002 Десятый международный семинар IEEE по качеству обслуживания (кат. № 02EX564) . стр. 77–86. дои : 10.1109/IWQoS.2002.1006576 . ISBN 978-0-7803-7426-3 . S2CID 62158653 .
^ Табатабаи, Сейед Мохаммадхосейн; Ле Будек, Жан-Ив (май 2021 г.). «Кругловая система дефицита: второй анализ сетевого исчисления» . 27-й симпозиум IEEE по встраиваемым технологиям и приложениям реального времени (RTAS), 2021 г. (PDF) . Нэшвилл, Теннесси, США: IEEE. стр. 171–183. дои : 10.1109/RTAS52030.2021.00022 . ISBN 978-1-6654-0386-3 . S2CID 235294011 .
^ «Модуль сетевого планировщика ядра DRR Linux» . ядро.орг . Проверено 7 сентября 2013 г.
^ Ленцини, Лучано; Мингоцци, Энцо; Стеа, Джованни (2007). «Анализ производительности модифицированных планировщиков циклического обслуживания дефицита» . IOS Журнал высокоскоростных сетей . 16 (4): 399–422.
^ Ленцини, Лучано; Мингоцци, Энцо; Стеа, Джованни (2006). Анализ производительности модифицированных планировщиков циклического обслуживания дефицита (технический отчет). Департамент информационной инженерии Пизанского университета.

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

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

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

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

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

[4] Табатабаи, Сейед Мохаммадхосейн; Ле Будек, Жан-Ив (май 2021 г.). «Кругловая система дефицита: второй анализ сетевого исчисления» . 27-й симпозиум IEEE по встраиваемым технологиям и приложениям реального времени (RTAS), 2021 г. (PDF) . Нэшвилл, Теннесси, США: IEEE. стр. 171–183. дои : 10.1109/RTAS52030.2021.00022 . ISBN 978-1-6654-0386-3 . S2CID 235294011 .

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

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

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

[1]

[а]

[2]

[3]

[4]

[5]

[6]