Evolutionary games in TCP networks with speed restriction policies

Competitive development of various versions of network protocols is an essential part of computer networks. The most-used protocol today is Transmission Control Protocol (TCP). There is a large number of implementations of the TCP protocol, which differ by mechanism of congestion control. TCP develo...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автори:	Ignatenko, O.P., Molchanov, O.A.
Формат:	Стаття
Мова:	rus
Опубліковано:	Інститут програмних систем НАН України 2018
Теми:	game theory Nash equilibrium evolutionary game evolutionary stable strategy replicator dynamics UDC 004.7
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/211
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-211
record_format	ojs
resource_txt_mv	ppisoftskievua/2b/363f4d72d6c73fbf11e1bc17586c212b.pdf
spelling	pp_isofts_kiev_ua-article-2112024-04-28T11:59:06Z Evolutionary games in TCP networks with speed restriction policies Эволюционные игры в TCP сетях с политиками ограничения скорости Еволюційні ігри в TCP мережах з політиками обмеження швидкості Ignatenko, O.P. Molchanov, O.A. game theory; Nash equilibrium; evolutionary game; evolutionary stable strategy; replicator dynamics UDC 004.7 теория игр; равновесие Нэша; эволюционные игры; эволюционно-стабильная стратегия; динамическое воспроизведения УДК 004.7 теорія ігор; рівновага Неша; еволюційні ігри; еволюційно-стабільна стратегія; динамічне відтворення УДК 004.7 Competitive development of various versions of network protocols is an essential part of computer networks. The most-used protocol today is Transmission Control Protocol (TCP). There is a large number of implementations of the TCP protocol, which differ by mechanism of congestion control. TCP develops by improving its existent implementations, vanishing some of them and via creation of a new ones. The possibility of using new versions of the protocol allows the user to increase the data rate by selecting the appropriate implementation of TCP. It is difficult to predict consequences of computer network users’ interaction in situations when many users try to achieve higher data rate by applying different TCP implementation. The actual task is to develop a theoretical and program tools to model such competitive dynamic interactions. This is the goal of my scientific-research work.Game theory, which is the theory of mathematical models of optimal decision making in situations of conflicts of interest, is the best suited to solve a particular problem because it allows you to find a solution in terms of non-cooperative interaction, which usually happens between the networks TCP-connections.This paper examines the possibility of coexistence of different implementations of protocols that users can change to improve their own capacity. It also examines games between protocols in cases when users’ packets management policies are applied.Problems in programming 2016; 4: 33-47 С развитием компьютерных сетей и их популяризацией, вопрос сохранения и обеспечения их эффективной работы выходит на первый план. Пользователи сети, которые могут влиять на обмен данными изменяя реализации протоколов обмена данными, создают проблему достижения справедливого разделения сетевых ресурсов. В данной работе исследуется возможность сосуществования различных реализаций протоколов, которые пользователи могут изменять для повышения собственной пропускной способности. С помощью теории игр определяются критерии существования состояний равновесия, при которых различные реализации протоколов могут сотрудничать и обеспечивать необходимый уровень пропускной способности для пользователей, а при каких определенная реализация будет доминировать над другой.Problems in programming 2016; 4: 33-47 Із розвитком комп’ютерних мереж і їх популяризацією, питання збереження і забезпечення їх ефективної роботи виходить на перший план. Користувачі мережі, які мають змогу впливати на обмін даними змінюючи реалізації протоколів обміну даними, створюють проблему досягнення справедливого поділу мережевих ресурсів. В даній роботі досліджується можливість співіснування різних реалізацій протоколів, які користувачі можуть змінювати з метою підвищення власної пропускної спроможності. За допомогою теорії ігор визначаються критерії існування станів рівноваги, за яких різні реалізації протоколів можуть співпрацювати і забезпечувати необхідний рівень пропускної спроможності для користувачів, а за яких певна реалізація домінуватиме над іншою.Problems in programming 2016; 4: 33-47 Інститут програмних систем НАН України 2018-07-03 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/211 10.15407/pp2016.04.033 PROBLEMS IN PROGRAMMING; No 4 (2016); 33-47 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2016); 33-47 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2016); 33-47 1727-4907 10.15407/pp2016.04 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/211/203 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2024-04-28T11:59:06Z
collection	OJS
language	rus
topic	game theory Nash equilibrium evolutionary game evolutionary stable strategy replicator dynamics UDC 004.7
spellingShingle	game theory Nash equilibrium evolutionary game evolutionary stable strategy replicator dynamics UDC 004.7 Ignatenko, O.P. Molchanov, O.A. Evolutionary games in TCP networks with speed restriction policies
topic_facet	game theory Nash equilibrium evolutionary game evolutionary stable strategy replicator dynamics UDC 004.7 теория игр равновесие Нэша эволюционные игры эволюционно-стабильная стратегия динамическое воспроизведения УДК 004.7 теорія ігор рівновага Неша еволюційні ігри еволюційно-стабільна стратегія динамічне відтворення УДК 004.7
format	Article
author	Ignatenko, O.P. Molchanov, O.A.
author_facet	Ignatenko, O.P. Molchanov, O.A.
author_sort	Ignatenko, O.P.
title	Evolutionary games in TCP networks with speed restriction policies
title_short	Evolutionary games in TCP networks with speed restriction policies
title_full	Evolutionary games in TCP networks with speed restriction policies
title_fullStr	Evolutionary games in TCP networks with speed restriction policies
title_full_unstemmed	Evolutionary games in TCP networks with speed restriction policies
title_sort	evolutionary games in tcp networks with speed restriction policies
title_alt	Эволюционные игры в TCP сетях с политиками ограничения скорости Еволюційні ігри в TCP мережах з політиками обмеження швидкості
description	Competitive development of various versions of network protocols is an essential part of computer networks. The most-used protocol today is Transmission Control Protocol (TCP). There is a large number of implementations of the TCP protocol, which differ by mechanism of congestion control. TCP develops by improving its existent implementations, vanishing some of them and via creation of a new ones. The possibility of using new versions of the protocol allows the user to increase the data rate by selecting the appropriate implementation of TCP. It is difficult to predict consequences of computer network users’ interaction in situations when many users try to achieve higher data rate by applying different TCP implementation. The actual task is to develop a theoretical and program tools to model such competitive dynamic interactions. This is the goal of my scientific-research work.Game theory, which is the theory of mathematical models of optimal decision making in situations of conflicts of interest, is the best suited to solve a particular problem because it allows you to find a solution in terms of non-cooperative interaction, which usually happens between the networks TCP-connections.This paper examines the possibility of coexistence of different implementations of protocols that users can change to improve their own capacity. It also examines games between protocols in cases when users’ packets management policies are applied.Problems in programming 2016; 4: 33-47
publisher	Інститут програмних систем НАН України
publishDate	2018
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/211
work_keys_str_mv	AT ignatenkoop evolutionarygamesintcpnetworkswithspeedrestrictionpolicies AT molchanovoa evolutionarygamesintcpnetworkswithspeedrestrictionpolicies AT ignatenkoop évolûcionnyeigryvtcpsetâhspolitikamiograničeniâskorosti AT molchanovoa évolûcionnyeigryvtcpsetâhspolitikamiograničeniâskorosti AT ignatenkoop evolûcíjníígrivtcpmerežahzpolítikamiobmežennâšvidkostí AT molchanovoa evolûcíjníígrivtcpmerežahzpolítikamiobmežennâšvidkostí
first_indexed	2024-09-16T04:08:16Z
last_indexed	2024-09-16T04:08:16Z
_version_	1818568175348875264
fulltext	Інструментальні засоби та середовища програмування © О.П. Ігнатенко, О.А. Молчанов, 2016 ISSN 1727-4907. Проблеми програмування. 2016. № 4 33 УДК 004.7 О.П. Ігнатенко, О.А. Молчанов ЕВОЛЮЦІЙНІ ІГРИ В TCP МЕРЕЖАХ З ПОЛІТИКАМИ ОБМЕЖЕННЯ ШВИДКОСТІ Із розвитком комп’ютерних мереж і їх популяризацією, питання збереження і забезпечення їх ефектив- ної роботи виходить на перший план. Користувачі мережі, які мають змогу впливати на обмін даними змінюючи реалізації протоколів обміну даними, створюють проблему досягнення справедливого поділу мережевих ресурсів. В даній роботі досліджується можливість співіснування різних реалізацій прото- колів, які користувачі можуть змінювати з метою підвищення власної пропускної спроможності. За до- помогою теорії ігор визначаються критерії існування станів рівноваги, за яких різні реалізації протоко- лів можуть співпрацювати і забезпечувати необхідний рівень пропускної спроможності для користува- чів, а за яких певна реалізація домінуватиме над іншою. Ключові слова: теорія ігор, рівновага Неша, еволюційні ігри, еволюційно-стабільна стратегія, динаміч- не відтворення. Вступ Конкурентний розвиток різних вер- сій мережевих протоколів є невід’ємною частиною розвитку комп’ютерних мереж. Найбільш вживаним протоколом на сього- дні є протокол TCP. Ядром протоколу є механізм керування переповнення, який контролює передачу пакетів у залежності від завантаженості вузьких місць мережі, при їх спільному використанні численни- ми користувачами. Ідея керування перепо- вненням досить проста: збільшити швид- кість, якщо мережа недовантажена, або зменшити швидкість, якщо вона переван- тажена. Момент зміни швидкості визнача- ється на основі інформації, яку користувач може отримати про те, чи дійшов його па- кет (за допомогою пакетів підтвердження ACK), або про те, що мережа переванта- жена (якщо він не отримає підтвердження протягом певного часу). На даний час вже створена велика кількість реалізацій протоколу TCP ([1]), що відрізняються між собою різними під- ходами до реалізації механізму керування переповненням. Розвиток TCP відбуваєть- ся шляхом вдосконалення існуючих його реалізацій, а також через відмову від де- яких з них і появу нових реалізацій. Мож- ливість застосування нових версій прото- колу дає користувачеві змогу підвищити швидкість передачі даних за допомогою вибору відповідного алгоритму реалізації TCP. У ситуаціях, коли багато користува- чів намагаються досягти більш високої швидкості передачі даних, передбачити наслідки такої їх взаємодії буває непросто. Це приводить до необхідності рішення проблем забезпечення стабільної та ефек- тивної роботи комп’ютерної мережі і спра- ведливого поділу ресурсів між її раціона- льними користувачами в умовах їх дина- мічної конкурентної взаємодії. Огляд наукових праць. З активіза- цією використання інтернету, а також з появою мобільних пристроїв та набуттям широкої популярності бездротовими ме- режами, необхідність у рішенні даної про- блеми надихає вчених в усьому світі на віднаходження нових методів для забезпе- чення ефективності функціонування комп’ютерних мереж. Природнім шляхом до рішення є за- стосування теорії ігор при розгляді взає- модії користувачів у мережі [2–6]. Деякі автори [2] базуючись на теорії ігор пропонують впровадити планувальни- ки та менеджери черг, які «карають» TCP- потоки, що порушують принципи керу- вання переповненням. У роботі [3] пропонується засновані на теоретико-ігровому підході протоколи, які, базуючись на даних, що отримують користувачі, дозволяють динамічно змі- нювати значення функції ціни передачі по- відомлень, що дає змогу адаптивно зміню- вати швидкість передачі, щоб досягти рів- новаги Неша у передачі пакетів. Інструментальні засоби та середовища програмування 34 Роботи [4–6] присвячені визначен- ню еволюційно-стабільної стратегії (ЕСС) для користувачів при пересилці даних. ЕСС [7] є поняттям з теорії еволюційних ігор, що визначається як стратегія (чиста або змішана), при дотриманні якої пропо- рції популяцій не змінюються у часі і вони захищені від нападу інших малих популя- цій. Під популяцією, в контексті комп’ютерних мереж, мається на увазі група гравців – користувачів мережі, а стратегія – певна реалізація протоколу TCP. У роботах [5, 6] наводиться модель еволюційної гри «Яструб-Голуб» і за до- помогою рівняння динамічної рівноваги визначаються умови існування ЕСС при взаємодії популяцій, що використовують алгоритм адитивне збільшення / мульти- плікативне зменшення (АЗМЗ) з різними параметрами. Постановка задачі Розглянуті роботи хоч і охоплюють широке коло шляхів до застосування тео- рії ігор при моделюванні роботи протоко- лу TCP в комп’ютерних мережах, але не розглядають випадки, коли маршрутиза- тори використовують не тривіальну полі- тику обслуговування пакетів. Мова йде не про політику «покарання», описану в ро- боті [2], а про політику маршрутизатора, коли він обмежує максимальну швидкість потоків за певним законом. У даній роботі досліджується існу- вання точки рівноваги при взаємодії TCP- потоків, що реалізують алгоритм АЗМЗ, у вузькому місці мережі, тоді, коли марш- рутизатор обмежує їх максимальну швид- кість. Зокрема, розглядаються випадки, коли маршрутизатор обмежує швидкість потоків у певному сталому співвідношен- ні (лінійно) і на певну сталу величину. Математична модель На сьогодні в протоколах TCP ви- користовуються кілька алгоритмів для ке- рування переповненням. Це такі алгорит- ми, як АЗМЗ та мультиплікативне збіль- шення/мультиплікативне зменшення (МЗМЗ), а також їх варіація – адитивне збільшення/адитивне зменшення (АЗАЗ). Алгоритм мультиплікативне збільшен- ня/адитивне зменшення практично не ви- користовується, оскільки він дуже погано забезпечує керування переповненням, адже при його використанні вікно швидко зростає й повільно падає, що призводить до багатьох послідовних втрат пакетів, по- ки вікно зменшуватиметься. АЗАЗ дещо кращий, але й він недостатньо швидко зменшує вікно переповнення. МЗМЗ наразі використовується для забезпечення з’єднань через канали високої швидкості. Оскільки можливість таких каналів значно більша за інші, повільний зріст вікна пере- повнення призводить до неефективного їх використання. Хоча МЗМЗ й забезпечує необхідну швидкість зростання вікна, але він не забезпечує справедливого поділу каналу між з’єднаннями. За час розробки різних версій про- токолу TCP стало зрозуміло, що саме ал- горитм АЗМЗ забезпечує гарний рівень керування переповненнями, оскільки за такого алгоритму вікно зростає повільно і спадає швидко, що дає змогу швидше по- вертати вікно до розміру, за якого не ви- никає втрат пакетів, а після зменшення ві- кна – довше уникати нових втрат пакетів, а також забезпечує справедливий поділ ка- налу між різними з’єднаннями. Даний ал- горитм можна записати у вигляді наступ- ної системи: ( 1)cwnd t   ( ) α, поки нема = переповнення ( ) β, при втраті пакету cwnd t cwnd t      (1) де cwnd(t) – вікно переповнення у час t, α – величина, на яку збільшується вікно пере- повнення, β – коефіцієнт, який визначає у скільки разів зменшиться вікно перепов- нення після втрати пакету. Причому α і β мають наступні обмеження: 0 1, 0.    (2) Чому саме алгоритм АЗМЗ такий цікавий з точки зору теоретико-ігрового підходу моделювання взаємодії користу- вачів, що поділяють спільний канал? Для того, щоб відповісти на це питання, пока- жемо, що алгоритм АЗМЗ утворює неру- Інструментальні засоби та середовища програмування 35 хому точку, яка відповідає рішенню «гри» між з’єднаннями – рівновазі за Нешем. Модель мережі. Нехай є топологія мережі, показана на рис. 1. В даній мережі 2 користувачі відкривають TCP-з’єднання, що реалізують алгоритм АЗМЗ для керу- вання переповненням, з сервером і надси- лають до нього якісь дані. Пропускна спроможність каналу C між сервером і ма- ршрутизатором менша, ніж сумарна про- пускна спроможність каналів від першого і другого користувачів до маршрутизатора, що забезпечує заповнення буфера маршру- тизатора пакетами, що очікуватимуть об- робки, і їх відкидання в разі його перепов- нення. Політика маршрутизатора для від- кидання пакетів – «відкидання з хвоста» (droptail), тобто якщо буфер, до якого над- ходить новий пакет, переповнений, тоді новий пакет відкидається. Причому відки- дання відбувається для обох з’єднань од- ночасно, тобто додатково відкидається па- кет другого з’єднання, що знаходиться у буфері (така поведінка спостерігалась у роботі [8]). Нехай пріоритети у з’єднань рівні (пріоритетність відсутня). Окрім цьо- го, модель задовольняє умовам, визначе- ним у роботі [4]. За визначених умов, поділ спільно- го каналу між користувачами має обме- ження, графічно показані на рис. 2. Рис. 1. Модель мережі Геометричне доведення теореми про нерухому точку для АЗМЗ. Якщо ро- здивитись поділ каналу TCP-з’єднаннями, що використовують АЗМЗ з параметрами (α1, β1) та (α2, β2) для керування перепов- ненням, в описаній моделі, який спостері- гається в роботі [6] (рис. 2), то можна зро- бити припущення, що через певний час поділ каналу між користувачами стабілізу- ється і користувачі поділяють канал між собою пропорційно до параметрів АЗМЗ. Нехай множина X  ℝ2 – це множи- на всіх можливих значень швидкостей (або величини вікна переповнення) двох з’єднань, що поділяють спільний канал. Вона обмежена трикутником 0CC, зобра- женим на рис. 2, тож очевидно, що вона є опуклою множиною. Нехай функція d – функція, що визначає відстань між двома точками множини X . Тоді ( , )X d – це ме- тричний простір. Рис. 2. Обмеження швидкості та поділ каналу між вдома з’єднаннями Згідно з теоремою Банаха про неру- хому точку, в n -мірному повному метрич- ному просторі nB  ℝn, в якому існує сти- скаюче відображення f : n nB B , існує єдина нерухома точка, така що ( )f x x . Нехай ( )f x – це перетворення, яке відбу- вається за один цикл роботи алгоритму АЗМЗ, що визначається системою (1). В такому разі для того, щоб довести, що да- ний алгоритм збігається до нерухомої точ- ки, достатньо показати, що функція ( )f x є стискаючою. Покажемо спочатку це для розглянутої моделі (двовимірного випад- ку), тобто для X . Стискаючою функція називається функція f, для якої виконується наступна умова: 1 2 1 2( ( ), ( )) ( , ),d f x f x d x x Інструментальні засоби та середовища програмування 36 де  : 0 ≤  < 1 – коефіцієнт стискання, ix – деяка точка метричного простору X . Перепишемо систему (1) у вигляді відображення точок прямої ),,0(( 121 CССС )0,(2 CC (рис. 3) у саму себе: ,: txxf   (3) де x та tx   – точки відрізку 21СС , t : min {t ≥ 0: tx    C}, а  і  можуть бути записані у наступному вигляді:        2 1 0 0    , . 2 1           Відображення (3), згідно із визна- ченням і враховуючи обмеження на  і  , є відображенням CCf : , і є неперерв- ним, оскільки є комбінацією неперервних лінійних відображень. Нехай 21   (якщо ж 12   , то можемо поміняти індекси з’єднань, щоб розглядати випадок, коли 21   ). Нехай маємо дві точки А(x1, y1) і B(x2, y2), які на- лежать відрізу 21СС . Подіємо на ці точки перетворенням  x. Перед цим представи- мо  у вигляді наступної комбінації пере- творень: . 0 01 10 01 1 211                  I Рис. 3. Перетворення АЗМЗ для точок A і B Спочатку подіємо на точки A і B перетворенням .1I В результаті отрима- ємо дві нові точки A і B , які лежать на прямій, паралельній прямій 21СС , оскіль- ки координати цих точок були зменшені в однакову кількість разів, рівну 1 . Тепер подіємо на точки A і B перетворенням   і отримаємо точки A′′ і B′′. Оскільки в матриці   одне зі значень рівне 1, то од- на координата ( ix ) кожної з точок не змі- ниться, а друга ( iy ) зменшиться у вели- чину 121  . Якщо на отримані точки подіяти перетворенням t , то ми отрима- ємо нові точки D та E, що належатимуть прямій x + y = C (назвемо її с), а саме відрізку 21СС , оскільки 0i , відповідно й напрям вектора  лежить у межах кута (0, /2). Для того щоб показати, що відо- браження (3) є стискаючим, достатньо по- казати, що d(AB) > d(DE). Очевидно, що d(A′B′) < d(AB) для  1 <1. Оскільки пряма c, на якій лежить відрізок AB, та відрізок BA  паралельні, і перетворення t є па- ралельною проекцією, то довжина відрізка утвореного цим перетворенням, прикладе- ним до A і B , рівна довжині для  i >0. t  має ті ж властивості, що і t , але в прик- ладенні до точок A і B . А оскільки d(A′′B′′) ≤ d(), причому одна координата – не змінюється, то мож- на зробити висновок, що відрізок DE, отриманий внаслідок прикладення перет- ворення t до відрізку A′′B′′, буде не бі- льшим за відрізок BA  . Таким чином ма- ємо наступну нерівність, яка й доводить, що перетворення (3) є стискаючим: ).()()( ABdBAdDEd  (4) Аналітичне доведення теореми про нерухому точку для АЗМЗ. Довести те, що нерухома точка для відображення (3) у X існує, причому існує єдина, можна й аналітично, за допомогою протиріччя. Нехай маємо дві точки 1 , x2  C, x1 *  x2 , x1 : βx1 * + αt1 = x1 , x2 : βx2 * + αt2 = Інструментальні засоби та середовища програмування 37 = x2 , тобто такі, що при перетворенні (3) переходять самі у себе, а відповідно є не- рухомими. Нехай є деяка точка y = x1 + + (1 – )x2 * – деяка точка з відрізку x1 x2 . Застосуємо відображення (3) до точки y :  ytyyf )( ytxx   ))1(( 21 . (5) Якщо C записати як C + (1 – )C, а ty розписати за формулою 1 2 1 2 n n n C y z T         , то отримаємо наступне значення: 1 2 1 ( (1 )yt C C         * * 1 1 1 2 1( ( ) (1 )( ) )x x      * * 2 1 2 2 2( ( ) (1 )( ) ),x x     яке після рівноцінних перетворень прийме вигляд 1 2(1 ) .yt t t    (6) Підставивши значення (6) у форму- лу (5) і виконавши рівноцінні перетво- рення, отримаємо наступне рівняння: * * 1 1 2 2( ) ( ) (1 )( ) ,f y x t x t y           що можливо лише у випадку, коли всі 1  і всі 0  . А це протирічить умові. Доведення теореми про нерухому точку для АЗМЗ для будь-якого скін- ченного числа з’єднань. Розглянемо мо- дель, описану у попередньому пункті, але тепер для N з’єднань. Довести, що при взаємодії N TCP-з’єднань, що реалізують АЗМЗ, існує єдина нерухома точка, можна аналогічно з доведенням для випадку двомірного простору. Для N з’єднань швидкість надси- лання даних обмежена простором nX , який має обмеження 0ix  і Cx N i i  1 , де ix – швидкість i-го з’єднання.  і  можуть бути записані у наступному ви- гляді:                n    ...00 ............ 0...0 0...0 2 1 , . ... 2 1                n    Якщо, як і раніше, взяти дві довіль- ні точки А і B, що належать Cx N i i  1 , ро- змістити i у порядку зменшення зі збі- льшенням індексу, розкласти  у вигляді добутку  I1 , і послідовно виконати ві- дображення I1 ,   та t , то ми отрима- ємо точки D та E, причому такі, що відпо- відатимуть умові (4). Це досягається за- вдяки тому, що перетворення I1 змен- шить довжину відрізка AB, а   та t не збільшать довжину відрізка отриманого внаслідок дії I1 . Модель з лінійним обмеженням швидкості. Модель, розглянута у роботі [5], описує взаємодію двох TCP-з’єднань, що реалізують АЗМЗ, у каналі з пропуск- ною спроможністю C. Політика маршру- тизатора така, що сумарна швидкість пе- ресилки даних обома з’єднаннями не пе- ревищує C й обмеження швидкості може бути записне як x + y ≤ C. У попередньому пункті ми обґрунтували існування рівно- ваги за Нешем у такій моделі. Але чи існувала би рівновага, якби політика ма- ршрутизатора була іншою? Якби він об- межував швидкість для деяких з’єднань, чи сприяв іншим? Для відповіді на це питання розглянемо модифікації описаної моделі. Модифікуємо модель, визначивши політику маршрутизатора параметричним рівнянням: 1 2 ,x y C   де i – додатній параметр обмеження швидкості пересилки пакетів для i-го Інструментальні засоби та середовища програмування 38 з’єднання. Слід зазначити, що i ≥ 1, оскі- льки в іншому випадку (коли 0 < i < 1) можлива ситуація, коли фактичне значення швидкості пересилки даних з’єднанням буде більшим за пропускну спроможність C, що є неможливим. Зазначена політика маршрутизатора певною мірою відповідає визначенню «пріоритетів» для різних з’єднань. Це не є тим пріоритетом, який вказується в сег- ментах протоколу TCP, але така політика дозволяє зменшити швидкість надсилання даних для з’єднань TCP, що реалізують АЗМЗ. Ситуації, коли деяке i > 1, відпо- відають політиці обмеження швидкості пересилки пакетів деякого з’єднання. Як- що обидва i > 1, то частина пропускної здатності взагалі не використовуватиметь- ся даними з’єднаннями, що можливо ко- ли, наприклад, частина спільного каналу була зарезервована для виділених каналів, які потребують певного постійного зна- чення пропускної спроможності. Приклад поділу каналу між з’єднаннями показано на рис. 4. Рис. 4. Обмеження пропускної спромож- ності для з’єднань з лінійним обмеженням швидкості ( 1 2  , 2 1  ) Доведення існування нерухомої точки для моделі з лінійним обмежен- ням швидкості. У випадку, коли пряма С1С2 була зміщена відповідно до парамет- рів 1 і 2 (рис. 5), нерухома точка теж існує і вона єдина. Доведення аналогічне до геометричного доведення, наведеного вище. Після того, як i розташовані у порядку спадання, й до точок A і B що на- лежать 1 2 ,x y C   застосовано відо- браження I1 , будуть отримані точки A′ і B′, причому виконується права частина нерівності (4). При застосуванні перетво- рення αt на до точок A′′ і B′′, отриманих після застосування перетворення   на точках A′ і B′ виконуватиметься й ліва ча- стина нерівності (4). Рис. 5. Перетворення АЗМЗ для точок A і B (для моделі з лінійним обмеженням швидкості) Матрична гра та функція корис- ності для моделі з лінійним обмежен- ням швидкості. Сформулюємо для опи- саної моделі умови гри «Яструб-Голуб» (рис. 6). Оскільки рівняння прямої, що об- межує швидкість з’єднань у вузькому мі- сці мережі змінилось, маємо записати но- ву формулу для функції корисності, що враховує параметри 1 і 2 . Запишемо рівняння для відображення АЗМЗ в даній моделі: 1 2 1 1 2 1n n n nC x y x y         1 1 1 2 2 2( ) ( )n n n nx T y T         . (7) За допомогою (6) можна записати нову формулу для визначення часу до від- кидання пакетів маршрутизатором: Інструментальні засоби та середовища програмування 39 1 1 2 2 1 1 2 2 .n n n C x y T             Рис. 6. Біматрична гра “Яструб-Голуб” Тепер можемо записати значення швидкості пересилки даних першим з’єднанням у момент часу перед n+1-м відкиданням пакету 1nx  – (значення для 1ny  знаходиться аналогічно): 1 2 1 1 1 1 1 2 2 α β β α , α δ α δ n n n n C x x T qx      1 1 2 2 2 1 1 1 2 2 α δ β α δ β , β 1 β α δ α δ i iq      . Якщо таким же чином розписати nx через 1nx  , а його через 2nx  і т. д., то отримаємо наступне значення nx для до- вільного n: 1 2 0 1 1 2 2 (1 ) . (1 ) n n n C q x q x q             Тоді формули для знаходження се- реднього значення для x і T можуть бути записані наступним чином: 1 2 1 1 2 2 α β 1 lim α δ α δ (1 ) n n C x x q       1 2 1 1 2 2 2 1 α β . α δ β α δ β C   1 2 1 1 2 2 2 1 β β lim α δ β α δ β n n C T T     . Значення функції корисності може бути розраховане за формулою:  λ ,i iJ K Thp R  (8) де K – коефіцієнт збільшення значення корисності, iThp – швидкість надсилання пакетів,  – коефіцієнт чутливості до втрати пакетів, R = 1 / T – швидкість втра- ти пакетів. Для визначення значення функції корисності для даної моделі залишилось визначити значення Thp : 1 1 1 2 1 1 1 2 2 2 1 β 1 β α β . 2 2 α δ β α δ β x x C Thp       Хоча всі формули розглядають мо- дель відносно x, але для y всі значення ро- зраховуються аналогічно. Отримані серед- ні значення Thp та T, можна використову- вати у формулі (8) для визначення функції корисності для кожного з’єднання. Критерії існування ЕСС для мо- делі з лінійним обмеженням швидкості. Критеріями існування ЕСС для даної мо- делі за визначених умов будуть наступні значення: 2 1 2 1 2 1 1 1 2 2 2 1 ( ) 8( ) C               , 2 1 2 2 1 1 2 1 2 2 2 2 2 2 1 1 1 2 2 2 1 ( (1 ) 4 ( ) C                   2 1 2 1 2 1 1 2( 2 2 )),           для чистих стратегій та 2 1 2 1 1 1 2 1 2 2 2 2 2 2 1 1 1 2 2 2 1 ( (1 ) 4 ( ) C                   2 1 2 1 2 1 1 2( 2 2 )),           2 1 2 2 1 2 2 1 2 2 2 2 2 2 2 1 1 2 2 2 1 ( (2 4 ( ) C                   2 1 1 2 2 2 1 22 ) (1 ))           для змішаних. Модель зі сталим обмеженням швидкості. Більш реальною, в порівнянні з попередньою, є політика маршрутизатора Інструментальні засоби та середовища програмування 40 за сталим обмеженням швидкості, тобто обмеження певною константною величи- ною. Така політика застосовується в без- дротових мережах для обмеження швидко- сті особливо агресивних з’єднань. Це ро- биться для того, щоб маршрутизатор не був зайнятий обробкою даних лише одно- го з’єднання, а, в певній мірі, справедливо обслуговував всі з’єднання, чиї дані про- ходять через нього. Знов модифікуємо модель, визначе- ну вище. Нехай x* та y* обмеження швид- кості для кожного з двох з’єднань (тобто їх максимальна швидкість не може переви- щувати ці обмеження). Тоді політика мар- шрутизатора може бути записана наступ- ним чином: * , , x y C x x y y    або в іншій формі: min{ , , }x y x y C x y    . Графічно така політика маршрути- затора показана на рис. 7. Рис. 7. Обмеження максимальної швидкос- ті передачі даних з’єднаннями за допомо- гою констант Доведення існування нерухомої точки для моделі зі сталим обмеженням швидкості. Оскільки границя області до- пустимих значень швидкостей з’єднань у моделі зі сталим обмеженням швидкості визначається не однією прямою, доведення того, що відображення АЗМЗ стискаюче для такого випадку складніше. Для даної моделі множина X обмежена прямими x = 0, x = x, y = 0, y = y* та x + y = C. Якщо розглянути окремо три облас- ті, утворені поділом множини X променя- ми j та h з рис. 8, то для кожної окремо до- вести що перетворення АЗМЗ є стискаю- чим досить просто, й аналогічно до дове- дення для моделі без обмежень. Покажемо, що для критичних випадків, такого як ві- дображення точок A і B, що лежать на різ- них прямих, відображення (3) все ще є стискаючим. Після того, як на точки A і B подія- но відображенням I1 , отримані точки A′ і B′. Нехай промінь j перетинається з пря- мими x = x* і x + y = C у точці J, а з прями- ми x = 1 x* (на якій лежить A′) і x + y = = 1 C (на якій лежить B′) у точці J′. Оскі- льки 0A, j та 0B – промені, а прямі x = x* і x = 1 x* паралельні, та прямі x + y = C і x + y = 1 C – паралельні, то за властивістю променів, що випущені з однієї точки й перетинають паралельні прямі, можна ска- зати, що d(A′J′) < d(AJ) і d(B′J′) < d(BJ). Рис. 8. Відображення АЗМЗ для моделі зі сталим обмеженням швидкості Про точки A′′, J′′ і B′′, отримані вна- слідок дії на точки A′, J′ і B′ відображенням β′, можна сказати наступне: Інструментальні засоби та середовища програмування 41 1) d(A′′J′′) = d(A′J′), оскільки коор- дината x однакова у A′ і J′, а відображення β′, згідно з визначенням, впливає лише на координату y; 2) d(B′′J′′) ≤ d(B′J′). Якщо подіяти відображенням αt на відрізок B′′J′′, то d(EF) ≤ d(B′′J′′), як і було показано раніше. Якщо подіяти відображенням αt* на відрізок A′′J′′, де t: min{x+αt  y}, то до- вжина утвореного відрізку (l) буде рівна довжині A′′J′′, хоча довжина відрізку, який утвориться на прямій x + y = C (позначимо це відрізок g) може бути й більшою (тобто d(DF) > d(A′B′) й, можливо, d(DF) > d(AB)). Але якщо подіяти на точки A і B відобра- женням αt, де t: min{x+αt  x + y = C}, то довжина отриманого відрізку буде бі- льшою за довжину відрізку g, оскільки d(AB) > l. Таким чином, умова (4) виконуєть- ся для даного перетворення, що й треба було довести. Функція корисності для моделі зі сталим обмеженням швидкості. Оскіль- ки дана модель обмежує швидкість кіль- кома функціями, необхідно роздивитись кожен випадок окремо. Для випадку, коли є 2 з’єднання необхідно роздивитись на- ступні три випадки: * * x C y y y       , що відповідає ситуації, коли нерухома точка знаходиться на пря- мій y = y; * x C y y C x       , що відповідає ситуації, коли нерухома точка лежить на прямій x + y = C; * * x x y C x       , що відповідає ситуації, коли нерухома точка знаходиться на пря- мій x = x. Друга ситуація була розглянута у [5 і 6], тож розглянемо перший та третій випадки. Для першого випадку відображення АЗМЗ може бути записане формулою: n n nx y x y    * 1 2 2n n n ny y y y T      . Звідси ми можемо знайти значення nT : * * * 2 2 2 2 n n y y y y T          * * 2 2 2 2 (1 ) . y y       (9) Оскільки nT не залежить від поточ- них координат nx та ny , його значення відповідає значенню середнього часу до відкидання пакетів T . Знайдемо значення швидкості пере- силки даних першим з’єднанням у момент часу перед n+1-м відкиданням пакетів: 1 2 1 1 1 1 2 n n n n y x x T x             . Формула для знаходження nx для будь-якого n та середнє значення x можуть бути визначені за допомогою формул: 1 2 1 0 1 2 1 1 , 1 n n n y x x             1 2 1 2 2 1 2 1 1 lim . 1 n n y y x x                 Значення середньої швидкості пере- силки даних для обох з’єднань може бути знайдене за наступними формулами: 1 1 1 2 1 2 1 1 , 2 2 x x y Thp            (10) 2 2 2 1 . 2 2 y y Thp y        (11) Аналогічно знаходяться значення для другого з’єднання. Отримавши значен- ня T та Thp , їх можна використати для роз- рахунку значення функції корисності (8). Значення T та Thp для третього ви- падку, за якого нерухома точка знаходить- Інструментальні засоби та середовища програмування 42 ся на прямій x = x, можуть бути знайдені аналогічно до того, як були знайдені ці значення для першого випадку, розгляну- того вище. Ці значення можуть бути запи- сані наступними формулами: 1 1 1 . x T     (12) 1 1 1 1 . 2 2 x x Thp x        (13) 1 2 2 1 2 1 2 1 . 2 2 y y x Thp            (14) Визначивши значення середнього часу T та середньої швидкості надсилання пакетів користувачами Thp , можна визна- чити значення функцій корисності для різ- них комбінацій параметрів АЗМЗ протоко- лу TCP. Нехай, як і в [5], є дві стратегії, які можуть обирати користувачі, з параметра- ми АЗМЗ ( 1 , 1 ) для агресивної стратегії H і ( 2 , 2 ) для мирної стратегії D. Зна- чення функції корисності для різних стра- тегій можна буде визначити за різними формулами. Для випадків, коли два з’єднання використовують однакові стра- тегії, вони поділять спільний канал порів- ну, тобто виконуватиметься умова * x C y y C x       . Вважаємо, що x* + y* ≤ C. В такому разі значення для T та Thp відпо- відатимуть значенням з [4]. У випадках, коли взаємодіють різні стратегії, і викону- ються умови * * x C y y y       і/або * * y x x x C     , для розрахунку функції корисності слід використовувати значення T та Thp , що визначаються за формулами (9), (10), (11), (12), (13) і (14). Визначивши всі функції корисності для даної моделі, можна перейти до визна- чення критеріїв існування ЕСС. Критерії існування ЕСС для мо- делі зі сталим обмеженням швидкості. Оскільки при розгляді даної моделі необ- хідно розглядати 3 окремі випадки поло- ження нерухомої точки, то й умови існу- вання ЕСС також будуть розбиті на три частини. Для чистих стратегій обмеження 1 матиме значення таке ж, як і визначене в [6]. Значення ж 2 буде різним, в залеж- ності від того, чи виконується умова * * x C y y y       , тобто: 1 2 2 1 . y x C y C y            (15) Слід зазначити, що в умові (15) i і i не відповідають стратегіям H і D, а приймають значення в залежності від кон- кретної формули. У разі виконання умови (15) 2 ма- тиме наступне значення: * 2 1 2 1 2 2 1 2 (2 (1 ) 2 (1 ))1 2 2 y C              * 1 * 1 , ( 2 ) y C C y     а в разі невиконання 2 1 2 2 1 2 1 2 2 2 2 1 2 2 1 ( (1 ) 4( ) C               2 1 1 2( 2 1)).      Для змішаних стратегій, у разі ви- конання умови (15), 1 матиме таке ж зна- чення, як і 2 для чистих стратегій. Зна- чення ж 2 буде залежати від того, чи ви- конується умова * * y x x x C     , тобто: 2 1 1 2 . x y C x C x            (16) У разі виконання умови (16) 2 ма- тиме наступне значення: 1 2 2 2(1 ) (1 )C 4 x        1 2 1 2 2 12 x C C x           . Інструментальні засоби та середовища програмування 43 А в разі невиконання умови, 2 прийме значення 2 1 2 1 2 1 2 2 1 2 2 2 2 2 2 1 2 2 1 ( (1 2 ) (1 )) . 4( ) С                     При розгляді випадку, коли корис- тувачі мають симетрично протилежні об- меження, значення параметра чутливості до втрати пакетів будуть аналогічні до значень, отриманих за допомогою виве- дених вище формул. Різниця полягатиме лише у тому, що замість y буде x і на- впаки. Еволюційна гра для модифікова- них математичних моделей. Нехай є по- пуляція гравців, які поділяють вузьке міс- це мережі, і які можуть динамічно обирати одну з двох стратегій (реалізацій АЗМЗ). Рішення про зміну стратегії приймається гравцем на основі значення функції корис- ності, яке визначається із певною затрим- кою, оскільки потрібен певний час, для то- го щоб порівняти наскільки нова стратегія краща за попередню. В процесі такого ви- бору, з часом, за певних умов, вибір кори- стувачів може стати або однаковим, або розподілитись (тобто вони обиратимуть стратегію з певною ймовірністю). Така взаємодія користувачів і нази- вається еволюційною грою (в прикладенні до комп’ютерних мереж). Умови існування стабільного рішення такої гри, тобто ЕСС, для розглянутих модифікованих моделей були визначені на основі обмежень зна- чення параметра чутливості до втрат паке- тів λ . У загальному випадку цей параметр може мати різні значення для кожного з’єднання. Але при розгляді еволюційної гри для даних моделей ми вважаємо, що його значення однакове у всіх з’єднань. Результати моделювання такої гри наведені у наступному розділі. Моделювання Модель з лінійним обмеженням швидкості. Нехай маємо двох користува- чів з наступними значеннями параметрів АЗМЗ: ( 1 , 1 ) = (1.0, 0.8), ( 2 , 2 ) = =(1.0, 0.5). Встановимо параметр 1 рів- ним 2.0, а 2 рівним 1.0. Зазначимо, що розмір буферу було встановлено у 100 па- кетів (розмір всіх пакетів з даними рів- ний). Пропускна спроможність спільного каналу C становить 1000 пакетів на секу- нду. Середні значення швидкостей корис- тувачів матимуть значення 3 1 , . 8 8 x C y C  На рис. 9 показано поділ каналу за визначених значень параметрів. Отримані значення майже точно ві- дповідають розрахованим. На рис. 10 по- казано відношення величин вікна перепов- нення користувачів для визначених пара- метрів. Рис. 9. Графік проходження пакетів корис- тувачів через спільний канал при ( 1 , 1 ) = =(1.0, 0.8), ( 2 , 2 ) = (1.0, 0.5), ( 1 , 2 ) = =(2.0, 1.0) (пряма лінія – перший користу- вач, пунктирна лінія – другий) Рис. 10. Графік залежності величин вікна переповнення для двох користувачів при ( 1 , 1 ) = (1.0, 0.8), ( 2 , 2 ) = (1.0, 0.5), ( 1 , 2 ) = (2.0, 1.0) Інструментальні засоби та середовища програмування 44 Зробимо зміну параметра. Встано- вимо 1 = 0.5 і 2 = 0.8. Розраховані зна- чення середніх швидкостей рівні 3 9 , . 14 14 x C y C  Графіки поділу каналу та відно- шення величин вікна переповнення для нових параметрів показані на рис. 11 та рис. 12 відповідно. Рис. 11. Графік проходження пакетів кори- стувачів через спільний канал при ( 1 , 1 ) = (1.0, 0.5), ( 2 , 2 ) = (1.0, 0.8), ( 1 , 2 ) = (2.0, 1.0) (пряма лінія – перший користувач, пунктирна лінія – другий) Рис. 12. Графік залежності величин вікна переповнення для двох користувачів при ( 1 , 1 ) = (1.0, 0.5), ( 2 , 2 ) = (1.0, 0.8), ( 1 , 2 ) = (2.0, 1.0) Нехай z приймає значення 0,75C, а параметри АЗМЗ ( 1 , 1 ) = (1.5, 0.75), ( 2 , 2 ) = (1.0, 0.5), тоді умова (16) може бути записана як 2 1 1 2 1 0.25 . 4 x C x C C          Можна побачити, що за даних па- раметрів, нерухома точка відображення АЗМЗ знаходиться на стику двох прямих, щоб обмежують швидкість передачі. За формулами (13) і (14) розрахуємо значення середніх швидкостей користувачів за но- вих умов: 3 1 , . 4 4 x C y C  Графік поділу спільного каналу для нових значень параметрів показано на рис. 13. Рис. 13. Графік проходження пакетів кори- стувачів через спільний канал при ( 1 , 1 ) = (1.5, 0.75), ( 2 , 2 ) = (1.0, 0.5), z = 0.75C Як видно з графіка, перший корис- тувач захоплює більшу частину каналу, і його швидкість знаходиться на межі до- пустимої швидкості, тобто є трошки бі- льшою, ніж очікувана середня швидкість. Швидкість першого користувача дещо менша за очікувану. Це стається через те, що при великій різниці між парамет- рами АЗМЗ, синхронне відкидання паке- тів більше впливає на “мирне” з’єднання, ніж на “агресивне”. Для того, щоб випра- вити це, необхідно ускладнити процес керування чергою, й відкидати більше пакетів “агресивного” користувача, ніж “мирного”. Графік відношення значень вікна переповнення показано на рис. 14. Інструментальні засоби та середовища програмування 45 Рис. 14. Графік залежності величин вікна пропускання для двох користувачів при ( 1 , 1 ) = (1.5, 0.75), ( 2 , 2 ) = (1.0, 0.5), z = 0.75C Еволюційна гра для моделі з лі- нійним обмеженням швидкості. Нехай маємо популяцію користувачів, які дина- мічно обирають одну з двох реалізацій протоколу TCP, що реалізують алгоритм АЗМЗ з параметрами ( 1 , 1 ) = (1.0, 0.7), ( 2 , 2 ) = (1.0, 0.5), а коефіцієнти обме- ження швидкості рівні ( 1 , 2 ) = (1.1, 1.0), та С = 1000. Для визначених параметрів АЗМЗ значення  матиме наступні обме- ження для ЕСС в змішаних стратегіях: 72995 75000.  Якщо  = 5, K = 1.5, а  = 73500, то розподіл користувачів за протоколами мо- жна побачити на рис. 15. Рис. 15. Частка користувачів, що викорис- товують протокол TCP з параметрами ( 1 , 1 ) = (1.0, 0.7), ( 2 , 2 ) = (1.0, 0.5), ( 1 , 2 ) = (1.1, 1.0) Еволюційна гра для моделі зі ста- лим обмеженням швидкості. Нехай має- мо популяцію користувачів, які динаміч- но обирають одну з двох реалізацій про- токолу TCP, що реалізують алгоритм АЗМЗ з параметрами ( 1 , 1 ) = (2.0, 0.8), ( 2 , 2 ) = (1.5, 0.2), а коефіцієнт обме- ження швидкості z = 0.8C (що задовольняє умові (16)), та С = 1000. Для визначених параметрів АЗМЗ значення  матиме на- ступні обмеження для ЕСС в змішаних стратегіях: 37333 48000.  При  = 5, K = 1.5, а  = 40000, то розподіл користувачів за протоколами мо- жна побачити на рис. 16. Збільшення значення коефіцієнта  до 43000 призведе до зменшення очікува- ної частки користувачів, що застосовують першу стратегію (рис. 17). Рис. 16. Частка користувачів, що викорис- товують протокол TCP з параметрами ( 1 , 1 ) = (2.0, 0.8), ( 2 , 2 ) = (1.5, 0.2), z = 0.8C,  = 40000 Рис. 17. Частка користувачів, що викорис- товують протокол TCP з параметрами ( 1 , 1 ) = (1.0, 0.7), ( 2 , 2 ) = (1.0, 0.5), z = 0.8C,  = 43000 Інструментальні засоби та середовища програмування 46 Висновки У роботі доведено існування точки рівноваги при використанні спеціальних політик обслуговування пакетів користу- вачів. Проведено моделювання, яке на практиці підтвердило збіжність поділу спі- льного каналу між користувачами до ста- лого значення. В подальшому було б доцільно ро- зширити досліджену модель на довільну структуру мережі з довільною кількістю користувачів, а також дослідити взаємодію TCP-протоколів, що реалізують інші алго- ритми (напр. МЗМЗ). 1. Afanasyev A., Tilley N., Reiher P., Kleinrock L. Host-to-Host Congestion Control for TCP // IEEE Communications Surveys & Tutori- als. – 2012. – 12(3). – P. 304–342. 2. Garg R., Kamra A., Khurana V. A game- theoretic approach towards congestion con- trol in communication networks // Computer Communications Review. – 2002. – 32(3). – P. 47–61. 3. Alpcan, T., Bas¸ar, T. A utility-based conges- tion control scheme for Internet-style net- works with delay // IEEE Transactions on Networking. – 2005. – 13(6). – P. 1261–1274. 4. Altman E., El-Azouzi R., Hayel Y., Tembine H. An evolutionary game approach for the design of congestion control protocols in wireless networks // Proceedings of 2008 6th International Symposium on Mod- eling and Optimization in Mobile. – 2008. 5. Altman E., El-Azouzi R., Hayel Y., Tembine H. The evolution of transport protocols: an evolutionary game perspective // Computer Networks Journal. – 2009. – 53(10). – P. 1751–1759. 6. Ignatenko O. and Synetskyi O. Evolutionary Game of N Competing AIMD Connections // Information and Communication Technolo- gies in Education, Research, and Industrial Applications, Springer International Publish- ing. – 2014. – P. 325–342. 7. Maynard Smith J. Game theory and the evo- lution of fighting // John Maynard Smith (Ed.), On Evolution, Edinburgh University Press. – 1972. – P. 8–28. 8. Ait-Hellal, O., Altman, E., Elouadghiri, D., Erramdani, M., Mikou, N. Performance of TCP/IP: the case of two Controlled Sources // ICCC’97. – 1997. References 1. Afanasyev A., Tilley N., Reiher P., Kleinrock L. Host-to-Host Congestion Control for TCP // IEEE Communications Surveys & Tutorials. – 2012. – 12(3). – P. 304–342. 2. Garg R., Kamra A., Khurana V. A game- theoretic approach towards congestion control in communication networks // Computer Communications Review. – 2002. – 32(3). – P. 47–61. 3. Alpcan, T., Bas¸ar, T. A utility-based congestion control scheme for Internet-style networks with delay // IEEE Transactions on Networking. – 2005. – 13(6). – P. 1261–1274. 4. Altman E., El-Azouzi R., Hayel Y., Tembine H. An evolutionary game approach for the design of congestion control protocols in wireless networks // Proceedings of 2008 6th International Symposium on Modeling and Optimization in Mobile. – 2008. 5. Altman E., El-Azouzi R., Hayel Y., Tembine H. The evolution of transport protocols: an evolutionary game perspective // Computer Networks Journal. – 2009. – 53(10). – P. 1751–1759. 6. Ignatenko O. and Synetskyi O. Evolutionary Game of N Competing AIMD Connections // Information and Communication Technolo- gies in Education, Research, and Industrial Applications, Springer International Publish- ing. – 2014. – P. 325–342. 7. Maynard Smith J. Game theory and the evolution of fighting. John Maynard Smith (Ed.), On Evolution, Edinburgh University Press. – 1972. – P. 8–28. 8. Ait-Hellal, O., Altman, E., Elouadghiri, D., Erramdani, M., Mikou, N. Performance of TCP/IP: the case of two Controlled Sources // ICCC’97. – 1997. Одержано 29.09.2016 Інструментальні засоби та середовища програмування 47 Про авторів: Ігнатенко Олексій Петрович, кандидат фізико-математичних наук, старший науковий співробітник, Кількість наукових публікацій в українських виданнях – 35. http://orcid.org/0000-0001-8692-02062, Молчанов Олексій Андрійович, аспірант, Кількість наукових публікацій в українських виданнях – 2. http://orcid.org/0000-0001-8384-0918. Місце роботи авторів: Інститут програмних систем НАН України, 03187, Київ-187, Проспект Академіка Глушкова, 40. Тел.: 526 6025. E-mail: o.ignatenko@gmail.com Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», 03056, Київ-56, проспект Перемоги, 37. E-mail: oleksii.molchanov@gmail.com mailto:o.ignatenko@gmail.com mailto:oleksii.molchanov@gmail.com

Evolutionary games in TCP networks with speed restriction policies

Репозитарії

Схожі ресурси