Взвешенная справедливая очередь () — механизм планирования пакетных потоков данных с различными приоритетами. Его целью является регулировать использования одного канала передачи данных несколькими конкурирующими потоками. В данном случае под потоком понимается очередь пакетов данных.
Это обобщение алгоритма (FQ). Оба планировщика имеют отдельные FIFO-очереди для каждого потока данных. Так, если канал со скоростью используется для потоков, то скорость обработки каждого из них будет при использовании честного планировщика. Честный планировщик с приоритетными коэффициентами позволяет регулировать долю каждого потока. Если имеется активных потоков, с приоритетами , то -й поток будет иметь скорость .
Теория Каждому пришедшему пакету присваивается виртуальное время начала и конца обработки , где — это номер пакета, а i — номер потока. Время начала и конца вычисляются по следующим формулам:
,
где и — время прихода и длина пакета соответственно.
— виртуальная функция времени, которая определяется как , где j — все активные сессии, r — скорость j-го канала.
Пример Пусть у нас есть три очереди: первые две с приоритетом 1 и третья имеет приоритет 2. С самого начала мы имеем 1 пакет в первой, два во второй и 5 в третьей. Пусть все пакеты одинакового размера.
01/4 101 201 501/21/41/4 101 201 4011/21/4 101 201 301.53/41/4 101 101 301.511/3 0—— 112 311.51 1/31/3 0—— 112 2121 2/31/3 0—— 112 112.51 2/31/3 0—— 0—— 112.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
Категория:Алгоритмы маршрутизации