Павликевич М.Й Телекомунікаційні мережі ч2. Мережі ІР

Подождите немного. Документ загружается.

2. Мережі IP.

_______________________________________________________________________________________

___________________________________________________________________________________________________

М. Павликевич. Телекомунікаційні мережі. Навчальний посібник для студентів спеціальності

"Інформаційні мережі зв'язку, 2009.

201

Швидке відновлення (тільки для Reno). У цьому стані TCP повторно пересилає пошкоджений

пакет, про що сигналізують 3 повторні ACK, і очікує на підтвердження для цілого пересланого вікна

перед поверненням до уникнення перевантаження. Якщо підтвердження відсутнє, то TCP Reno

здійснює паузу і переходить до стану повільного старту.

Обидва алгоритми зменшують вікно перевантаження до 1 MSS, якщо настає пауза.

TCP New Reno вдосконалює повторне пересилання протягом фази швидкого відновлення TCP

Reno. Для кожного здубльованого ACK, яке повертається до TCP New Reno, висилається новий

невисланий пакет з кінця вікна перевантаження, що утримує вікно пересилання повним.Для кожного

ACK, яке здійснює частковий прогрес у просторі послідовності, передавач вважає, що ACK вказує на

нове порожнє місце і висилається пакет, наступний за підтвердженим номером послідовності.

Оскільки таймер паузи запускається повторно кожного разу, коли досягнено прогрес у

передавальному буфері, то це дозволяє New Reno заповнювати великі порожні місця або багато

порожніх місць у просторі послідовності, подібно до TCP SACK.Тому що New Reno може висилати

новий пакет з кінця вікна перевантаження протягом фази швидкого відновлення, висока перепускна

здатність забезпечується протягом процесу заповнення порожніх місць навіть про наявності багатьох

порожніх місць, кожне від багатьох пакетів. Коли TCP розпочинає швидке відновлення, він записує

найвищий номер послідовності непідтвердженого пакету. Коли цей номер послідовності отримує

підтвердження, TCP повертається до стану уникнення перевантаження.

Проблеми з алгоритмом New Reno з’являються тоді, коли відсутні втрати пакетів, натомість

порушений порядок слідування понад трьох номерів послідовності у пакетах. Коли це трапляється, то

New Reno помилково розпочинає швидке відновлення, однак коли пакет з порушеною послідовністю

доручений, з’являється прогрес номерів послідовності ACK і від цього моменту до завершення

швидкого відновлення кожен біт прогресу номерів послідовності викликає непотрібне повторне

пересилання, яке негайно підтверджується. New Reno має кращі характеристики як від SACK при

низькому рівні втрат пакетів, так і Reno при високому рівні таких втрат.

9.1.4. TCP Vegas

TCP Vegas. Раніше всі встановлення пауз і вимірювання періоду обігу петлі TCP базувалися

виключно на останньому висланому пакеті з передавального буфера. Пізніше був впроваджений TCP

Vegas, у якому паузи встановлювалися і RTT вимірювалися для кожного пакету у передавальному

буфері. Крім того, Vegas використовує адитивне збільшення та адитивне зменшення вікна

перевантаження. Однак цей варіант мало поширений.

9.2. Методи, базовані на роутері

9.2.1. Алгоритм RED

9.2.1.1.

Завдання алгоритму RED

Хоч TCP є наскрізним протоколом, мережа може сприяти TCP в оптимізації його

характеристик. Одна з можливостей полягає у зміні поведінки черги в мережі шляхом використання

завчасного випадкового виявлення (Random Early Detection - RED). RED дозволяє мережевому

роутеру видаляти пакет, навіть коли наявне додаткове місце у черзі. Така взаємодія між завчасним

випадковим виявленням і TCP є дуже ефективною.

RED використовує зважену усереднену довжину черги як коефіцієнт ймовірності видалення

