Зважений алгоритм

Размещено на http://www.allbest.ru/

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

ПРІОРИТЕТІВ ТА КЛАСІВ

1.Зважений алгоритм рівномірного обслуговування черг на основі потоку (Flow-Based WFQ)

Алгоритм FQ розглядає всі потоки як такі, що мають рівні пріоритети, однак на практиці потоки такими не є. Існують потоки, яким при обслуговуванні має віддаватися перевага. З метою урахування різних пріоритетів потоків алгоритм FQ був модифікований шляхом уведення ваги потоку, пропорційно до якої і надаватимуться ресурси. Таке розширення алгоритму FQ одержало назву алгоритму зваженого рівномірного обслуговування черг на основі потоку (Flow-Based WFQ). Відповідно до механізму WFQ вага пакета визначається на підставі значення поля IP-пріоритету в заголовку пакета:

, (1)

де - значення поля IP-пріоритету в заголовку пакета.

В операційних системах IOS Cisco версії 12.0(5)Т і вище WFQ-вага потоку помножується на 8. Отже, WFQ-вага трафіка, переданого без гарантій (IP-пріоритет 0), дорівнює 4096·8=32768, а формула для розрахунку ваги пакета приймає вигляд:

. (2)

Алгоритм WFQ базується на обчисленні порядкового номера пакета і використовує для цього два параметри: розмір пакета в байтах і вагу пакета . Порядковий номер пакета дорівнює добутку його розміру в байтах і ваги пакета:

.

Слід зазначити, що пряма відповідність між побайтовим планувальником кругового обслуговування й алгоритмом FQ зникає в алгоритмі WFQ, оскільки перед обчисленням порядкового номера пакета розмір пакета збільшується на його вагу. Іншими словами, відповідно до алгоритму WFQ порядковий номер пакета визначає відносне знаходження пакета в WFQ-планувальнику, а лічильник циклів - порядковий номер останнього пакета, який обслугований WFQ- планувальником.

Припустимо, що пакети потоку А мають пріоритет 5, а пакети потоків В і С - пріоритет 0. Відповідно до алгоритму WFQ пакетам потоку А призначається вага 683, а пакетам потоків В і С - вага 409 Усі параметри потоків, розглянутих у даному прикладі, наведені в табл. 1. На момент надходження першого пакета (А1) значення лічильника циклів дорівнювало 100.

Таблиця 1 - Приклад роботи алгоритму зваженого рівномірного обслуговування черг WFQ на основі потоку

Порядковий номер пакета A1 обчислюється за формулою (1):

(1)

алгоритм процесор маршрутизатор

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

Для пасивного потоку трафіка і складає 100+(683х128)=87524. Порядкові номери пакетів А2 і A3 будуть розраховуватися вже з урахуванням їхньої належності до активного потоку і складають 87524+(683х128)=174948 і 174948+(683х128)=262372 відповідно. Для пакетів В1 і С1, використовуючи формулу (1) для пасивного потоку, одержимо 100+(4096х64)=262244 і 100+(4096х32)=131172 відповідно. Отже, планувальник WFQ обслуговує отримані пакети в порядку А1, С1, А2, В1, A3, як показано на рис. 1.

Якщо пакети А4 і D1 (новий потік із пріоритетом 0 і розміром пакета
32 байта) будуть отримані відразу після обробки планувальником WFQ пакета А1, їм будуть призначені порядкові номери 349796=((683х128)+262372) і 218596=((4096х32)+87524), відповідно. Тепер планувальник WFQ обслуговуватиме пакети, що залишилися, так: С1, А2, D1, В1, A3 і А4 (рис. 2).

Рисунок 1 - Ілюстрація роботи алгоритму зваженого рівномірного

обслуговування черг (WFQ) на основі потоку

Рисунок 2 - Зміна в порядку обслуговування пакетів, яка викликана

надходженням пакетів D1 і А4

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

З огляду на це, черги механізму WFQ на основі потоку називаються також чергами діалогу (conversation queue). Оскільки пам'ять є обмеженим ресурсом, кількість черг діалогу за замовчуванням обмежено 25 Незважаючи на це, даний параметр може змінити адміністратор.

Алгоритм зваженого рівномірного обслуговування черг (WFQ) на основі потоку реалізований у більшості маршрутизаторів Cisco. Одне з найпомітніших виключень складають маршрутизатори Cisco серії 12000. Механізм обслуговування черг WFQ на основі потоку є стандартним для всіх інтерфейсів зі смугою пропускання нижче 2 Мбіт/с.

Розглянемо таку задачу. На послідовному інтерфейсі застосовується алгоритм зваженого рівномірного обслуговування черг (WFQ) на основі потоку для обробки восьми потоків трафіка - по одному на кожне значення IP-пріоритету. Як зміниться розподіл смуги пропускання для кожного потоку, якщо на послідовному інтерфейсі оброблятиметься 25 потоків трафіку - 18 потоків з IP-пріоритетом 1 і по одному потоку на кожне інше значення IP-пріоритету?

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

