МЕХАНІЗМИ КРУГОВОГО ОБСЛУГОВУВАННЯ ЧЕРГ

Содержание

1. Зважений алгоритм кругового обслуговування WRR і модифікований алгоритм зваженого кругового обслуговування MWRR

2. Модифікований алгоритм кругового обслуговування з дефіцитом MDRR

3. Рекомендації щодо вибору стратегії черг

1. Зважений алгоритм кругового обслуговування WRR і модифікований алгоритм зваженого кругового обслуговування MWRR

Механізм обслуговування черг має бути максимально наближений до ідеальної моделі планувальника GPS. Механізм кругового обслуговування (Round Robin), що обробляє за цикл один пакет (замість нескінченно малого обсягу даних) з кожної непорожньої черги, є найпростішою реалізацією схеми GPS. В механізмі FQ на основі обчислення порядкового номера пакета імітується робота GPS-сервера, який обслуговує в окремий момент часу 1 байт даних.

Найточніша імітація планувальника GPS досягається в механізмі кругового обслуговування у випадку рівності розміру всіх пакетів. Зважений алгоритм кругового обслуговування (Weighted Round Robin, WRR) є розширенням планувальника кругового обслуговування, відповідно до якого кожному потокові трафіка призначається своя вага. Алгоритм WRR обробляє потік трафіка пропорційно до його ваги. Розглянутий раніше алгоритм CQ можна також розглядати як WRR з додаванням пріоритетної черги.

Найкраще WRR-планувальник узгоджується з механізмом комутації ATM, відповідно до якого пакет подається у вигляді чарунок, а алгоритм WRR використовується для обробки черг, які заповнюються чарунками. По суті, WRR є механізмом кругового обслуговування на основі чарунок, де вага потоку визначає кількість чарунок, які обслуговуються за один цикл. Отже, кожній черзі надається частина смуги пропускання інтерфейса відповідно до ваги потоку трафіка, яка не залежить від розміру пакета.

З метою підтримки пакетів змінного розміру було створено модифікований зважений алгоритм кругового обслуговування (MWRR), що використовує лічильник дефіциту, асоційований з кожною WRR-чергою.

Перед початком обслуговування черг значення відповідних їм лічильників дефіциту встановлюється рівним вазі черги. Обробка пакета починається і продовжується тільки в тому випадку, якщо значення лічильника дефіциту більше нуля. Після обслуговування пакета, що складається з чарунок, значення лічильника дефіциту зменшується на . Коли значення лічильника дефіциту стане менше нуля або рівним нулеві, планувальник переходить до обслуговування наступної черги. У кожному новому циклі значення лічильника дефіциту черги збільшується на вагу черги.

Ефективна ширина смуги пропускання черги - прямо пропорційна її вазі і розраховується за формулою

, (1)

де - ширина смуги пропускання інтерфейса; - загальна кількість активних черг.

Розглянемо роботу алгоритму MWRR на прикладі. Припустимо, що алгоритм MWRR використовується для обслуговування трьох черг (черги з номерами 0, 1,2), вага кожної з яких 2, 3 і 4 відповідно (рис.1).

Кожна черга складається з дев'яти чарунок (рис.1). Чарунки, що є частинами одного пакета, мають однаковий відтінок сірого кольору. Приміром, у черзі 2 знаходяться три пакети, що складаються з двох, трьох і чотирьох чарунок, відповідно.

Рисунок 1 - WRR-черги і відповідні значення їхніх лічильників дефіциту до початку обслуговування

Першою обслуговується черга 0. При ініціалізації лічильника дефіциту присвоюється значення 2, що дорівнює вазі черги. На початку черги 0 знаходиться пакет з чотирьох чарунок. Отже, після обслуговування цього пакета значення лічильника дефіциту дорівнюватиме 2 - 4=-2. Оскільки значення лічильника дефіциту від’ємне, черга 0 не може бути обслугована доти, поки значення лічильника дефіциту не стане більше нуля (рис.2).

Наступною обслуговується черга 1. При ініціалізації лічильника дефіциту йому присвоюється значення 3. У результаті обслуговування пакета з трьох чарунок, що знаходиться на початку черги 1, значення лічильника дефіциту стає рівним 3 - 3=0. Оскільки значення лічильника дефіциту дорівнює нулеві, планувальник алгоритму MWRR приступає до обробки наступної черги (рис.2).

Останньою обслуговується черга 2. При ініціалізації лічильника дефіциту йому присвоюється значення 4. У результаті обслуговування пакета з двох чарунок, що знаходиться на початку черги 2, значення лічильника дефіциту стає рівним 4 - 2=2. Оскільки значення лічильника дефіциту більше нуля, MWRR-планувальник обробляє наступний пакет з трьох чарунок. Після обслуговування цього пакета значення лічильника дефіциту черги 2 стає рівним 2 - 3 =-1, як показано на рис.2. Планувальник MWRR приступає до другого циклу обслуговування черги 0. Значення лічильника дефіциту черги 0, встановлене на першому циклі, дорівнює - 2. У результаті збільшення значення лічильника дефіциту на вагу черги воно стає рівним - 2+2=0. Оскільки значення лічильника дефіциту усе ще не більше нуля, планувальник алгоритму MWRR приступає до обробки наступної черги (рис.3).

Рисунок 2 - Стан черг алгоритму MWWR після першого циклу обслуговування

Рисунок 3 - Стан черги алгоритму MWWR після другого циклу обслуговування

Після першого циклу обслуговування значення лічильника дефіциту черги 1 дорівнювало нулеві. В другому циклі обслуговування значення лічильника дефіциту збільшується на вагу черги і стає рівним 0+3=3.

У результаті обслуговування пакета з чотирьох чарунок, що знаходиться на початку черги 1, значення лічильника дефіциту стає рівним 3 - 4 = - 1, як показано на рис.3.

У другому циклі обслуговування значення лічильника дефіциту черги 2 збільшується на її вагу і стає рівним - 1+4=3. У результаті обслуговування пакета з чотирьох чарунок, що знаходиться на початку черги 2, значення лічильника дефіциту стає рівним 3 - 4 = - 1. Оскільки тепер черга 2 стає порожньою, значення її лічильника дефіциту скидається в нуль (рис.3).

Рисунок 4 - Стан черги алгоритму MWWR після третього циклу обслуговування

--> ЧИТАТЬ ПОЛНОСТЬЮ <--