БАЗОВІАЛГОРИТМИ ОБСЛУГОВУВАННЯ ЧЕРГ
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 байт.
Припустимо, щорозмір пакетів трьох різних протоколів дорівнює 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% означає, що в періодперевантаження даному класові не гарантується передача.
Прикладієрархічного розподілу ресурсів наведений на рис. 5
/>
Рисунок 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-minfair-share allocation scheme). У відповідності до зваженої максимінної схемирівномірного розподілу ресурсів кожному користувачеві надається рівномірначастка ресурсів, пропорційна до його ваги. Принцип максимінного рівномірногорозподілу ресурсів було покладено в основу узагальненої схеми поділу процесорногочасу (Generalized Processor Sharing, GPS). У відповідності зі схемою GPS коженпотік трафіка вміщується у власну логічну чергу, після чого нескінченно малийобсяг даних з кожної непорожньої черги обслуговується за круговим принципом.Необхідність обробки нескінченно малого обсягу даних на кожному колі обумовленавимогою рівномірного обслуговування всіх непорожніх черг на будь-якомукінцевому часовому інтервалі. Отже, схема GPS є справедливою в будь-який моментчасу. Якщо ж усім потокам трафікапризначити вагу, то обсяг даних потоку, який оброблюється за одне коло, будепропорційний його вазі. Подібне розширення схеми GPS фактично є зваженоюмаксимінною схемою рівномірного обслуговування. Незважаючи на те, що GPS єідеальним втіленням максимінної схеми рівномірного розподілу ресурсів, цюмодель не можна реалізувати на практиці. Це пов'язано з припущенням пронескінченно малий обсяг даних, що обслуговуються, кожного кола.
7.Алгоритм рівномірного обслуговуваннячерг (FQ)
Спробоюпрактичної реалізації схеми GPS є алгоритм рівномірного обслуговування черг(FQ) на основі обчислення порядкового номера пакета, що імітує роботуGPS-сервера, який обслуговує в окремий момент часу 1 байт даних. Алгоритм FQмоделює схему GPS шляхом обчислення порядкового номера кожного отриманогопакета. Власне кажучи, порядковий номер пакета є службовою позначкою, якавизначає відносний порядок обробки пакетів.
Одним з основнихпонять алгоритму FQ є поняття лічильника циклів (Round Number, RN), значенняякого відповідає кількості виконаних циклів побайтового планувальника круговогообслуговування в заданий момент часу. Лічильник циклів безпосередньо визначаєзначення порядкового номера пакета.
З метоюілюстрації способу моделювання схеми GPS за допомогою алгоритму FQ розглянемотри потоки трафіка – А, В і С, розміри пакетів яких складають 128, 64 і 32байт, відповідно. Пакети надходять один за іншим на завантажений FQ-сервер упорядку Al, A2, A3, Bl, C1. Першим на FQ-сервер надходить пакет А1, потім–пакет А2 і т.д.
Потік вважаєтьсяактивним (active), якщо хоча б один із пакетів з цього потоку знаходиться вочікуванні обслуговування; у іншому випадку потік вважається пасивним(inactive).
Припустимо, щосистемою FQ був отриманий пакет А1, який належить пасивному потокові. Повнаобробка 128-байтового пакета побайтовим планувальником кругового обслуговуванняпотребує 128 циклів. Якщо на момент одержання пакета А1 значення лічильникациклів дорівнювало 100, то після повної передачі пакета А1 це значення складе100+128=228. По суті, порядковий номер пакета є номером циклу, в якомуздійснюється передача останнього байта пакета. Оскільки в дійсностіпланувальник за один раз реалізує передачу всього пакета, а не його одногобайта, він обслуговує весь пакет незалежно від того, чи зрівнявся лічильникциклів з порядковим номером пакета (рис.9).
Коли система FQотримає пакет А2, він уже належатиме активному потокові трафіка завдякинаявності в черзі пакета А1 з порядковим номером 228. Порядковий номер пакетаА2 дорівнюватиме 228+128=356, оскільки його слід передати після пакета А1.Аналогічно, пакетові A3 призначається порядковий номер 356+128=484. Оскількипакети В1 і С1 належать пасивним потокам трафіка, їхні порядкові номеридорівнюють 164=(100+64) і 132=(100+32), відповідно (рис. 9). З урахуваннямобчислених порядкових номерів пакети будуть обслуговані в такій послідовності:С1, В1, А1, А2, А3.
Отже, порядковийномер (Sequence Number) /> пакетадовжиною /> байт, що визначаєчерговість його обробки, можна розрахувати за формулою:
/> (1)
де /> – значення лічильникациклів на момент надходження пакета (дорівнює порядковому номерові останньогообслуговуваного пакета); /> –значення найбільшого порядкового номера пакета, який поставлений в чергу цьогопотоку (для активного потоку).
Лічильник циклів /> використовується винятководля розрахунку порядкового номера пакетів, які належать новим (пасивним)потокам трафіка. Порядковий номер пакетів, що належать активним потокамтрафіка, розраховується з урахуванням найбільшого порядкового номера пакета зцього потоку, який поставлений в чергу.
/>
Рисунок 9 – Прикладмоделювання побайтового GPS-планувальника кругового обслуговування за допомогоюалгоритму FQ
Слід зазначити,що лічильник циклів оновлюється при передачі кожного чергового пакета, прицьому його нове значення дорівнює порядковому номерові пакета, що передається.Отже, якщо 32-байтовый пакет D1, що належить новому потоку, буде прийнятий умомент передачі пакета А1, значення лічильника циклів дорівнюватиме 228, апорядковий номер пакета D1 – 260=(228+32). Оскільки порядковий номер пакета D1менше порядкових номерів пакетів А2 і A3, він буде переданий раніше за цихпакетів. Зміна в порядку обслуговування пакетів схематично зображена на рис.10.
/>
Рисунок 10 –Зміна в порядку обслуговування пакетів, яка викликана надходженням пакета D1 умомент передачі пакета А1