Базові алгоритми обслуговування черг (стр. 1 из 3)

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

1. Загальна характеристика розподілу канальних ресурсів

Задача розподілу канальних ресурсів між потоками розв’язується шляхом організації черг і встановленням певного порядку обслуговування поставлених у чергу пакетів. Як було зазначено в лекції 1, порядок обробки поставлених у чергу пакетів визначає частоту їхнього обслуговування, а отже, і кількість канальних ресурсів, які надаються даному потоку.

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

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

Алгоритм обслуговування черг як механізм забезпечення QoS має задовольняти таким вимогам.

1. Алгоритм обслуговування черг із підтримкою QoS повинен мати засіб диференціювання пакетів і засіб визначення рівня обслуговування кожного пакета.

2. Алгоритм має гарантувати якість обслуговування пакетів шляхом розподілення ресурсів для кожного окремого потоку трафіка або за допомогою визначення відносного пріоритету потоків.

3. Алгоритм обслуговування черг із підтримкою QoS має забезпечувати захист і рівномірну обробку всіх потоків трафіка з однаковим пріоритетом (наприклад, трафіка, що доставляється без гарантій).

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

Механізми обслуговування черг можна класифікувати за такими ознаками (рис. 1): реалізований принцип розподілу ресурсів (без розподілу ресурсів, пріоритетний розподіл шляхом застосування однойменного обслуговування, пропорційний розподіл шляхом кругового обслуговування черг і рівномірний розподіл шляхом реалізації максимінної схеми); надання гарантій за будь-якими параметрами мережного з'єднання (у термінах смуги пропускання або гарантованої затримки); принцип формування черг (формування черг за потоками або за класами); режим виконання (розподілений на процесорах VIP-плат або нерозподілений на центральному процесорі маршрутизатора).

Найчастіше в маршрутизаторах і комутаторах застосовуються такі алгоритми обробки черг:

- алгоритм FIFO;

- пріоритетне обслуговування (Priority Queuing, PQ);

- справедливе обслуговування (Fair Queuing, FQ);

- обслуговування на основі класу (Class Based Queuing, CBQ);

- зважене справедливе обслуговування (Weighted Fair Queuing, WFQ);

- зважене справедливе обслуговування на основі класу (Class Based WFQ, CBWFQ);

- обслуговування з малою затримкою (Low Latency Queuing, LLQ);

- зважене кругове обслуговування (Weighted Round-Robin, WRR) і його модифікації;

- кругове обслуговування з дефіцитом (Deficit Round-Robin, DRR) і його модифікації.

Рисунок 1 – Класифікація механізмів обслуговування черг

2. Механізм обслуговування черг FIFO

обслуговування алгоритм черга комутатор

FIFO (First In – First Out, "першим прийшов – першим пішов") є найпростішим механізмом обслуговування черг, відповідно до якого пакети передаються на вихід у тому порядку, в якому вони надійшли на вхід.

Цей механізм є алгоритмом обробки черг за замовчуванням у всіх пристроях з комутацією пакетів. Незаперечною його перевагою є простота реалізації і відсутність потреби в конфігуруванні. Головний недолік – неможливість диференційованої обробки пакетів різних потоків. Усі пакети знаходяться у загальній черзі на рівних правах – і пакети чутливого до затримок мовного трафіка, і пакети нечутливого до затримок, але дуже інтенсивного трафіка резервного копіювання, тривалі пульсації якого можуть надовго затримати мовний пакет. Іншими словами механізм FIFO не здатний забезпечити рівномірне обслуговування потоків трафіка з однаковим пріоритетом і захистити їх від потоків з нерівномірною інтенсивністю, він допускає перевагу потоків високої інтенсивності над всіма іншими потоками трафіка. Отже, черги FIFO необхідні для нормальної роботи мережних пристроїв, але їх недостатньо для підтримки диференційованої якості обслуговування. Черги FIFO за замовчуванням застосовуються для інтерфейса зі швидкістю вище 2 Мбіт/с (наприклад, Ethernet).

3. Механізм пріоритетного обслуговування черг PQ

Механізм пріоритетного обслуговування черг припускає наявність чотирьох вихідних підчерг – підчерги з високим, середнім, звичайним і низьким пріоритетом обслуговування. Належність потоку трафіка до кожної з чотирьох черг визначається мережним адміністратором.Пакети, що знаходяться у черзі з високим пріоритетом обслуговування, передаються першими. Коли ця черга виявляється порожньою, починається передача пакетів наступної за пріоритетом обслуговування черги і т.д. Відзначимо, що передача пакетів черги із середнім пріоритетом обслуговування не почнеться доти, доки не будуть обслуговані всі пакети черги з вищим пріоритетом.Механізм пріоритетного обслуговування черг PQ підтримує класифікацію пакетів у залежності від вхідного інтерфейса, простого або розширеного списку доступу на підставі IP-адреси, розміру пакета і аплікації, що згенерувала цей пакет. Слід зазначити, що некласифікований трафік за замовчуванням належить до черги зі звичайним пріоритетом обслуговування. У межах черги пакети обробляються відповідно до механізму FIFO. Обмежений розмір буферної пам'яті мережного пристрою вимагає, щоб черги пакетів, що очікують обслуговування, мали деяку граничну довжину. Звичайно за замовчуванням усім пріоритетним чергам надаються однакові буфери, але багато пристроїв дозволяють адміністраторові призначати кожній черзі буфер індивідуального розміру. Пріоритетне обслуговування черг забезпечує високу якість обслуговування для пакетів із черги з найвищим пріоритетом. Якщо середня інтенсивність їхнього надходження в пристрій не перевершує пропускної здатності вихідного інтерфейса (і продуктивності внутрішніх блоків самого пристрою), то пакети вищого пріоритету завжди отримують ту пропускну здатність, що їм потрібна. Рівень затримок пакетів з найвищим пріоритетом також мінімальний. Що ж стосується інших класів пріоритетів, то якість їхнього обслуговування буде нижчою, ніж у пакетів найвищого пріоритету, причому рівень зниження заздалегідь передбачити досить важко. Це залежить від інтенсивності трафіка з найвищим пріоритетом.Пріоритетне обслуговування пакетів потрібно в мережах, де передача трафіка, необхідного для розв’язання критично важливих задач, має бути здійснена навіть за умови повного домінування трафіка з найвищим пріоритетом в моменти перевантаження мережі. Тому пріоритетне обслуговування зазвичай застосовується в тому випадку, коли в мережі є один клас трафіка, наприклад, мовний трафік, чуттєвий до затримок, але його інтенсивність невелика, так що його обслуговування не занадто знижує якість передачі пакетів іншого трафіка. Отже, головною перевагою пріоритетного обслуговування є відносна простота в реалізації і висока якість обслуговування трафіка з найвищим пріоритетом. Основні недоліки полягають у такому:

- необхідність ретельного контролю трафіка на етапі доступу в мережу з метою належного надання пріоритету;

- відсутність верхньої межі для кожного з рівнів пріоритету;

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

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 байт.