У першому випадку ми маємо справу з восьми потоками - по одному на кожне значення IP-пріоритету. Потік трафіка з нульовим IP-пріоритетом займає смуги пропускання каналу, потік трафіка з першим IP-пріоритетом - 2/36 смуги пропускання каналу, потік трафіка з другим IP-пріоритетом -3/36 смуги пропускання каналу і т.д.

У другому випадку кількість потоків зростає до 25 - 18 потоків з IP- пріоритетом 1 і по одному потоку на кожне інше значення IP- пріоритету. Тепер кожен потік трафіку з IP-пріоритетом 0 займає лише смуги пропускання каналу, кожен потік трафіка з першим IP-пріоритетом - 2/70 смуги пропускання каналу і т.д.

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

Для обслуговування пакетів критично важливих аплікацій або мовного трафіка може застосовуватися різновид рівномірного обслуговування черг (WFQ) на основі потоку, до якого введена одна пріоритетна черга PQWFQ (1PQ+WFQ). Мовні пакети знаходяться в пріоритетній черзі і завжди обслуговуються першими, за рахунок чого досягається прийнятна якість їхнього обслуговування.

2.Розподілений алгоритм зваженого рівномірного обслуговування черг на основі потоку (Flow-Based Distributed WFQ, DWFQ)

Алгоритм WFQ можна реалізувати як на центральному процесорі, так і в розподіленому режимі. Розподілений алгоритм зваженого рівномірного обслуговування черг на основі потоку (Flow-Based Distributed WFQ, DWFQ) реалізується в розподіленому режимі на маршрутизаторах Cisco серії 7500, які побудовані на базі інтерфейсних плат VІР (Versatile Interface Processor -універсальний інтерфейсний процесор), що оснащені вбудованими процесорами. Саме процесором лінійної плати VІР і виконується механізм DWFQ. Підтримка DWFQ на основі потоку вимагає від маршрутизатора підтримки розподіленого механізму швидкісної комутації пакетів Cisco (Distributed Cisco Express Forwarding, DCEF). Реалізація алгоритму DWFQ передбачає наявність обмеження на розмір окремої черги і сукупного обмеження на розмір усіх черг системи. Обмеження на розмір окремої черги застосовується тільки у випадку досягнення сукупного обмеження на розмір усіх черг системи.

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

3 Алгоритм зваженого рівномірного обслуговування на основі класу (CBWFQ)

У рамках схеми зваженого рівномірного обслуговування WFQ черги можуть надаватися як для окремого потоку - WFQ на основі потоку (Flow-Based WFQ), так і для цілого класу трафіка - WFQ на основі класу (Class-Based WFQ, CBWFQ).

Алгоритм CBWFQ можна отримати з алгоритму WFQ на основі потоку шляхом додання до останнього модуля класифікації трафіка. Так само як WFQ на основі потоку, CBWFQ можна реалізувати у нерозподіленому і розподіленому режимах.

У першому випадку алгоритм виконується на центральному процесорі маршрутизатора і базується на обчисленні порядкового номера пакета. В другому випадку алгоритм виконується процесором інтерфейсної плати VІР і використовує календарні черги.

Алгоритм CBWFQ дозволяє явно вказати необхідну мінімальну смугу пропускання для кожного класу трафіка. Це вигідно відрізняє даний алгоритм від алгоритму WFQ на основі потоку, відповідно до якого мінімальна смуга пропускання потоку визначалася неявно на підставі ваги всіх активних потоків WFQ-системи.

Заснований на класах CBWFQ у маршрутизаторах Cisco має два варіанти:

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

класи трафіка визначаються значеннями полів TоS.

Для варіанта QoS-груп адміністратор задає вагу пропускної здатності, яка надається кожній QoS-групі, а також (опціонно) максимальну довжину черги. Для черг, заснованих на класах QoS, пакети, що не належать до жодної з груп, належать до групи 0. При призначенні ваги в механізмі WFQ потрібно брати до уваги таке:

один відсоток наявної пропускної здатності автоматично призначається QoS-групі 0;

загальна вага всіх інших груп не може перевищувати 99%;

будь-яка пропускна здатність, що залишається після призначення ваги, виділяється QoS-групі 0.

Для варіанта, що використовує для класифікації значення TоS, існують ваги класів за замовчуванням. Вони призначаються, якщо адміністратор явно не задав їх за допомогою команди weight.

Для класифікації використовується два молодших біти трирозрядного поля IP Precedence в полі TоS, тому в цьому варіанті існує всього чотири класи трафіка.

За замовчуванням, класові 0 надається 10% вихідної пропускної здатності, класові 1 - 20%, класові 2 - 30% і класові 3 - 40%. Чим вище клас, тим важливіший трафік, тому виділення йому за замовчуванням більшої частки пропускної здатності створює для нього більш привілегійовані умови передачі.

Порівняльна характеристика основних варіантів алгоритму зваженого рівномірного обслуговування наведена в табл. 2.

Таблиця 2 - Порівняльна характеристика механізмів обслуговування черг WFQ на основі потоку і CBWFQ

4.Механізм обслуговування черг із малою затримкою LLQ

Механізм обслуговування черг із малою затримкою (low latency queuing -LLQ) є модифікованим механізмом CBWFQ з додаванням пріоритетної черги.

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

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

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

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

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

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

Размещено на Allbest.ru