пакету. Якщо усереднена довжина черги зростає, то зростає і ймовірність видалення пакету (рис. 9.3).

Малий блок пакетів можна переслати через фільтр RED відносно цілим, тоді як більші блоки пакетів

будуть відчувати зростаючий вищий темп видалення. Підтримане навантаження буде надалі

збільшувати темп видалення пакетів. Це веде до того, що TCP-сесія з більшими вікритими вікнами

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

Головною метою RED є уникнення ситуацій, у яких всі потоки TCP відчувають

перевантаження в той сам час, всі роблять відступ і поновлення від того самого темпу, тобто

тенденцій до синхронізації поведінки потоків. При використанні RED найбільш імпульсивні потоки

2. Мережі IP.

_______________________________________________________________________________________

___________________________________________________________________________________________________

М. Павликевич. Телекомунікаційні мережі. Навчальний посібник для студентів спеціальності

"Інформаційні мережі зв'язку, 2009.

202

мають найбільшу ймовірність видалення пакетів, тоді як потоки з меншим рівнем імпульсивності

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

впливу повної втрати сигналів ACK, яка веде до паузи і рестарту сесії в режимі повільного старту.

Намір полягає в сигналізації найбільш імпульсивній сесії TCP ймовірності очікування насичення

черги і видалення її кінцівки перед досягненням умови такого видалення, дозволяючи сесії TCP

застосувати швидке відновлення за умови відсутності перевантаження. Іншою метою RED є

уможливити ефективну роботу черги з масштабованою глибиною черги через цілий розмір черги

всередині часової шкали коливань глибини черги того самого порядку, як середнє значення RTT

потоку трафіку.

Рис. 9.3. Поведінка RED.

Поза увагою RED залишається спостереження, що TCP встановлює дуже мало припущень

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

зворотнього зв’язку щодо узгоджених характеристик, який був би генерований мережею. Як

мінімальне наближення TCP використовує втрати пакетів як сигнал про характеристики мережі,

інтерпретуючи подію втрати пакетів у малому масштабі як подію перевантаження мережі внаслідок

піку навантаження, і подію тривалої втрати пакетів як ознаку більш критичного перевантаження.

RED сприяє збільшенню кількості сигналів про маломасштабні перевантаження і таким чином уникає

довготривалих умовперевантаження.

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

наявну можливість переповнення черги, і надавач повинен пристосуватися до цих умов. Головною

метою є забезпечення уникнення перевантаження шляхом регулювання довжини (розміру) черги у

буфері роутера. Додаткові цілі включають уникнення глобальної синхронізації і впливу

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

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

Перше завдання механізму уникнення перевантаження полягає у виявленні перевантаження,

яке зароджується. Схема уникнення перевантаження підтримує мережу в області малих затримок і

високої перепускної здатності. Середня довжина черги може утримуватися малою, а флуктуації

актуальної її довжини повинні дозволити поглинути імпульсивність трафіку і короткочасне

перевантаження. Оскільки роутер може моніторувати розмір черги у часі, то такий роутер є

придатним агентом для виявлення зародження перевантаження. Тому що роутер має уніфіковану

точку зору на різні джерела, які можуть впливати на перевантаження, то роутер також придатний до

вирушення, які з цих джерел слід повідомити про перевантаження.

У мережі зі сполученнями, які характеризуються різними RTT, вимогами щодо перепускної

здатності і чутливостями до затримок, роутер є найбільш придатним агентом для визначення впливу

обсягу і тривалості короткочасного імпульсу (викиду) трафіку на розмір черги, яка може бути

сприйнята цим роутером. Роутер може здійснити це, регулюючи часові константи, вживані

2. Мережі IP.

_______________________________________________________________________________________

___________________________________________________________________________________________________

М. Павликевич. Телекомунікаційні мережі. Навчальний посібник для студентів спеціальності

"Інформаційні мережі зв'язку, 2009.

203

