Національний університет “ Києво-Могилянська Академія ” Реферат з курсу “ Інтелектуальні мережі ”
на тему:
“ Технологія ATMта алгоритм RED” Студентки 4-го курсу
департаменту
комп’ютерних технологій Фіялка Світлани Київ-1999 Зміст
Технологія ATMта її характеристики……………………………………3 ст.
Алгоритм RED: червоне світло для зайвих пакетів………….………..5 ст.
REDв мережах TCP/IP………………………………………….…….5 ст.
REDв мережах ATM…………………………………………………………6 ст.
Що ж таке ATM?ATMабоAsynchronous Transfer Mode (Режим асинхронної передачі) – це технологія комутації пакетів, що формує ядро Broadband ISDN або Broadband Integrated Services Digital Network (Багатофункціональна цифрова мережа) і забезпечує передачу цифрових, голосових і мультимедійних даних одночасно через одні і тіж лінії. Спочатку швидкість передачі була визначена 155 Мбіт/с, потім 662 Мбіт/с і планується до 2.488 Гбіт/c. ATMвикористовується як в локальних, так і глобальних мережах, успішно застосовується для зв’язку локальних мереж, сильно віддалених одна від одної.
Загальні характеристики ATM:
Лінії зв’язку – оптичні, локальні і довгі. Довгі лінії можуть бути виділеними (арендуємими) та коммутаційними.
Забезпечення паралельної передачі. Кожний вузол може мати виділене з’єднання з будь-яким іншим вузлом.
Робота завжди на максимальній швидкості.
Використання пакетів фіксованої довжини — чарунка по 53байти.
Коррекція помилок і маршрутизації на апаратному рівні (частково завдяки фіксованому розміру чарунок).
Одночасна передача даних, відеоінформації та голосу. Фіксований розмір чарунок забезпечує рівномірний голосовий потік.
Легкість балансування завантаження. Комутація пакетів дозволяє при необхідності підвищення пропускної можливості встановити множину віртуальних ланцюгів між передатчиком та приймачем.
Типи фізичних інтерфейсів. Інтерфейс користувача UNI(User Network Interface), визначений ATM-форумом, допускає різні типи фізичного інтерфейсу:
SONETабо Synchronous Optical Network (Стандарт ANSIдля оптоволоконних мереж), ОС-3, STS-3або STM-1 в термінології CCITT (Consultative Committee on International Telephone and Telegraph – Міжнародний комітет стандартизації телефонного і телеграфного зв’язку), 155.52 Мбіт/с
DS3, 44.736 Мбіт/с
100 Мбіт/с з кодуванням 4В/5В
155 Мбіт/cз кодуванням 8В/10В Всі ці інтерфейси використовують оптоволокно, хоча розробляються варіанти стандартів на витковій паріUTP-3 або Unshielded Twisted Pair (Неекранована виткова пара проводів). Сервіси. Для різних видів інформації (голос, відеоінформація, дані), що передаються за допомогою ATM, визначені такі класи сервісів:
клас Aвикористовується для передачі з постійною швидкістю потоку даних (Constant Bit Rate – CBR). Він забезпечує емуляцію комутуємого каналу, підходить для голосових даних.
клас Bвикористовується для передачі з змінною швидкістю потоку даних (Variable Bit Rate – VBR), наприклад, для відеоконференцій.
клас Cвикористовується для передачі даних з встановленням з’єднання (ABR).
клас Dвикористовується для передачі даних без встановлення з’єднання (UBR).
Як формується чарунка?Для кожного класу сервісу встановлені протокольні блоки даних PDU(Protocol Data Unit), які є блоками даних для чарунок. Кожний PDUмістить 48 октетів– груп по 8 біт (разом 48 байт), що використовуються для заголовку, концевика і власне даних (Payload в термінології ATM). Інші 5 октетівчарунки (разом 5 байт) складають заголовок ATM. В нього входять 4 бітазагального керування потоком, 8 бітідентифікатора вітуального шляху VPI (Virtual Path Identifier), 16 бітідентифікатора віртуального каналу VCI (Virtual Channel Identifier), 3 бітавказівника типу даних (Payload Type), 1 бітCLP(Cell Loss Priority) та 8 бітHEC (Header Error Control). БітCLPвизначає можливість відкидання даної чарунки у випадку напруженого рівня трафику.
В ATMрозрізняють 3 плани (групи діяльності):
план керування, на якому встановлюються і обслуговуються виклики і з’єднання
план користувачів, на якому відбувається звичайний обмін даними
план менеджменту, який координує всі 3 плани і керує ресурсами
Як же відбувається передача?Потоки даних від різних типів сервісів (голос, відеоінформація, дані і чарунки від ATM-станцій) оброблюються сервісами відповідних класів і “розфасовуються” у 48-октетні PDU, які вкладаються у чарунки і мультиплексуються у потік чарунок для передачі. (Саме слово мультиплексування означає комбінування окремих сигналів в єдину швидкісну передачу). За допомогою ATMв носій передаються чарунки з багатьох джерел. Вони можуть змішуватись, проте кожна має свою цільову адресу, а саме: чарунки містять ідентифікатори віртуальних каналів і шляхів, які використовуються для досягнення адресата призначення (перші 5 октетів чарунки). ATM-комутатор використовує інформацію ідентифікаторів для направлення чарунок у відповідний порт. Потік чарунок кодується і передається через фізичне середовище передачі ATM-мережі. При мультиплексації сигнали надходять по порядку через регулярні проміжки часу. Тобто – всі чарунки за часом і розміром однакові. На приймальному боці відбуваються зворотні перетворення і потоки даних передаються на вихід відповідним сервісам. --PAGE_BREAK--
Плюси ATM.
ATM комбінує мультиплексацію і комутацію пакетів в одному універсальному методі передачі даних. Він підтримує передачу даних в локальних мережах, а також передачу голосової і відеоінфомації. Так як чарунки мають невеликий розмір, вони обробляються швидко. Затримка на перемикання пакетів невелика. Це має важливе значення для передачі мови і відео, які дуже залежать від часу.
ATM– це транспортний протокол, який працює на підрівні MACрівня зв’язку даних. Завдяки цьому він може працювати над багатьма топологіями фізичного рівня, на відміну від FDDI(Fiber Distributed Data Interface – використовується для міжмережної передачі даних, використовує топологію подвійного кільця). ATMне базується на якомусь конкретному протоколі. Він може відображати будь-який вид пакету в 53-байтову чарунку і передавати її по кабелю або глобальній мережі.
ATMможе використовуватися в якості фізичного носія для організації глобальних мереж SONET, які телефонні компанії використовують в телефонних лініях і мережних комунікаціях.
Стандарт ATMне обмежений швидкістю передачі як FDDI (працює зі швидкістю 100 Мбіт/с).
Малий розмір чарунок не потребує спеціальної обробки як в FDDI.
Алгоритм RED: червоне світло для зайвих пакетів
Якщо вже було згадано про біт CLP (Cell Loss Priority), який визначає можливість відкидання даної чарунки у випадку напруженого трафіку, то доречною буде і розповідь про так званий алгоритм REDабо Random Early Detection (Своєчасне знаходження перевантаження).
Дуже широко застосовується для передачі трафіка локальних мереж і Internet зазначений вище тип сервісу UBR(клас D), що зумовлено його простою реалізацією. До трафіка не пред’являються які-небудь жорсткі вимоги і мережа просто передає стільки даних користувача, скільки може. Відповідно “поведінка” трафіка в мережі ATMстає неконтрольованою, що призводить до небажаних наслідків, таких як перевантаження і втрата даних.
Для поліпшення функціональних можливостей UBRв нього було введено ряд механізмів керування трафіком, в тому числі EPD(раннє відкидання пакетів) та PPD (відкидання залишків пакетів). Даний тип сервісу отримав назву UBR+.Крім того існує ще так званий алгоритм RED.Спочатку він був запропонований для пакетних мереж: він добре себе зарекомендував при роботі с протоколом TCP.
REDв мережахTCP/IP
TCP – протокол, що орієнтований на з’єднання, в зв’язку з чим він має ряд особливостей. TCPпочинає свою роботу з процедури встановлення з’єднання і узгодження (синхронізації) основних параметрів, таких як розмір вікна підтвердження та максимальний розмір пакету. Після синхронізації TCPвідразу посилає стільки пакетів, скільки допускає розмір вікна підтвердження.
Подібний вибух навантаження не є небезпечним для швидкісних мереж. Проте в комплексних мережах, де можуть існувати низькошвидкісні ділянки і перевантажені комутатори, непередбачена поява великої кількості пакетів може призвести до істотного зниження пропускної здатності (що зумовлено втратами трафіка і наступною його ретрансляцією). В сучасних реалізаціях протоколу TCPуникнути цих неприємностей дозволяє механізм Slow Start.
У випадку використання Slow Startпротокол TCP, після синхронізації пакетів, спочатку відсилає один пакет, потім (коли отримано підтвердження на його доставку) – два, чотири, і так до тих пір, поки кількість пакетів, що передаються одночасно, не буде відповідати розмірам вікна підтвердження. При втраті хоча б одного з пакетів джерело починає процедуру Slow Start знову. В різних реалізаціях TCP(TCP Tahoe, TCP Reno) кількість пакетів, з якої починається передача, і коефіцієнт збільшення кількості пакетів можуть динамічно залежати від часу поширення пакетів (Round-trip time – RTT).Це дає можливість адекватно реагувати на стан мережі.
Алгоритм RED дозволяє контролювати навантаження мережі за допомогою вибіркового випадкового знищення деяких пакетів, що спонукає протоколи, схожі на TCP, зменшувати швидкість передачі. При втраті хоча б одного пакету протокол TCPпочинає процедуру Slow Start спочатку: це знижує об’єм трафіку, що надходить в мережу. Найдоцільніше не чекати повного перевантаження мережі (тоді буде видалений весь трафік), а вже на підступах до небезпечної ділянки вибірково знищувати окремі пакети, інформуючи тим самим джерела навантаження про поточну пропускну здатність мережі.
Крім того, алгоритм REDв мережах TCP/IPдопомагає позбавитись від проблеми, відомої під назвою “тотальна синхронізація”. Вона виникає, коли декілька джерел, що працюють через один і той же перевантажений сегмент мережі, дізнаються про втрати пакетів. Як наслідок, ці джерела одночасно зменшують швидкість, а потім одночасно її нарощують, що призводить до нового перевантаження і втрачання пакетів. Таким чином, стан мережі періодично змінюється від простою до перевантаження.
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-мережі. продолжение
--PAGE_BREAK--
Середня довжина черги (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
Ймовірність знищення пакетів підраховується так:
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 (Cell RED)працює з кожною чарункою, P-RED(Packet RED)– з групою чарунок, що утворюють AAL5 PDU.
Алгоритм C-REDвраховує кожну окрему чарунку і, таким чином, має повну картину стану мережі в кожний поточний момент. Недолік даного алгоритму – складність його реалізації при роботі на великих швидкостях. У високошвидкосних мережах ATMпроцедура перерахування середньої довжини черги QueueLength при появі кожної нової чарунки може стати достатньо складною і дорогою, тому в них звичайно використовується P-RED.
Алгоритм P-REDпрацює з групою чарунок, які утворюють один пакет, інкапсульований в ATM(наприклад, IP-пакет). Перерахування середньої довжини черги здійснюється для всіх чарунок пакету лише один раз – в момент надходження першої чарунки. P-REDне є таким гнучким, як C-RED, проте він може бути реалізований на найшвидших каналах.
Серед недоліків алгоритму REDпри роботі в мережі ATMслід відзначити такий. REDвідкидає лише одну або декілька чарунок з тих, які утворюють вихідний пакет. Передача по мережі інших чарунок (неповного пакету) продовжується, вони будуть знищені лише в приймачі на рівні адаптації AAL5. Цю проблему дозволяє вирішити алгоритм Partial Packet Discard PPD,який забезпечує видалення неповних пакетів.
В алгоритмі RED ймовірність знищення пакету є функцією від його довжини. Розміри пакетів, що передаються, визначаються динамічно в процесі передачі через ATM-комутатор. В AAL5границі пакетів визначаються полями PTIв заголовку чарунки, що відмічає останню чарунку пакету. Оскільки визначити розмір ще не прийнятого пакету неможна, то його вважають рівним розміру останнього пакету, що був прийнятий по даному віртуальному каналу. Таким чином, можна використовувати залежність знищення чарунки від кількості чарунок, що утворюють вихідний пакет AAL5 PDU, тобто від розміру пакету (що не має місце в алгоритмі EPD).
У випадку широкого діапазону коливання навантаження алгоритм REDможе не відреагувати на переповнення буферу, тому він звичайно застосовується з алгоритмом EPD. Алгоритм EPDздійснює не вибіркове знищення однієї чарунки, а відкидає цілий пакет, що дозоляє різко знизити навантаження на ATM-комутатор.
При появі першої чарунки ATM-комутатор аналізує (використовуючи поле PTIзаголовку), чи є вона першою чарункою пакету AAL5 PDU. Якщо чарунка є початком пакету, ATM-комутатор перераховує середню довжину черги QueueLength (перерахування здійсняється лише для першої чарунки пакету). Якщо довжина черги менше або дорівнює порогу спрацювання алгоритму RED (QueueLength=
Може виникнути слушне питання: навіщо використовувати алгоритм RED, який підраховує ймовірність знищення чарунок в пакеті, коли алгоритм PPD, що починає працювати слідом, знищує всі залишки пакету, не зважаючи на будь-які зміни ймовірності знищення. Основним плюсом алгоритму REDє можливість підрахування для кожного віртуального з’єднання ймовірності знищення чарунок в залежності від розміру пакету (AAL5), що передається по даному віртуальному з’єднанню. Чим більше пакети, тим вища ймовірність їх знищення. Це дозволяє справедливо розподілити смугу пропуску між потоками даних різних користувачів, що не можна зробити, використовуючи алгоритми EPD/PPD самостійно.
Нарешті, якщо довжина черги перевищує допустиме значення MaxThreshold (QueueLength>MaxThreshold), то в роботу відразу включається алгоритм EPD, який дозволяє швидко і ефективно зняти перевантаження шляхом одночасного знищення великої кількості чарунок.
Ефективне використання пропускної здатності існуючих мереж TCP/IPта ATMє одним з основних питань, що стоять перед провайдерами та вироблювачами апаратури. В зв’язку з цим настільки великий інтерес до різних методів підвищення пропускної здатності. Алгоритм REDрекомендований до застосування в Internet (RFC 2309); на сьогодні він став практично стандартною функцією маршрутизаторів TCP/IPі комутаторів ATM.
Список використаної літератури:
М.Гук. Сети NetWare 3.12-4.1. -Санкт-Петербург: Питер, 1997.- 432с.
А.И.Гусева. Технология межсетевых взаимодействий. -Москва: Диалог-Мифи, 1997.- 272с.
О.Алленов. “Алгоритм RED: красный свет для лишних пакетов”. //Сети, 1998, № 11