Круговой взвешенный алгоритм

редактировать

алгоритм планирования, в котором работы (задачи или потоки данных) чередуются пропорционально назначенному им весу

Взвешенный циклический перебор (WRR ) - это алгоритм планирования, используемый в сетях для планирования потоков данных, но также используемый для планирования процессов.

Взвешенный циклический перебор является обобщением циклического планирования. Он обслуживает набор очередей или задач. В то время как циклический перебор очередей / задач дает одну возможность обслуживания за цикл, взвешенный круговой перебор предлагает каждому фиксированное количество возможностей, рабочий вес, установленный в конфигурации. Затем это позволяет влиять на долю емкости, получаемую каждой очередью / задачей.

В компьютерных сетях возможность обслуживания - это передача одного пакета, если выбранная очередь не пуста. Если все пакеты имеют одинаковый размер, WRR представляет собой простейшее приближение обобщенного совместного использования процессора (GPS).

Существует несколько вариантов WRR. Основными из них являются классический WRR и Interleaved WRR.

Содержание

1 Алгоритм
- 1.1 Принципы
- 1.2 Классический WRR
- 1.3 Чередующийся WRR
- 1.4 Пример
2 Планирование задач
3 Свойства
4 Ограничения и улучшения
5 См. Также
6 Ссылки

Алгоритм

Принципы

WRR представлен ниже как сетевой планировщик. Его также можно использовать для планирования задач аналогичным образом.

Взвешенный планировщик сети с циклическим перебором имеет $n {\ displaystyle n}$ $n$ очередей ввода, $q 1,..., q n {\ displaystyle q_ {1},..., q_ {n}}$ ${\ displaystyle q_ {1},..., q_ {n}}$ . С каждой очередью $q i {\ displaystyle q_ {i}}$ $q_ {i}$ связано $w i {\ displaystyle w_ {i}}$ $w_ {i}$ , положительное целое число, называемое весом. Планировщик WRR имеет циклическое поведение. В каждом цикле каждая очередь $q i {\ displaystyle q_ {i}}$ $q_ {i}$ имеет $w i {\ displaystyle w_ {i}}$ $w_ {i}$ возможности выбросов.

Различные алгоритмы WRR различаются распределением этих возможностей в цикле.

Классический WRR

В классическом WRR планировщик циклически перебирает очереди. Когда выбрана очередь $qi {\ displaystyle q_ {i}}$ $q_ {i}$ , планировщик будет отправлять пакеты до выброса $wi {\ displaystyle w_ {i}}$ $w_ {i}$ пакет или конец очереди.

Константа и переменные: const N // Nb очередей const weight [1..N] // вес каждой очереди queues [1..N] // очереди i // индекс очереди c // пакет counter Инструкции :while true doдля i in1.. N do c: = 0 while (не очередь [ i].empty) и (c

Interleaved WRR

Let $wmax = max {wi} {\ displaystyle w_ {max} = \ max \ {w_ {i} \}}$ ${\ displaystyle w_ {max} = \ max \ {w_ {i} \}}$ - максимальный вес. В IWRR каждый цикл разбивается на $wmax {\ displaystyle w_ {max}}$ ${\ displaystyle w_ {max}}$ раундов. Очередь с весом $wi {\ displaystyle w_ {i}}$ $w_ {i}$ может отправить один пакет на раунде $r {\ displaystyle r}$ $r$ , только если $r ≤ wi {\ displaystyle r \ leq w_ {i}}$ ${\ displaystyle r \ leq w_ {i}}$ .

Константа и переменные: const N // Кол-во очередей const weight [1..N] // вес каждой очереди const w_max queues [1..N] // очереди i // индекс очереди r // счетчик раундов Инструкции:

while true dofor r in1.. w_max doдля i in1.. N doif(не queue [i].empt y) и (weight [1..N]>= r) затем send (queue [i].head ()) queue [i].dequeue ()

Пример

Пример планирование для CWRR и IWRR

Рассмотрим систему с тремя очередями $q 1, q 2, q 3 {\ displaystyle q_ {1}, q_ {2}, q_ {3}}$ ${\ displaystyle q_ {1}, q_ {2}, q_ {3}}$ и соответствующие веса $w 1 = 5, w 2 = 2, w 3 = 3 {\ displaystyle w_ {1} = 5, w_ {2} = 2, w_ {3} = 3}$ ${\ displaystyle w_ {1} = 5, w_ {2} = 2, w_ {3} = 3}$ . Рассмотрим ситуацию, когда это 7 пакетов в первой очереди, A, B, C, D, E, F, G, 3 во второй очереди, U, V, W и 2 в третьей очереди X, Y . Предположим, что пакетов больше нет.

В классическом WRR в первом цикле планировщик сначала выбирает $q 1 {\ displaystyle q_ {1}}$ $q_ {1}$ и передает пять пакетов в начале очереди, A, B, C, D, E (поскольку $w 1 = 5 {\ displaystyle w_ {1} = 5}$ ${\ displaystyle w_ {1} = 5}$ ), то выбирается вторая очередь, $q 2 {\ displaystyle q_ {2}}$ $q_ {2}$ , и передает два пакета в начале очереди, U, V (поскольку $w 2 = 2 {\ displaystyle w_ { 2} = 2}$ ${\ displaystyle w_ {2} = 2}$ ), и, наконец, он выбирает третью очередь, вес которой равен 3, но только два пакета, поэтому он передает X, Y . Сразу после окончания передачи Y начинается второй цикл, и F, G из $q 1 {\ displaystyle q_ {1}}$ $q_ {1}$ передаются, за которыми следует W из $q 2 {\ displaystyle q_ {2}}$ $q_ {2}$ .