низкочастотними (згладжуючи ми) фільтрами при обчисленні середньої довжини черги. Метою

роутера є виявлення зародження перевантаження, обумовленого деякими тривалими RTT.

Другим завданням роутера при здійсненні уникнення перевантаження є вирішити, які

сполучення повідомляти про перевантаження в мережі. Якщо перевантаження виявлене перед

цілковитим заповненням буфера роутера, то цей роутер не мусить видалять пакети, щоб

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

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

у видаленні пакету, встановленні біта у заголовку пакету або в іншому способі, зрозумілому для

транспортного протоколу. Поточний механізм зворотнього зв’язку в мережах TCP/IP для роутерів

полягає у видаленні пакетів і моделювання у цій роботі враховує це.

Одне з завдань полягає в униканні впливу імпульсивності трафіку. Мережі містять

сполучення з різними діапазонами імпульсивності трафіку, а роутери з алгоритмами Tail Drop або

Random Drop піддані на вплив імпульсивного трафіку. Наприклад, чим більш імпульсивним є трафік

в окремому сполученні, тим більш ймовірним є переповнення черги в роутері, оснащеному Tail Drop.

Іншим завданням при вирішенні того, які сполучення повинні повідомлятися про

перевантаження, є уникнення глобальної синхронізації, яка призводить до повідомлення всіх

сполучень про потребу зменшення їх вікон у той сам час. Це призводить до значного зменшення

перепускної здатності мережі.

Роутери, оснащені RED, використовують рандомізацію при виборі того, які вхідні пакети

маркувати. При використанні цього методу ймовірність маркування пакету з конкретного сполучення

прямо пропорційна до ширини смуги через роутер, яку використовує це сполучення спільно з

іншими. Цей метод ефективно впроваджений без потреби окремої підтримки кожного сполучення в

роутері.

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

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

роутер видаляє вхідні пакети, коли середня довжина черги перевищує певний максимальний поріг.

Цей метод може використовуватися для регулювання середньої довжини черги навіть коли більшість

сполучень тривають менше від RTT (як це може виявитися при модифікованих транспортних

протоколах у високошвидкісних мережах) і навіть коли сполучення відмовить у зменшенні своєї

перепускної здатності у відповідь на маркований або видалений пакет.

9.2.1.2.

Алгоритм RED

Тут описаний алгоритм для роутерів, оснащених RED. Роутери RED обчислюють середній

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

Середній розмір черги порівнюється з двома пороговими значеннями –мінімальним і максимальним.

Коли середній розмір черги менший від мінімального порогового значення, то жоден пакет не

маркується, коли ж середній розмір черги більший від максимального порогового значення, то

маркується кожен пакет. Якщо позначені пакети фактично видаляються або якщо всі джерельні вузли

працюють спільно, то цим досягається те, що середній розмір черги помітно не перевищує

максимальний поріг.

Якщо середній розмір черги лежить між мінімальним і максимальним пороговими

значеннями, то кожен вхідний пакет маркується з ймовірністю

p , де

p є функцією від середнього

розміру черги avg. Кожного разу, коли пакет маркується, ймовірність того, що маркований пакет

походить від певного сполучення, є прямо пропорційною до частки використання ширини смуги

роутера цим сполученням. Загальний алгоритм RED наведений на рис. 9.4.

Рис. 9.4. Загальний алгоритм RED.

2. Мережі IP.

_______________________________________________________________________________________

___________________________________________________________________________________________________

М. Павликевич. Телекомунікаційні мережі. Навчальний посібник для студентів спеціальності

"Інформаційні мережі зв'язку, 2009.

204

Фактично роутер, оснащений RED, використовує два окремі алгоритми. Алгоритм

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

наявна у черзі роутера. Алгоритм обчислення ймовірності маркування пакетів визначає, як часто

розтер маркує пакети, забезпечуючи поточний рівень перевантаження. Мета полягає у тому, щоб з

