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

Рисунок 4 – Приклади розподілу ресурсів з використанням різних критеріїв класифікації трафіка

Рисунок 5 – Приклад ієрархічного розподілу ресурсів

Механізм обслуговування CBQ є дуже розповсюдженим, він реалізований у Packet Filter (pf) у сімействі операційних систем BSD.

Розглянемо приклад. Нехай маємо таку структуру черг:

Тут Root Queue – коренева черга – займає всю смугу пропускання каналу (2 Мбіт/с). Коренева черга має три дочірні черги std, ssh і ftp, яким надається 50%, 25% і 25% від сумарної смуги відповідно. Черга ssh у свою чергу має дві дочірні підчерги: ssh_login і ssh_bulk, що поділяють смугу, яку виділено для ssh, в співвідношенні 1:3 (25% і 75%).

У рамках CBQ можливе введення пріоритетів. Черги одного рівня ієрархії і рівного пріоритету обслуговуються за круговим принципом (WRR). Черга, що має вищий пріоритет, обслуговується першою. У даному прикладі спочатку обслуговується черга ftp (пріоритет 3), потім черги з пріоритетом 1 – std і ssh за круговим принципом. Коли обслуговуватиметься черга ssh, спочатку вилучаються пакети з ssh_login (пріоритет 4), потім з ssh_bulk (пріоритет 1). Пріоритети черг різного рівня ієрархії (ftp і ssh_login) не порівнюються. Запис borrow для черги ftp означає, що цій черзі дозволено запозичати ресурси (смугу пропускання), які виділені для інших черг цього ж рівня ієрархії, але ними не використовуються. Розглянута черга конфігурується на інтерфейсі fxp0 за допомогою наступних команд:

Тут записи ecn і red означають, що в цих чергах працюють механізми боротьби з перевантаженнями ECN і RED.

6. Максимінна схема рівномірного розподілу ресурсів

З метою забезпечення рівномірного обслуговування використовується максимінна схема рівномірного розподілу ресурсів (max-min fair-share allocation scheme). Основними її правилами є такі:

• ресурси розподіляються в порядку підвищення вимог;

• користувач не може отримати обсяг ресурсів, який перевищує його потреби;

• ресурси розподіляються рівномірно між користувачами з незадоволеними вимогами.

Розглянемо приклад. Припустимо, що загальний обсяг доступного ресурсу дорівнює 14 одиницям. Вимоги до ресурсу користувачів А, В, С, D та Е складають 2, 2, 3, 5 і 6 одиниць, відповідно. Розподіл ресурсу починається з джерела з найменшими вимогами, який одержує обсяг ресурсу, що дорівнює відношенню всього запасу ресурсу до загальної кількості користувачів. Отже, у розглянутому нами випадку користувачам А і В буде надано 14/5=2,8 одиниць ресурсу (рис. 6). Однак вимоги користувачів А і В складають усього лише 2 одиниці ресурсу. У цьому випадку надлишковий ресурс обсягом 1,6 одиниць (по 0,8 одиниць з кожного користувача) рівномірно розподіляється між трьома іншими користувачами. Отже, користувачі С, D та Е одержують по 2,8 + (1,6/3) = 3,33 одиниць ресурсу (рис. 7). Наступним за обсягом висунутих вимог до ресурсів є користувач С. Вимоги користувача С на 0,33 одиниці менше обсягу ресурсів, що йому пропонується. Надлишковий ресурс обсягом 0,33 одиниці рівномірно розподіляється між користувачами D і Е, кожний з яких одержує по 3,33 + (0,33/2)=3,5 одиниці ресурсу (рис. 8).

Рисунок 6 – Розподіл ресурсів для користувачів А і В

Рисунок 7 – Розподіл ресурсів для користувача С

Рисунок 8 – Розподіл ресурсів для користувачів D та E

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

,

де – сумарний запас ресурсів; – обсяг уже розподілених ресурсів;

– кількість користувачів, яким ще потрібні ресурси.

Як видно з рис. 6 – 8, вимоги користувачів А та В задовольняються в повному обсязі, тому що вони не перевищують значення, отриманого в результаті рівномірного розподілу ресурсів між усіма користувачами. На кроці 2 цілком задовольняються вимоги користувача С. А запити користувачів D і Е залишаються незадоволеними.

Зверніть увагу, що всі користувачі з незадоволеними вимогами (тобто з вимогами, обсяг яких перевищує їх максимінну рівномірну частку), одержують рівні обсяги ресурсів. Максимінна схема рівномірного розподілу ресурсів одержала свою назву в зв'язку з тим, що користувач з незадоволеними вимогами одержує максимум з можливих мінімальних рівномірних часток. Максимінна схема рівномірного розподілу ресурсів, у якій кожному користувачеві призначається певна вага, одержала назву зваженої максимінної схеми рівномірного розподілу ресурсів (weighted max-min fair-share allocation scheme). У відповідності до зваженої максимінної схеми рівномірного розподілу ресурсів кожному користувачеві надається рівномірна частка ресурсів, пропорційна до його ваги. Принцип максимінного рівномірного розподілу ресурсів було покладено в основу узагальненої схеми поділу процесорного часу (Generalized Processor Sharing, GPS). У відповідності зі схемою GPS кожен потік трафіка вміщується у власну логічну чергу, після чого нескінченно малий обсяг даних з кожної непорожньої черги обслуговується за круговим принципом. Необхідність обробки нескінченно малого обсягу даних на кожному колі обумовлена вимогою рівномірного обслуговування всіх непорожніх черг на будь-якому кінцевому часовому інтервалі. Отже, схема GPS є справедливою в будь-який момент часу.Якщо ж усім потокам трафіка призначити вагу, то обсяг даних потоку, який оброблюється за одне коло, буде пропорційний його вазі. Подібне розширення схеми GPS фактично є зваженою максимінною схемою рівномірного обслуговування. Незважаючи на те, що GPS є ідеальним втіленням максимінної схеми рівномірного розподілу ресурсів, цю модель не можна реалізувати на практиці. Це пов'язано з припущенням про нескінченно малий обсяг даних, що обслуговуються, кожного кола.