Механiзми кругового обслуговування черг

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

Содержание

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

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

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

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

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

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

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

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

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

, (1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нове значення лiчильника дефiциту черги 1 дорiвнюi - 1+3=2.

У результатi обслуговування пакета з двох чарунок, який знаходиться на початку черги 1, значення лiчильника дефiциту стаi рiвним 2 - 2 = 0. Оскiльки тепер черга 1 стаi порожньою, планувальник алгоритму MWRR приступаi до обробки черги 0, як показано на рис.4.

У четвертому циклi обслуговування черги 0 значення ii лiчильника дефiциту стаi рiвним 2. У результатi обслуговування пакета з трьох чарунок, що знаходиться на початку черги 0, значення лiчильника дефiциту стаi рiвним - 1. Оскiльки тепер черга 0 стаi порожньою, значення ii лiчильника дефiциту скидаiться в нуль.

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

У маршрутизаторах Cisco серii 12000 використовуiться модифiкований алгоритм кругового обслуговування з дефiцитом (Modified Deficit Round Robin, MDRR). Вiдповiдно до DRR-планувальника кожна черга характеризуiться пов'язаним з нею квантовим значенням (quantum value) - середньою кiлькiстю байтiв, що обслуговуються протягом кожного циклу, - та лiчильником дефiциту, початкове значення якого встановлюiться рiвним квантовому значенню. Кожна непорожня черга обробляiться за круговим принципом. Сума розмiрiв пакетiв, якi обслуговуються за один цикл, приблизно дорiвнюi квантовому значенню черги. Обробка пакетiв черги реалiзуiться до тих пiр, доки значення лiчильника дефiциту залишаiться бiльше нуля. У результатi обслуговування кожного пакета значення лiчильника дефiциту черги зменшуiться на величину, яка дорiвнюi розмiру пакета в байтах. Коли значення лiчильника дефiциту стаi менше нуля або рiвним нулевi, DRR-планувальник переходить до обробки наступноi черги. Слiд зазначити, що в кожному новому циклi значення лiчильника дефiциту збiльшуiться на величину квантового значення. Як видно, квантове значення в DRR застосовуiться з тiiю ж метою, що i вага в MWRR.

Пiсля обслуговування черги значення ii лiчильника дефiциту i розмiром дебету, який залежить вiд того, чи було перевищено квантове значення черги кiлькiстю байтiв, якi оброблено протягом попереднього циклу. Обсяг даних, що будуть обробленi в наступному циклi обслуговування черги, розраховуiться як рiзниця квантового значення i лiчильника дефiциту.

З метою пiдвищення ефективностi механiзму DRR квантове значення маi дорiвнювати розмiровi в байтах пакета максимального обсягу. Це даi гарантiю, що DRR-планувальник завжди обслуговуватиме щонайменше один пакет з кожноi черги.

Описаний вище узагальнений алгоритм DRR модифiкуiться за допомогою додавання так званоi черги з малою затримкою (low-latency queue). Вiдповiдно до алгоритму MDRR усi черги, за винятком черги з малою затримкою, обслуговуються за круговим принципом. Черга з малою затримкою може обслуговуватися в двох режимах: режимi строгого прiоритету i режимi чергування прiоритетiв.

У режимi строгого прiоритету (strict priority mode) черга з малою затримкою обслуговуiться за наявностi в нiй хоча б одного пакета, що обумовлюi мiнiмально можливу затримку для класу трафiка, який оброблюiться за допомогою цiii черги. У той же час слiд зазначити, що високопрiоритетна черга з малою затримкою здатна на тривалий перiод часу зайняти всi 100% смуги пропускання iнтерфейса i тим самим "придушити" iншi MDRR-черги.

У режимi чергування прiоритетiв (alternate priority mode) черга з малою затримкою обробляiться в промiжках мiж обробкою iнших черг. На додаток до черги з малою затримкою алгоритм MDRR пiдтримуi ще сiм черг. Припустимо, що черга з малою затримкою маi номер 0. Тодi вiдповiдно до режиму прiоритету, що чергуiться, черги механiзму MDRR обслуговуються в такому порядку: 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0,Режим чергування прiоритетiв дозволяi зменшити максимальну затримку обслуговування черги 0 iз суми квантових значень (що було б у випадку традицiйного механiзму кругового обслуговування) до максимального квантового значення серед всiх iнших черг.

Розглянемо роботу алгоритму MDRR на прикладi. Припустимо, що алгоритм MDRR використовуiться для обслуговування трьох черг - черги 2, черги 1 i черги 0, - вага яких дорiвнюi 1, 2 i 1, вiдповiдно (табл.1). Черга 2 i чергою з малою затримкою, яка обслуговуiться в режимi прiоритету, що чергуiться. Схематичне зображення черг та вiдповiднi до них значення лiчильникiв дефiциту поданi на рис.5.

Таблиця 1 - Вага i квантовi значення черг, що обслуговуються за допомогою алгоритму MDRR

Номер черги	Вага	Квантове значення = вага MTU (MTU = 1500 байт)
Черга 2	1	1500
Черга 1	2	3000
Черга 0	1	1500

Вместе с этим смотрят:

GPS-навигация

IP-телефония. Особенности цифровой офисной связи

РЖсторiя звтАЩязку та його розвиток

Автоматика, телемеханика и связь

Анализ режимов автоматического управления