ДонНТУ   Портал магістрів

Реферат за темою випускної роботи

Зміст

Вступ

Сучасні засоби комунікацій використовують переважно канали зв'язку з пакетною комутацією. Це дозволяє підвищити ефективність використання каналів, проте призводить до зниження надійності доставки інформації. При перевантаженні каналу з пакетною комутацією можлива ситуація, коли пакет на вході каналу не поміститься у вхідний буфер, а буде відкинутий. Для забезпечення гарантованої доставки по каналах без гарантованої доставки були розроблені спеціальні протоколи. Один з найбільш популярних – це протокол TCP із стека протоколів TCP/IP. Він проектувався для доставки даних служб обміну файлами, електронної пошти і тому подібне. Для цих служб основною вимогою була коректна доставка інформації. При цьому час доставки не був критичним чинником. Розвиток мультимедійних технологій поставив завдання доставки повідомлень при дотриманні високих вимог якості обслуговування: мала затримка і мала варіація затримки. Це завдання вирішується за допомогою регулювання швидкості передачі і прийому повідомлень.

Управління швидкістю передачі здійснюється за допомогою алгоритму управління перевантаженням (TCP congestion control algorithm). Саме він управляє шириною ковзаючого вікна і контролює інтенсивність передачі даних tcp-передавачем. У нім реалізовані обробники наступних подій: прийом відповіді-підтвердження доставки від приймача, втрата пакету в буфері маршрутизатора (на дорозі доставки пакету), перевищення часу чекання відповіді приймача. Протокол TCP проектувався для розподілених мереж із значним часом доставки. Спочатку в протокол був закладений простий алгоритм з мінімальним обчислювальним навантаженням на процесор системи. Продуктивність процесорів за останніх 30 років виросла багато разів, пропускна спроможність каналів зв'язку збільшилася в тисячі разів, а час доставки для високошвидкісних локальних і глобальних мереж складає долі мікросекунд. Відповідно до технічного прогресу розвивався і протокол TCP.

1. Актуальність теми

Проблема перевантаження в мережах TСР/ІР виникає у разі, коли кількість переданих даних починає наближатися до значення допустимої пропускної спроможності мережі. При цьому погіршуються основні показники якості обслуговування. Ці погіршення можуть виражатися в збільшенні числа втрачених пакетів і часу затримок. Управління перевантаженнями є актуальним завданням, оскільки кількість кінцевих користувачів глобальної мережі, а, отже, об'єми переданих даних, постійно збільшуються. Зростає також доля мультимедійного трафіку реального часу, вплив перевантажень на який особливо критично. Завдання механізмів управління перевантаженнями полягає в тому, щоб підтримувати кількість даних, переданих по мережі, нижче за рівень, при якому пропускна спроможність мережі починає різко падати, обмежуючи потоки вхідного і вихідного трафіку.

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

Магістерська робота присвячена актуальній науковій задачі оцінювання ефективності роботи алгоритмів для боротьби з з перевантаженням протоколів транспортного рівня стека ТСР/ІР. У якості математичного моделі викоритстовується гідродинамична модель потоку, яка дозволяє врахувати всі особливості роботи противовантижних алгоритмів.

2. Мета і задачі дослідження та заплановані результати

Метою дослідження є моделювання та оцінка ефективності роботи алгоритмів для боротьби з перевантаженням протоколів транспортного рівня стека ТСР/ІР.

Основні задачі дослідження:

  1. Проаналізувати основні алгоритми, які використовуються в протоколі ТСР для боротьби с перевантаженнями.
  2. Розробити реалізацію математичної гідродинамічної моделі для обраних противоперевантажних алгоритмів.
  3. Провести моделювання роботи обраних алгоритмів при різних вхідних параметрах.
  4. На основі отриманих результатів провести аналіз та порівняти роботу різних алгоритмів у однакових умовах.

Об'єкт дослідження: мультисервісна мережа

