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

редактировать

Алгоритм сетевого планирования

Справедливая организация взвешенных очередей (WFQ ) алгоритм сетевого планирования. WFQ является как пакетной реализацией политики обобщенного совместного использования процессора (GPS), так и естественным расширением справедливой организации очередей (FQ В то время как FQ разделяет пропускную способность канала в равных частях, WFQ позволяет планировщикам определять для каждого потока, какая часть пропускной способности будет предоставлена.

Взвешенная справедливая организация очередей также известна как посылка GPS (PGPS или P-GPS), поскольку он аппроксимирует обобщенное совместное использование процессора «с точностью до одного времени передачи пакета, независимо от шаблонов прибытия».

Содержание

1 Параметризация и справедливость
2 Алгоритм
3 WFQ как GPS приближение
4 История
5 См. также
6 Ссылки

Параметризация и справедливость

Как и в других алгоритмах планирования, подобных GPS, выбор весов остается на усмотрение администратора сети. Не существует однозначного определения того, что «справедливо» (см. Справедливая организация очереди § Справедливость для дальнейшего обсуждения).

Путем динамического регулирования весов WFQ, WFQ можно использовать для управления качеством обслуживания, например, для достижения гарантированной скорости передачи данных.

Может быть пропорционально справедливое поведение достигается установкой весов на $wi = 1 / ci {\ displaystyle w_ {i} = 1 / c_ {i}}$ $w_ {i} = 1 / c_ {i}$ , где $ci {\ displaystyle c_ {i}}$ $c_ {i}$ - стоимость одного бита данных потока данных $i {\ displaystyle i}$ $i$ . Например, в сотовых сетях с расширенным спектром CDMA стоимостью может быть требуемая энергия (уровень помех), а в системах с динамическим распределением каналов стоимостью может быть количество ближайших базовых станций. станции станций, которые не могут использовать один и тот же частотный канал, чтобы избежать помех в совмещенном канале.

Алгоритм

В WFQ планировщик, обрабатывающий N потоков, настроен с одним весом $w i {\ displaystyle w_ {i}}$ $w_ {i}$ для каждого потока. Тогда поток числа $i {\ displaystyle i}$ $i$ достигнет средней скорости передачи данных $wi (w 1 + w 2 +... + w N) R {\ displaystyle {\ frac {w_ {i}} {(w_ {1} + w_ {2} +... + w_ {N})}} R}$ ${\ frac {w_ {i}} {(w_ {1 } + w_ {2} +... + w_ {N})}} R$ , где $R {\ displaystyle R }$ $R$ - скорость ссылки. Планировщик WFQ, у которого все веса равны, является планировщиком FQ.

Как и все планировщики справедливой организации очередей, каждый поток защищен от других, и можно доказать, что если поток данных ограничен дырявым ведром, ограничение сквозной задержки может быть гарантирован.

Алгоритм WFQ очень похож на алгоритм FQ. Для каждого пакета будет вычислена виртуальная теоретическая дата отправления, определяемая как дата отправления, если планировщик был идеальным планировщиком GPS. Затем каждый раз, когда выходной канал бездействует, для передачи выбирается пакет с наименьшей датой.

Псевдокод можно получить просто из одного из FQ, заменив вычисление виртуального времени отправления на

packet.virFinish = virStart + packet.size / Ri

с $R i = wi (w 1 + w 2 +... + W N) R {\ displaystyle R_ {i} = {\ frac {w_ {i}} {(w_ {1} + w_ {2} +... + w_ {N})}} R}$ ${\ displaystyle R_ {i} = {\ frac {w_ {i}} {(w_ {1} + w_ {2} +... + w_ {N})}} R}$ .

WFQ как приближение GPS

WFQ под названием PGPS был разработан как "отличный приближение к GPS ", и было доказано, что он аппроксимирует GPS" с точностью до времени передачи одного пакета, независимо от шаблонов прибытия ".

Поскольку реализация WFQ аналогична справедливой организации очереди, он имеет такую же сложность O (log (n)), где n - количество потоков. Эта сложность возникает из-за необходимости выбирать очередь с наименьшим виртуальным временем завершения каждый раз при отправке пакета.

После WFQ было определено несколько других реализаций GPS.

Даже если WFQ опаздывает не более чем на "один пакет". идеальная политика GPS, она может быть сколь угодно впереди. Справедливая организация очереди наихудшего случая (WF2Q) исправляет это, добавляя виртуальный запуск службы к каждому пакету, и выбирает пакет только в том случае, если его виртуальный запуск службы не меньше текущего времени.
выбор очереди с минимальным виртуальным временем завершения может быть затруднен на скорости передачи данных. Затем были определены другие приближения GPS с меньшей сложностью, такие как циклический перебор дефицита.

История

Введение параметров для распределения полосы пропускания произвольным образом, упомянутых в конце как возможное расширение до FQ. Термин взвешенный впервые появляется в.

См. Также

Ссылки