Честная очередь с весовыми коэффициентами

Честная очередь с весовыми коэффициентами

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

Это обобщение алгоритма честных планировщиков (англ. Fair Queuing) (FQ). Оба планировщика имеют отдельные FIFO-очереди для каждого потока данных. Так, если канал со скоростью R используется для N потоков, то скорость обработки каждого из них будет R / N при использовании честного планировщика. Честный планировщик с приоритетными коэффициентами позволяет регулировать долю каждого потока. Если имеется N активных потоков, с приоритетами w1,w2...wN, то 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 — все активные сессии.

Пример

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

V(t) dV(t) N1 S1 F1 N2 S2 F2 N3 S3 F3
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

Ссылки



Wikimedia Foundation. 2010.

Смотреть что такое "Честная очередь с весовыми коэффициентами" в других словарях:

  • WFQ — Честная очередь с весовыми коэффициентами (WFQ) (от англ. Weighted Fair Queuing) это механизм планирования пакетных потоков данных с различными приоритетами. Его целью является регулировать использования одного канала передачи данных несколькими… …   Википедия

  • Wfq — Честная очередь с весовыми коэффициентами (WFQ) (от англ. Weighted Fair Queuing) это механизм планирования пакетных потоков данных с различными приоритетами. Его целью является регулировать использования одного канала передачи данных несколькими… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»