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

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

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

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

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

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

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

Алгоритм [ править ]

В WFQ планировщик, обрабатывающий $N$ потоков, настроен с одним весом для каждого потока. Тогда поток номеров достигнет средней скорости передачи данных , где - скорость соединения. Планировщик WFQ, у которого все веса равны, является планировщиком FQ. $w_{i}$ $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, он может быть впереди произвольно. Наихудший случай справедливой Weighted Fair Queuing (WF2Q) фиксирует его путем добавления виртуального начала обслуживания к каждому пакету, и выбирает пакет только если его виртуальный старт обслуживания не меньше , чем текущее время. ^[3]
Выбор очереди с минимальным виртуальным временем завершения может быть затруднен на скорости передачи данных. Затем были определены другие приближения GPS с меньшей сложностью, такие как циклический поиск дефицита .

История [ править ]

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

См. Также [ править ]

Ссылки [ править ]

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

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

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

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

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

[1]