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

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

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

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

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

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

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

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

Алгоритм

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

Как и все планировщики с честной очередностью, каждый поток защищен от других, и можно доказать, что если поток данных ограничен дырявым ведром , то можно гарантировать ограничение сквозной задержки. ^[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, он может быть произвольно впереди. Worst-case Fair Weighted Fair Queueing (WF2Q) исправляет это, добавляя виртуальное начало обслуживания к каждому пакету и выбирает пакет, только если его виртуальное начало обслуживания не меньше текущего времени. ^[3]
Выбор очереди с минимальным виртуальным временем финиша может быть трудно реализовать на скорости провода. Затем были определены другие приближения GPS с меньшей сложностью, такие как дефицитный циклический робин .

История

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

Смотрите также

Ссылки

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

[GPS-1] Parekh, AK; Gallager, RG (1993). "Обобщенный подход к разделению процессоров для управления потоками в сетях с интегрированными службами: случай с одним узлом" (PDF) . IEEE/ACM Transactions on Networking . 1 (3): 344. doi :10.1109/90.234856. S2CID 52808341.

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

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

[FQ-4] Демерс, А.; Кешав, С.; Шенкер, С. (1989). «Анализ и моделирование алгоритма справедливой очереди». ACM SIGCOMM Computer Communication Review . 19 (4): 1. doi : 10.1145/75247.75248 .