одного боку, роутер маркував пакети з досить рівномірними інтервалами, щоб уникнути тенденцій та

уникнути глобальної синхронізації, а з другого – щоб він маркував пакети достатньо часто для

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

на рис. 9.5.

Рис. 9.5. Детальний алгоритм RED.

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

порожня, тобто коли темп відбору пакетів з черги перевищує темп їх надходження. Це робиться для

того, щоб оцінити кількість m малих пакетів, які могли б бути переслані даним роутером протягом

періоду, коли черга порожня. Після періоду порожньої черги роутер обчислює середній розмір черги,

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

Оскільки avg змінюється від min

до max

, то ймовірність маркування пакету p

змінюється

лінійно від 0 до max









thththpb

minmaxminavgmaxp  .

2. Мережі IP.

_______________________________________________________________________________________

___________________________________________________________________________________________________

М. Павликевич. Телекомунікаційні мережі. Навчальний посібник для студентів спеціальності

"Інформаційні мережі зв'язку, 2009.

205

Остаточна ймовірність маркування пакету

p повільно зростає, бо зростає лічильник після

останнього маркованого пакету:





bba

pcountpp  1 .

Як показано нижче, призводить до того, що роутер не очікує надто довго, перш ніж маркувати пакет.

Роутер маркує кожен пакет, який прибуває до нього, коли середня довжина черги avg

перевищує max

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

З цією опцією середній розмір черги точно відображає сердню затримку в роутері. Коли

використовується ця опція, алгоритм повинен бути модифікований, щоб ймовірність маркування

пакету була пропорційною до розміру пакету в байтах:

У цьому випадку ймовірність маркування великого пакету більша, ніж малого.

Нижче детально розглянено встановлення різних параметрів роутера RED. При обчисленні

середньої довжини черги вага черги w

визначається обсягом і тривалістю імпульсивності розміру

черги, допустимої для роутера. Мінімальне і максимальне порогові значення min

і max

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

бажаний компроміс (такий, як компроміс між максимальною перепускною здатністю і мінімальною

затримкою) залежить від характеристик мережі та є предметом подальших досліджень. Також

розглянено деякі аспекти обчислення ймовірності маркування пакету.

9.2.1.3.

Обчислення середньої довжини черги

Роутери RED використовують низькочастотний фільтр для обчислення середньої довжини

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

трафіку або тимчасового перевантаження, не призводить до значного збільшення середньої довжини

черги.

Низькочастотний фільтр має експоненціальне ковзне середнє значення (exponential weighted

moving average – EWMA):





avgwavgwavg

 1

Вага w

визначає часову постійну НЧ-фільтра. Нижче розглянемо верхню і нижню межі встановлення

q .

Обчислення середньої довжини черги

може бути впроваджене відносно ефективно, коли w

від’ємною степінню двійки.

Якщо w

занадто велика, то процедура усереднення не згладжує тимчасові перевантаження у

мережі. Приймемо, що початково черга порожня, а далі збільшується від 0 до L пакетів при

надходженні L пакетів. Після надходження L-го пакету середня довжина черги avg

дорівнює





Lavg







На рис. 9.6 показана середня довжина черги avg

у залежності від w

і L . Величини w

лежать в межах

0.001..0.005, а значення L – від 10 до 100. Якщо задане мінімальне порогове значення min

і треба

дозволити імпульсу з L пакетів прибути до роутера, то вага w

повинна бути вибрана такою, щоб

задовільнити нерівність для avg

< min





min

L 







Наприклад, для min

=5 і L=50 необхідно вибрати w

 0.0042.

2. Мережі IP.

_______________________________________________________________________________________

___________________________________________________________________________________________________

М. Павликевич. Телекомунікаційні мережі. Навчальний посібник для студентів спеціальності

"Інформаційні мережі зв'язку, 2009.

206

Рис. 9.6. Залежність середньої довжини черги avg

