Реферат: Базові алгоритми обслуговування черг

- високий ризик подавлення низькопріоритних потоків потоками з найвищим пріоритетом.

4 . Зважені черги, що настроюються

Механізм CQ (Custom Queuing, CQ, "черга, що настроюється" або "звичайна черга") надає адміністратору можливість вручну задати розподіл ресурсів, тобто розподілити смугу пропускання. Іноді CQ називають також механізмом замовленого резервування ресурсів. Механізм CQ обробляє кожну непорожню чергу в режимі кругового обслуговування (Round Robin), усякий раз передаючи з цієї черги певну кількість пакетів, яка додатково настроюється. Замовлене обслуговування черг дозволяє гарантувати надання певної частини смуги пропускання трафіка, необхідному для виконання критично важливих задач, у той же час не забуваючи і про інший трафік мережі. Механізм замовленого обслуговування черг CQ підтримує класифікацію пакетів у залежності від вхідного інтерфейса, простого або розширеного списку доступу на підставі IP-адреси, розміру пакета та аплікації, що згенерувало цей пакет. Відповідно до механізму CQ трафік можна розподілити за 16 чергами (рис. 2). Крім цього, існує додаткова нульова системна черга, яка призначена виключно для обробки високопріоритетних пакетів, таких, як пакети підтримки з'єднання і управляючих пакетів. Ця черга є пріоритетною і її пакети передаються першими. Трафік користувачів не може оброблятися в системній черзі.

Рисунок 2 – Механізм замовленого обслуговування черг CQ

У рамках CQ черги 1–16 обслуговуються за круговим принципом, починаючи з першої. З кожною чергою пов'язаний свій лічильник байт (Byte Count, BC), який визначає кількість байтів, що має бути передана з цієї черги, перш ніж перейти до наступної. Пакети з черги передаються доти, поки не перевищиться значення лічильника байт або черга не виявиться порожньою. Після цього система переходить до наступної непорожньої черги. Відзначимо, що якщо значення лічильника байт було перевищено, пакет, що передається в поточний момент часу, передається повністю. Наприклад, якщо значення лічильника байтів дорівнюватиме 100, а розмір пакета –1024 байта, то щораз при обслуговуванні даної черги маршрутизатор передаватиме 1024, а не 100 байт.

Припустимо, що розмір пакетів трьох різних протоколів дорівнює 500, 300 і 100 байт відповідно. Для того, щоб рівномірно розподілити смугу пропущення між трьома протоколами, ви можете спробувати встановити значення лічильника байтів для кожної черги рівним 200. Слід зазначити, що подібне рішення, проте, не приведе до розподілу смуги пропускання в пропорції 33/33/33. Коли маршрутизатор обслуговує першу чергу, він передає щораз 500-байтовий пакет інформації; другу чергу – 300-байтовий пакет; третю чергу –два 100-байтових пакета. Отже, дійсний розподіл смуги пропускання здійснюється в пропорції 50/30/20. До такого непередбачуваного результату призвело занадто мале значення лічильника байтів.

Насправді досить велике значення лічильників байтів також може призвести до досить небажаного розподілу смуги пропускання. Якщо всім трьом чергам надати значення лічильника байтів, яке дорівнює 10 Кбайт, то, незважаючи на те, що пакети кожного з протоколів обслуговуватимуться швидко в момент обробки черги, відповідної цьому протоколові, може пройти досить багато часу, перш ніж ця черга обслуговуватимуться знову. У розглянутому нами випадку одним з найбільш оптимальних рішень є установка значень лічильників байтів черг таким, що дорівнюють 500, 600 і 500 байт відповідно, що приведе до розподілу смуги пропускання в пропорції 31:38:31.

Отже, задача розподілу смуги пропускання в заданих пропорціях між декількома потоками зводиться до визначення коректного значення лічильника байтів. Для розрахунку такого значення лічильника байтів BC пропонується такий алгоритм.

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

Крок 1. Розраховуються допоміжні змінні , , .

Крок 2. Отримані значення , , нормалізуються й округляються у більший бік до найближчого цілого числа

,

, .

Крок 3. Розраховуються значення лічильників байтів

, , .

Крок 4. Розраховується розподіл смуги між чергами, який забезпечується отриманими значеннями лічильників байтів , , :

,

де – загальна кількість черг. У даному прикладі =3.

Крок Якщо отриманий розподіл значно відхиляється від заданого (), то необхідно повернутися до кроку 2 і помножити коефіцієнти пропорції кількості пакетів з кожної черги, що мають передаватися за один раз, , , (до операції округлення) на деяке спеціальне число. Це число підбирається, виходячи з міркувань максимального наближення коефіцієнтів пропорцій до цілих чисел, хоча воно не обов'язково має бути цілим.

5 . Алгоритм організації черг на основі класу CBQ

Алгоритм CBQ (Class-Based Queuing) забезпечує ієрархічний розподіл ресурсів і цікавий у першу чергу ієрархічним підходом в організації черг.

У рамках CBQ смуга пропускання каналу поділяється між декількома класами трафіка в заздалегідь заданих співвідношеннях, причому кожному з класів у період перевантаження гарантується певна частка загальної смуги. За відсутності перевантаження смугу пропускання, яку виділено для одного класу трафіка і яка не використовується ним цілком, можна розділити між іншими класами, інтенсивність надходження яких перевищує виділену їм смугу. У рамках CBQ використовується два планувальника: загальний планувальник (general scheduler) і планувальник розподілу ресурсів (link-sharing scheduler), між якими проводиться строге розмежування (рис. 3).

Рисунок 3 – Механізм CBQ

Вхідний трафік класифікується і розділяється на кілька черг відповідно до заздалегідь заданих правил фільтрації. Загальний планувальник (як правило, це WRR) визначає, з якої черги обслуговуватиметься наступний пакет. Черга вибирається виходячи з того, щоб гарантувати кожному класу трафіка щонайменше задану частку від сумарної пропускної здатності каналу (гарантована смуга). У рамках окремих черг використовується механізм FIFO.

Вихідний трафік контролюється шляхом оцінки часу між сусідніми пакетами одного класу трафіка. На підставі цієї інформації трафік класифікується як такий, що перевищує ліміт (over-limit), як такий, що укладається в ліміт (under-limit) або як такий, що залишився (at-limit). Трафік вважається як таким, що перевищує ліміт, якщо смуга, яку він використовує більше, ніж йому гарантується, відповідно трафік є таким, що укладається в ліміт, якщо він використовує смугу менше йому гарантованої.

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

Як уже відзначалося вище, у CBQ застосовується ієрархічний підхід до розподілу ресурсів (hierarchical link-sharing). Для окремого класу трафіка в CBQ створюється своя черга, причому існують різні варіанти побудови критеріїв класифікації, наприклад, класифікація може базуватися на аплікації, яка згенерувала пакет, або на адресах відправника й одержувача. Приклади відповідних схем поділу ресурсів наведені на рис. 4. На рис. 4 для кожного класу трафіка зазначена частка сумарної смуги пропускання, гарантована даному класові в умовах перевантаження. Виділення якому-небудь класові 0% означає, що в період перевантаження даному класові не гарантується передача.