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

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

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

Теория

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

$S(k,i)=max(F(k-1,i),V(a(k,i)))$

$F(k,i)=S(k,i)+L(k,i)/r(i)$, $F(0,i)=0$

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

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

Пример

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

$V(t)$	$dV(t)$	$N_{1}$	$S_{1}$	$F_{1}$	$N_{2}$	$S_{2}$	$F_{2}$	$N_{3}$	$S_{3}$	$F_{3}$
0	1/4	1	0	1	2	0	1	5	0	1/2
1/4	1/4	1	0	1	2	0	1	4	0	1
1/2	1/4	1	0	1	2	0	1	3	0	1.5
3/4	1/4	1	0	1	1	0	1	3	0	1.5
1	1/3	0	—	—	1	1	2	3	1	1.5
1 1/3	1/3	0	—	—	1	1	2	2	1	2
1 2/3	1/3	0	—	—	1	1	2	1	1	2.5
1 2/3	1/3	0	—	—	0	—	—	1	1	2.5

Ссылки

• https://web.archive.org/web/20091230065403/http://www.sics.se/~ianm/WFQ/wfq_descrip/
• http://www.mathcs.emory.edu/~cheung/Courses/558/Syllabus/11-Fairness/WFQ.html