від значень w

і L.

Роутери RED повинні утримувати середню довжину черги нижче від певного порогового

значення. Однак це дає незначні можливості, якщо обчислене середнє avg не є розумним

відображенням поточної середньої довжини черги. Якщо вага w

встановлена занадто малою, то avg

занадто повільно відповідає на зміни в актуальній довжині черги. У цьому випадку розтер нездатний

виявити початкову стадію перевантаження.

Припустимо, що черга змінилася з порожньої до одного пакету, і що коли пакети прибувають

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

початковий розмір черги дорівнює нулю. У цьому випадку вона здійснює





w 1ln1 надходжень

пакетів (зі збереженням довжини черги рівною 1), доки середня довжина черги досягне значення

e/1163.0 

. Для w

=0.001 це наступає при надходженні 1000 пакетів, для w

=0.002 – при

надходженні 500 пакетів, для w

=0.03 – при надходженні 333 пакетів і т.д. У більшості випадків

використовують w

=0.002.

Оптимальні значення min

і max

залежать від бажаної середньої довжини черги. Якщо

типовий трафік досить імпульсивний, то поріг min

повинен бути достатньо великим, щоб дозволити

використання каналу на прийнятно високому рівні. Для типового трафіку і сполучення з розумно

великим добутком затримка*ширина_смуги мінімальний поріг, рівний одному пакету, призвівби до

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

конкретної суміші трафіків може бути предметом подальших досліджень.

Оптимальне значення max

частково залежить від максимальної усередненої затримки,

дозволеної для роутера. Роутер RED працює ефективніше, коли різниця max

- min

більша від

типового збільнення обчисленої середньої довжини черги за один інтервал обігу петлі (RTT).

Придатним правилом є встановлення max

≥2* min

9.2.1.4.

Обчислення ймовірності маркування пакету.

Початкова ймовірність маркування пакету p

обчислюється як лінійна функція середньої

довжини черги. Відомі два методи обчислення ймовірності маркування пакету. У першому методі,

коли середня довжина черги постійна, кількість вхідних пакетів між маркованими пакетами є

випадковою величиною з геометричним законом розподілу. У другому методі – це випадкова

величина з рівномірним законом розподілу.

Початкова ймовірність маркування пакету обчислюється за формулою (). Параметр max

вказує максимальне значення ймовірності маркування p

, яке досягається, коли середній розмір

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

У першому методі (випадкові величини з геометричним законом розподілу) кожен пакет

маркується з ймовірністю p

. Нехай інтервал між маркованими пакетами X визначений кількістю

2. Мережі IP.

_______________________________________________________________________________________

___________________________________________________________________________________________________

М. Павликевич. Телекомунікаційні мережі. Навчальний посібник для студентів спеціальності

"Інформаційні мережі зв'язку, 2009.

207

немаркованих пакетів, які надійшли після останнього маркованого пакету перед черговим

маркованим пакетом. Оскільки кожен пакет маркується з ймовірністю p

, то









ppnXProb



 .

Інтервал X – випадкова величина, розподілена геометрично з параметром p

і математичним

очікуванням





pXE 1 .

При постійній середній довжині черги мета полягає у маркуванні пакетів з можливо

регулярним інтервалом між ними. Небажано мати занадто багато маркованих пакетів, зібраних разом,

а також небажано мати занадто довгий інтервал між маркованими пакетами. Обидві ситуації можуть

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

Другий метод (рівномірно розподілені випадкові величини). Більш бажаною альтернативою

