Потокові моделі мережі Інтернет за умов атак на відмову
This paper deals with fluid controlled models of networks under flooding denial of service attacks. We proposed a new approach to analyzing network work using fluid models and conflict control theory domain. Using analytic model there is found solution for certain class of networks and Nash equilibr...
Збережено в:
| Дата: | 2015 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2015
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/102 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-102 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/1b/4bfd6d50e4c212e6f63089729a401f1b.pdf |
| spelling |
pp_isofts_kiev_ua-article-1022018-09-26T12:35:14Z Потокові моделі мережі Інтернет за умов атак на відмову Andon, Ph.I. Ignatenko, O.P. attacks to refuse UDC 004.7 атаки на отказ УДК 004.7 атаки на відмову УДК 004.7 This paper deals with fluid controlled models of networks under flooding denial of service attacks. We proposed a new approach to analyzing network work using fluid models and conflict control theory domain. Using analytic model there is found solution for certain class of networks and Nash equilibrium. We consider special case of network activity – denial of service attack and found dependency on download time depending of attack direction and traffic volume. The theoretical results were tested in simulation environment NS-2. Дана робота присвячена потоковому моделюванню процесів керування потоками даних у мережах за умов поглинаючих атак на відмову. Описано алгоритм керування перевантаженням ТСР (протокол керування передачею), побудована потокова модель ТСР з’єднання. Розглянута задача оптимального завантаження файлу та ігрової взаємодії двох користувачів. Для моделі поглинаючої атаки отримані аналітичні оцінки погіршення якості зв’язку в залежності від обсягу атаки. Інститут програмних систем НАН України 2015-09-10 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/102 PROBLEMS IN PROGRAMMING; No 2-3 (2012) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2012) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2012) 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/102/101 Copyright (c) 2015 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2018-09-26T12:35:14Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
attacks to refuse UDC 004.7 |
| spellingShingle |
attacks to refuse UDC 004.7 Andon, Ph.I. Ignatenko, O.P. Потокові моделі мережі Інтернет за умов атак на відмову |
| topic_facet |
attacks to refuse UDC 004.7 атаки на отказ УДК 004.7 атаки на відмову УДК 004.7 |
| format |
Article |
| author |
Andon, Ph.I. Ignatenko, O.P. |
| author_facet |
Andon, Ph.I. Ignatenko, O.P. |
| author_sort |
Andon, Ph.I. |
| title |
Потокові моделі мережі Інтернет за умов атак на відмову |
| title_short |
Потокові моделі мережі Інтернет за умов атак на відмову |
| title_full |
Потокові моделі мережі Інтернет за умов атак на відмову |
| title_fullStr |
Потокові моделі мережі Інтернет за умов атак на відмову |
| title_full_unstemmed |
Потокові моделі мережі Інтернет за умов атак на відмову |
| title_sort |
потокові моделі мережі інтернет за умов атак на відмову |
| description |
This paper deals with fluid controlled models of networks under flooding denial of service attacks. We proposed a new approach to analyzing network work using fluid models and conflict control theory domain. Using analytic model there is found solution for certain class of networks and Nash equilibrium. We consider special case of network activity – denial of service attack and found dependency on download time depending of attack direction and traffic volume. The theoretical results were tested in simulation environment NS-2. |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2015 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/102 |
| work_keys_str_mv |
AT andonphi potokovímodelímerežíínternetzaumovataknavídmovu AT ignatenkoop potokovímodelímerežíínternetzaumovataknavídmovu |
| first_indexed |
2025-07-17T09:54:03Z |
| last_indexed |
2025-07-17T09:54:03Z |
| _version_ |
1838409845426880512 |
| fulltext |
Прикладне програмне забезпечення
УДК 004.7
ПОТОКОВІ МОДЕЛІ МЕРЕЖІ ІНТЕРНЕТ
ЗА УМОВ АТАК НА ВІДМОВУ
П.І. Андон, О.П. Ігнатенко
Інститут програмних систем НАН України,
03187, Київ, проспект Академіка Глушкова, 40.
Тел.:+380 (44) 526 3309, факс: 380 (44) 526 6025,
e-mail: ignat@isofts.kiev.ua
Дана робота присвячена потоковому моделюванню процесів керування потоками даних у мережах за умов поглинаючих атак на
відмову. Описано алгоритм керування перевантаженням ТСР (протокол керування передачею), побудована потокова модель ТСР
з’єднання. Розглянута задача оптимального завантаження файлу та ігрової взаємодії двох користувачів. Для моделі поглинаючої
атаки отримані аналітичні оцінки погіршення якості зв’язку в залежності від обсягу атаки.
This paper deals with fluid controlled models of networks under flooding denial of service attacks. We proposed a new approach to
analyzing network work using fluid models and conflict control theory domain. Using analytic model there is found solution for certain class
of networks and Nash equilibrium. We consider special case of network activity – denial of service attack and found dependency on
download time depending of attack direction and traffic volume. The theoretical results were tested in simulation environment NS-2.
Вступ
Сучасні комп’ютерні мережі пронизують майже всі області людської діяльності. Інтернет стрімко
увійшов у наше життя об’єднавши понад два мільярди користувачів у найбільшу в історії людства
комунікаційну структуру. На сьогодні спостерігається стійкий розвиток мереж у напрямку зростання
розподіленості, інтелектуалізації і складності. Забезпечення стабільної роботи цих систем неможливе без
адекватних моделей їх роботи – детерміністичних, стохастичних, імітаційних тощо. Кожна з них призначена
для розв’язання окремого класу проблем, представляючи роботу системи в певному розрізі.
Особливий інтерес представляє дослідження процесів керування потоками даних, оскільки розвиток
мережі Інтернет поставила перед розробниками нові проблеми, головна з яких полягає у необхідності
забезпечення стійкої роботи і справедливого розподілу ресурсів між користувачами. Для розв’язання цих
проблем були створені спеціальні алгоритми, що регулюють поведінку користувачів у мережі – протоколи.
Перші протоколи були інженерними евристичними рішеннями. Пізніше Л. Клейнроком на базі теорії масового
обслуговування був розроблений перший теоретично обґрунтований протокол (TCP – протокол керування
передачею). На сьогодні дослідниками запропоновано більше 50 реалізацій алгоритмів керування потоками
даних (TCP алгоритмів). Загальна ситуація ускладнюється тим, що взаємодія різних протоколів часто носить
конкурентний характер, що призводить до нерівномірного розподілу ресурсів. Питання стійкості і
справедливості розподілу ресурсів досліджувалися Ф. Келі [1], С. Лоу та Ф. Паганіні [2], Р. Срікантом [3]. Слід
відзначити, що розвиток IP телефонії, Grid і Cloud обчислень, трансляція відео і аудіо потоків значно
загострила проблему гарантованого обслуговування користувачів. Внаслідок цього, особливу важливість
набуває розвиток аналітичних методів дослідження роботи мереж з обслуговування різнотипних
конфліктуючих користувачів. Конфлікт тут розуміється у сенсі конкуренції за ресурси, при цьому кожен з
користувачів зацікавлений у стабільній роботі мережі. Ігрові підходи до аналізу процесів у мережах
досліджувалися такими науковцями як С. Лоу [4 – 5] та іншими.
Однак до цього часу невирішеною залишається проблема створення інтегрованої потокової моделі
взаємодії різних користувачів за умов різних протоколів і обмежених ресурсів.
Зовсім інша проблема виникає, коли один з гравців зацікавлений у погіршенні роботи системи. Це –
ситуація зловмисного використання, так звана атака на відмову [6]. Такі атаки можуть проявлятися у дуже
різноманітні способи, але, так чи інакше, наслідком є значне погіршення якості або повне припинення роботи
мережі. На сьогоднішній момент існує досить багато різних видів атак на відмову, кожна з яких використовує
певну особливість побудови мережі або вразливості програмного забезпечення. За умов постійного зростання
типів і потужності атак були здійснені спроби розробити теоретичні моделі виявлення і протидії, які б
дозволили ефективно протидіяти цим негативним явищам. Значна частина досліджень присвячена розробкам
нових протоколів, мереж, засобів аутентифікації, які б унеможливили появу атак взагалі. Ефективність цих
підходів, як правило, залежить від впровадження нових схем по всій мережі Інтернет, що значно зменшує їх
практичну цінність. Застосування ігрових методів до аналітичного моделювання атак на відмову з врахуванням
поведінки зловмисних користувачів та створення теоретично обґрунтованих стратегій протидії їм дозволило б
досягти значних успіхів у вирішенні цієї проблеми.
Ефективна робота такої складної і масштабної структури як Інтернет залежить від багатьох факторів.
Алгоритми, що забезпечують надійний обмін даними між різними користувачами (протоколи) складаються з
© П.І. Андон, О.П. Ігнатенко, 2012
ISSN 1727-4907. Проблеми програмування. 2012. № 2-3. Спеціальний випуск 450
Прикладне програмне забезпечення
451
різних рівнів реалізації, кожен з яких призначений для виконання певних задач. Структура рівнів моделі ТСР/IP
показана на рис. 1.
Рівень прикладних програмних
систем
Транспортний рівень
Рівень IP
Рівень доступу до мережі
Рис. 1. Стек ТСР/IP
Найнижчим рівнем є рівень доступу до мережі. На цьому рівні визначається використання фізичних
елементів мережі для передачі IP датаграм (пакетів даних) таких як кабелі, повторювачі та інтерфейсні плати.
На сьогодні найбільш поширеною технологією фізичного рівня мереж є Ethernet.
Рівень IP. Даний рівень має ключове значення для роботи мережі Інтернет і призначений для передачі
пакетів даних з одного комп’ютера на інший. ІР надає єдиний механізм роботи з різнорідним устаткуванням.
Всі служби і протоколи вищих рівнів використовують IP як засіб передачі пакетів.
ІР виконує наступні функції:
• визначає датаграму – пакет, що є основним елементом процесу передачі даних в мережі;
• визначає схему адресації Інтернету;
• забезпечує передачу даних між рівнем доступу до мережі і транспортним рівнем;
• пересилає датаграми на заданий комп’ютер;
• забезпечує фрагментацію і зборку даних.
ІР відповідає за надійну передачу даних за заданою адресою але не надає гарантій щодо отримання
вірних даних (дані можуть прийти з помилкою).
Транспортний рівень. Транспортний рівень відповідає за надійну передачу даних з одного вузла на
інший. На даному рівні вперше з’являється поняття гарантування якості (за успішного завершення роботу
протоколу вузол отримує заплановані дані). ТСР є найбільш поширеним представником алгоритмів цього рівня
[7]. ТСР забезпечує двонаправлений потік пакетів між двома вузлами. При цьому для синхронізації
використовуються спеціальні ідентифікатори послідовності пакетів і пакти підтвердження (так звані АСК
пакети або повідомлення). За їх допомогою виявляється втрати, зміни у порядку надходження та дублювання
пакетів. Ще одним призначенням АСК повідомлень є керування обсягом потоку джерела (механізм АСК
clocking – зворотній зв'язок на основі підтверджень), який запобігає перевантаженню вхідної черги одержувача.
Інший ключовий механізм ТСР – керування на основі вікна доступу запобігає перевантаженню проміжних
вузлів мережі.
Гарантований зв'язок, який надає ТСР не завжди підходить для потреб користувача. Наприклад, аудіо і
відео потоки, програми реального часу більш чутливі до рівня затримок ніж до втрат окремих пакетів. Для них
можуть бути більш прийнятними протоколи найкращого можливого зв’язку, зокрема UDP.
Рівень прикладних програмних систем. Існує значна кількість протоколів, що використовують
транспортний рівень для організації сесій, служб та допоміжних програм, наприклад:
• DNS – Domain Name System – переводить адресацію мережі (наприклад, IP адреси) у зрозумілі
людям назви (сайтів, доменів) і навпаки;
• DHCP – Dynamic Host Configuration Protocol – автоматично призначає Інтернет адреси комп’ютерам
та користувачам;
• FTP – File Transfer Protocol – протокол, що використовується для передачі файлів;
• HTTP – HyperText Transfer Protocol – Інтернет протокол для надсилання і прийому веб-сторінок.
Керування перевантаженнями. Одним з найважливіших елементів, який впливає на роботу всієї
системи є алгоритм керування перевантаженнями. Алгоритми керування перевантаженням мають регулювати
обсяги потоків даних, що генеруються кінцевими вузлами та мінімізувати затримки і втрати. Наявна на
сьогодні висока ефективність мережі Інтернет пов’язана, насамперед, з ТСР, який наразі є найбільш
поширеною і розвиненою схемою керування перевантаженнями.
ТСР надає розподілений і децентралізований механізм, згідно до якого кожен користувач має
оптимально використовувати спільні ресурси мережі. Оптимально в даному контексті означає, що обсяг
потоків даних користувачів має бути максимальним але не допускати перевантаження мережі. За умов
наявності великої кількості користувачів, які не мають фізичної можливості узгоджувати свої дії та відсутності
повної інформованості про стан завантаженості та наявності вільних ресурсів мережі розробка таких
алгоритмів представляє складну проблему. При розгляді задачі оптимізації необхідно виділити критерії, які має
максимізувати або мінімізувати алгоритм (або принаймі гарантувати певний рівень).
Прикладне програмне забезпечення
Уникнення перевантаження. Головна причина розробки алгоритму ТСР полягала у запобіганню
перевантаження мережі. За відсутності достовірної інформації про стан мережі алгоритм вважає ознакою
перевантаження втрату пакетів. Це необхідна умова (якщо відбулось перевантаження, то пакети відкидаються,
тобто втрачаються) але іноді втрати пакетів можуть спричинятися збоями обладнання, помилками і навіть
погодою (для безпровідних мереж). В сучасних схемах також використовується такий неявний індикатор
можливого перевантаження, як зростання часу на доставку пакета.
Ефективне використання ресурсів. Працездатність мережі вимірюється пропускною здатністю її
вузького місця. Якщо вузьке місце працює не у повну потужність, то ресурси втрачаються. Тому, якщо у
процесі роботи системи у вузькому місці вивільнилися додаткові ресурси, алгоритм має вміти використати їх у
розумно найшвидший спосіб.
Справедливість розподілу. Спільне використання потужностей мережі різними користувачами
вимагає здійснювати явний або неявний розподіл ресурсів поміж ними. Алгоритм, таким чином, має
забезпечувати прогнозовану та справедливу схему поділу наявних потужностей.
1. Опис ТСР алгоритмів
Найважливішим елементом алгоритму ТСР, який вирізняє його поміж інших є керування на основі
вікна (congestion window). Вікно – це кількість пакетів, яку джерело може надіслати в мережу без
підтвердження. За допомогою вікна обмежується максимальний обсяг пакетів користувача, що може
перебувати в мережі. Підтвердження – це спеціальне повідомлення (АСК пакет), яке містить унікальну для
з’єднання послідовність ідентифікації наступного пакета, що очікується адресатом. Ідентифікатори
призначаються пакетам упорядковано, тому механізм зворотних підтверджень є одночасно способом
підтвердження доставки пакета (якщо очікується новий пакет) і способом виявлення втрат (якщо очікується
вже надісланий пакет). Механізм АСК пакетів дозволяє адаптувати швидкість передачі відповідно до змін стану
мережі – при уповільненні швидкості надходження АСК повідомлень уповільнюється швидкість джерела, хоча
вікно при цьому може залишатись незмінним. З механізмом зворотних підтверджень зв’язане поняття RTT –
round trip time – час повного повернення. За визначенням RTT – це час необхідний на проходження пакету до
адресата та повернення підтвердження про доставку.
Керування на основі вікна та механізм АСК повідомлень не допускає тотального перевантаження
мережі і адаптується до змін в обсязі вільних ресурсів (у сторону збільшення або зменшення) та дозволяє у
поєднанні з AQM алгоритмами розподіляти ресурси між користувачами. Як уже зазначалось, основною
інформацією про стан мережі є підтвердження доставки пакета або його втрати. Взагалі кажучи причини втрати
пакета можуть бути різними, однак ми зосередимося на втратах, спричинених перевантаженнями мережі.
Кожний пакет підтвердження включає ідентифікатор пакета, що наразі очікується адресатом. Іншими словами
отримання АСК пакета з ідентифікатором N означає успішну доставку всіх пакетів з номером 1−N . Якщо
пакет M було втрачено, то джерело буде отримувати АСК пакети з ідентифікатором M за кожний пакет, що
надійде після факту втрати до того часу поки пакет M не буде надіслано знову. Таким чином, втрата пакета
спричиняє як мінімум дублювання підтвердження. Однак причин появи дублюючих АСК пакетів більше – це
може статись внаслідок затримки пакета і надходження його не у порядку слідування (внаслідок зміни
маршруту руху) або через дублювання АСК повідомлення мережею. Тому рішення про втрату пакета
приймається на стороні джерела. Це стається внаслідок настання однієї з двох подій: перевищено час на
очікування підтвердження (змінна з’єднання RTO) або отримано три дублюючих АСК підтвердження. Значення
RTO не є постійним а визначається на основі усередненого RTT. Також якщо відбувається втрата пакета після
перевищення RTO застосовується експонентний механізм збільшення.
Опис основних станів системи ТСР. Виділяють чотири окремих стани ТСР з’єднання. З кожним
з’єднанням пов’язані змінні: поточне вікно – cwnd та ssthresh – параметр переходу в стан уникнення
перевантаження.
При встановленні ТСР з’єднання дорівнює 2 а нескінченності. cwnd ssthresh
Повільний старт. Перший стан в якому знаходиться з’єднання у момент встановлення або після
відновлення. Якщо < ssthresh то розмір вікна зростає на одиницю за кожний пакет підтвердження.
Іншими словами протягом
cwnd
RTT періоду вікно подвоюється. Якщо вважати RTT постійне, то вікно зростає за
експонентою. Стан повільного старту продовжується до виникнення однієї з наступних подій:
- змінна стає більшою за . ТСР з’єднання переходить у стан уникнення перевантаження; cwnd ssthresh
- затримка підтвердження перевищує (пакет вважається втраченим за таймаутом). Перехід у стан
очікування;
RTO
- виникнення дублюючого підтвердження. На відміну від попередньої події, яка свідчить про «значне»
перевантаження доставка дублюючого АСК пакета означає, що пакет втрачено через тимчасовий збій або
мережа підійшла до стану перевантаження і слід зменшити швидкість. Перехід у стан швидкого відновлення.
Уникнення перевантаження. В даному режимі збільшується на одиницю за кожний cwnd RTT . Як і в
попередньому стані перевищення або дублюючий переводить з’єднання у відповідний стан. RTO ACK
Очікування. Після виникнення тайм-ауту (перевищення часу очікування поточної величини )
виконуються наступні дії:
RTO
- втрачений пакет надсилається повторно;
452
Прикладне програмне забезпечення
- оновлюються значення змінних
2
cwndssthresh = , 1=cwnd ;
- значення подвоюється. RTO
Стан очікування виникає при суттєвій затримці доставки пакета, що означає значне перевантаження
мережі. В такій ситуації доцільно тестувати мережу тільки через зростаючі періоди часу, які визначаються
змінною . В кінці кінців або буде підтверджено доставку пакета і з’єднання перейде у стан повільного
старту або користувач закриє з’єднання.
RTO
Швидке відновлення. ТСР з’єднання потрапляє у стан швидкого відновлення після виникнення трьох
дублюючих АСК повідомлень. При цьому оновлюється значення
2
cwndssthresh = і відбувається повторне
надсилання пакета. Якщо час очікування перевищує то з’єднання переходить у стан очікування; якщо
АСК успішно отримано, то з’єднання переходить у стан уникнення перевантаження з
RTO
ssthreshcwnd = .
Зменшення вікна наполовину означає (за умови рівномірного надходження пакетів підтвердження), що
протягом половини RTT з’єднання буде очікувати на підтвердження отримання пакетів і лише після
досягнення кількості пакетів у мережі розміру вікна зможе відновити надсилання.
2. Потокове моделювання мереж ТСР
Опишемо динамічну потокову модель мережі [8]. Будемо вважати, що мережа складається з вузлів і
з’єднуючих ланок. На кожному вузлі розташовані одна або більше черг з якими пов’язані обслуговуючі
ресурси. Користувач надсилає у мережу потік своїх пакетів, керуючи швидкістю передачі – функцією )(tλ .
Введемо множину індексів черг та відповідний вектор черг . Кожна черга зв’язана з
обчислювальним ресурсом , , який обслуговує потік пакетів.
},...,2,1{ MJ = )(tq j
)(tu j Jj∈
Кожен вузол може містити одну або більше черг. Позначимо },...,2,1{ pK = множину індексів вузлів.
Введемо функцію відповідності , Kjs ∈)( Jj∈ , яка визначає належність черги до вузла . Матриця
відповідності визначається наступним чином:
j k
C
⎩
⎨
⎧
≠
=
=
.)(0
,)(1
kjs
kjs
cij
Матриця описує структуру розташування черг на вузлах. Після обробки пакети залишають вузол
мережі і можуть або залишити її межі або потрапити на інший вузол. Шлях переходу пакета з вузла на вузол
називається маршрутом і задається матрицею :
C
R
⎩
⎨
⎧
≠
=
=
.)(0
,)(1
ijr
ijr
rij
де – функція, що задає чергу в яку потрапляють пакети з - ої черги. Jjr ∈)( j
При переповненні черги пакети, що надходять втрачаються. Цей процес описується функціями втрат
[ ]{ }⎪⎩
⎪
⎨
⎧
≥+−
<
= max
max
0,min
0
),(
qqBu
qq
ql
j
j λ
λ , Jj∈ .
Введемо також функцію сумарних втрат користувача за всіма чергами )(tΛ . Керування ),()( qutu λ=
будемо вважати функцією, неперервною за λ та за для q Qq int∈ . В точках границі Q ),( qu λ може мати
розриви першого роду.
Після закінчення обслуговування пакетів користувача сервер надсилає йому підтвердження про
успішну обробку. Позначимо функції, що описують доставку підтверджень. )(tv
Для кожного користувача заданий цільовий функціонал )(⋅iJ , який той намагається мінімізувати.
Зокрема, таким функціоналом може бути час закінчення обробки певного обсягу пакетів
⎪⎭
⎪
⎬
⎫
⎪⎩
⎪
⎨
⎧
≥≥= ∫ int
0
)(:0min))(( i
t
ii dvttJ λττλ .
Таким чином, динаміка роботи мережі описується наступною системою диференційних рівнянь:
))(),(()()()( tqtltuBt
dt
tqd λλ ++= . (1)
453
Прикладне програмне забезпечення
На систему (1) накладені наступні обмеження, що випливають з природи реальних мереж і мають
ключове значення для розв’язання задач ігрового керування.
• пропускні здатності ланок мережі є обмеженими, отже обсяг сумарного потоку кожної черги не може
перевищувати задану величину [ ] jj dBu ≤+λ , Jj∈ ;
• обсяги черг більші за нуль та обмежені за величиною – , max)(0 jj qtq ≤≤ Jj∈ ;
• керування будемо вважати кусково неперервною функцією зі значеннями з опуклого
компакту відповідного простору. Особливістю схем керування мережами є залежність функції від
стану та розривність за цією змінною;
),( qtu
)(tq
• )(tλ – невід’ємна кусково неперервна функція, обмежена за величиною , max)(0 λλ ≤≤ t Jj∈ . Якщо
користувач працює в рамках ТСР мережі, то існує додаткове обмеження, пов’язане з керуванням на
основі вікна доступу. Позначимо – величину вікна у момент часу t , тоді для кожного моменту
часу має виконуватися нерівність:
0)( ≥tw
0≥T
[ ]∫ ≤+−
T
Twdttltvt
0
)()()()(λ . (2)
Нерівність (2) означає, що кількість пакетів, які можуть потрапити у мережу на момент часу T не може
бути більша за сумарну кількість підтверджених і втрачених пакетів плюс розмір вікна в цей момент часу.
Запишемо (1) у скороченій формі )),(( qtfq λ=& . Ця система диференціальних рівнянь визначена в
області , де LQ× { }max0: ii
M qqRqQ ≤≤∈= , { }max0),0,...,0,( λ≤≤= xxL . Функцію )(tλ будемо вважати
кусково неперервною. Зафіксуємо )(⋅λ , тоді ),()),(( qtfqtf =λ . Будемо говорити, що функція задовольняє
умовам Каратеордорі, якщо в області : TQ×
1) визначена для майже всіх t і неперервна за ; ),( qtf q
2) вимірна за t для кожного ; ),( qtf q
3) )(),( tmqtf ≤ , де інтегрована за Лебегом на кожному скінченому відрізку. )(tm
Теорема 1. (Філіпов, [9]) Якщо функція задовольняє умовам Каратеодорі при ),( qtf attt +≤≤ 00 ,
bqq ≤− 0 , то на відрізку відрізку існує розв’язок задачі ],[ 00 dtt + ),( qtfq =& , . При цьому число
таке, що ,
00 )( qtq = d
ad ≤<0 bdt ≤+φ )( 0 , . ∫=φ
t
t
dssmt
0
)()(
Зауваження. Система (1) не задовольняє умовам Каратеодорі, оскільки розривна за . ()f q
Теорема 2. (Філіпов [9]) Нехай – рівняння Каратеодорі в замкнутій обмеженій області .
Тоді кожний розв’язок, що проходить всередині можна продовжити в обидві сторони до виходу на границю
області.
),( qtfq =& D
D
Твердження 1. Якщо , кусково-неперервна, обмежена функція, і неперервна у
то існує розв’язок системи (1) в області
)(tλ ],[ 10 ttt∈ ),( qtf
Qint LQ× .
Доведення приведене у роботі [10].
Покажемо тепер, що задача завантаження файлу, тобто задача (1) з функціоналом якості
має розв’язок. Введемо додаткову змінну таку, що
Моментом закінчення завантаження назвемо перший момент часу для якого
⎪⎭
⎪
⎬
⎫
⎪⎩
⎪
⎨
⎧
λ≥ττ≥=λ ∫ int
0
)(:0min))((
t
dvttJ 0q ∫ ττ−λ=
t
dvtq
0
int
0 )()( .
t 0)(0 =tq . Зауважимо, що
)(0 τ= vq& , . (3) int
00 )( λ=tq
Формалізуємо визначення функції )(τv . Оскільки )(τv – потік підтверджених пакетів, що покидають
один з вузлів системи, то існує індекс , такий, що Ii∈ )()( tvtui = . Позначимо L – множину можливих значень
функції для будь якого . Будемо вважати, що )(tλ 0≥t L – опуклий компакт.
Твердження 2. Якщо для системи (1)-(3) виконується ∅≠λ−=
∈λ
I
L
BULBU )(* і момент закінчення
завантаження , то для кожної існує , така, що ,
черга спадають монотонно і втрати пакетів нульові.
∞<))(,( 0tqLT Lt ∈λ )(* Utu ∈)(* ))(,())(),(),(( 00
** tqLTtquT =⋅⋅λ
)(0 tq
454
Прикладне програмне забезпечення
Доведення. Розглянемо множину досяжності системи (1). Нехай задана функція , тоді
, де
Lt ∈λ )(*
}))()(()(:{)(
0
*
0 ∫ ττ+τλ+=∈=
t
dButqqQqtQ )(τu – будь-яка допустима функція. Зрозуміло, що
компактна, опукла множина, що неперервно залежить від часу. Позначимо
лінійний підпростір, що породжений вектором через
∫ τ+τλ+=
t
dBUtqtQ
0
*
0 ))(()()(
0q M , π – оператор ортогонального проектування на
його ортогональне доповнення ⊥M . Умова ∞<))(,( 0tqLT означає існування моменту часу коли )(}0{ TQπ∈ .
Мінімальний такий час існує і дорівнює . ))(,( 0tqLTT =
Тоді можна вибрати селектор [ ]LBUw *∈ , такий, що . Визначимо з умови
, тоді рівно в момент часу виконується
)( 0
0
tqwd
T
t
−=τ∫ )(* tu
wttBu +λ−= )()( ** T 0)(0 =Tq і швидкість зменшення стаціонарна і
дорівнює . Доведення закінчене. w
На практиці, однак, часто виникає ситуація, коли обсяг вхідного потоку перевищує можливості вузлів з
обробки даних (можливо тимчасово). В цьому випадку зайві пакети очікують на обробку в черзі, а в разі
переповнення черги – втрачаються. Виявляється, що за певних умов для задачі (1)-(3) можна підібрати таку
функцію втрат, щоб існував скінчений час закінчення завантаження і відповідна стратегія.
Твердження 3. Якщо для системи (1) – (3) виконується умова ∅≠λ−=
∈λ
I
L
BULBU )(* і існує момент
закінчення завантаження , Нехай задана функція вхідного потоку даних , для якогось
, тоді існує функція втрат , така, що і момент закінчення завантаження
.
∞<))(,( 0tqLT CLt ∈λ )(
1>C 1)( +∈λ MRl ∅≠λ−λ+
∈λ
I
L
lBU )))(((
∞<⋅λ ))(),(( 0tqT
Доведення. Розглянемо λ
−
=λ
C
Cl 1)( , тоді Ll ∈λ−λ)( і можна застосувати твердження 2. Покажемо,
що моменти закінчення завантаження співпадають. Для кожної функції CLt ∈λ )( існують , ))(( tl λ ))(( tu λ такі,
що LBUtltBut *))(())(()( ∈λ+λ+λ . Тоді
LtBUtqdlButqtq
t
*)())()()(()()( 0
0
0 +∈ττ+τ+τλ+= ∫ .
Отже, час закінчення не може бути меншим за . З іншого боку, завжди можна підібрати
, щоб виконувалась рівність
))(,( 0tqLT
))(( tl λ wtltBut =λ+λ+λ ))(())(()( , де вибране з попереднього твердження, тобто
так, щоб . Таким чином швидкість зменшення збігається і
w
)( 0
0
tqwd
T
t
−=τ∫ )(0 tq ))(,())(),(( 00 tqLTtqT =⋅λ .
Наслідок. Для пари функцій , )(tλ )(λl моделі з втратами існує моделі без втрат, що моменти
закінчення завантаження збігаються.
Lt ∈λ )(*
Розглянемо модель мережі з одним користувачем, маршрутизатором і сервером. Обмежимося
розглядом системи з двома режимами – уникнення перевантаження і швидким відновленням. Керування на
основі вікна означає, що в стані рівноваги вікно переключається між цими двома режимами. Спочатку вікно
лінійно зростає до максимального значення . При виникненні переповнення черги виникає втрата,
внаслідок якої вікно зменшується удвічі.
maxw
Рис. 2
455
Прикладне програмне забезпечення
Усереднене вікно max
4
3)(1 wdttw
RTT
w
RTTt
t
cp == ∫
+
. Припущення щодо динаміки процесу:
• будемо вважати RTT сталими і рівним
2
maxw ;
• система має одне вузьке місце, обробка пакетів в інших чергах відбувається «миттєво»;
• повідомлення про доставку також надходять миттєво.
Тоді швидкість передачі даних дорівнює *
*
max*max*
4
3
4
3
q
uwRTTw ==λ , де
2
minmax
* qqq +
= –
усереднена черга. Значення визначене. Розглянемо динаміку зміни обсягу черги після факту
зменшення вікна удвічі. Оскільки джерело не може надсилати нічого до часу поки кількість пакетів у
системи не буде рівна розміру вікна. Для часу виконуються рівності:
maxq )(tq
*t
*t
*
max
***maxmin
2
)( twtwtuqq +==−= ,
1
2
*
max
max
*
+
−
=
u
wq
t .
Тоді усереднена черга дорівнює
)1(422
2
*
max*
*
*
max*
+
+
+
+
=
u
wu
u
uqq , *
*
max*
4
3
q
uw=λ .
Розглянемо задачу завантаження файлу. Нехай задана загальна кількість пакетів , які потрібно
завантажити на сервер за найкоротший час. Завантаження вважається закінченим, якщо кількість
підтверджених пакетів досягає заданої. Динаміка системи описується системою диференціальних рівнянь:
intλ
)()()( 11 tuttq −λ=& ,
)()()( 212 tututq −=& ,
)()()( 323 tututq −=& , (4)
при цьому на фазові змінні і функції накладені наступні обмеження:
max)(0 λλ ≤≤ t ,
0)( ≥tui , 1)()(
3
3
1
1 ≤+
μμ
tutu , 22 )( μ≤tu ,
max)(0 ii qtq ≤≤ , 0)( 0 =tqi , .3,2,1=i
Функції обробки пакетів на маршрутизаторах ui даному прикладі працюють за принципом FIFO. Крім
цього на першому вузлі більший пріоритет надається пакетам підтвердження. Загальноприйняті [16]
визначення функцій керування призводять до виникнення ковзних режимів, що ускладнює їх аналіз. В роботах
[11 – 16] розглянуто та обґрунтовано підхід до визначення , який усуває ковзні режими.
)(t в
)(tui
⎪
⎪
⎩
⎪
⎪
⎨
⎧
>⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−
=⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−
=
0)(,)(1
0)(,)(1),(min
)(
1
3
3
1
1
3
3
1
1
tqtu
tqtut
tu
μ
μ
μ
μλ
;
( )
⎩
⎨
⎧
>
=
=
0)(,
0)(,)(,min
)(
22
212
2 tq
tqtu
tu
μ
μ
;
( )
⎩
⎨
⎧
>
=
=
0)(,
0)(,)(,min
)(
33
323
3 tq
tqtu
tu
μ
μ
. (5)
З тверджень 1 – 3 випливає існування оптимального керування для задачі (4) з функціями (5).
Характерною особливістю задач даного типу є наявність «значної» кількості оптимальних керувань , що
обґрунтовується наступним твердженням.
)(* tu
Твердження 4. Якщо керування оптимальне, то вузьке місце максимально завантажене протягом
усього часу завантаження файлу. Якщо за керування вузьке місце максимально завантажене протягом
усього часу завантаження файлу, то відповідний час оптимальний.
)(* tλ
)(* tλ
Твердження доведене у роботі [17].
456
Прикладне програмне забезпечення
Наслідок. Керування завжди є оптимальним. max)( λ=λ t
3. Ігрові потокові моделі мереж
Розглянемо систему з двома користувачами що завантажують файли на один сервер [25, 26]. При цьому
вони використовують спільну мережу. Для моделювання процесу їх взаємодії в рамках підходу потокових
моделей і теорії ігор, введемо віртуальні з’єднання , де індекс означає користувача, індекс відповідає
черзі. Віртуальне з’єднання означає, що ресурси одного вузла розподіляються (за допомогою функції ) між
обслуговуванням різних потоків пакетів користувачів, тобто
)(tqk
i k i
)(tuk
)()( tqtq i
k
k
i∑ = . Таким чином, задача зводиться до
системи з динамікою виду (1) для функцій )(tiλ , кожна з яких зв’язана з окремим користувачем та
використовується для мінімізації часу завантаження.
))(),(()()()()(
21 tqtltuBtt
dt
tqd λλλ +++= . (7)
При цьому функції втрат мають вигляд
⎪⎩
⎪
⎨
⎧
=+
<
= max
max
)(,)]()([
)(,0)(
iii
ii
i qtqtuBt
qtqtl
λ
,
функції обробки розподіляються пропорційно до вхідних потоків. )(tuk
i
Існування розв’язку для допустимих функцій )(1 tλ , )(1 tλ випливає з попередніх тверджень.
Твердження 5. Нехай для моделі з двома користувачами задані функції , і .
Позначимо час закінчення завантаження , відповідно. Тоді перший користувач може за допомогою
керування зменшити свій час завантаження. Існує рівновага за Нешем у грі завантаження (1).
Зокрема, керування , дають точку рівноваги.
)(*
1 tλ )(*
2 tλ max
1
*
1 )( λ≠λ t
*
1T *
1T
max
11 )(ˆ λλ ≡t
max
1
*
1 )( λλ =t max
2
*
2 )( λλ =t
Доведення. Зафіксуємо , . Розглянемо , де )(*
1 tλ )(*
2 tλ )()()( 2
0
1
0 tqtqtp +=
)()( 1
1
0 tvtq =& , . )()( 2
2
0 tvtq =&
Якщо вузьке місце не завантажене пакетами, то збільшення )(1 tλ призведе до збільшення частки
пакетів першого користувача, що проходять і тим самим зменшать час закінчення.
Якщо вузьке місце системи вже працює на максимальному режимі, то час закінчення буде визначатись
часткою, яка припадає на пакети кожного користувача (ця частка може залежати від часу). Однак і в цьому
випадку збільшення до максимуму збільшить частку пакетів, що обробляються (можливо збільшить і
втрати також), що, для фіксованої функції зменшить час завантаження.
)(1 tλ
)(2 tλ
Наслідок. Якщо користувач зменшує свою швидкість )(1 tλ , то час завантаження принаймі не зростає.
Тоді існує рівновага за Нешем у грі завантаження. Зокрема, керування , дають точку
рівноваги.
max
1
*
1 )( λ=λ t max
2
*
2 )( λ=λ t
Модель завантаження з одним користувачем за умов атаки на відмову
Розглянемо роботу системи (7) за наявності атаки. В даній роботі ми розглядаємо спрощену модель
поглинаючої атаки [6]. Трафік атаки потрапляє на сервер, вимагає ресурсів на обробку та, після обробки,
відкидається як помилковий. Виявляється, що атака різних ланок мережі суттєво відрізняється за наслідками
для роботи мережі. Будемо розглядати атаку мережі з одним користувачем, та за виконання наступних
припущень:
• маршрутизатор є вузьким місцем, потужність сервера набагато більша;
• атака фільтрується під час обробки на маршрутизаторі.
Динаміку процесу атаки мережі запишемо у вигляді рівняння:
)()()()( tltuBttq −++= αλ& , (8)
де ),...,( 31 ααα = – трафік атаки.
Проаналізуємо атаку вигляду 31 ),0,( αα системи (8). Нехай система з одним користувачем перебуває у
стані рівноваги, тоді відомі значення середнього вікна, швидкості і часу завантаження файлу:
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
++
+
λ
=
λ
λ
=
4
1
2)1(3
4),,( max
max
*max
max
*
int
*
intmax*max*
w
q
uw
q
u
wuqT . (9)
457
Прикладне програмне забезпечення
Твердження 6. Атака вигляду призведе до нового мінімального часу закінчення завантаження )0,0,( 1α
),,()( *
max
1
max*max*
u
qwuqTT α−=α , якщо *
max
max
1
2 u
q
w −
≤α і +∞=T інакше.
Доведення. Оскільки ресурси діляться пропорційно до потоків користувачів, то для опрацювання
пакетів атаки знадобляться ресурси 1α . Якщо 1α більше за , то черга переповнюється і, оскільки джерело
атаки не зменшує свою швидкість при втратах, швидкість користувача впаде до нуля.
*u
Якщо , то у черзі буде знаходитись пакетів атаки, де *
1 u<α *
1tα *
max
*
u
qt = – час звільнення черги.
Тоді максимальна кількість пакетів, що може перебувати в системі скорочується до *
max
1
max
u
qw α− . Оскільки
справжнє вікно коливається навколо середньої величини, то для оцінки працездатності достатньо вимагати,
щоб . Виконуються співвідношення 1min ≥w
2
1
*
max
1
max
min
u
qw
w
α−
=≤ ,
*
max
max
1
2 u
q
w −
≤α .
Скористаємося формулою (9) для нового значення максимального вікна.
На рис. 3 показані залежності часу виконання від обсягу трафіка атаки для різних значень потужності
сервера . *u
Рис. 3. Вплив атаки на час завантаження
Висновки
В роботі здійснено огляд механізмів керування у мережах Інтернет, описані основні елементи ТСР
протоколу та розроблена ігрова потокова моделі роботи мережі. Ця модель представляє систему керованих
диференційних рівнянь з розривною правою частиною. Поставлена задача оптимального завантаження файлу
та знайдені необхідні умови існування її розв’язку. Розглянуто задачу взаємодії двох користувачів, показано
існування рівноваги за Нешем.
Для моделі з топологією користувач-сервер-маршрутизатор розв’язується задача впливу атаки на відмову.
Знайдені аналітичні залежності погіршення якості (часу завантаження файлу) в залежності від обсягу трафіка
атаки. Проведене імітаційне моделювання для різних типів протоколів. Таким чином, в результаті виконання
роботи побудована аналітична потокова модель керування потоками даних у комп’ютерних мережах.
Розроблена модель дозволяє провести аналіз поведінки користувачів в рамках диференційної гри та оцінити
якість і роботу системи керування а також знайти точки рівноваги мережі. Для різних типів атак знайдені
стратегії протидії, проведене імітаційне моделювання основних типів протоколів та їх вразливості до атак на
відмову.
458
Прикладне програмне забезпечення
459
2. w S.H. Scalable laws for stable network congestion control // Proc. of IEEE Conference on Decision and Control. –
1. Kelly F.P. Charging and rate control for elastic traffic // European Trans. on Telecommunications. – 1997. – 8. – Р. 33 – 37.
Paganini F., Doyle J.C., Lo
2001. – 1. – P. 185 – 190.
3. Srikant R. The Mathematics of Internet Congestion Control. – Springer Verlag, 2004. – 137 р.
4. Low S. Paganini F., Doyle J. Internet congestion control // IEEE Control Syst. Mag. – 2002. – 22 (1). – Р. 28 – 43.
5. . A Mathematical Framework for Designing a Low-Loss, Low-Delay Internet // Network and Spatial Economics. – 2004. – 4 Low S.H., Srikant R
(1). – P. 75 – 102.
Андон П.І., Ігнатенко О.П. Атаки 6. на відмову в мережі Інтернет: опис проблеми та підходів щодо її вирішення / Ін-т програмних
10. Моделювання процесів керування комп’ютерними мережами за умов конфлікту // Проблеми програмування. – 2009. – № 2-3.
11. моделі динамічного планування черг в компю’терних мережах за умов конфлікту // Проблеми програмування. –
12. ресурсів у багатопроцесорних середовищах за умов конфлікту і невизначеності // Зб. праць міжнар.
13. керування потоками даних мережі Інтернет за умов нестабільної поведінки // Проблеми програмування. – № 3,
14.
часні комп'ютерні системи та мережі: розробка та використання» (29 вересня – 01 жовтня 2011, Україна,
15. керування мережами // Матеріали Міжнародної наукової конференції CSE (24 вересня – 26
16. нференції
Застосування інформаційних та комп’ютерних технологій» (12 – 14 жовтня 2011, Азербайджан, Баку), 2011. – С. 271 – 276.
систем. – Препр. – К.; 2008. – 50 с.
7. Welzl M. Network Congestion Control: Managing Internet Traffic. Wiley. – 2005. – 263 р.
8. Meyn S. Control Techniques for Complex Networks. – Cambridge University Press. – 2007. – 582 p.
9. Филиппов А.Ф. Дифференциальные уравнения с разрывной правой частью. – М.: Наука, 1985. – 224 с.
Ігнатенко О.П.
– С. 125 – 136.
Ігнатенко О.П. Потокові
2010. – № 1. – С. 35 – 43.
Ігнатенко О.П., Кордубан Д.О. Розподіл
конф. CSE-2010. – 2010. – C. 210 – 211.
Ігнатенко О.П. Моделі
2011. – С. 38 – 51.
Ігнатенко О.П., Кордубан Д.О. Потокові керовані моделі мереж з втратами за умов атаки на відмову // Матеріали V Міжнародної
наукової конференції «Су
Львів), 2011. – С. 72-73.
Ігнатенко О.П. Ігрові потокові моделі
листопада 2011, Україна, Львів), 2011.
Ігнатенко О.П. Потокові керовані моделі мереж за умов атаки на відмову // Матеріали VІ Міжнародної наукової ко
«
2. Потокове моделювання мереж ТСР
3. Ігрові потокові моделі мереж
Модель завантаження з одним користувачем за умов атаки на відмову
|