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

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

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

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

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

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

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

Алгоритм

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

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

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

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

packet.virFinish = virStart + packet.size / Ri

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

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

WFQ под названием PGPS был разработан как «отличное приближение к GPS», и было доказано, что он приближает GPS «с точностью до времени передачи одного пакета, независимо от схемы поступления». ^[1]

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

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

Даже если WFQ отстает не более чем на «один пакет» относительно идеальной политики GPS, он может быть сколь угодно впереди. Функция Fair Weighted Fair Queuing (WF2Q) для наихудшего случая исправляет это, добавляя к каждому пакету виртуальное начало обслуживания и выбирает пакет только в том случае, если его виртуальное начало обслуживания не меньше текущего времени. ^[3]
Выбор очереди с минимальным виртуальным временем завершения может оказаться затруднительным при скорости передачи данных. Затем были определены другие приближения GPS, менее сложные, например, циклический алгоритм с дефицитом .

История

Введение параметров для произвольного разделения полосы пропускания упомянуто в конце ^[4] как возможное расширение FQ. Термин «взвешенный» впервые появляется в . ^[1]

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с Парех, АК; Галлагер, Р.Г. (1993). «Обобщенный подход к совместному использованию процессоров для управления потоками в сетях с интеграцией услуг: случай с одним узлом» (PDF) . Транзакции IEEE/ACM в сети . 1 (3): 344. дои : 10.1109/90.234856 . S2CID 52808341 .
^ Стилиадис, Д.; Варма, А. (1998). «Серверы с задержкой: общая модель анализа алгоритмов планирования трафика» (PDF) . Транзакции IEEE/ACM в сети . 6 (5): 611. дои : 10.1109/90.731196 .
^ Беннетт, JCR; Хуэй Чжан (1996). «WF/sup 2/Q: справедливо взвешенная справедливая очередь в наихудшем случае». Труды IEEE INFOCOM '96. Конференция по компьютерным коммуникациям . Том. 1. п. 120. дои : 10.1109/INFCOM.1996.497885 . ISBN 978-0-8186-7293-4 . S2CID 17558577 .
^ Демерс, А.; Кешав, С.; Шенкер, С. (1989). «Анализ и моделирование справедливого алгоритма организации очередей» . Обзор компьютерных коммуникаций ACM SIGCOMM . 19 (4): 1. дои : 10.1145/75247.75248 .

[GPS-1] Перейти обратно: ^а ^б ^с Парех, АК; Галлагер, Р.Г. (1993). «Обобщенный подход к совместному использованию процессоров для управления потоками в сетях с интеграцией услуг: случай с одним узлом» (PDF) . Транзакции IEEE/ACM в сети . 1 (3): 344. дои : 10.1109/90.234856 . S2CID 52808341 .

[2] Стилиадис, Д.; Варма, А. (1998). «Серверы с задержкой: общая модель анализа алгоритмов планирования трафика» (PDF) . Транзакции IEEE/ACM в сети . 6 (5): 611. дои : 10.1109/90.731196 .

[WF2Q-3] Беннетт, JCR; Хуэй Чжан (1996). «WF/sup 2/Q: справедливо взвешенная справедливая очередь в наихудшем случае». Труды IEEE INFOCOM '96. Конференция по компьютерным коммуникациям . Том. 1. п. 120. дои : 10.1109/INFCOM.1996.497885 . ISBN 978-0-8186-7293-4 . S2CID 17558577 .

[FQ-4] Демерс, А.; Кешав, С.; Шенкер, С. (1989). «Анализ и моделирование справедливого алгоритма организации очередей» . Обзор компьютерных коммуникаций ACM SIGCOMM . 19 (4): 1. дои : 10.1145/75247.75248 .

[1]

[2]

[3]

[4]