При чередовании WRR первый цикл делится на 5 циклов. В первом (r = 1 ) отправляется по одному пакету из каждой очереди (A, U, X ), во втором раунде (r = 2 ), также отправляется другой пакет из каждой очереди (B, V, Y ), в третьем раунде (r = 3 ) только очереди $q 1, q 3 {\ displaystyle q_ {1}, q_ {3}}$ ${\ displaystyle q_ {1}, q_ {3}}$ разрешено отправлять пакет ( $w 1>= r {\ displaystyle w_ {1}>= r}$ $w_{1}>= r$ , $w 2 < r {\displaystyle w_{2}$ ${\ displaystyle w_ {2} <r}$ и $w 3>= r {\ displaystyle w_ {3}>= r}$ $w_{3}>= r$ ), но с $q 3 {\ displaystyle q_ {3}}$ $q_ {3}$ пусто, отправляется только C из $q 1 {\ displaystyle q_ {1}}$ $q_ {1}$ , а в четвертом и пятом раундах отправляется только D, E из $q 1 {\ displaystyle q_ {1}}$ $q_ {1}$ отправляются. Затем запускается второй цикл, в котором отправляются F, W, G .

Планирование задач

Планирование задач или процессов может выполняться в WRR аналогично планированию пакетов: при рассмотрении набора $n {\ displaystyle n}$ $n$ активные задачи, они планируются циклически, каждая задача $τ i {\ displaystyle \ tau _ {i}}$ $\ tau _ {i}$ получает $wi {\ displaystyle w_ {i}}$ $w_ {i}$ квант или срез процессорного времени.

Свойства

Как и циклический алгоритм, взвешенное циклическое планирование простое, легкое в реализации, экономия работы и отсутствие голодания.

При планировании пакетов, если все пакеты имеют одинаковый размер, то WRR является приближением Общий доступ к процессору : очередь $qi {\ displaystyle q_ {i}}$ $q_ {i}$ получит долгосрочную часть пропускной способности, равную $wi ∑ j = 1 nwj {\ displaystyle {\ frac {w_ {i}} {\ sum _ {j = 1} ^ {n} w_ {j} }}}$ ${\ displaystyle {\ frac {w_ {i}} {\ sum _ {j = 1} ^ {n} w_ {j}}}}$ (если все очереди активны), в то время как GPS обслуживает бесконечно малые объемы данных из каждой непустой очереди и предлагает эту часть на любом интервале.

Если в очередях есть пакеты переменной длины, часть полосы пропускания, полученная каждой очередью, зависит не только от весов, но и от размеров пакетов.

Если средний размер пакетов $si {\ displaystyle s_ {i}}$ $s_ {i}$ известен для каждой очереди, $qi {\ displaystyle q_ {i}}$ $q_ {i}$ , каждая очередь получит долгосрочную часть полосы пропускания, равную $si × wi ∑ j = 1 nsj × wj {\ displaystyle {\ frac {s_ {i} \ times w_ {i}} {\ sum _ {j = 1} ^ {n} s_ {j} \ times w_ {j}}}}$ ${\ displaystyle {\ frac {s_ {i} \ times w_ {i}} {\ sum _ {j = 1} ^ {n} s_ {j} \ times w_ {j}}}}$ . Если цель - передать каждой очереди $qi {\ displaystyle q_ {i}}$ $q_ {i}$ часть $ρ i {\ displaystyle \ rho _ {i}}$ $\ rho _ {i}$ емкости ссылки (с $∑ i = 1 n ρ i = 1 {\ displaystyle \ sum _ {i = 1} ^ {n} \ rho _ {i} = 1}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} \ rho _ {i} = 1}$ ), один может установить $wi = ρ isi {\ displaystyle w_ {i} = {\ frac {\ rho _ {i}} {s_ {i}}}}$ ${\ displaystyle w_ {i} = {\ frac {\ rho _ {i}} {s_ {i} }}}$ .

Ограничения и улучшения

WRR для Планирование сетевых пакетов было впервые предложено Катевенисом, Сидиропулосом и Куркубетисом в 1991 году специально для планирования в сетях ATM с использованием пакетов (ячеек) фиксированного размера. Основное ограничение взвешенной циклической организации очередей состоит в том, что она обеспечивает правильный процент полосы пропускания для каждого класса обслуживания, только если все пакеты во всех очередях имеют одинаковый размер или когда средний размер пакета известен заранее. В более общем случае IP-сетей с пакетами переменного размера, для приближения GPS весовые коэффициенты должны быть скорректированы на основе размера пакета. Это требует оценки среднего размера пакета, что затрудняет получение хорошего приближения GPS на практике с WRR.

Круговой алгоритм дефицита - это более поздняя разновидность WRR, которая обеспечивает лучшее приближение GPS без предварительного знания среднего размера пакета каждого соединения. Также были введены более эффективные дисциплины планирования, которые справляются с упомянутыми выше ограничениями (например, взвешенная справедливая организация очереди ).

См. Также

Ссылки