Взвешенная справедливая очередь

Взвешенная справедливая очередь (англ. Weighted fair queuing, WFQ) — механизм планирования пакетных потоков данных с различными приоритетами. Его целью является регулировать использования одного канала передачи данных несколькими конкурирующими потоками. В данном случае под потоком понимается очередь пакетов данных.

Это обобщение алгоритма честных планировщиков (англ. Fair Queuing) (FQ). Оба планировщика имеют отдельные FIFO-очереди для каждого потока данных. Так, если канал со скоростью R {displaystyle R} используется для N {displaystyle N} потоков, то скорость обработки каждого из них будет R / N {displaystyle R/N} при использовании честного планировщика. Честный планировщик с приоритетными коэффициентами позволяет регулировать долю каждого потока. Если имеется N {displaystyle N} активных потоков, с приоритетами w 1 , w 2 . . . w N {displaystyle w_{1},w_{2}...w_{N}} , то i {displaystyle i} -й поток будет иметь скорость R w i ( w 1 + w 2 + . . . + w N ) {displaystyle {frac {Rw_{i}}{(w_{1}+w_{2}+...+w_{N})}}} .

Теория

Каждому пришедшему пакету p i k {displaystyle p_{i}^{k}} присваивается виртуальное время начала S i k {displaystyle S_{i}^{k}} и конца обработки F i k {displaystyle F_{i}^{k}} , где k {displaystyle k} — это номер пакета, а i — номер потока. Время начала и конца вычисляются по следующим формулам:

S ( k , i ) = m a x ( F ( k − 1 , i ) , V ( a ( k , i ) ) ) {displaystyle S(k,i)=max(F(k-1,i),V(a(k,i)))} F ( k , i ) = S ( k , i ) + L ( k , i ) / r ( i ) {displaystyle F(k,i)=S(k,i)+L(k,i)/r(i)} , F ( 0 , i ) = 0 {displaystyle F(0,i)=0}

где a ( k , i ) {displaystyle a(k,i)} и L ( k , i ) {displaystyle L(k,i)} — время прихода и длина пакета соответственно.

V ( t ) {displaystyle V(t)} — виртуальная функция времени, которая определяется как d V ( t ) / d t = 1 Σ r j {displaystyle dV(t)/dt={frac {1}{Sigma r_{j}}}} , где j — все активные сессии, r — скорость j-го канала.

Пример

Пусть у нас есть три очереди: первые две с приоритетом 1 и третья имеет приоритет 2. С самого начала мы имеем 1 пакет в первой, два во второй и 5 в третьей. Пусть все пакеты одинакового размера.