Навигация
Алгоритм «кошика маркерів»
13995
знаков
1
таблица
5
изображений
2 Алгоритм «кошика маркерів»
Для перевірки відповідності вхідного трафіку заданому профілю і механізм обмеження трафіку, і механізм вирівнювання трафіку вимагають вимірювання параметрів потоку. При цьому основними параметрами, якими оперують у процесі вимірювання (дозування) трафіка, є такі:
q Т – період усереднення швидкості;
q CIR (Committed Information Rate) біт/с – середня або узгоджена швидкість, яку трафік не має перевищувати;
q Bc, байт – обсяг пульсації, що відповідає середній швидкості CIR і періоду Т, 
(узгоджений або стандартний розмір сплеску);
q Вe, байт – припустиме перевищення обсягу пульсації (розширений розмір сплеску).
Існує два основних алгоритми вимірювання трафіка – алгоритм «кошика маркерів» (token bucket) і алгоритм «дірявого відра» (leaky bucket). Перший переважно використовується для контролю параметрів трафіка в IP-мережах, а другий – у мережах ATM і Frame Relay. Розглянемо їх у загальному вигляді.
Алгоритм «кошика маркерів» дозволяє оцінити й обмежити середню швидкість і величину пульсації потоку пакетів. Цей алгоритм базується на порівнянні потоку пакетів з деяким еталонним потоком маркерів, що заповнюють умовний кошик – «кошик маркерів» (рис. 3).
Під маркером у цьому випадку розуміється якийсь абстрактний об'єкт, носій «порції» інформації. Генератор маркерів періодично з постійним інтервалом w направляє черговий маркер у «кошик» з обмеженим обсягом b байт. Усі маркери мають однаковий обсяг m байт, а генерація маркерів відбувається так, що «кошик» заповнюється зі швидкістю r біт/с, де r = 8m/w. Ця швидкість r і є максимальною середньою швидкістю для трафіка пакетів, а обсяг «кошика» відповідає максимальному розмірові пульсації потоку пакетів, тобто з використанням уведених вище термінів r=CIR, b=Bc. Якщо сумарний обсяг маркерів у «кошику» дорівнює b, то надходження маркерів тимчасово припиняється. Фактично «кошик маркерів» є лічильником, що збільшується на m кожні w секунд.
При застосуванні алгоритму «кошика маркерів» профіль трафіка визначається середньою швидкістю r і обсягом пульсації b. Порівняння еталонного і реального потоків виконує сервер – абстрактний пристрій, що має два входи. Вхід 1 пов'язаний з чергою пакетів, а вхід 2 – з «кошиком маркерів». Сервер також має вихід, на який він передає пакети з вхідної черги пакетів. Вхід 1 сервера моделює вхідний інтерфейс маршрутизатора, а вихід – вихідний інтерфейс. Під час передавання пакета з «кошика» вилучаються маркери загальним обсягом у М байт (з точністю до розміру одного маркера, тобто до m байт).
Рисунок 3 – Алгоритм «кошика маркерів»
Якщо ж «кошик» заповнений недостатньо, то пакет обробляється одним із двох описаних нижче нестандартних способів, вибір якого залежить від мети застосування алгоритму.
Перший варіант, алгоритм «кошика маркерів» застосовується для згладжування трафіка, у цьому випадку пакет просто затримується в черзі на деякий додатковий час, очікуючи надходження в «кошик» потрібної кількості маркерів. Отже, навіть якщо в результаті пульсації в систему приходить велика група пакетів, з черги пакети виходять більш рівномірно, у темпі, що задається генератором маркерів.
Другий варіант, алгоритм «кошика маркерів» використовується для обмеження трафіка, тоді пакет відкидається як такий, що не відповідає профілю. Більш м'яким рішенням може бути повторне маркування пакета зі зниженням його статусу при подальшому обслуговуванні. Наприклад, пакет можна позначити особливою позначкою (відкидати за необхідності), у результаті чого під час перевантажень маршрутизатори відкидатимуть цей пакет у першу чергу. При диференційованому обслуговуванні пакет можна перевести в інший клас, який обслуговується з нижчою якістю.
Сутність алгоритму «кошика маркерів» полягає в тому, що він дозволяє передачу даних пачками, але обмежує тривалість пачки. Нехай пропускна здатність вихідного інтерфейсу, що моделюється виходом сервера, дорівнює R. Це означає, що сервер не може передавати дані на вихід зі швидкістю, що перевищує R біт/с. Можна показати, що на будь-якому інтервалі часу t середня швидкість потоку, який виходить із сервера, дорівнює мінімальній серед двох величин: R і r+ b/t. При великих значеннях t швидкість вихідного потоку наближається до r – це і свідчить про те, що алгоритм забезпечує бажану середню швидкість. У той же час протягом невеликого часу t пакети можуть виходити із сервера зі швидкістю, яка перевищує r. Якщо r+ b/t < R, то вони виходять із сервера зі швидкістю r+ b/t, у протилежному випадку інтерфейс обмежує цю швидкість до величини R. Період часу t відповідає пульсації трафіка. Ця ситуація спостерігається тоді, коли протягом деякого часу пакети не надходили до сервера, так що «кошик» цілком заповнився маркерами (тобто часу, більшого ніж b/r). Якщо після цього до входу сервера надійде велика послідовність пакетів, які йдуть один за одним, то ці пакети передаватимуться на вихід зі швидкістю вихідного інтерфейса R також один за одним, без інтервалів. Максимальний час такої пульсації складає b/(R-r) секунд, після чого обов'язково наступить пауза, яка необхідна для наповнення спустілого «кошика». Обсяг пульсації складає Rb/(R-r) байт. З наведеного співвідношення видно, що алгоритм «кошика маркерів» починає погано працювати, якщо середня швидкість r обирається близькою до пропускної здатності вихідного інтерфейса. У цьому випадку пульсація може продовжуватися дуже довго, що знецінює алгоритм.
3 Алгоритм «дірявого відра»
Для контролю угоди про параметри якості обслуговування всі комутатори мережі Frame Relay підтримують алгоритм «драного відра» (leaky bucket). Цей алгоритм, як і алгоритм «кошика маркерів», дозволяє контролювати середню швидкість і пульсацію трафіка, однак робить це у інший спосіб.
Алгоритмом передбачається, що трафік контролюється кожні Т секунд. На кожному з цих інтервалів часу трафік повинний мати середню швидкість не більш обумовленої швидкості CIR. Швидкість контролюється, базуючись на підрахунку обсягу даних, що надійшли за період Т. Якщо цей обсяг менше або дорівнює Bc, то фактична швидкість трафіка була менше Вс/Т, тобто менше CIR. Перевищення обсягом пульсації обумовленого значення Вс на величину Be вважається «м'яким» порушенням – пакети-порушники мають бути позначені DE=1, але не відкинуті. При перевищенні обсягом пульсації величини Вc + Вe кадри відкидаються.
Алгоритм (рис. 4) використовує лічильник байт С, які надійшли від користувача. Кожні Т секунд цей лічильник зменшується на величину Вс (або ж скидається в 0, якщо значення лічильника менше, ніж Вс). Це найчастіше ілюструється «відром», з якого дискретно, кожні Т секунд, витікає обсяг, рівний мінімальному з чисел Вс або С (рис. 4). Усі кадри, дані яких не збільшили значення лічильника вище порогу Вс, пропускаються в мережу зі значенням позначки DE=0. Кадри, дані яких призвели до значення лічильника, більшого за Вс, але меншого за Bc+Be, також передаються в мережу, але з позначкою DE=1. І, нарешті, кадри, що призвели до значення лічильника, більшого за Bc+Be, відкидаються комутатором.
Рисунок 4 – Алгоритм «дірявого відра»
Користувач може домовитися про підтримку не всіх параметрів якості обслуговування для даного віртуального каналу, а тільки деяких. Наприклад, можна використовувати тільки параметри CIR і Bc. Цей варіант дає якісніше обслуговування, тому що кадри ніколи не відкидаються комутатором відразу. Комутатор тільки позначає кадри, що перевищують поріг Bc за час Т, позначкою DE=1. Якщо мережа не зазнає перевантажень, то кадри такого каналу завжди надходять до кінцевого вузла, навіть якщо користувач постійно порушує договір з мережею.
Популярним є ще один різновид замовлення на обслуговування, при якому обумовлюється тільки поріг Be, а швидкість CIR=0. Усі кадри такого каналу відразу ж позначаються позначкою DE=1, але відправляються в мережу, а при перевищенні порога Be відкидаються. Контрольний інтервал часу Т в цьому випадку обчислюється як Be /R, де R – швидкість доступу до каналу.
Алгоритм допускає різні модифікації, наприклад, використання більшої кількості порогів обсягу пульсації, використання замість обсягу пульсації значення максимальної швидкості і т.п.
Одна з модифікацій алгоритму «дірявого відра» за назвою Generic Cell Rate Algorithm (GCRA) застосовується в мережах ATM для контролю декількох параметрів: пікової швидкості, середньої швидкості, варіації інтервалу надходження чарунок і обсягу пульсації.
За своєю суттю алгоритм «дірявого відра» – це не що інше, як однолінійна система масового обслуговування з постійним часом обслуговування. Цей механізм перетворює нерівномірний потік пакетів від процесів користувача в рівномірний потік пакетів у мережі з постійною швидкістю, що не залежить від нерівномірності вхідного потоку.
Як видно з опису, алгоритм «дірявого відра» «суворіше» контролює пульсації трафіка, ніж алгоритм «кошика маркерів». Алгоритм «кошика маркерів» дозволяє трафіку в періоди зниженої активності накопичувати обсяг пульсації, а потім використовувати ці накопичення в періоди сплесків трафіка. В алгоритмі «дірявого відра» такої можливості немає, тому що лічильник С скидається в нуль примусово наприкінці кожного періоду Т незалежно від того, скільки байтів надійшло від користувача в мережу протягом цього періоду. Ще одне розходження двох алгоритмів полягає в тому, що при переповненні «маркерного кошика» алгоритм ігнорує маркери, але ніколи не відкидає пакети. Алгоритм «дірявого відра», навпаки, при переповненні викидає самі пакети.
Похожие работы
... 10 Tбіт/с. Крім того, використання розподілених комбінованих підсилювачів й ербієвих підсилювачів дозволяє збільшити дальність зв'язку без переприйому до 200 км. 3. Базова архітектура управління мережними ресурсами в ТКС Забезпечення наскрізного QoS "з кінця в кінець" (end-to-end) у рамках гетерогенної ТКС припускає використання таких засобів управління (рис.4): 1. Засоби управління, які ...
... значних результатів. За підсумками роботи за рік показники якості значно краще, ніж встановлені для них нормативні рівні, як українські, так і міжнародні. Розділ 3. Шляхи вдосконалення управління якістю послуг Інтернет зв’язку в компанії «People.net» 3.1 Вдосконалення системи стандартів якості послуг Інтернет зв’язку Сьогодні в Україні відмічено масовий рух із впровадження на підприє ...
... ї комп’ютерної мережі авіакомпанії «Північна компанія» 2.3.1 Програмний пакет проектування і моделювання гетерогенних комп'ютерних мереж NetCracker Professional Призначення системи: автоматизоване проектування і моделювання локальних і корпоративних комп'ютерних мереж в цілях мінімізації витрат часу і засобів на розробку, верифікацію проектів. Функції: створення проекту мережі; анімаційне ...
... підприємства 15080 Ціна підприємства 165879 Податок на додану вартість 33175,8 Ціна для замовника 199055 Таким чином розрахунок показав, що собівартість проекту «Організація локально-обчислювальної мережі агентства нерухомості» складає 150799 грн., якщо цей проект продаватиметься, то його ціна для споживача складе 199055 грн. При цьому з кожного екземпляра проданого проекту буде ...
0 комментариев