About one dynamic model of conflictcontrol user interaction in open information environments

The work deals with game control models of data flows in networks that use TCP congestion control algorithms. This paper presents an overview of the problems, highlighted its relevance, and described current approaches to its solution. For networks with varying data flows and the presence of conflic...

Full description

Saved in:

Bibliographic Details
Date:	2015
Main Author:	Ignatenko, O.P.
Format:	Article
Language:	Ukrainian
Published:	PROBLEMS IN PROGRAMMING 2015
Subjects:	Managing Internet Traffic
Online Access:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/107
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Problems in programming
Download file:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-107
record_format	ojs
resource_txt_mv	ppisoftskievua/73/9b11479e54d0fe7871c3b40f28c0de73.pdf
spelling	pp_isofts_kiev_ua-article-1072018-07-23T08:49:18Z About one dynamic model of conflictcontrol user interaction in open information environments Одна динамическая конфликтно управляемая модель взаимодействия пользователей в открытых информационных средах Одна динамічна конфліктно керована модель взаємодії користувачів у відкритих інформаційних середовищах Ignatenko, O.P. Managing Internet Traffic Управление интернет-трафиком Управління інтернет-трафіком The work deals with game control models of data flows in networks that use TCP congestion control algorithms. This paper presents an overview of the problems, highlighted its relevance, and described current approaches to its solution. For networks with varying data flows and the presence of conflicting users, a new approach to the analysis based on conflict-control fluid models is proposed. We build controlled model for constant window and demonstrate the existence of optimal solution of the download file problem. A game of two users that transmit data over a shared communication channel is considered and found the conditions of data losses. Работа посвящена моделям игрового управления потоками данных в сетях,которые используют ТСР алгоритмы управления перегрузками. В работепредставлен обзор проблемы, подчеркнута ее актуальность, описаны существующие подходы к ее решению. Для сетей с изменяющимися потоками данных и наличия конфликтующих пользователей предлагается новый подход к анализу работы сети на базе конфликтно управляемых потоковых моделей. Построена модель одного класса сетей с фиксированным окном доступа и показано существование оптимального в смысле быстродействия решение задачи загрузки файла. Дана робота присвячена моделям ігрового керування потоками даних у мережах, що використовують ТСР алгоритми керування перевантаженнями. В роботі представлено огляд проблеми, підкреслена її актуальність, описані існуючі підходи до вирішення. Для мереж зі змінними протоками даних і наявності конфліктуючих користувачів пропонується новий підхід до аналізу роботи мережі на базі конфліктно-керованих потокових моделей. Побудована модель одного класу мереж з фіксованим вікном доступу та доведене існування оптимального у сенсі швидкодії розв’язку задачі завантаження файлу. Розглянуто гру двох користувачів, що намагаються передавати дані через спільний канал та знайдені умови виникнення втрат. PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2015-09-22 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/107 PROBLEMS IN PROGRAMMING; No 4 (2012) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2012) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2012) 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/107/107 Copyright (c) 2015 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2018-07-23T08:49:18Z
collection	OJS
language	Ukrainian
topic	Managing Internet Traffic
spellingShingle	Managing Internet Traffic Ignatenko, O.P. About one dynamic model of conflictcontrol user interaction in open information environments
topic_facet	Managing Internet Traffic Управление интернет-трафиком Управління інтернет-трафіком
format	Article
author	Ignatenko, O.P.
author_facet	Ignatenko, O.P.
author_sort	Ignatenko, O.P.
title	About one dynamic model of conflictcontrol user interaction in open information environments
title_short	About one dynamic model of conflictcontrol user interaction in open information environments
title_full	About one dynamic model of conflictcontrol user interaction in open information environments
title_fullStr	About one dynamic model of conflictcontrol user interaction in open information environments
title_full_unstemmed	About one dynamic model of conflictcontrol user interaction in open information environments
title_sort	about one dynamic model of conflictcontrol user interaction in open information environments
title_alt	Одна динамическая конфликтно управляемая модель взаимодействия пользователей в открытых информационных средах Одна динамічна конфліктно керована модель взаємодії користувачів у відкритих інформаційних середовищах
description	The work deals with game control models of data flows in networks that use TCP congestion control algorithms. This paper presents an overview of the problems, highlighted its relevance, and described current approaches to its solution. For networks with varying data flows and the presence of conflicting users, a new approach to the analysis based on conflict-control fluid models is proposed. We build controlled model for constant window and demonstrate the existence of optimal solution of the download file problem. A game of two users that transmit data over a shared communication channel is considered and found the conditions of data losses.
publisher	PROBLEMS IN PROGRAMMING
publishDate	2015
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/107
work_keys_str_mv	AT ignatenkoop aboutonedynamicmodelofconflictcontroluserinteractioninopeninformationenvironments AT ignatenkoop odnadinamičeskaâkonfliktnoupravlâemaâmodelʹvzaimodejstviâpolʹzovatelejvotkrytyhinformacionnyhsredah AT ignatenkoop odnadinamíčnakonflíktnokerovanamodelʹvzaêmodííkoristuvačívuvídkritihínformacíjnihseredoviŝah
first_indexed	2025-07-17T09:58:55Z
last_indexed	2025-07-17T09:58:55Z
_version_	1850411494972325888
fulltext	Програмування для комп’ютерних мереж та Internet © О.П. Ігнатенко, 2012 50 ISSN 1727-4907. Проблеми програмування. 2012. № 4 УДК 004.7 О.П. Ігнатенко ОДНА ДИНАМІЧНА КОНФЛІКТНО КЕРОВАНА МОДЕЛЬ ВЗАЄМОДІЇ КОРИСТУВАЧІВ У ВІДКРИТИХ ІНФОРМАЦІЙНИХ СЕРЕДОВИЩАХ Дана робота присвячена моделям ігрового керування потоками даних у мережах, що використовують ТСР алгоритми керування перевантаженнями. В роботі представлено огляд проблеми, підкреслена її актуальність, описані існуючі підходи до вирішення. Для мереж зі змінними протоками даних і наявно- сті конфліктуючих користувачів пропонується новий підхід до аналізу роботи мережі на базі конфлікт- но-керованих потокових моделей. Побудована модель одного класу мереж з фіксованим вікном досту- пу та доведене існування оптимального у сенсі швидкодії розв’язку задачі завантаження файлу. Розгля- нуто гру двох користувачів, що намагаються передавати дані через спільний канал та знайдені умови виникнення втрат. Вступ Актуальність проблеми. Сучасні відкриті інформаційні середовища (ВІС) пов’язані практично з усіма областями людської діяльності. Інтернет стрімко увійшов у наше життя об’єднавши понад два мільярди користувачів у найбільшу в історії людства комунікаційну структуру. На сьогодні спостерігається стійкий розви- ток ВІС у напрямку зростання розподіле- ності, інтелектуалізації і складності. За- безпечення стабільної роботи цих систем неможливе без адекватних моделей їх роботи – детерміністичних, стохастичних, імітаційних тощо. Кожна з них розв’язує окремий клас проблем, представляючи роботу ВІС в певному розрізі. Важливим і актуальним напрямком в моделюванні ВІС є застосування потоко- вих моделей, який дозволяє використати потужний апарат теорії керування і дослі- дити роботу ВІС «в цілому», відкидаючи деталі. В рамках цього підходу було отри- мано багато вагомих результатів в області аналізу стійкості поведінки мереж, які описані, в роботах Келі, Кумара, Сріканта, Мейна та інших. Цей підхід дозволяє про- аналізувати структурні характеристики ВІС, що обумовлені топологією мережі, однак він, як правило, не враховує поведі- нку користувачів ВІС і їх потреби. Розробка потокових моделей, які б враховували поведінку користувачів на основі використання ігрових підходів могла б заповнити цей пробіл. Зрозуміло, що ВІС, як правило, складаються з різно- рідних обчислювальних і комунікаційних ресурсів. Відмінності у ресурсах різних частин системи і нерівномірність вхідного потоку завдань можуть призвести до знач- них коливань завантаженості ресурсів системи і погіршення ефективності робо- ти. Задача розподілу ресурсів у неоднорід- них багатопроцесорних системах при здійсненні обчислень є, у загальному ви- падку, NP складною проблемою. Підхід потокового моделювання дозволяє знайти прийнятне наближення розв’язку за неве- ликий час, що є критично важливим у системах реального часу. Цей підхід запо- чатковувався і розвивається наразі у робо- тах Вейса, Назараті, Прасани. Врахування при такому моделюван- ні конкуренції за ресурси між користува- чами ВІС дозволило б більш адекватно вирішувати цю проблему. Зростання кількості користувачів ВІС, їх диференціація за завданнями та їх поведінка поставила перед розробника- ми нові проблеми, головна з яких поля- гає у необхідності забезпечення стійкої роботи і справедливого розподілу ресур- сів між користувачами. Для розв’язання цих проблем були створені спеціальні алгоритми, що регулюють поведінку ко- ристувачів у мережі – протоколи. Перші протоколи були інженерними евристич- Програмування для комп’ютерних мереж та Internet ними рішеннями. Пізніше Леонардом Клейнроком на базі теорії масового об- слуговування був розроблений перший теоретично обґрунтований протокол. На сьогодні дослідниками запропонова- но більше 50 реалізацій алгоритмів керу- вання потоками даних (TCP протоколів). Загальна ситуація ускладнюється тим, що взаємодія різних протоколів часто носить конкурентний характер, що призводить до нерівномірного розподілу ресурсів. Пи- тання стійкості і справедливості розподілу ресурсів досліджувалися Альтманом, Лоу, Паганіні. Слід відзначити, що розвиток IP телефонії, Grid і Cloud обчислень, транс- ляція відео і аудіо потоків значно заго- стрила проблему гарантованого обслуго- вування користувачів. Внаслідок цього, особливу важливість набуває розвиток аналітичних методів дослідження роботи мереж з обслуговування різнотипних ко- нфліктуючих користувачів. Конфлікт тут розуміється у сенсі конкуренції за ре- сурси, при цьому кожен з користувачів зацікавлений у стабільній роботі мережі. Ігрові підходи до аналізу процесів у мережах досліджувалися такими науко- вцями як Альтманом, Сандхольмом, Лоу та іншими. Однак до цього часу невирішеною залишається проблема створення інтег- рованої потокової моделі взаємодії різних користувачів за умов різних протоколів і обмежених ресурсів. Зовсім інша проблема виникає, коли один з гравців зацікавлений у погіршенні роботи елементів ВІС. Це – ситуація зло- вмисного використання, так звана атака на відмову. Такі атаки можуть проявлятися у дуже різноманітні способи, але, так чи інакше, наслідком є значне погіршення якості або повне припинення роботи еле- мента ВІС. На сьогоднішній момент існує досить багато різних видів атак на відмову, кожна з яких використовує певну особли- вість побудови мережі або вразливості програмного забезпечення. За умов по- стійного зростання типів і потужності атак були здійснені спроби розробити теорети- чні моделі виявлення і протидії, які б до- зволили ефективно протидіяти цим нега- тивним явищам. Основними напрямки стали моделі виявлення перевантажень (Іоанідіс, Флойд та інші), особливостей (Гіл, Полетто, Ченг, Кулкарні, Пенг, Дарховський) і аномальної поведінки (Денінг, Магларас, Чен). Задача протидії вирішувалась в рамках евристичних алго- ритмів, які відсікали трафік атаки. У якості прикладів можна відзначити схему D-WARD, розроблену Е. Мірковіч та схе- му протидії Т. Пенга. Значна частина до- сліджень присвячена розробкам нових протоколів, мереж, засобів аутентифікації, які б унеможливили появу атак взагалі. Ефективність цих підходів, як правило, залежить від впровадження нових схем по всій мережі Інтернет, що значно зменшує їх практичну цінність. Застосування ігрових методів до аналітичного моделювання атак на відмо- ву з урахуванням поведінки зловмисних користувачів ВІС та створення теорети- чно обґрунтованих стратегій протидії їм дозволило б досягти значних успіхів у вирішенні цієї проблеми. Все це дає підстави вважати, що розробка методів, моделей та засобів ігро- вого керування відкритими інформаційни- ми середовищами за умов конфліктної взаємодії користувачів і атак на відмову є актуальною науково-технічною пробле- мою, вирішення якої сприятиме стійкому та безпечному функціонуванні ВІС. 1. Аналітичні моделі керування мережами В першому розділі проведено аналіз існуючих моделей і методів керування відкритими інформаційними середовища- ми та виявлено невирішені актуальні зада- чі керування за умов конфліктної взаємодії та атак на відмову. Аналіз предметної області дозволяє виділити такі основні сутності: • користувачі. Поведінка корис- тувачів визначається задачами, що стоять перед ними. Ці задачі, як правило, поляга- ють у виконанні певних операцій на серве- рах (завантаження даних, здійснення обчи- слень та інше). Взаємодія різних користу- вачів може бути конфліктною з огляду на обмежену кількість ресурсів системи; 51 Програмування для комп’ютерних мереж та Internet • сервери. Сервери надають по- слуги користувачам через мережу. За умов обмеженості ресурсів їх основною задачею є справедливий розподіл своїх можливос- тей з метою виконання задач користувачів; • комунікаційна мережа. Пред- ставляє складне середовище, що включає канали зв’язку, маршрутизатори, протоко- ли взаємодії користувачів, механізми ке- рування перевантаженнями. До основних задач цієї системи належать: стабільна передача даних користувачів, стабільна і прогнозована робота, рівномірний розпо- діл ресурсів. Опишемо основні типи аналітичних моделей, що використовуються для аналізу роботи мереж на сьогодні. Потокова модель керування окремим стаціонарним потоком даних. Історично першим підходом опису мереж були моделі теорії масового обслуговуван- ня. Мережі масового обслуговування скла- даються зі скінченної кількості вузлів і характеризуються вхідним потоком запи- тів, що потребують обслуговування на вузлах, характеристиками схем маршрути- зації і обробки на вузлах. Розглянемо детерміністичну потокову модель [1]. Нехай мережа складається з вузлів, позначимо – чергу на -тому вузлі. Потік вхідних пакетів, що потрапляє ззовні на вхід -го вузла описується швидкістю , можливості обробки даного вузла – потужністю , . Тоді динаміка мережі описується системою диференцій- них рівнянь: N ( )iq t i i iλ iu Ni ,...1= ( )q t Buλ= +& , (1) де Uu ∈ – керування, B – матриця, що описує структуру мережі. На змінні u , q , λ накладені наступні обмеження: NRqu +∈λ,, , 1≤uC , Qq ∈ , (2) де – структурна матриця (визначає спільне використання потужностей на вузлах), – компакт з , що описує область в якій може знаходитися система. Допустимим позиційним керуванням сис- теми (1) називається вимірна функція C Q NR+ ( ) :u Q U⋅ → , яка задовольняє обмеженням (2). Керування ( )( )u q t називається стабі- лізуючим, якщо розв’язок системи (1) для даного керування ( )0; 0q t q → при ∞→t для будь-якого Qq ∈0 . Основною задачею, яка ставиться, зокрема, в роботах [1, 2] є пошук умов існування стабілізуючого керування для системи (1) – (2). Якщо задано критерій якості роботи системи ( )( )J q ⋅ , то виникає задача знаходження оптимального керування: ( )( ) ( ) min u J q ⋅ ⋅ → ( )q t Buλ= +& , , , Nu q Rλ +∈ , 1≤uC , Qq ∈ . (3) Якщо критерій якості має вигляд часу приведення траєкторії до нуля (тобто розвантаження всіх черг) задача (3) стає задачею про оптимальну швидкодію. Для таких моделей існує добре роз- винена теорія, однак застосування її до реальних мереж ускладнене наступними факторами: 1) необхідність повної інформованості; 2) припущення про стаціонарність вхід- ного потоку; 3) відсутність у моделях (1)-(3) втрат і їх впливу на поведінку користувачів; 4) відсутність диференціації між корис- тувачами; 5) умова існування стабілізуючого керу- вання полягає в тому, щоб потужності системи завжди були більші потужно- сті вхідного потоку. В реальних системах ці умови по- рушуються майже завжди. Тим не менше моделі (1)-(3) дозволяють аналітично оці- нити структуру мережі, описати її харак- теристики (виявити вузькі місця, обчисли- ти час розвантаження тощо). Модель розподілу ресурсів Ф. Келі. З розвитком Інтернету пробле- ми дослідження мереж з багатьма кон- куруючими учасниками стали привертати 52 Програмування для комп’ютерних мереж та Internet увагу дослідників. Робота Ф. Келі [2] була, по суті, першою комплексною математичною моделлю, яка продемонс- трувала принцип розподілу пакетів у системі, що працює на основі оптиміза- ції функцій корисності користувачів. Застосування теорії опуклого програму- вання дозволило сформулювати необхідні умови існування розв’язку – точки рівноважного розподілу ресурсів мере- жі. Опишемо цей результат. Мережа в даній моделі представляється набором ланок, кожна з яких описується макси- мальною пропускною здатністю , . Ланки мережі спільно вико- ристовуються джерелами, кожне з яких характеризується швидкістю передачі пакетів , . З кожним джерелом (користувачем) пов’язана функція корис- ності та фіксований однозначний маршрут – множина ланок, яка викори- стовується потоком пакетів даного ко- ристувача. Нехай – функція, яка дорівнює одиниці якщо джерело викори- стовує lc Ml ,...,1= ix Pi ,...,1= ( )i iU x ( ),r i j i j -ту ланку, тоді позначимо R – матрицю маршрутизації: ( ){ } 1,..., 1,..., , i Pij j M R r r i j = = = = . Тоді задача рівноважного розподілу ресурсів між користувачами може бути сформульована у вигляді нелінійної про- грами: ( ) 0 max i i x i U x ≥ ∑ , cxR ≤ . (4) Доведено, що якщо – зроста- ючі строго опуклі вниз функції, то існує єдиний розв’язок задачі (4). ( )iU ⋅ Підхід Ф. Келі дозволив знайти умови існування точки рівноваги мережі з багатьма конкуруючими користувачами, що мало значний вплив на подальший розвиток даного напрямку. До основних недоліків даної моделі слід віднести: 1) статичний підхід до аналізу мережі – розглядається тільки точка рівноваги; 2) не врахована робота вузлів мережі – наявність затримок, буферизація, різні алгоритми обробки вхідних пакетів; 3) відсутнє моделювання СС алгоритмів. Узагальнені моделі розподілу на основі теорії нелінійного програмуван- ня. У роботі Ф. Келі було встановлено зв'язок між прямою і двоїстою задачами та функціями корисності користувачів і вар- тістю використання мережі. Була доведена стійкість алгоритмів для невеликих збурень за умов відсутності затримок. Пізніше ряд авторів [3–5] досліджу- вали різні узагальнення цього підходу, та розвинули загальну теорію розподілено- го керування, що спричинило до появи нових схем та алгоритмів. Зокрема, Мо і Варланд [3] запропонували алгоритм на основі затримок, який забезпечує справед- ливий розподіл ресурсів між користувача- ми (у сенсі пропорційної справедливості). Пізніше ці ідеї були покладені у основу алгоритму TCP FAST [6]. Каніар і Срікант [7] дослідили схему зворотного зв’язку від мережі до користувача. Запропонована ними ідея помічати а не відкидати пакети отри- мала назву ECN (explicit congestion notification) і вважається перспективним напрямком розвитку Інтеренту. Моделі AIMD динаміки та ТСР- подібних з’єднань. Головним недоліком моделей попередніх параграфів є те, що в них не враховано процеси керування пере- вантаження – те, що складає найважливі- ший елемент сучасного Інтернету. Керу- вання перевантаженнями – основа ТСР алгоритму представляє реалізацію простої ідеї: Кожен користувач має збільшувати свою швидкість за умови успішного проходження його пакетів і зменшувати у разі виникнення перевантаження ме- режі. Наступним кроком до побудови аналітичної моделі роботи ТСР мереж є узагальнена модель AIMD динаміки. AIMD (Additive increase, multiplicative decrease) – адитивне збільшення, мульти- плікативне зменшення, означає, що дже- рело нарощує свою швидкість додаючи 53 Програмування для комп’ютерних мереж та Internet певну константу протягом кожного пері- оду часу, коли не було перевантаження, та зменшуючи її у певну визначену кількість раз протягом кожного моменту часу, коли перевантаження виникало. Суттєво новим в даній моделі є поява механізмів керуван- ня на основі вікна (congestion window). Вікно – це кількість пакетів, яку джерело може надіслати в мережу без підтверджен- ня. За допомогою вікна обмежується максимальний обсяг пакетів користувача, що може перебувати в мережі. Підтвер- дження – це спеціальне повідомлення (АСК пакет), яке містить унікальну для з’єднання послідовність ідентифікації наступного пакета, що очікується адреса- том. Ідентифікатори призначаються паке- там упорядковано, тому механізм зворот- них підтверджень є одночасно способом підтвердження доставки пакета (якщо очікується новий пакет) і способом вияв- лення втрат (якщо очікується вже надісла- ний пакет). Механізм АСК пакетів дозво- ляє адаптувати швидкість передачі відпо- відно до змін стану мережі – при уповіль- ненні швидкості надходження АСК повід- омлень уповільнюється швидкість джере- ла, хоча вікно при цьому може залишатись незмінним. З механізмом зворотних під- тверджень зв’язане поняття RTT – round trip time – час повного повернення. За визначенням RTT – це час необхідний на проходження пакету до адресата та повер- нення підтвердження про доставку. Позначимо розмір вікна -го джерела в момент часу , – RTT стану рівноваги, яке вважається сталим. Тоді за визначенням )(twi i t iτ ( ) ( )i i i w t x t τ = – швидкість передачі даних у момент часу . При цьо- му усереднюється на проміжках часу , тобто динаміка з меншим масштабом не береться до уваги у цій моделі. Нехай – ймовірність маркування пакета у ланці мережі у момент часу (в рамках ECN схеми пакети не відкидаються а по- мічаються спеціальним маркером, що значно спрощує процес виявлення втрат пакетів). Ключовим припущенням в цій моделі [7] є припущення про адитивність маркування: t )(txi iτ )(tpl l t ( ) (i li l s t r p t= )l∑ , що є природнім якщо мале. Якщо ж припущення порушується, то модель може застосовуватися, але вигляд функцій кори- сності ускладниться. Опишемо поведінку окремого з’єднання з TCP Reno подібною поведінкою (TCP Reno включає AIMD динаміку джерела, керування переванта- женням та зворотній зв’язок на основі втрат). Нехай в момент часу швидкість передачі пакетів дорівнює ( )lp t t ( )ix t . Вважаю- чи, що підтвердження повертаються з такою ж швидкістю (що вірно в точці рівноваги мережі) користувач отримує ( )( ) ( )1 i is t x t− позитивних підтверджень. Кожне позитивне підтвердження збільшує вікно на ( ) 1 iw t . Також джерело отримує (усереднено) ( ) ( )i iq t x t помічених або негативних підтверджень, кожне з яких зменшує вікно удвічі. Отже динаміка шви- дкості джерела може бути представлена у вигляді ( ) ( ) ( ) ( )2 2 1 1 2 i i i i s t ix t s t τ − = −& x t . (5) Інший варіант моделі (5) для випад- ку коли вікно детерміністично збільшуєть- ся на 1 за кожний RTT описано у роботах [8] ( ) ( ) ( )2 2 1 1 2i i i ix t s t x τ = −& t . Ще одна варіація (5) використову- ється якщо ми припускаємо, що вікно зменшується удвічі за кожний період RTT, який містить хоча б одне негативне під- твердження. Це змінює мультиплікативну частину: ( ) ( ) ( )2 1 ( ) 1 2 i i i ii s t ix t s ττ t x t− = −& . 54 Програмування для комп’ютерних мереж та Internet Дана модель досліджувалась у ро- ботах [8, 9]. Моделі з урахуванням AQM алго- ритмів. Можливості керування заванта- женістю на рівні джерела обмежені. Сис- тема керування перевантаженнями, реалі- зована тільки на стороні клієнта не може бути ефективною, оскільки: • протокол роботи у мережі Інтернет не є обов’язковим стандартом. Навіть у рамках стандарту TCP різні реалізації ведуть себе по різному при виникненні втрат. Інші типи протоколів можуть взага- лі не зменшувати свою швидкість при перевантаженні (як, наприклад, CBR мережі); • деякі протоколи більш «агресивні» і захоплюють більші потужності каналів зв’язку, якщо їх вчасно не обмежити. Ін- формація для таких обмежень наявні тіль- ки на маршрутизаторі, який опрацьовує всі потоки даних; • маршрутизатор може стати ціллю атаки на відмову, або бути перевантаже- ний великими потоками трафіка, тому йому потрібно мати власну систему захис- ту від перевантажень. Найбільш поширеними механізма- ми AQM є DropTail та RED. DropTail істо- рично був першим і природнім рішенням. Згідно з ним пакети, що надійшли помі- щуються у загальну чергу і опрацьовують- ся згідно з порядком надходження. Якщо черга переповнюється, пакети відкидають- ся. Особливістю потокової моделі DropTail є негладкість правої частини відповідного диференційного рівняння: ( ) ( ) ( ) ( )2 2 1 1 2 i i i i s t ix t s t τ − = −& x t l , ( ) ( ) ( ) ( ) ( ) ( ) ( ) max max0 0 li i l l l i l li i l l i li i l l i r x t u q t q q t r x t u q t q r x t u q t − + ⎧ ⎡ ⎤ − =⎪ ⎢ ⎥ ⎪ ⎣ ⎦ ⎪ ⎡ ⎤⎪= − < <⎨⎢ ⎥ ⎪⎣ ⎦ ⎪ ⎡ ⎤⎪ − =⎢ ⎥⎪ ⎣ ⎦⎩ ∑ ∑ ∑ & . (6) Модель (6) для узагальненої пове- дінки ( )ix t , яке визначається цільовою функцією проаналізовано в роботах [10, 11]. )(xJi Довгий час DropTail був єдиним AQM алгоритмом, однак в його поведінці (особливо у комбінації з ТСР) було вияв- лено два суттєвих недоліки: залипання. Один або декілька по- токів даних займають чергу і не дозволя- ють іншим з’єднанням отримати доступ; переповнення. Якщо черги майже повністю заповнені і відбувся стрибок трафіка, то відбудеться втрата багатьох пакетів. У результаті відразу багато з’єднань обмежать свою швидкість і канал буде недовантажено. Оскільки класичний TCP підвищує свою швидкість надсилання аж до виникнення втрат, то черги знову переповняться і ситуація переповнення буде повторюватися періодично. Беззаперечним плюсом DropTail є простота його реалізації. RED – це схема раннього ймовірні- сного відкидання пакетів. Алгоритм RED (ймовірнісне раннє виявлення) використо- вується для згладжування піків трафіку і більш рівномірного обслуговування пото- ків користувачів. Уперше цей алгоритм було запропоновано в роботі С. Флойда і В. Джекобсона [12] як метод, що дозволяє «підтримувати середню завантаженість черг на низькому рівні але допускає тим- часові перепади трафіку». Для цього за- стосовується ймовірнісне відкидання паке- тів. Ймовірність відкидання залежить від середнього значення черги (яке за- пам’ятовується за певний період часу). Рішення про відкидання пакетів прийма- ється наступним чином: • якщо розмір черги менше за , то пакети не відкидаються; minq • якщо розмір черги більше за і менше за , то ймовірність відкидання пропорційна до розміру черги з заданим коефіцієнтом; minq maxq • якщо розмір черги перевищує , то всі вхідні пакети відкидаються. maxq 55 Програмування для комп’ютерних мереж та Internet Точне моделювання ТСР динамі- ки. Створення аналітичної моделі, яка б давала змогу прогнозувати поведінку ТСР з’єднань у мережі надзвичайно важливе для дослідження динаміки су- часних мереж. На перший план тут вихо- дять стійкість і справедливість розподілу ресурсів. Проблема полягає у постійних стохастичних збуреннях, які впливають на затримки і втрати пакетів користувачів. Тому необхідно знати чи є алгоритм керу- вання мережею стійким, тобто таким, що при появі збурень повертає систему до стану рівноваги. Ще одним джерелом нестабільності є поведінки користувачів – їх кількість і запити можуть непередба- чувано змінюватися. Ці зміни утворюють новий рівноважний розподіл ресурсів мережі і алгоритми керування повинні достатньо швидко і плавно переводити систему у нову точку. Важливою характе- ристикою розподілу ресурсів у мережі є справедливість. Питання стійкості справе- дливого розподілу і справедливості стійкої рівноваги мережі складають другу про- блему, якою наразі посилено займаються дослідники. Умови існування і єдиності точки рівноваги (для ідеалізованої математичної моделі мережі) були знайдені Ф. Келі [2]. Пізніше для ідеалізованих схем ТСР (без затримок, з рівномірно розподіленими підтвердженнями) було застосовано мето- ди аналізу стійкості за Ляпуновим теорії керування (Лоу 1999, Канніур Срікант 2002, Алтман 1998, Вен Арак 2004). В цих роботах не враховувалась наявність затри- мок, що критично важливо для стійкості реальних систем. Локальна стійкість схеми ТСР Reno з AQM RED з урахуванням затримок досліджена у роботах [13, 14]. Аналіз показав, що даний протокол стає нестійкий при зростанні затримок та (що було досить несподівано) потужностей мережі. Цей результат спричинив до появи нового напрямку досліджень – розробки протоколів, локально стійких у високопро- дуктивних мережах. Інший напрямок – визначення умов глобальної стійкості за умов наявності затримок пов'язаний з функціоналами Красовського – Ляпунова [15, 16]. У 2007 році Вей [17] вказав на сут- тєвий недолік існуючих потокових моде- лей – відсутність моделювання ефектів пакетного рівня. Вся ідея потокового мо- делювання полягає у заміні потоку пакетів на непевну «субстанцію», що струмує через канали зв’язку. Однак, алгоритм ТСР суттєво використовує два пакетно- орієнтовані механізми – керування на основі зворотних підтверджень та керу- вання на основі вікна, тому теоретичні моделі не могли передбачити і проаналізу- вати ефекти, що виникали у реальних системах. У роботах [18 – 20] здійснена спро- ба побудувати адекватну модель ТСР з’єднання. При потоковому моделю- ванні мереж центром уваги є швидкість передачі даних джерелами. Причина тут полягає у тому, що стан кожного вузла мережі визначається різницею між вхідним трафіком та потужністю цього вузла. Зна- ючи швидкість надходження пакетів у мережу можна зробити висновки про стій- кість, черги та завантаженість системи. Основна проблема з ТСР алгоритмами полягає в нетривіальній залежності майбу- тньої швидкості джерела від поточної. На додачу, в ТСР головною внутрішньою змінною і керуючим параметром є розмір вікна, який неявно (в залежності від швид- кості повернення АСК пакетів) визначає швидкість передачі даних. Моделювання цих двох механізмів на сьогодні активно розвивається дослідниками. Позначимо ( )f t загальна кількість пакетів, що надіслані джерелом у мережу але ще не підтверджені. Ці пакети або відповідні їм АСК пакети можуть перебу- вати у чергах або лініях зв’язку. Якщо припустити, що ( )f t const= , то зрозуміло, що за інтервал часу джерело має надіслати у мережу рівно ( )( ,t t tτ+ ) ( )f t паке- тів; тут ( )tτ – час необхідний щоб остан- ній пакет, надісланий у мережу до момен- ту часу включно був підтверджений. В реальних системах звісно t ( )f t змінюється протягом часу. Важливим однак є значен- ня ( )f ⋅ на кінці інтервалу. Загальна кіль- 56 Програмування для комп’ютерних мереж та Internet кість пакетів, яку джерело має надіслати у систему для збереження балансу дорівнює ( )( )f t tτ+ . Нехай швидкість джерела описується функцією ( )λ ⋅ , тоді за визна- ченням функції ( )f ⋅ для кожного моменту часу t виконується співвідношення ( ) ( ) ( )( t t t d f t t τ λ θ θ τ + = +∫ ) . (7) Складність аналізу (7) полягає у не- відомій природі затримки ( )tτ . Ця затри- мка залежить від стану системи у момент часу та дій гравців протягом усього інтервалу . У зв’язку з цим в сучасних дослідженнях застосовується різні наближення. Найбільш розповсю- джена лінійна форма t [ ( )),t t tτ+ ( ) ( )q t t d u τ = + , де – постійна затримка, пов’язана з каналами зв’язку, d ( )q t u – затримка, пов’язана з запо- вненням вузького місця з чергою ( )q t і пропускною спроможністю (вважається фіксованою). u У роботі К. Якобсона [19] дослі- джена модель DAE, яка для випадку ліній- них затримок і мережі з одним вузьким місцем описується наступними співвідно- шеннями ( ) ( ) ( )cq t t t uλ λ= + −& , ( ) ( ) ( )( ) t t t d f t t τ λ θ θ τ + = +∫ , ( ) ( )q t t d u τ = + , ( ) ≥ ) 0q t , (8 де – швидкість фонового трафіку. В от вища імітаційного моделювання NS-2. за інтерва ( ) 0f t ≥ , cλ роб і К. Якобсона встановлені умови стійкості, побудована модель DAE прото- колу FAST, встановлена стійкість для системи багатьох користувачів з різнорід- ними RTT. Проведене експериментальне підтвердження з використанням середо- Дещо інша модель запропонована у роботі Н. Мьоллера [20]. Усереднюючи лом ( ),t t tτ⎡ ⎤+⎣ ⎦ можемо вважати, що у стані ( ) ( рівноваги ) ( ) f t tλ τ = . Слід зазначити, що в реальн вікно t их системах алгоритму ТСР ( )w t буде відрізнятися від ( )f t , однак в р ках даної моделі вони ься рівними. Отже динаміка черги ого місця системи описується рів- нянням ам вважают вузьк ( ) ( ) ( ) w t q t q t d u = + & . Це – так звана інтегруюча модель (оскільки буфер вузького місця виступає у ролі інтегратора трафіку). З іншого боку, незалежно від внутрішньої робо- ти мережі вона повертає підтвердження зі швидкістю вузького місця системи. Використовуючи дану властивість побу- дована статична модель керованої ме- режі: ( ) ( )w t q t uτ γ = − , ( ) ( )w t t uλ γ γ = + & , де τ – RTT, яке вважається сталим, 1 c u λγ = − Інтегрую одна одній t чи , що функці – доступна потужність системи. ча і статична моделі суперечать , кожна з них описує певну частину ТСР механізму. Розвитком стала побудова об’єднаної моделі (Н. Мьоллер). Нехай ( ) ( ) 1t w t s dsλ= ∫ – розмір вікна. Вважаю ї ( 0 )w t , ( )tλ задо- вольняють умовам теореми про можна записати: ( ) ( )( 1t w t s wλ λ= −∫ & & середнє ) ( ) ( ) ( )( ) 0 0 1 0 , t s ds t t t w t= − − ( ) 57 Програмування для комп’ютерних мереж та Internet ( ) ( ) ( )0 0 ( ) w t t w q t u λ τ = + + & . t Розглядаючи систему бе затримок модель поведінки джерела записується з ( ) ( ) ( ) ( )( ) cq t w t t u q t u w t λ γ τ = + + − + & & . 2. Узагальнена модель оптималь ного керування потоками даних у мережі Інтернет д модел • с переда ються; - Опишемо динамічну потокову мо- ель мережі. При побудові аналітичної і будемо вважати, що: ес передачі пакетів проц у мережі апрок имується неперервними потоками; • кожен користувач пов'язаний з фік- сованим з’єднанням та маршрутом - чі даних, які не змінюються протягом усього часу розгляду моделі; • втрата окремого пакету вважається незначною подією, якою можна знехтува- ти. В рамках моделі розглядаються поведі- нка мережі «в цілому»; • кожна ланка мережі однозначно пов’язана з чергою. Черги функціонують за принципом FIFO. При переповненні черги нові пакети втрача • пакети підтвердження і інформація про втрату пакетів доставляються миттєво і не завантажують мережу (нульові інфор- маційні затримки); • з кожним користувачем пов’язана його функція корисності ( )iJ ⋅ , яку він намагається мінімізувати своїми діями. Будемо вважати, що мережа склада- ється з вузлів і з’єднуючих ланок. На кож- ному вузлі розташовані одна або більше черг з якими пов’язані обслуговуючі ре- сурси. Позначимо { }1, 2,...,I N= множину індексів користувачів. Користувач надси- лає у мережу потік своїх пакетів, керуючи швидкістю переда ю чі – функціє ( )i tλ , Ii∈ . Введемо множину індексів черг { }1, 2,...,J M= та відповідний вектор черг ( ) . Побудуємо матрицюjq t A насту ним о пакети i -го користувача пляють на вхід п чином – якщ потра j -ї черг то відпові- дний елемент матриці 1=ij , в іншому випадку 0 и, a =ija . Кожна черга зв’язана з обчислювальним ресурс ( )j Jjом u t , ∈ , який обс є потік пакетів. Оскільки потік пакетів складається з п в користувачів, то, взагалі кажучи, кожна функція )(...)()( 1 tututu n jjj ++= (звичайно деякі з цих компонентів можуть бути рівні нулю). П ратегії роз- поділу ресурсів лугову отокі ст різних итання визначення ( )u t буде розглядатися пізніше. Кожен вузо же містити одну або більше черг л мо { }1, 2,...,K p= . Позначимо множину індексів вузлів. Введемо функ- цію відповідності ( )s j K∈ визначає належність черги , Jj∈ , яка j до вузла k . Матриця відповідн визначається наступним чином: ( ості C ) ( ) 1 ij s j k c ⎧⎪= ⎨0 s j k = ≠⎪⎩ . Матриця описує структуру роз- ташування черг вузлах. Після обробки пакети ть C на залишаю вузол мережі і можуть або залишити її межі або потрапити на інший вузол. Шлях переходу пакету з вузла на вузол називається маршрутом і задається матрицею R : ( )1 ij r j i r ⎧ =⎪= ⎨ ( )0 r j i≠⎪⎩ , де ( )r j J∈ – функція, що є чергу у яку потрапляють пакети з зада j -ої черги. При су- ється ф ≥+λ− max0,min qqBuA j , переповненні черги пакети, що надходять втрачаються. Цей процес опи ункціями втрат ⎪ ⎨ ⎧ < =λ max0 ),( qq ql j [ ]{ }⎪⎩ Jj∈ . 58 Програмування для комп’ютерних мереж та Internet Введемо також нкцію сумарних втрат фу i -го користувача по всім чергам ( )i tΛ . Після закінчення обслуговування в користувача сервер надсилає йому підтвердження про успішну обробку. По- значимо ( )iv t функції, що описують до- ставку під джень. Для кожного к цільови пакеті твер ористувача заданий й функціонал ( )iJ ⋅ , який той нама- гається мінімізувати. ема, таким фун- кціоналом може бути час закінчення обро- бки певного обсягу пакетів ⎧ t Зокр λ≥ττ≥=λ ∫ int 0 )(:0min))(( iii dvttJ . Таким чином, динаміка роботи ме- режі ⎭ ⎬ ⎫ ⎩ ⎨ описується наступною системою звичайних диференційних рівнянь: ( )dq t ( ) ( ) ( ) ( )( ),A t Bu t l t q t dt λ λ= + + . (9) На систему (1) накладені наступні обмеження, що випливають з природи реальних мереж і мають ключове значення для розв’язання задач ігрового керування. • пропускні здатності ланок мережі є обме еж ними, отже обсяг сумарного потоку кожної черги не може перевищувати зада- ну величину [ ] jjA Bu dλ + ≤ , Jj∈ ; • обсяги н та черг більші за уль обме- жені за величиною – ( ) max0 j jq t q≤ ≤ , Jj∈ керу ; • вання будемо вважати ку- сков зна непе ( )u t о гладким зі ченнями з опуклого компакту відповідного простору; • функції ( )i tλ – невід’ємні кусково рервні функції обмежені за величи- ною ( ) max0 i itλ λ≤ ≤ , Jj , ∈ . увЯкщо корист ач працює в рамках ТСР мережі (як буде вважатися у більшій частині роботи), то існує додаткове обме- ження, пов’язане з керуванням на основі вікна доступу. Позначимо ( ) 0w t ≥ – вели- чину вікна у момент часу t , тоді для кож- ного моменту часу 0 має виконуватися нерівність: ≥T ( ) ( ) ( ) 0 ( ) T i i it v t t dt w Tλ − + Λ ≤⎡ ⎤⎣ ⎦∫ . (10) Нерівність (10) означає, що кількість пакетів, які можуть потрапити у мережу на момент часу T не може бути більша за сумарну кількість під- тверджених і втрачених пакетів плюс розмір вікна в цей момент часу. Дина- міка з обмеженням (10) досить складна для дослідження, тому в даній роботі ми обмежимося простою топологією ме- режі (яка тим не менше дозволить зрозумі- ти важливі властивості взаємодії потоків даних користувачів). Проста динаміка. Розглянемо сис- тему з одним сервером та двома користу- вачами, яка описується системою дифере- нціальних рівнянь: ( ) ( ) ( ) (1 2( )q t t t u t l tλ λ= + − −& ) , ( ) max0,q t q⎡ ⎤∈ ⎣ ⎦ , , max( ) 0,u t u⎡ ⎤∈⎣ ⎦ max( ) 0,i itλ λ⎡ ⎤∈⎣ ⎦ , . (11) 2,1=i За аналогією з теорією диференціа- льних ігор такий тип динаміки можна назвати простою динамікою. Введемо допоміжні змінні ( )iq t , що описують обсяг черги, який займають пакети -го користувача у момент часу i t та ( )iu t – частина ресурсів сервера, що використовується для обслуговування пакетів -го користувача у момент часу . Будемо вважати, що час обертання пакетів (затримка) описується функцією i t ( ) max( ) q t T t u = . Іншими словами це час, нео- бхідний на повне звільнення поточної черги від пакетів, що потрапили туди до часу t . Визначимо функції обробки та відкидання пакетів. Якщо швидко- сті і розміри пакетів достатньо близькі можна вважати, що пакети потрапля- 59 Програмування для комп’ютерних мереж та Internet ють у чергу пропорційно швидкості по- токів: ( ) ( )( ) ( )( ) max 1,2 i i i i u t T t u t t T t λ λ = − = −∑ , ( ) ( ){ } ( ) ( ) max max max 0, , ( ) . 0, i i i t u t q t q l t q t q λ⎧ − =⎪= ⎨ <⎪⎩ (12) При цьому якщо ( ) ( )1 2 0t tλ λ= = покладемо . ( ) 0iu t = Задача передачі фіксованого обсягу даних за мінімальний час має вигляд ( )( ) int 0 min 0 : ( ) min . t i i iJ t t u dλ τ τ λ ⎧ ⎫⎪ ⎪= ≥ ≥ →⎨ ⎬ ⎪ ⎪⎩ ⎭ ∫ Задача (11) з функціями (12) може бути записана у вигляді ( ) ( )( ),q f q t tλ=& , ( )0 0q t = . (13) Функція ( )f t визначена для , обмежена та інтегрована. Існує розв’язок рівняння ],0[ +∞∈t ( )q t для будь-яких допустимих функцій ( )1 tλ , . ( )2 tλ Покажемо тепер, що в задачі опти- мального керування існує розв’язок. Побудуємо множину досяжності першого гравця ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ ττ== ∫ t t duuuttU 0 )(:),( 101 , де інтеграл береться по всім вимірним допустимим функціям. Зафіксуємо страте- гію і розглянемо можливі для різних значень . )(2 ⋅λ ( )1u t max 1 10,λ λ⎡ ⎤∈⎣ ⎦ Оскільки ( ) ( ) max max max 1 1 max 1 2 1 2 0 u u t t λ λ λ λ λ λ ≤ ≤ + + , то ( ) ( ) 0 max max 1 1 0 max 1 2 , 0, t t uU t t dλ τ λ λ τ ⎡ ⎤ ⎢ ⎥= ⎢ ⎥+⎣ ⎦ ∫ , де ( ) ( ) 0 max max max max 1 1 0max max max 1 2 1 2 t t u ud t tλ λτ λ λ τ λ λ ≥ − + +∫ . Отже існує T , таке, що ( )int 1 1 ,U t tλ ∈ 0 . З компактності ( )1 0,U t t випливає існування мінімального часу. Твердження 1. Для мінімальний час завершення першого користувача дорівнює ( )2 t constλ = ( )int max 1 2min 1 max max 1 T u λ λ λ λ + = . Для довільної мінімальний час можна оцінити наступною формулою: ( )2 tλ ( )int max 1 2min 1 max max 1 T u λ λ λ λ + ≤ . Доведення. Для будь-якої ( )2λ ⋅ стратегія дає не більший час завантаження порівняно з іншими ( ) max 1 1tλ λ≡ ( )1λ ⋅ : ( ) (min max min 1 1 1 1( )T Tλ )λ≤ ⋅ для всіх ( )1λ ⋅ . Далі, при значення ча- су є максимальним. ( ) max 2 2tλ λ= Наслідок. Пара керувань є точкою рівноваги за Нешем у грі заван- таження. max i iλ λ= Пара стратегій може бути неефективною точкою рівноваги через високі рівні втрат. ( )max max 1 2,λ λ Достатні умови виникнення втрат. Твердження 2. Якщо виконується одна з наступних умов то для системи (13) ( )1 0l t ≡ для [ ]0 ,t t∈ +∞ : 1) ; ( )max max 1 2 t uλ λ+ ≤ 60 Програмування для комп’ютерних мереж та Internet 2) ( ) max max int max max1 1 2max max max 1 2 q u λ λ λ λ λ λ ≥ + + − . Доведення. Якщо виконується умо- ва 1), то і ( ) 0q t =& ( )1 0l t = . Виконання умови 2) означає, що за час заповнення черги max max max max 1 2 qt uλ λ = + − загальна кількість пакетів першого користувача які потрапили у систему max * 1 max max 1 2 t λ λ λ+ більша за intλ . Якщо умови 1), 2) не виконуються в системі можуть виникнути втрати. Оціни- мо втрати у точці рівноваги . Час заповнення черги визначено вище, загальний час завершення завантаження дорівнює ( max max 1 2,λ λ ) t ( )int max max 1 2 max max 1 T u λ λ λ λ + = . Загальні втрати ( ) * * * * max 1 1 1 T T t t l t dt u dtλ⎡ ⎤= −⎣ ⎦∫ ∫ = * * max max max 1 1 1 max max 1 2 T t u dtλλ λ λ ⎡ ⎤ = −⎢ ⎥ +⎢ ⎥⎣ ⎦ ∫ = ( ) max max * * max 1 1 1 max max 1 2 uT t λλ λ λ ⎡ = − −⎢ +⎢⎣ ⎤ =⎥ ⎥⎦ ( ) max maxint max max max 1 1 2max max max 1 2 qu u λλ λ λ λ λ = + − − + . Динаміка з фіксованим вікном доступу. Розглянемо динаміку системи (13) з одним користувачем та додатковим обмеженням у вигляді вікна доступу: ( ) ( ) ( ) (1 1q t t u t l tλ= − −& ) , max( ) [0, ]q t q∈ , , ( ) max 1 10,tλ λ⎡ ⎤∈⎣ ⎦ ( ) ( ) ( )1 1 0 T t u t l t dt wλ⎡ ⎤− − ≤⎣ ⎦∫ , ( )( )J λ ⋅ = int 0 min 0 : ( ) min . t i it u dτ τ λ ⎧ ⎫⎪ ⎪= ≥ ≥ →⎨ ⎬ ⎪ ⎪⎩ ⎭ ∫ (14) Оскільки для системи з одним користувачем ( ) ( ) 1 max 1 0, 0 ( ) , 0 t u t u t λ λ ⎧ =⎪= ⎨ >⎪⎩ , то ( )( )J λ ⋅ мінімальний якщо ( )1 tλ мак- симальна. Визначимо функцію наступ- ним чином: ( )* tλ max max max * int max max max max , 0, ( ) , , wt u t wu t u u λ λ λ λ λ ⎧ ⎡ ⎤∈⎪ ⎢ ⎥−⎣ ⎦⎪= ⎨ ⎛ ⎤⎪ ∈⎜ ⎥⎜⎪ − ⎥⎝ ⎦⎩ , якщо int max max max w u u λ λ ≤ − , то . ( )* mtλ λ= ax Твердження 3. Задача (14) має мі- німум. Мінімум досягається, зокрема, на функції . ( )* tλ Доведення. Існування мінімуму ви- пливає з загальних теорем існування розв’язку диференціального рівняння та того факту, що множина ( ) 0 t iu dτ τ∫ є опук- лим компактом, який неперервно (у мет- риці Хаусдорфа) залежить від та зростає у сенсі вкладення ( t ( ) ( ) 0 0 t T i iu d u dτ τ τ⊂∫ ∫ τ , якщо Tt ≤ ). Розглянемо множину точок, в яких втрати ненульові. Позначимо момент закінчення завантаження T , тобто 61 Програмування для комп’ютерних мереж та Internet ( ) int 0 T iu d iτ τ λ=∫ і такий момент часу мінімальний, 0,T T⎡ ⎤= ⎣ ⎦ , lT = ( ){ }10 : 0t l t= ≥ > . Функція втрат визнача- ється наступним чином: ( ) ( ){ } max 1 1 1 max max 0, , ( ) ( ) 0, ( ) t u t q t q l t q t q λ⎧ − =⎪= ⎨ <⎪⎩ . Оскільки розв’язок ( )q t є абсолютно неперервна функція, то множина ( ){ }max0 :qT t q t q= ≥ = є об’єднання за- мкнутих множин в 1R (тобто об’єднання точок та відрізків). Оскільки функція ( )1λ ⋅ – вимірна, то і також, тому – вимірна множина. Введемо функцію ( )1l ⋅ l qT T⊂ ( )1̂ tλ за наступною формулою: ( ) ( )1 1 max ,ˆ , l l t t T t u t λ λ ⎧ ∉⎪= ⎨ ∈⎪⎩ T 1 . Зрозуміло, що допустима функція (вимірна та задовольняє умовам системи (14)), і . Тому час закінчення завантаження співпа- дає – . Отже, якщо мінімум досяга- ється для функції , то і для також. Для системи (14) мінімальний час закінчення завантаження дорівнює ( )1̂ tλ ( ) ( ) ( ) ( ) ( )1 1 ˆq t u t t u t l tλ λ= − = − −& ˆT T= ( )1 tλ ( )1̂ tλ int maxu λ . Пряма перевірка показує, що він досяга- ється на функції . ( )* tλ Гра двох учасників з фіксованим вікном доступу. Нехай динаміка системи з одним сервером та двома користувачами, опису- ється системою диференціальних рівнянь: ( ) ( ) ( ) ( ) ( )1 2q t t t u t l tλ λ= + − −& , max( ) [0, ]q t q∈ , , max( ) [0, ]u t u∈ ( ) ( ) ( ) 0 T i i it u t l t dt wλ i− − ≤⎡ ⎤⎣ ⎦∫ , ( ) max0,i itλ λ⎡ ⎤∈⎣ ⎦ , min)(:0min))(( int 0 → ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ λ≥ττ≥=⋅λ ∫ i t iii dutJ , 2,1=i . (15) Функції ( )iu t , ( )il t визначені формулами (12). Введемо допоміжні змінні ( )iq t , ( )il t . Твердження 4. Якщо виконується одна з наступних умов то для системи (15) ( ) 0l t ≡ для ],[ 0 +∞∈ tt : 1) ; ( )max max max 1 2 t uλ λ+ ≤ 2) ; max 1 2w w q+ ≤ 3) ( ) max max int max max 1 2max max max 1 2 iq u λ λ λ λ λ λ ≥ + + − , 2,1=i . Доведення. Доведення для пунктів 1), 3) повторює доведення з твердження 2. Нехай виконується умова 2), тоді сумарна кількість пакетів, що можуть перебувати у черзі 21 ww + менше за , отже втрати не виникають. maxq Висновки Дана робота присвячена моделям ігрового керування потоками даних у мережах, що використовують ТСР алгори- тми керування перевантаженнями. В робо- ті представлено огляд проблеми, підкрес- лена її актуальність, описані існуючі під- ходи до вирішення. Для мереж зі змінними протоками даних і наявності конфліктую- чих користувачів пропонується новий підхід до аналізу роботи мережі на базі конфліктно-керованих потокових моделей. Побудована модель одного класу мереж з фіксованим вікном доступу та доведене 62 Програмування для комп’ютерних мереж та Internet існування оптимального у сенсі швидкодії розв’язку задачі завантаження файлу. Розглянуто гру двох користувачів, що намагаються передавати дані через спіль- ний канал та знайдені умови виникнення втрат. 1. Meyn S. Control Techniques for Complex Networks. – Cambridge University Press. – 2007. – 582 p. 2. Kelly F.P. Charging and rate control for elastic traffic // European Trans. on Telecommunications. – 1997. – 8. – Р. 33 – 37. 3. Mo J., Walrand J. Fair end-to-end window- based congestion control // IEEE/ACM Transactions on Networking. – 2000. – 8. – P. 556 – 567. 4. La R.J., Anantharam V. Charge-sensitive TCP and rate control in the Internet // Proc. IEEE Infocom. – 2000. – P. 1166 – 1175. 5. Low S.H., Lapsley D.E. Optimization flow control: Basic algorithm and convergence // IEEE/ACM Transactions on Networking. – 1999. – 7, N 6. – P. 861 – 874. 6. Paganini F., Doyle J.C., Low S.H. Scalable laws for stable network congestion control // Proc. of IEEE Conference on Decision and Control. – 2001. – 1. – P. 185 – 190. 7. Kunniyur S. and Srikant R. “A time-scale decomposition approach to adaptive explicit congestion notification (ECN) marking,” // IEEE Transactions on Automatic Control, June 2002. – Vol. 47(6). – P. 882–894. 8. Low S.H., Srikant R. A Mathematical Frame- work for Designing a Low-Loss, Low-Delay Internet // Network and Spatial Economics. – 2004. – 4 (1). – P. 75 – 102. 9. Low S. Paganini F., Doyle J. Internet conges- tion control // IEEE Control Syst. Mag. – 2002. – 22 (1). – Р. 28–43. 10. Alpcan T. and Başar T. Network Security: A Decision and Game Theoretic Approach. Cambridge University Press, 2010. 11. Alpcan T. and Başar T. “A game theoretic analysis of intrusion detection in access con- trol systems,” in Proc. of the 43rd IEEE Con- ference on Decision and Control, Paradise Is- land, Bahamas, December 2004. – P. 1568– 1573. 12. Floyd S. and Jacobson V. Random early detection gateways for congestion avoidance // IEEE/ACM Transactions on Networking. – 1993. –1(4). – P. 397–413. 13. Hollot C. V., Misra V., Towsley D., and Gong W. Analysis and design of controllers for AQM routers supporting TCP flows // IEEE Transactions on Automatic Control. – 2002. – 47(6). – P. 945–959. 14. Tan L., Zhang W., Peng G., and Chen G. Stability of TCP/RED systems in AQM routers // IEEE Transactions on Automatic Control. – 2006. – 51(8). – P. 1393–1398. 15. Deb S. and Srikant R. Global stability of congestion controllers for the Internet // IEEE Transactions on Automatic Control. – 2003. – 48(6). – P. 1055–1060. 16. Ying L., Dullerud G. E., and Srikant R. Global stability of Internet congestion controllers with heterogeneous delays // IEEE/ACM Transactions on Networking. – 2006. – 14(3). – P. 579–591. 17. Wei. X. Microscopic behavior of TCP conges- tion control. PhD thesis, California Institute of Technology. 2007. 18. Welzl M. Network Congestion Control: Man- aging Internet Traffic. Wiley. – 2005. – 263 р. 19. Jacobsson K. Dynamic modeling of Internet congestion control. PhD thesis, KTH school 2008 of electrical engeneering. 20. Möller. N. Window-based congestion control. PhD thesis, The Royal Institute of Technol- ogy, KTH. 2008. Одержано 23.11.2011 Про автора: Ігнатенко Олексій Петрович, кандидат фізико-математичних наук, старший науковий співробітник, докторант. Місце роботи автора: Інститут програмних систем НАН України, 03187, Київ-187, проспект Академіка Глушкова, 40. Тел.: 526 6025. e-mail: o.ignatenko@gmail.com 63 mailto:o.ignatenko@gmail.com

About one dynamic model of conflictcontrol user interaction in open information environments

Institution

Similar Items