Предмет дослідження: алгоритми для боротьби з перевантаженням протоколів транспортного рівня стека ТСР/ІР

3. Наукова новизна

Наукова новизна магістерської роботи полягає в тому, що запропонована методика комплексної оцінки ефективності алгоритмів для боротьби з перевантаженням протоколів транспортного рівня стека ТСР/ІР

4. Аналіз існуючих досліджень та публікацій

Проблема перевантаження в каналах зв’язку мереж TСР/ІР є досить актуальною на даний момент, тому їй присвячена велика кількість робіт, в якіх розкривається сутність даної проблеми, причини її виникнення та шляхи вирешення [1, 2,7,8,9].

Дослідження роботи противоперевантажних алгоритмів транспортного рівня стеку TСР/ІР описано в роботах [3 - 5, 10].

Оскільки для спостерігання поведінки алгоритмів для боротьби з перевантаженням необхідно використовувати таку математичну модель, яка буде враховувати всі особливості роботи алгоритму, то на даний час дуже розповсюдженою є гідродинамічна модель потоку (fluid flow model), яка наведена в роботі [6].

5. Моделювання та оцінка ефективності алгоритмів TCP Reno та TCP Vegas

На даний момент існує цілий ряд реалізацій методів управління перевантаженнями в протоколі TCP, що розрізняються в застосовності до вирішень різних завдань. Наприклад, TCP Vegas дозволяє враховувати стан каналу зв'язки, TCP Westwood враховує високий рівень втрат в каналах зв'язку, TCP Hamilton використовується для локальних мереж з високою пропускною спроможністю. Найбільш розповсюдженими реалізаціями протоколу є TCP Reno та TCP Vegas, які будемо використовувати для подальшого дослідження роботи противоперевантажних алгоритмів.

5.1 Аналіз роботи алгоритмів TCP Reno та TCP Vegas

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

TCP Reno має два етапи зміни розміру вікна:

1) фаза повільного старту

2) фаза уникнення перевантаження

Коли відправник отримує підтвердження доставки в момент часу t + tA [с] поточне значення розмір вікна перевантаження cwnd(t) перетворюється на cwnd(t + tA) відповідно (1):

Формула 1

де ssth(t) [пакет] – значення порогу, при якому TCP йде від фази повільного старту в фазу уникнення перевантаження .

Коли внаслідок таймаута виявлено втрати пакетів, значення cwnd(t) і ssth(t) оновлюються наступним чином:

Формула 2

З іншого боку, коли TCP виявляє втрати пакетів згідно алгоритму швидкої передачі, cwnd(t) і ssth(t) оновлюються іншим чином:

Формула 3

TCP Reno потім переходить у фазі швидкого відновлення. На цьому етапі розмір вікна збільшується на один пакет, коли отримується дублююче підтвердження. З іншого боку, cwnd(t) дорівнює ssth(t) при надходженні підтвердження на пакет, що надіслане знову.

У разі таймаута cwnd(t) ssth(t) приймають вигляд (2).

Як можна легко побачити, механізм уникнення перевантажень, прийнятий в TCP Reno, викликає періодичні коливання через постійне оновлення розміру вікна. Швидкість, з якою кожне з’єднання оновлює розмір вікна залежить від циклу затримки з'єднання. Отже з’єднання із коротшим затримки може оновити розмір вікна швидше, ніж з’єднання з більшим часом затримки і тим самим несправедливо вкрасти частку пропускної здатності[4].

TCP Vegas використовує різницю між очікуваною та фактичною швидкістю потоків для оцінки пропускної здатності мережі. Ідея в тому, що коли мережі не перевантажена, фактична швидкість потоку буде близький до очікуваної. В іншому випадку фактична швидкість потоку буде менше, ніж очікувана швидкість потоку. TCP Vegas за допомогою цієї різниці швидкостей потоку, оцінює рівень заторів у мережі та відповідним чином оновлює розмір вікна. Звернімо увагу, що ця різниці швидкостей потоку можуть бути легко перекладений на різницю між розмір вікна і кількістю визнаних пакетів у часі, використовуючи рівняння:

Формула 4

де Expected – очікувана швидкість, Actual – фактичнa швидкість, BaseRTT – мінімальний час проходження сигналу туди та назад при першому з’єднанні.

Деталі алгоритму: 1. Джерело обчислює очікувану швидкість потоку за формулою

Формула 5

де CWND – поточний розмір вікна.

2. Джерело оцінює поточну швидкість потоку за допомогою фактичного RTT:

Формула 6

де RTT є фактичним часом проходження сигналу туди та назад.

Джерело, використовуючи очікувану та фактичну швидкість потоку, обчислює оцінку відставання у черзі за формулою (4)

Джерело оновлює розмір вікон таким чином:

Формула 7

Рис. 1 ілюструє поведінку. Розглянемо просту мережу з одним підключенням і одним каналом ємністю. Нехай BaseRTT бути затримка мінімального проходження сигналу туди і назад. Пропускна здатність цього з'єднання є window/( BaseRTT) коли window< C*BaseRTT.

Управління розміром вікна TCP Vegas [2]

Рисунок 1 – Управління розміром вікна TCP Vegas

На рис. 1, w відповідає розміру вікна де window=C * BaseRTT. Коли window> w, починає будуватися черга і (Expected - Actual)> 0. TCP Vegas збільшує розмір вікна під час наступного проходження сигналу якщо window< w+а , зменшується розмір вікна, якщо window> w+b. В іншому випадку, він залишає розміру вікна без зміни.

На рис. 1, Diff оцінює розмір черги. TCP Vegas намагається тримати прийняті а пакети, але не більше, ніж b пакетів в черзі. Причиною цього є що TCP Vegas спробує виявити і використовувати додаткову пропускну здатність, коли вона стає доступна без перевантажень в мережі. Таким чином, коли є тільки одне підключення, розмір вікна TCP Vegas сходиться до точки, що лежить між w +а і w +b.

Звернімо увагу, що цей механізм принципово відрізняється від того, що використовуються TCP Reno. TCP Reno завжди оновлює розмір вікна, щоб гарантувати повною утилізацію пропускної спроможності, що веде до постійної втрати пакетів, тоді як TCP Vegas викликає будь-яких коливання в розмірі вікна після того, як він сходиться до точка рівноваги[4].

5.2 Математичний опис гідродинамічної моделі потоку для алгоритмів TCP Reno та TCP Vegas

Розрахунок зміни розміру вікна та довжини черги виконується за допомогою гідродинамічної моделі потоку. Для кожного алгоритму розробляється своя гідродинамічної моделі, яка враховує конкретні особливості даного алгоритму. В даному випадку використовується алгоритми TCP Reno та TCP Vegas .

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

Формули 8-10

де W(t) позначає середній розмір вікна TCP [пакети], Q(t) – середня довжина черги [пакети], R(t) – RTT [секунди], С – пропускна спроможність каналу [пакет/с], N(t) – кількість TCP сесій, p(t) – ймовірнісна функція маркірування пакету, G(x) – нелінійна функція, яка описує зміну розміру вікна.

Функція G(x) описується виразом:

Формула 11

Диференціальні рівняння (3) та (4) описують динамічне керування вікна TCP. Перший елемент 1/Ri описує у вікні адитивне збільшення фази, другий елемент W(t)/2 – мультиплікативне зменшення фази (в тому числі ймовірнісна функція маркірування пакету). Елемент G(a-Diff) в рівнянні (9) описує збільшення розміру вікна на 1, а другий елемент G(Diff-b) – зменшення розміру вікна на 1.

Рівняння (10) описує довжину черги вузьким місцем, як різниця між швидкістю прибуття пакету NW/R і пропускною спроможністю С, припускаючи, що там є немає внутрішньої динаміки в вузькому місці (грубо кажучи, простих інтеграторів).

