Русская Википедия:Взвешенная справедливая очередь
Взвешенная справедливая очередь (Шаблон:Lang-en) — механизм планирования пакетных потоков данных с различными приоритетами. Его целью является регулировать использования одного канала передачи данных несколькими конкурирующими потоками. В данном случае под потоком понимается очередь пакетов данных.
Это обобщение алгоритма Шаблон:Нп2 (FQ). Оба планировщика имеют отдельные FIFO-очереди для каждого потока данных. Так, если канал со скоростью <math>R</math> используется для <math>N</math> потоков, то скорость обработки каждого из них будет <math>R/N</math> при использовании честного планировщика. Честный планировщик с приоритетными коэффициентами позволяет регулировать долю каждого потока. Если имеется <math>N</math> активных потоков, с приоритетами <math>w_1, w_2 ... w_N</math>, то <math>i</math>-й поток будет иметь скорость <math>\frac{Rw_i}{(w_1+w_2+...+w_N)}</math>.
Теория
Каждому пришедшему пакету <math>p_i^k</math> присваивается виртуальное время начала <math>S_i^k</math> и конца обработки <math>F_i^k</math>, где <math>k</math> — это номер пакета, а i — номер потока. Время начала и конца вычисляются по следующим формулам:
- <math>S(k,i) = max(F(k-1,i), V(a(k,i)))</math>
- <math>F(k,i) = S(k,i) + L(k,i)/r(i)</math>, <math>F(0,i) = 0</math>
где <math>a(k,i)</math> и <math>L(k,i)</math> — время прихода и длина пакета соответственно.
<math>V(t)</math> — виртуальная функция времени, которая определяется как <math>dV(t)/dt = \frac{1}{\Sigma r_j}</math>, где j — все активные сессии, r — скорость j-го канала.
Пример
Пусть у нас есть три очереди: первые две с приоритетом 1 и третья имеет приоритет 2. С самого начала мы имеем 1 пакет в первой, два во второй и 5 в третьей. Пусть все пакеты одинакового размера.
<math>V(t)</math> | <math>dV(t)</math> | <math>N_1</math> | <math>S_1</math> | <math>F_1</math> | <math>N_2</math> | <math>S_2</math> | <math>F_2</math> | <math>N_3</math> | <math>S_3</math> | <math>F_3</math> |
---|---|---|---|---|---|---|---|---|---|---|
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
Шаблон:Rq Шаблон:Изолированная статья