МЕХАНІЗМИ КРУГОВОГО ОБСЛУГОВУВАННЯ ЧЕРГ
Содержание
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 післятретього циклу обслуговування
Планувальник MWRR приступає до третього циклу обслуговуваннячерги 0. Значення лічильника дефіциту збільшується 0+2=2. У результаті обслуговуванняпакета з двох чарунок, що знаходиться на початку черги 0, значення лічильника дефіцитустає рівним 2 — 2=0. MWRR-планувальник припиняє обробку черги 0 і переходить дочерги 1 (рис.4).
Нове значення лічильника дефіциту черги 1 дорівнює- 1+3=2.
У результаті обслуговування пакета з двох чарунок,який знаходиться на початку черги 1, значення лічильника дефіциту стає рівним 2- 2 = 0. Оскільки тепер черга 1 стає порожньою, планувальник алгоритму MWRR приступаєдо обробки черги 0, як показано на рис.4.
У четвертому циклі обслуговування черги 0 значенняїї лічильника дефіциту стає рівним 2. У результаті обслуговування пакета з трьохчарунок, що знаходиться на початку черги 0, значення лічильника дефіциту стає рівним- 1. Оскільки тепер черга 0 стає порожньою, значення її лічильника дефіциту скидаєтьсяв нуль.
2. Модифікований алгоритм кругового обслуговуванняз дефіцитом MDRR
У маршрутизаторах Cisco серії 12000 використовуєтьсямодифікований алгоритм кругового обслуговування з дефіцитом (Modified Deficit RoundRobin, MDRR). Відповідно до DRR-планувальника кожна черга характеризується пов'язанимз нею квантовим значенням (quantum value) — середньою кількістю байтів, що обслуговуютьсяпротягом кожного циклу, — та лічильником дефіциту, початкове значення якого встановлюєтьсярівним квантовому значенню. Кожна непорожня черга обробляється за круговим принципом.Сума розмірів пакетів, які обслуговуються за один цикл, приблизно дорівнює квантовомузначенню черги. Обробка пакетів черги реалізується до тих пір, доки значення лічильникадефіциту залишається більше нуля. У результаті обслуговування кожного пакета значеннялічильника дефіциту черги зменшується на величину, яка дорівнює розміру пакета вбайтах. Коли значення лічильника дефіциту стає менше нуля або рівним нулеві, DRR-планувальникпереходить до обробки наступної черги. Слід зазначити, що в кожному новому циклізначення лічильника дефіциту збільшується на величину квантового значення. Як видно,квантове значення в DRR застосовується з тією ж метою, що і вага в MWRR.
Після обслуговування черги значення її лічильникадефіциту є розміром дебету, який залежить від того, чи було перевищено квантовезначення черги кількістю байтів, які оброблено протягом попереднього циклу. Обсягданих, що будуть оброблені в наступному циклі обслуговування черги, розраховуєтьсяяк різниця квантового значення і лічильника дефіциту.
З метою підвищення ефективності механізму DRR квантовезначення має дорівнювати розмірові в байтах пакета максимального обсягу. Це даєгарантію, що DRR-планувальник завжди обслуговуватиме щонайменше один пакет з кожноїчерги.
Описаний вище узагальнений алгоритм DRR модифікуєтьсяза допомогою додавання так званої черги з малою затримкою (low-latency queue). Відповіднодо алгоритму MDRR усі черги, за винятком черги з малою затримкою, обслуговуютьсяза круговим принципом. Черга з малою затримкою може обслуговуватися в двох режимах:режимі строгого пріоритету і режимі чергування пріоритетів.
У режимі строгого пріоритету (strict priority mode)черга з малою затримкою обслуговується за наявності в ній хоча б одного пакета,що обумовлює мінімально можливу затримку для класу трафіка, який оброблюється задопомогою цієї черги. У той же час слід зазначити, що високопріоритетна черга змалою затримкою здатна на тривалий період часу зайняти всі 100% смуги пропусканняінтерфейса і тим самим «придушити» інші MDRR-черги.
У режимі чергування пріоритетів (alternate prioritymode) черга з малою затримкою обробляється в проміжках між обробкою інших черг.На додаток до черги з малою затримкою алгоритм MDRR підтримує ще сім черг. Припустимо,що черга з малою затримкою має номер 0. Тоді відповідно до режиму пріоритету, щочергується, черги механізму MDRR обслуговуються в такому порядку: 0, 1, 0, 2, 0,3, 0, 4, 0, 5, 0, 6, 0, Режим чергування пріоритетів дозволяє зменшити максимальнузатримку обслуговування черги 0 із суми квантових значень (що було б у випадку традиційногомеханізму кругового обслуговування) до максимального квантового значення серед всіхінших черг.
Розглянемо роботу алгоритму MDRR на прикладі. Припустимо,що алгоритм MDRR використовується для обслуговування трьох черг — черги 2, черги1 і черги 0, — вага яких дорівнює 1, 2 і 1, відповідно (табл.1). Черга 2 є чергоюз малою затримкою, яка обслуговується в режимі пріоритету, що чергується. Схематичнезображення черг та відповідні до них значення лічильників дефіциту подані на рис.5.
Таблиця1 — Вага і квантові значення черг, що обслуговуються за допомогою алгоритму MDRRНомер черги Вага
Квантове значення = вага/>MTU (MTU = 1500 байт) Черга 2 1 1500 Черга 1 2 3000 Черга 0 1 1500
Коли механізм MDRR сконфігуровано на вихідномуінтерфейсі маршрутизатора, як максимальний розмір одиниці передачі інформації (MaximumTransmission Unit, MTU) використовується відповідне значення MTU цього інтерфейса.
Першою обслуговується черга 2. При ініціалізаціїлічильника дефіциту йому присвоюється значення 1500, яке дорівнює квантовому значеннючерги. Черга 2 обслуговується доти, доки відповідне їй значення лічильника дефіцитузалишається більше нуля. Після обслуговування пакета значення лічильника дефіцитучерги 2 зменшується на величину, яка дорівнює розмірові пакета в байтах. Оскількипоточне значення лічильника дефіциту (1500) більше нуля, планувальник MDRR обслуговує500-байтовий пакет, що знаходиться на початку черги 2. Нове значення лічильникадефіциту черги 2 стає рівним 1500 — 500=1000. Оскільки нове значення лічильникадефіциту усе ще більше нуля, планувальник MDRR починає обслуговування наступногоу черзі пакета. У результаті передачі 1500-байтового пакета значення лічильникадефіциту зменшується до 1000 — 1500=-500, після чого MDRR-планувальник переходитьдо обслуговування наступної черги. Стан черг і відповідних їм значень лічильниківдефіциту після закінчення обслуговування черги 2 схематично подано на рис.6.
/>
Рисунок 5 — MDRR — черги і відповідні значеннялічильників дефіциту до початку обслуговування черги 2
/>
Рисунок 6 — Стан черг і відповідних їм значеньлічильників дефіциту після першого циклу обслуговування
Оскільки обслуговування черги 2 здійснюється врежимі чергування пріоритетів MDRR-планувальник переходить до обробки іншої черги,номер якої вибирається відповідно до кругового принципу. Припустимо, що підійшлачерга обслуговування черги 0. При ініціалізації лічильника дефіциту йому присвоюєтьсязначення 1500, яке дорівнює квантовому значенню черги 0. У результаті обслуговування1500-байтового пакета значення лічильника дефіциту зменшується до 1500 — 1500 =0. Відповідно до алгоритму MDRR-планувальник завершує обслуговування черги 0. Станчерг і відповідних їм значень лічильників дефіциту після закінчення обслуговуваннячерги 0 схематично подане на рис.
Оскільки режим чергування пріоритетів припускаєпостійне переключення MDRR-планувальника між чергою з малою затримкою та іншимичергами, наступною обслуговується черга 2. Нове значення лічильника дефіциту стаєрівним — 500+1500=1000. Оскільки значення лічильника дефіциту більше нуля, MDRR-планувальникприступає до обслуговування наступного пакета черги 2.
У результаті передачі 500-байтового пакета значеннялічильника дефіциту зменшується до 500. Незважаючи на те що MDRR-планувальник мігби обслужити як мінімум ще один пакет черги 2, це не є можливим, тому що черга порожня.Тому значення лічильника дефіциту черги 2 скидається в нуль. Оскільки порожня чергане обробляється MDRR-планувальником, значення лічильника дефіциту черги 2 з/>алишається рівним нулеві до постановки в цю чергунаступного пакета. Стан черг і відповідних їм значень лічильників дефіциту післязакінчення обслуговування черги 2 схематично подано на рис.8.
/>
Рисунок 7 — Стан черг і відповідних їм значеньлічильників дефіциту після першого циклу обслуговування черги 0
/>
Рисунок 8 — Стан черг і відповідних їм значеньлічильників дефіциту після другого циклу обслуговування черги 2
Наступною обслуговується черга 1, значення лічильникадефіциту якої встановлюється рівним 3000. MDRR-планувальник передає три пакети зчерги 1, у результаті чого значення її лічильника дефіциту зменшується до 3000- 1500 — 500 — 1500=-500. Стан черг і відповідних їм значень лічильників дефіцитупісля закінчення обслуговування черги 1 схематично подано на рис.9.
У результаті обслуговування двох пакетів черги0 значення її лічильника дефіциту стає рівним 1500-500-1500=-500. Оскільки черга0 стає порожньою, відповідне значення лічильника дефіциту скидається в нуль. Станчерг і відповідних їм значень лічильників дефіциту після закінчення обслуговуваннячерги 0 схематично подано на рис.10.
/>
Рисунок 9 — Стан черг і відповідних їм значеньлічильників дефіциту після першого циклу обслуговування черги 1
/>
Рисунок 10 — Стан черг і відповідних їмзначень лічильників дефіциту після другого циклу обслуговування черги 0
На наступному кроці MDRR-планувальник обробляєостанній пакет черги 1. Оскільки черга 1 стає порожньою, відповідне їй значеннялічильника дефіциту скидається в нуль.
Модифікований алгоритм кругового обслуговуванняз дефіцитом MDRR реалізований в маршрутизаторах Cisco серії 12000. Механізм MDRRможна сконфігурувати для обслуговування або черги вихідного інтерфейса (вихіднийблок маршрутизатора — ТХ), або черги вхідного інтерфейса (вхідний блок маршрутизатора- RX) при функціонуванні в режимі подачі черг комутаційної матриці маршрутизаторана вихідний інтерфейс.
механізм кругове обслуговування черга3. Рекомендації щодо вибору стратегіїчерг
Вибір схеми організації черг є одним з важливихкроків у проектуванні мережі і містить у собі такі етапи.
1. Визначити, чи знаходиться в стані перевантаженняканал зв'язку з глобальною мережею. У тому випадку, якщо перевантаження немає, тонемає й необхідності в додаткових діях. Але якщо спостерігаються періоди значногозавантаження каналу, то виникає потреба в реалізації механізмів розподілу ресурсів.
2. На наступному етапі варто з'ясувати, чи потрібнийстрогий контроль над розподілом трафіка відповідно до пріоритетів і чи є прийнятнимиавтоматичні настройки маршрутизатора. Слід зазначити, що коректне настроювання чергзовсім непроста задача. Для того щоб виконати її з найбільшою ефективністю, адміністратормережі має проаналізувати типи трафіка, що проходять через даний інтерфейс, з'ясувати,як розрізняти різні потоки трафіку, і визначити відносні пріоритети. Крім того,варто пам'ятати про те, що характер трафіка з часом міняється. А це вимагає регулярноговиконання такого аналізу.
3. Стратегіячерг базується на проведеному аналізі трафіка і визначенні відносних його пріоритетів(обговорюється на кроці 2).
4. На останньомукроці потрібно визначити, наскільки виділений трафік чутливий до затримок.
На рис.11 подано алгоритм дій адміністратора мережіз метою вибору типу черги.
/>
Рисунок 11 — Алгоритм вибору типу черги.