За допомогою гідродинамічної моделі потоку активне керування чергою можна інтерпретувати як зворотній зв'язок проблеми контролю, де дія контролю складається з маркування пакетів (з ймовірністю p) в залежності від довжини виміряної черги Q [6]

Для кращого розуміння принципу моделі гідродинамічного потоку представимо рівняння (8) та (10) схемою, яка приведена на рис. 2

Схема режиму управляння потоком за для уникнення перевантаження в вузькому місці для TCP Reno[6]

Рисунок 2 – Схема режиму управляння потоком за для уникнення перевантаження в вузькому місці для TCP Reno

Принцип гідродинамічної моделі потоку для TCP Vegas наведено на рис. 3.

Схема режиму управляння потоком за для уникнення перевантаження в вузькому місці для TCP Vegas

Рисунок 3 – Схема режиму управляння потоком за для уникнення перевантаження в вузькому місці для TCP Vegas

5.3 Метрики оцінки роботи противовантажних алгоритмів

Для оцінки якості роботи противовантажних алгоритмів транспортного рівня стека ТСР/ІР найчастіше використовують наступні метрики:

5.3 Моделювання та оцінка ефективності алгоритмів

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

На рис.4 наведена топологія такої мережі. За допомогою s1, s2,…,sN – позначені відправники трафіку, r1, r2, …, rN – одержувачі, R — маршрутизатори каналу. Вузьке місце приводить к тому, що пропускна спроможність всієї мережі обмежена одним або кількома компонентами, які називаються критичними елементами. В нашому випадку, критичними елементами є маршрутизатори каналу.

Топологія мережі з вузьким місцем

Рисунок 4 – Топологія мережі з вузьким місцем

(анімація: 7 кадрів, затрімка між кадрами 1 з, кількість циклів повторення — безконечне, розмір 145 Кбайт, створена при допомозі gifovina.ru)

Для моделювання використовуємо пакет прикладних програм MATLAB.

Вхідні параметри моделювання: RTT R=0,1 с, максимальна довжина черги Qmax=200 пакетів, кількість відправників S змінюється динамічно.

Результати моделювання приведені на рис.5 – 6

Графік залежність довжини черги Q(t)

Рисунок 5 – Графік залежність довжини черги Q(t)

Графік залежність розміру вікна W(t)

Рисунок 6 – Графік залежність розміру вікна W(t)

Проаналізувавши графіки, приведені на рис.5 – 6, можна відзначити, що по-перше, середній розмір вікна TCP Vegas менш в TCP Reno, але за рахунок меншого вагання, TCP Vegas передає більшу кількість даних, по-друге, середнє значення черги при використанні алгоритму TCP Vegas менше, ніж при використанні TCP Reno, оскільки TCP Vegas забезпечує більший об'єм переданих даних.

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

Формула 3
Формула 4

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

Формула 5
Формула 6

де vli – кількість втрачених пакетів для і-го користувача.

На основі отриманих результатів можна зробити вивід, що при використанні TCP Reno розподіл пропускної спроможності між користувачами більш нерівномірний, ніж при використанні TCP Vegas. Унаслідок такого розподілу пропускної спроможності алгоритмом TCP Reno виникає більша кількість втрат пакетів, чемв каналі зв'язку з використанням TCP Vegas. Також варто відзначити, що кількість переданих даних в разі використання алгоритму TCP Vegas більша, ніж в разі використання алгоритму TCP Reno. Дане явище можна пояснити тим, що при використанні TCP Vegas спостерігається менше вагання розміру вікна, чим при використанні TCP Reno.

Висновки

Моделювання роботи алгоритмів протоколів TCP Reno та TCP Vegas показало що двохфазна робота першого алгоритму призводить до значних коливань навантаження на мережу та більшому рівню втрат, ніж у алгоритму TCP Vegas. За рахунок реалізації більш складної схеми управління пропускною спроможністю, досягнуто зменшення рівня коливань корисного навантаження на мережу та зменшення втрат.

