Взвешенный циклический перебор ( WRR ) - это сетевой планировщик потоков данных, который также используется для планирования процессов .
Взвешенный циклический алгоритм [1] является обобщением циклического планирования . Он обслуживает набор очередей или задач. В то время как циклический перебор очередей или задач дает одну возможность обслуживания за цикл, взвешенный циклический перебор предлагает каждому фиксированное количество возможностей, определяемое настроенным весом, который служит для влияния на долю емкости, получаемую каждой очередью или задачей. . В компьютерных сетях возможностью обслуживания является отправка одного пакета, если выбранная очередь не пуста.
Если все пакеты имеют одинаковый размер, WRR представляет собой простейшее приближение обобщенного совместного использования процессора (GPS). Существует несколько вариантов WRR. [2] Основными из них являются классический WRR и чередующийся WRR.
Алгоритм
Принципы
WRR представлен ниже как сетевой планировщик . Его также можно использовать для планирования задач аналогичным образом.
Планировщик взвешенной циклической сети имеет входные очереди, . В каждую очередь связано , положительное целое число, называемое весом . Планировщик WRR работает циклически. В каждом цикле каждая очередь имеет возможности выбросов.
Различные алгоритмы WRR различаются распределением этих возможностей в цикле.
Классический WRR
В классическом WRR [2] [3] [4] планировщик циклически перебирает очереди. Когда очередь выбран, планировщик будет отправлять пакеты, вплоть до выброса пакет или конец очереди.
Константа и переменные: const N // Кол-во очередей const weight [1..N] // вес каждой очереди queues [1..N] // очереди i // индекс очереди c // счетчик пакетов Инструкции: пока верно do for i in 1 .. N do c: = 0 while (not queue [i] .empty) и (c |
Чередование WRR
Позволять , быть максимальным весом. В ИВРР [1] [5] каждый цикл разделен нараундов. Очередь с весом может выпустить один пакет за один раз только если .
Константа и переменные: const N // Кол-во очередей const weight [1..N] // вес каждой очереди const w_max queues [1..N] // очереди i // индекс очереди r // счетчик раундов Инструкции: в то время как true do для r в 1 .. w_max do для i в 1 .. N делать if ( not queue [i] .empty) и (weight [i]> = r) then отправить (очередь [i] .head ()) очередь [i] .dequeue () |
Пример
Рассмотрим систему с тремя очередями и соответствующие веса . Рассмотрим ситуацию , когда они находятся 7 пакетов в первой очереди, A, B, C, D, E, F, G , 3 во второй очереди, U, V, W и 2 в третьей очереди X, Y . Предположим, что пакетов больше нет.
В классическом WRR в первом цикле планировщик сначала выбирает и передает пять пакетов в начале очереди, A, B, C, D, E (поскольку), затем выбирается вторая очередь, , и передает два пакета в начале очереди, U, V (так как), И в прошлом он выбирает третью очередь, которая имеет вес равен 3 , но только два пакета, так что он передает X, Y . Сразу после окончания передачи Y запускается второй цикл, а F, G изпередаются, за которыми следует W из.
При чередовании WRR первый цикл делится на 5 раундов. В первом ( r = 1 ) отправляется по одному пакету из каждой очереди ( A, U, X ), во втором раунде ( r = 2 ) также отправляется еще один пакет из каждой очереди ( B, V, Y ) , в третьем раунде ( r = 3 ) только очереди разрешено отправлять пакет (, а также ), но с тех пор пусто, только C изотправляется, а в четвертом и пятом раундах только D, E изпосланы. Затем запускается второй цикл, куда отправляются F, W, G.
Планирование задач
Планирование задач или процессов может выполняться в WRR аналогично планированию пакетов: при рассмотрении набора активные задачи, они планируются циклически, каждая задача получает квант или срез процессорного времени. [6] [7]
Характеристики
Подобно циклическому перебору , взвешенное циклическое планирование простое, легко реализуемое, экономное и свободное от голодания .
При планировании пакетов, если все пакеты имеют одинаковый размер, то WRR и IWRR являются приближением общего разделения процессора : [8] очередь получит долгосрочную часть пропускной способности, равную (если все очереди активны), в то время как GPS обслуживает бесконечно малые объемы данных из каждой непустой очереди и предлагает эту часть на любом интервале.
Если в очередях есть пакеты переменной длины, часть полосы пропускания, получаемая каждой очередью, зависит не только от весов, но и от размеров пакетов.
Если средний размер пакетов известен каждой очереди , каждая очередь получит долгосрочную часть полосы пропускания, равную . Если цель - дать каждой очереди порция пропускной способности канала (с ) можно установить .
Поскольку IWRR имеет меньшие пакеты для каждого класса, чем WRR, это подразумевает меньшие задержки в наихудшем случае. [9]
Ограничения и улучшения
WRR для планирования сетевых пакетов был впервые предложен Катевенисом, Сидиропулосом и Куркубетисом в 1991 году [1] специально для планирования в сетях ATM с использованием пакетов (ячеек) фиксированного размера. Основное ограничение взвешенной циклической организации очередей состоит в том, что она обеспечивает правильный процент полосы пропускания для каждого класса обслуживания только в том случае, если все пакеты во всех очередях имеют одинаковый размер или когда средний размер пакета известен заранее. В более общем случае IP-сетей с пакетами переменного размера для приближения GPS весовые коэффициенты должны быть скорректированы на основе размера пакета. Это требует оценки среднего размера пакета, что затрудняет получение хорошего приближения GPS на практике с WRR. [1]
Циклический перебор дефицита - это более поздний вариант WRR, который обеспечивает лучшее приближение GPS без предварительного знания среднего размера пакета каждого соединения. Также были введены более эффективные дисциплины планирования, которые позволяют справляться с упомянутыми выше ограничениями (например, взвешенная справедливая организация очередей ).
Смотрите также
Рекомендации
- ^ a b c d Катевенис, М .; Sidgiropoulos, S .; Куркубетис, К. (1991). «Взвешенное циклическое мультиплексирование ячеек в микросхеме коммутатора ATM общего назначения». Журнал IEEE по избранным областям коммуникаций . 9 (8): 1265–1279. DOI : 10.1109 / 49.105173 . ISSN 0733-8716 .
- ^ а б Часкар, HM; Мэдхоу, У. (2003). «Справедливое планирование с настраиваемой задержкой: циклический подход». Транзакции IEEE / ACM в сети . 11 (4): 592–601. DOI : 10.1109 / TNET.2003.815290 . ISSN 1063-6692 .
- ^ Брахими, Б .; Aubrun, C .; Рондо, Э. (2006). «Моделирование и имитация политик планирования, реализуемых в коммутаторе Ethernet с использованием цветных сетей Петри»: 667–674. DOI : 10.1109 / ETFA.2006.355373 . Цитировать журнал требует
|journal=
( помощь ) - ^ Ф. Бейкер; Р. Пан (май 2016). «2.2.2. Циклические модели». On Queuing, Marking, and Dropping (Технический отчет). IETF. RFC 7806.
- ^ Семерия, Чак (2001). Поддержка дифференцированных классов обслуживания: дисциплины планирования очередей (PDF) (отчет). С. 15–18 . Дата обращения 4 мая 2020 .
- ^ Болье, Ален (зима 2017). «Операционные системы реального времени - планирование и планировщики» (PDF) . Дата обращения 4 мая 2020 .
- ^ США 20190266019 , Филип Д. Хирш, «Планирование задач с использованием улучшенных методов взвешенного циклического перебора », опубликовано 29 августа 2019 г.
- ^ Падение, Кевин (29 апреля 1999 г.). «EECS 122,« Введение в сети связи », лекция 27,« Планирование оптимальных и гарантированных соединений » » . Дата обращения 4 мая 2020 .
- ^ Табатабаи, Сейед Мохаммадхоссейн; Ле Будек, Жан-Ив; Бойер, Марк (22–24 сентября 2020 г.). «Чередование взвешенных циклических алгоритмов: сетевой расчетный анализ» . Proc. 32-й Междунар. Конгресс по телетрафику (ITC 32) . DOI : 10.1109 / ITC3249928.2020.00016 . Проверено 14 апреля 2021 года .CS1 maint: формат даты ( ссылка )