є вибір випадкової змінної з рівномірним законом розподілу серед {1, 2, …, 1/p

} (приймаючи для

спрощення, що значення 1/p

ціле. Це досягається, якщо ймовірність маркування для кожного

вхідного пакету дорівнює





pcountp 1 , де count – це кількість немаркованих пакетів, які

надійшли після останнього маркованого пакету. У цьому випадку

Математичне очікування дорівнює









2121 

pXE .

9.2.1.5.

Додаткові завдання роутерів RED

Крім завдань роутерів RED, розгляне них вище, існують окремі завдання щодо схем

уникнення перевантаження.

 Уникнення перевантаження. Якщо роутер RED фактично видаляє пакети, які надходять до

нього, коли середня довжина черги досягає максимального порогового значення, то роутер RED

гарантує, що обчислена середня довжина черги не перевищить це порогове значення. Якщол вага

у процедурі EWMA встановлена правильно, то роутер RED фактично регулює справжню

середню довжину черги. Якщо ж роутер RED встановлює біт у заголовку пакету при

перевищенні середньої довжини черги максимального порогу, а не видаляє пакет, то роутер RED

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

 Придатні часові масштаби. Після повідомлення сполучення про перевантаження шляхом

маркування пакету для роутера минає щонайменше один RTT до того, щоб він міг помітити

зменшення темпу прибуття пакетів. У роутерах RED часовий масштаб для виявлення

перевантаження приблизно узгоджений з часовим масштабом, потрібним сполученню для реакції

на перевантаження. Роутери RED не можуть повідомити сполучення про потребу зменшення їх

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

 Відсутність глобальної синхронізації. Темп, у якому роутери RED маркують пакети, залежить

від рівня перевантаження. Протягом низького перевантаження розтер має низьку ймовірність

маркування кожного вхідного пакету, але коли перевантаження зростає, то зростає також

ймовірність маркування.

 Максимізація глобального відношення перепускної здатності до затримки. При використанні

RED глобальне відношення перепускної здатності до затримки вище, ніж при застосуванні Tail

Drop.

 Справедливість. Однією з цілей механізму уникнення перевантаження є справедливий поділ

частки маркованих пакетів між різними сполученнями, так щоб ця частка для певного сполучення

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

сполученням. Однак роутери RED не чинять намагань для того, щоб кожне сполучення отримало

однакову частку спільної перепускної здатності. Роутери RED забезпечують механізм

ідентифікації рівня перевантаження, а також можуть бути використані для ідентифікації

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

2. Мережі IP.

_______________________________________________________________________________________

___________________________________________________________________________________________________

М. Павликевич. Телекомунікаційні мережі. Навчальний посібник для студентів спеціальності

"Інформаційні мережі зв'язку, 2009.

208

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

протягом періоду перевантаження.

 Придатність для багатьох середовищ. Рандомізований механізм маркування пакетів придатний

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

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

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

Навіть у мережі, де RED сигналізує про перевантаження шляхом видалення пакетів, існують різні

ситуації для TCP/IP, коли видалений пакет не має жодного впливу на будь-яке зменшення

навантаження роутера. Якщо роутер видаляє пакет у сполученні TCP/IP, то це видалення пакету може

бути виявлене джерелом, можливо, після того, як вичерпається таймер повторного пересилання.

Якщо роутер видалить пакет ACK зі сполучення TCP або пакет, не належний до сполучення TCP, то

це видалення пакету може бути не відзначене джерелом. Однак, навіть для перевантаженої мережі з

сумішшю трафіків з перевагою коротких TCP-сполучень або не-TCP-сполучень, роутер RED все ще

регулює середню довжину черги, видаляючи всі вхідні пакети, коли середня довжина черги

перевищує максимальне порогове значення.

9.2.1.6.

Впровадження алгоритму RED

Алгоритм RED може бути ефективно впроваджений з невеликою кількістю інструкцій для

кожного вхідного пакету. Крім того, алгоритм RED не є тісно пов’язаний з пересиланням пакетів і

пов’язані з цим обчислення не здійснюються на шляху, критичному щодо часових характеристик.

Більшість дій алгоритму RED, таких як обчислення середньої довжини черги та ймовірності

маркування пакетів, здійснюються паралельно з пересиланням пакетів або можуть бути здійснені як

низькопріритетні завдання. Це означає, що алгоритм RED не впливає на здатність роутера до обробки

пакетів і цей алгоритм може бути пристосований до вихідних високошвидкісних ліній.

Якщо алгоритм RED маркування пакетів полягає у встановленні біта-вказівника у заголовку

пакету, а не у видаленні вхідного пакету, то встановлення цього біта само по собі додає службове

навантаження до алгоритму. Однак, оскільки роутери RED маркують так мало пакетів, як це

можливе, то додаткове службове навантаження мінімальне.

Роутери RED обчислюють середню довжину черги, базуючись на надходженні пакетів, а не

на часовому інтервалі, тому обчислення середньої довжини черги модифікується, коли пакет

надходить до порожньої черги роутера. Після того, як пакет надійшов до порожньої черги, роутер

обчислює m – кількість пакетів, які можуть бути вислані роутером протягом часу, коли лінія

порожня. Роутер обчислює середню довжину черги так, якби m пакетів надійшли до роутера з

довжиною черги нуль:

де q_time – початковий відлік часу, коли черга порожня, s – типовий час висилання малого пакету. Це

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

протягом певного періоду часу. Після того, як інтервалу часу (time-q_time) обчислений з достатнім

рівнем точності, можна використати table lookup для отримання виразу (1-w

)

(time-q_time)/s

, який сам

повинен бути наближений степінню двійки.

Коли пакет надходить до роутера і середня довжина черги avg перевищує поріг max

, то

вхідний пакет маркується. Це не потребує\ переобчислення ймовірності маркування пакету. Однак

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

то початкова ймовірність маркування пакету обчислується так:

2. Мережі IP.

_______________________________________________________________________________________

___________________________________________________________________________________________________

М. Павликевич. Телекомунікаційні мережі. Навчальний посібник для студентів спеціальності

"Інформаційні мережі зв'язку, 2009.

209

Параметри max

, max

і min

фіксовані і визначаються попередньо. Значення max

і min

визначені

бажаними границями середньої довжини черги і можуть гнучко змінюватися. Однак фіксований

параметр max

повинен бути встановлений для діапазону значень. Зокрема, max

можна вибрати так,

щоб C

була степінню двійки.

Ефективний алгоритм (у псевдокоді) RED наведений на рис. 9.7.

Рис. 9.7. Ефективний алгоритм RED.

9.2.2. Алгоритм ECN

Альтернативним механізмом для роутерів є завантаження позначених пакетів з явним

прапорцем (бітом) ознайомлений з перевантаженням (Congestion Experienced – CE) у припущенні,

що надавач буде бачити і реагувати на це встановлення прапорця у спосіб, порівняльний до реакції на

видалення окремого пакету. Цей механізм, який називають явним оповіщенням про перевантаження

(Explicit Congestion Notification – ECN), використовує 2-бітову схему, претендуючи на використання

бітів 6 і 7 поля TOS IPv4 (або двох бітів CU (Currently Unused) поля Differetiated Services). Біт 6

встановлюється надавачем для позначення того, що це система транспорту, оснащена ECN (ECT-біт).

Біт 7 – це біт CE і він встановлюється роутером, коли середня довжина черги перевищує

сконфігурований пороговий рівень.

Алгоритм ECN полягає в тому, що активний роутер буде здійснювати RED, як описано вище.

Після того, як пакет вибрано, роутер може позначити біт CE у пакеті, якщо біт ECT встановлений; в

іншому випадку, він видалить вибраний пакет (рис. 9.8).

Взаємодія з TCP впроваджена дещо далі. Початкове TCP-підтвердження SYN включає

додаткову можливість використання прапорців ECN-echo (ECE) і зменшене вікно перевантаження

(Congestion Window Reduced – CWR), що дозволяє довільній системі узгоджувати зі своїм

відповідником, котрий з них буде обслуговувати пакети зі встановленим бітом CE протягом

пересилання даних (див. рис. 8.5). Надавач встановлює біт ECN у всі пакети, які він висилає. Якщо

надавач приймає пакет TCP з прапорцем ECN-echo, встановленим у заголовку TCP, то він регулює

своє вікно перевантаження так, ніби він здійснив швидке відновлення внаслідок втрати окремого

2. Мережі IP.

_______________________________________________________________________________________

___________________________________________________________________________________________________

М. Павликевич. Телекомунікаційні мережі. Навчальний посібник для студентів спеціальності

"Інформаційні мережі зв'язку, 2009.

210

пакету. Наступний висланий пакет буде мати встановлений TCP-прапорець CWR для вказівки

приймачу, що він повинен відреагувати на перевантаження. Додатковим попередженням є те, що

надавач буде реагувати таким чином щонайбільше один раз протягом кожного інтервалу RTT. Далі,

пакети TCP з встановленим прапорцем ECN-echo не будуть впливати на надавач всередині того

самого інтервалу RTT. Приймач буде встановлювати прапорець ECN-echo у всі пакети, якщо він

прийме пакет зі встановленим бітом CE. Це буде продовжуватися доти, доки він не прийме пакет зі

встановленим бітом CWR, який вказує, що надавач відреагував на перевантаження. Прапорець ECT

встановлюється тільки в пакетах, які містять дані. Пакети ACK TCP, які не містять даних, будуть

вислані з невстановленим бітом ECT. Сполучення не потребує очікувати на приняття трьох

здубльованих ACK для виявлення умови перевантаження. Замість цього приймач повідомлений про

зародження умови перевантаження через явне встановлення відповідного біта вказівки, який

повертається до надавача у відповідному ACK.

Рис. 9.8. Операції ECN.

Моделювання ECN з використанням функції маркування RED показує дещо кращу

перепускну здатність у порівнянні з конфігуруванням RED з функцією видалення пакетів. Однак

широке впровадження ECN не очікується в найближчому майбутньому, зокрема, в контексті

протоколу IPv4. На даному етапі відсутня явна стандартизація полів всередині заголовка данограми

IPv4, в якому переноситься ця інформація, і база впровадження IP тепер настільки широка, що будь-

які модифікації семантики полів у заголовку данограми IPv4 мусять бути дуже старанно розглянені,

щоб змінена інтерпретація полів не привела до неправильної поведінки у старших версіях стеку TCP

або у старших впровадженнях програмного забезпечення роутерів.

ECN забезпечує певен рівень покращення характеристик порівняно з схемою вилучення

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

повторним пересиланням пакетів та регулюванням вікна перевантаження в RED і регулюванням

вікна перевантаження в ECN. Найбільш помітне покращення, відзначене в експериментах з

моделюванням ECN, виявляється для коротких транзакцій TCP, наприклад, при роботі з Web, коли

вилучення пакетів алгоритмом RED з початкового потоку даних може викликати шестисекундну

затримку повторного пересилання. Порівняно з цим ECN дозволяє здійснювати пересилання без цієї

затримки.

Головною проблемою при ECN є потреба зміни операцій в обидвох роутерах і програмному

забезпеченні стеку TCP для пристосування до операцій ECN. Хоч пропозиції ECN старанно

побудовані, щоб дозволити суттєво нескоординоване впровадження до Internet без негативних

побічних ефектів, однак ефективність ECN щодо покращення загальної перепускної здатності мережі

буде безсумнівною тільки після того, як цей підхід буде широко сприйнятий. Оскільки Internet

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

може минути декілька років, перш ніж ECN буде широко впроваджене як у програмному

забезпеченні станцій, так і в системах роутінгу Internet. З другого боку, RED може бути швидше

впроваджено в Internet, бо він вимагає тільки локальної модифікації поведінки роутерів і залежить від

наявної реакції TCP на вилучення пакетів.