RED дозволяє запобігти тотальній синхронізації, вибірково знищуючи пакети певних джерел. А оскільки за чисто ймовірнисних причин великі пакети знищуються частіше ніж малі, то можна сподіватися на справедливий розподіл смуги пропуску. Звичайно, селективне знищення пакетів приводить до подібного результату, тільки коли джерело має який-небудь інтелектуальний механізм контролю за швидкістю передачі.
RED в мережах ATM.
Все вищезазначене відноситься і к роботі протоколу TCP через ATM. Тому алгоритм RED можна ефективно використовувати для керування передачею трафіка TCP/IP в мережах ATM. Крім того, в мережах ATM він використовується в якості механізму керування трафіком, що доповнює вже існуючі методи.
Керування трафіком є ключовим компонентом стабільної роботи ATM-мереж. В загальному випадку є два типи керування: превентивний та адаптивний.
Превентивний контроль базується на дотриманні трафік-контракту. Джерело трафіка повинно відповідати заздалегідь визначеним рамкам якості обслуговування за допомогою, наприклад, широковідомих механізмів контролю Leaky Bucket та Virtual Scheduling. Превентивний контроль застосовується в основному для CBR (сервіс класу A) та VBR (сервіс класу B), в яких характеристики трафіку відомі або піддаються прогнозуванню.
Адаптивний контроль заснований на використанні вільної смуги пропуску. Звичайно він реалізується для ABR (сервіс класу C) та UBR (сервіс класу D), які не мають жорстких вимог до якості обслуговування. Адаптивний контроль здійснюється за допомогою зворотнього зв’язку між джерелом та комутатором ATM, який може бути явним (для передачі інформації про перевантаження використовуються спеціальні чарунки, як в ABR) або прихованим (поведінка джерела трафіка змінюється у відповідності до змін поведінки мережі).
Алгоритм RED в мережах ATM використовує прихований зворотній зв’язок для повідомлення про перевантаження шляхом вибіркового знищення чарунок користувача. Замість того, щоб чекати перевантаження і переповнення буферу, наслідком чого стане знищення всіх даних, що надходять, RED знищує частину чарунок. Їх кількість і частота знищення визначаються параметром, що має назву ймовірність знищення. Цей параметр розраховується кожен раз у відповідності до поточного стану ресурсів ATM-комутатора, тобто фактично визначається довжиною черги на обслуговування трафіка в ATM-мережі.
Середня довжина черги (QueueLength) визначається так:
QueueLength=(1-1/2n)*PreviousQueueLength+CurrentQueueLength*1/2n.
Тут PreviousQueueLength – довжина черги на попередньому підрахунку; CurrentQueueLength – поточна довжина черги; n – ваговий коефіцієнт (n>=1), який визначає адміністратор мережі з наступних міркувань.
Якщо n має мале значення, середня довжина черги QueueLength фактично визначається поточною довжиною черги CurrentQueueLength. Тоді алгоритм RED чітко і швидко реагує на будь-які зміни поточної довжини черги, що дозволяє ATM-комутатору практично миттєво позбавитись від зайвих чарунок при найменшій загрозі перевантаження. Проте при дуже малих значеннях nRED почне необгрунтовано скидувати чарунки навіть при невеликих часових збільшеннях черг, які не є небезпечними і можуть бути оброблені без втрат.
Якщо коефіцієнт n має велике значення, середня довжина черги QueueLength стає функцією від попередньої довжини чеги PreviousQueueLength. Алгоритм RED досить повільно реагує на зміни довжини черги, що дозволяє ATM-комутаторам неначе згладжувати “піки” та ”провалля” трафіка без знищення чарунок. Але при дуже великих значеннях nRED може стати настільки повільним, що буде продовжувати знищення чарунок, навіть коли довжина черги стане менше за мінімальний поріг спрацювання цього алгоритму.
Роботу алгоритму RED можна описати так:
Якщо середня довжина черги QueueLength менше або дорівнює мінімально допустимому значенню порога спрацювання MinThreshold алгоритму RED (QueueLength<MinThreshold), то чарунка, що надходить, буде обслуговуватися ATM-комутатором. Якщо середня довжина черги QueueLength знаходиться в межах деякого діапазону (MinThreshold<QueueLength<MaxThreshold), то RED почне знищувати деяку частину чарунок. Доля чарунок, що будуть знищуватись, визначається значенням ймовірності знищення, яке розраховується у відповідності з станом ресурсів комутатора. Перерахування ймовірності знищення та сам процес знищення чарунок буде відбуватися до тих пір, поки значення середньої довжини черги QueueLength не буде нищим за мінімальний поріг MinThreshold.
Ймовірність знищення пакетів підраховується так:
Pa=Pb/(1-Count*Pb)
Тут: Pa– ймовірність знищення, Pb=Pmax * (QueueLength - MinThreshold)/( MaxThreshold - MinThreshold) * PacketSize/MaxPacketSize, де
Pmax– максимальна ймовірність знищення чарунок; Count – кількість чарунок, що є в черзі на момент останнього знищення; PacketSize – довжина пакету протоколу, інкапсульованого в ATM; MaxPacketSize – максимальна довжина пакету, інкапсульованого в ATM.
Якщо середня довжина черги QueueLength більше або рівна максимальнодопустимому значенню MaxThreshold (QueueLength >=MaxThreshold), то чарунка, що надійшла на вхід комутатора обов’язково буде знищена.
Як видно з формул, ймовірність знищення чарунок залежить від довжини інкапсульованих пакетів. Відповідно, великі пакети (наприклад, при перекачуванні файлів по FTP) будуть знищуватись частіше, ніж маленькі (наприклад, ті, що передаються по Telnet).
В мережах ATM використовуються дві модифікації алгоритму RED: C-RED(CellRED) працює з кожною чарункою, P-RED (PacketRED) – з групою чарунок, що утворюють AAL5 PDU.
Алгоритм C-RED враховує кожну окрему чарунку і, таким чином, має повну картину стану мережі в кожний поточний момент. Недолік даного алгоритму – складність його реалізації при роботі на великих швидкостях. У високошвидкосних мережах ATM процедура перерахування середньої довжини черги QueueLength при появі кожної нової чарунки може стати достатньо складною і дорогою, тому в них звичайно використовується P-RED.
Алгоритм P-RED працює з групою чарунок, які утворюють один пакет, інкапсульований в ATM (наприклад, IP-пакет). Перерахування середньої довжини черги здійснюється для всіх чарунок пакету лише один раз – в момент надходження першої чарунки. P-RED не є таким гнучким, як C-RED, проте він може бути реалізований на найшвидших каналах.
Серед недоліків алгоритму RED при роботі в мережі ATM слід відзначити такий. RED відкидає лише одну або декілька чарунок з тих, які утворюють вихідний пакет. Передача по мережі інших чарунок (неповного пакету) продовжується, вони будуть знищені лише в приймачі на рівні адаптації AAL5. Цю проблему дозволяє вирішити алгоритм PartialPacketDiscardPPD, який забезпечує видалення неповних пакетів.
В алгоритмі RED ймовірність знищення пакету є функцією від його довжини. Розміри пакетів, що передаються, визначаються динамічно в процесі передачі через ATM-комутатор. В AAL5 границі пакетів визначаються полями PTI в заголовку чарунки, що відмічає останню чарунку пакету. Оскільки визначити розмір ще не прийнятого пакету неможна, то його вважають рівним розміру останнього пакету, що був прийнятий по даному віртуальному каналу. Таким чином, можна використовувати залежність знищення чарунки від кількості чарунок, що утворюють вихідний пакет AAL5 PDU, тобто від розміру пакету (що не має місце в алгоритмі EPD).
У випадку широкого діапазону коливання навантаження алгоритм RED може не відреагувати на переповнення буферу, тому він звичайно застосовується з алгоритмом EPD. Алгоритм EPD здійснює не вибіркове знищення однієї чарунки, а відкидає цілий пакет, що дозоляє різко знизити навантаження на ATM-комутатор.
При появі першої чарунки ATM-комутатор аналізує (використовуючи поле PTI заголовку), чи є вона першою чарункою пакету AAL5 PDU. Якщо чарунка є початком пакету, ATM-комутатор перераховує середню довжину черги QueueLength (перерахування здійсняється лише для першої чарунки пакету). Якщо довжина черги менше або дорівнює порогу спрацювання алгоритму RED (QueueLength=<MinThreshold), то ця і всі наступні чарунки, що належать цьому пакету, будуть по мірі надходження обслуговуватися ATM-комутатором. Якщо середня довжина черги QueueLength знаходиться в межах MinThreshold<QueueLength<MaxThreshold, то підраховується ймовірність знищення чарунок, система переходить до стану знищення чарунок з частотою, визначеною ймовірністю знищення.
Може виникнути слушне питання: навіщо використовувати алгоритм RED, який підраховує ймовірність знищення чарунок в пакеті, коли алгоритм PPD, що починає працювати слідом, знищує всі залишки пакету, не зважаючи на будь-які зміни ймовірності знищення. Основним плюсом алгоритму RED є можливість підрахування для кожного віртуального з’єднання ймовірності знищення чарунок в залежності від розміру пакету (AAL5), що передається по даному віртуальному з’єднанню. Чим більше пакети, тим вища ймовірність їх знищення. Це дозволяє справедливо розподілити смугу пропуску між потоками даних різних користувачів, що не можна зробити, використовуючи алгоритми EPD/PPD самостійно.
Нарешті, якщо довжина черги перевищує допустиме значення MaxThreshold (QueueLength> MaxThreshold), то в роботу відразу включається алгоритм EPD, який дозволяє швидко і ефективно зняти перевантаження шляхом одночасного знищення великої кількості чарунок.
Ефективне використання пропускної здатності існуючих мереж TCP/IP та ATM є одним з основних питань, що стоять перед провайдерами та вироблювачами апаратури. В зв’язку з цим настільки великий інтерес до різних методів підвищення пропускної здатності. Алгоритм RED рекомендований до застосування в Internet (RFC 2309); на сьогодні він став практично стандартною функцією маршрутизаторів TCP/IP і комутаторів ATM.
Список використаної літератури:
1. М.Гук. Сети NetWare 3.12-4.1. -Санкт-Петербург: Питер, 1997.- 432с.
2. А.И.Гусева. Технология межсетевых взаимодействий. -Москва: Диалог-Мифи, 1997.- 272с.
3. О.Алленов. “Алгоритм RED: красный свет для лишних пакетов”. //Сети, 1998, № 11