Використання гідродинамічна модель потоку дозволяє враховувати особливості функціонування проти перевантажних алгоритмів. Модель може бути використана для моделювання поведінки різних реалізацій алгоритму TCP в умовах мереж складеної топології.

Проведене моделювання показує, що алгоритм TCP Vegas більш ефективно використовує пропускну спроможність каналу зв’язку, ніж TCP Reno за рахунок меншого коливання розміру вікна.

Примітка

При написанні даного реферату магістерська робота ще не завершена. Остаточне завершення: грудень 2013 року. Повний текст роботи та матеріали по темі можуть бути отримані у автора або його керівника після вказаної дати.

Перелік посилань

  1. Кучерявый Е.А. Управление трафиком и качество обслуживания в сети Интернет / Кучерявый Е.А. – СПб.: Наука и техника, 2004. – 336 с.
  2. Джамалипур А. Беспроводной мобильный Интернет. Архитектура, протоколы и сервисы/Джамалипур А. ; [пер.с англ. Ш. Салиев, В. Орлов] – М., Техносфера, 2009 – 496 с.
  3. Fall K. Simulation based comparisons of Tahoe, Reno and SACK TCP / K. Fall , S. Floyd – Computer Communications Review, , July 1996. —26(3):5-21.
  4. Analysis and comparison of TCP Reno and Vegas [Електронний ресурс] /Jeonghoon Mo, Richard J. La, Venkat Anantharam, Jean Walrand//INFOCOM – 1999 – Режим доступу : http://www.eecs.berkeley.edu/~ananth/1999-2001/Richard/MoLaInfocom1999.pdf
  5. Bonald Thomas Comparison of TCP Reno and TCP Vegasvia Fluid Approximation [Електронний ресурс]/Bonald Thomas// RR3563, Unite de recherche INRIA Sophia Antipolis Cedex (France) – 1998 – 34 pages, режим доступу до статті: netlab.caltech.edu/FAST/references/bonald_comparison.pdf
  6. A control theoretic analysis of RED [Електронний ресурс] / C.V. Hollot, Vishal Misra, Don Towsley, Wei-Bo Gong//INFOCOM — – 2001 – Режим доступу до статті: ftp://gaia.cs.umass.edu/pub/MisraInfocom01-RED-Control.pdf
  7. Jacobson V. Congestion Avoidance and Control/ V. Jacobson – Proceedings, SIGCOMM '88, Computer Communication Review, August 1988; reprinted in Computer Communication Review – January 1995.
  8. Jacobson V. Modified TCP Congestion Avoidance Algorithm/ V. Jacobson - End2 end-interest mailing list, 20 – April 1990.
  9. Srikant, R. The Mathematics of Internet Congestion Control (Systems and Control: Foundations and Applications)/ Rayadurgam Srikant – Birkhauser Boston, 2004.
  10. Батыр С.С. Построение модели сети передачи данных для исследований технологии AQM/Батыр С.С., Хорхордин А.В. // Сборник научных трудов ДонИЖТ Выпуск:28 . – Донецк, 2011 с.108-116
  11. Jain R. A Quantitative Measure of fairness and discrimination for resource allocation in systems/ R. Jain ,D.M. Chiu ,W. Hawe – DEC TR-301, Littleton, MA: Digital Equipment Corporation, 1984.
  12. Митчел Брэдли Пропускная способность и задержка [Електронний ресурс]/[переклад с англ. Дениса Матвеева]//Нестор – 2002. – №12 – Режим доступу: http://www.nestor.minsk.by/sr/2002/12/2122201.html
  13. Семенов Ю.А. Протокол TCP [Електронний ресурс]// Режим доступу: http://book.itep.ru/4/44/tcp_443.htm

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