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

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

Теория

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

${\displaystyle S(k,i)=max(F(k-1,i),V(a(k,i)))}$

${\displaystyle F(k,i)=S(k,i)+L(k,i)/r(i)}$ , ${\displaystyle F(0,i)=0}$

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

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

Пример

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

${\displaystyle V(t)}$	${\displaystyle dV(t)}$	${\displaystyle N_{1}}$	${\displaystyle S_{1}}$	${\displaystyle F_{1}}$	${\displaystyle N_{2}}$	${\displaystyle S_{2}}$	${\displaystyle F_{2}}$	${\displaystyle N_{3}}$	${\displaystyle S_{3}}$	${\displaystyle 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

Ссылки

На эту статью не ссылаются другие статьи Википедии . Пожалуйста, установите ссылки в соответствии с принятыми рекомендациями .