Моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту

При моделюванні мереж нерідко виникає необхідність урахування наслідків дій, спрямованих на погіршення роботи системи. Ці дії можуть бути результатом атаки або нескоординованості дій користувачів у самій системі. Одним з можливих підходів до аналізу такого роду ситуацій є потокові моделі (fluid mode...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2009
Автор:	Ігнатенко, О.П.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2009
Теми:	Прикладне програмне забезпечення
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/4599
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту. / O.П. Ігнатенко // Пробл. програмув. — 2009. — № 3. — С. 66-72. — Бібліогр.: 11 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-4599
record_format	dspace
spelling	irk-123456789-45992009-12-10T12:00:39Z Моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту Ігнатенко, О.П. Прикладне програмне забезпечення При моделюванні мереж нерідко виникає необхідність урахування наслідків дій, спрямованих на погіршення роботи системи. Ці дії можуть бути результатом атаки або нескоординованості дій користувачів у самій системі. Одним з можливих підходів до аналізу такого роду ситуацій є потокові моделі (fluid models). У роботі розглядається узагальнення моделі роботи сервера, що обслуговує користувачів на випадок конфлікту. Така модель дозволяє описати атакуючі дії та поведінку системи захисту. Проводиться формальна постановка задачі за наявності інтегральних обмежень на завдання користувачів. Знайдені умови за якими гра може бути закінчена за скінчений час. При моделировании сетей нередко возникает необходимость учета последствий умышленных действий, направленных на ухудшение работы системы. Эти действия могут быть результатом атаки или нескоординированости действий пользователей в самой системе. Одним из возможных подходов к анализу такого рода ситуаций являются потоковые модели. В работе рассматривается обобщение модели работы сервера, обслуживающего пользователей на случай конфликта. Проводится формальная постановка и анализ полученной дифференциальной игры. Найдены условия, при которых игра может быть закончена за конечное время. In the network management systems often encountered a situation where there is a need to deal with malicious intrusion attempts aimed to obstruct overall performance. These actions may be the result of attack or another action. One of the possible approaches to the analysis of such situations are fluid models and a discrete controlled random walk models. In this work a generalization of the usual models of single server queue which can describe the attacking action and behavior of the system of protection is presented. Formulation and analysis of the problem are proposed. There is found the conditions under which the game can be finished. 2009 Article Моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту. / O.П. Ігнатенко // Пробл. програмув. — 2009. — № 3. — С. 66-72. — Бібліогр.: 11 назв. — укр. 1727-4907 http://dspace.nbuv.gov.ua/handle/123456789/4599 004.7 uk Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Прикладне програмне забезпечення Прикладне програмне забезпечення
spellingShingle	Прикладне програмне забезпечення Прикладне програмне забезпечення Ігнатенко, О.П. Моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту
description	При моделюванні мереж нерідко виникає необхідність урахування наслідків дій, спрямованих на погіршення роботи системи. Ці дії можуть бути результатом атаки або нескоординованості дій користувачів у самій системі. Одним з можливих підходів до аналізу такого роду ситуацій є потокові моделі (fluid models). У роботі розглядається узагальнення моделі роботи сервера, що обслуговує користувачів на випадок конфлікту. Така модель дозволяє описати атакуючі дії та поведінку системи захисту. Проводиться формальна постановка задачі за наявності інтегральних обмежень на завдання користувачів. Знайдені умови за якими гра може бути закінчена за скінчений час.
format	Article
author	Ігнатенко, О.П.
author_facet	Ігнатенко, О.П.
author_sort	Ігнатенко, О.П.
title	Моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту
title_short	Моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту
title_full	Моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту
title_fullStr	Моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту
title_full_unstemmed	Моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту
title_sort	моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту
publisher	Інститут програмних систем НАН України
publishDate	2009
topic_facet	Прикладне програмне забезпечення
url	http://dspace.nbuv.gov.ua/handle/123456789/4599
citation_txt	Моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту. / O.П. Ігнатенко // Пробл. програмув. — 2009. — № 3. — С. 66-72. — Бібліогр.: 11 назв. — укр.
work_keys_str_mv	AT ígnatenkoop modelûvannâobslugovuvannâkoristuvačívumerežízodnimserveromzaumovkonflíktu
first_indexed	2025-07-02T07:47:55Z
last_indexed	2025-07-02T07:47:55Z
_version_	1836520545704738816
fulltext	Прикладне програмне забезпечення 66 УДК 004.7 О.П. Ігнатенко МОДЕЛЮВАННЯ ОБСЛУГОВУВАННЯ КОРИСТУВАЧІВ У МЕРЕЖІ З ОДНИМ СЕРВЕРОМ ЗА УМОВ КОНФЛІКТУ При моделюванні мереж нерідко виникає необхідність урахування наслідків дій, спрямованих на погі- ршення роботи системи. Ці дії можуть бути результатом атаки або нескоординованості дій користува- чів у самій системі. Одним з можливих підходів до аналізу такого роду ситуацій є потокові моделі (fluid models). У роботі розглядається узагальнення моделі роботи сервера, що обслуговує користувачів на випадок конфлікту. Така модель дозволяє описати атакуючі дії та поведінку системи захисту. Прово- диться формальна постановка задачі за наявності інтегральних обмежень на завдання користувачів. Знайдені умови за якими гра може бути закінчена за скінчений час. Вступ У даній роботі розглядаються мате- матичні моделі мереж, що функціонують в умовах конфлікту та невизначеності. Об- ласті застосування таких моделей охоп- люють найрізноманітніші галузі людської діяльності. Особливо важливими є інфор- маційні мережі. Навіть мережа, що моде- лює роботу невеликого провайдера Інтер- нет (Internet service provider) може бути надзвичайно складною. Проблеми керу- вання, що виникають у мережі Інтернет загалом спільні для всіх комунікаційних мереж. Це, зокрема, питання побудови стратегії маршрутизації пакетів з одного вузла до іншого через мережу, що склада- ється з буферів і ланок. Розглядаючи зада- чу створення стратегій керування інфор- маційними мережами важливо відзначити наступні її особливості: • окремі вузли не мають повної ін- формації щодо завантаженості буферів та ланок мережі. Всі рішення щодо маршру- тизації мають визначатися лише на основі доступної локальної інформації; • проектні рішення крім обмеження в інформованості мають також обмеження у протоколах функціонування мереж; • у недалекому майбутньому Інтер- нет буде передавати потоки аудіо та відео нарівні з звичайним трафіком даних, при цьому проблема розподілу ресурсів між різнорідними користувачами та забезпе- чення рівномірної роботи системи залиша- ється відкритою. Інтернет трафік представляє собою надзвичайно складний для аналізу об’єкт, який характеризується періодичністю та нестабільною динамікою. Його досліджен- ням присвячені чисельні роботи, напри- клад, [1, 2]. Часткова причина складності аналі- зу трафіка полягає у взаємодії великої кількості взаємопов’язаних комп’ютерів, керування яких визначається локальною інформованістю. Недостатність інформації про глобальні характеристики системи виливається у прийняття локально опти- мальних рішень. За певних умов такі рі- шення збігаються з оптимальними, але це трапляється досить рідко. З розвитком мереж з’являються додаткові можливості по інформуванню кожного вузла надійною інформацією про роботу системи за допо- могою спеціальних алгоритмів [1, 3]. Тому виникає необхідність у прове- денні досліджень і розробці алгоритмів маршрутизації, що суттєво використову- ють різноманітну інформацію про тополо- гію мережі та рівні завантаженості окре- мих ланок мережі. Ще одним важливим напрямком розвитку сучасних мереж є безпровідні мережі. На сьогодні вони тільки починають змінювати структуру і функціонування комунікаційних мереж, але необхідність їх подальшого розвитку не викликає сумніву. У безпровідних ме- режах схеми маршрутизації дуже схожі на ті, що використовуються у мережі Інтер- нет. Зокрема, в обох випадках ресурсами є живлення і пропускна здатність. Також спільними є наявність багатьох користува- чів і шляхів між користувачами та вузлами мережі. © О.П. Ігнатенко, 2009 ISSN 1727-4907. Проблеми програмування. 2009. № 3 Прикладне програмне забезпечення 67 Відмінність безпровідних мереж полягає у сильній мінливості структури в залежності від втрат пакетів та з’єднань. В результаті цього визначити максимальні можливі характеристики передачі пакетів надзвичайно складно, особливо в системах з багатьма користувачами. У комунікаційних мережах (на від- міну від виробничих мереж) існує сильна залежність між досягненням максималь- них частот потоків даних та схеми обробки пакетів – тобто протоколу. Високі значен- ня частот передачі як правило пов’язані з інтелектуальною обробкою інформації і вимагають створення специфічного про- грамного забезпечення. Іншою відмінністю є наявність по- милок, викликаних взаємним впливом багатьох користувачів. Такі помилки не є катастрофічними (як це може бути в сис- темах транспортування або виробництва) і можуть бути виправлені відповідним ко- дуванням протоколів. Керування комунікаційними мере- жами останні п'ятнадцять років було пред- метом жвавих досліджень, але все ще є досить молодою дисципліною. Кожен з її підрозділів прагне фокусуватися на пев- ному класі практичних задач. Наприклад, потокові рівноважні моделі використову- ються, в основному, для аналізу алгорит- мів маршрутизації. Дослідження лінійних програм зосереджені на стохастичних моделях і аналізу характеристик їх функ- ціонування та ін. Розгляд проблеми керування стоха- стичними моделями мереж на основі пото- кових моделей має певну історію [4]. Оп- тимізація потокових моделей пов’язана з книгою Андерсона і Неша [5], яка була присвячена нескінченно-вимірному ліній- ному програмуванню. У даній роботі продовжується роз- виток ідей, висловлених у [6 – 8] щодо застосування досягнень теорії конфліктних динамічних систем для моделювання ро- боти мережі. Такий підхід, який викорис- товуватиме потужний апарат для опису поведінки керованих систем за умов неви- значеності і конфлікту дозволить розроби- ти аналітичну модель поведінки системи, сконструювати стратегії керування та провести аналіз стійкості отриманого розв’язку. 1. Математичні моделі Мережа буде вважатися скінченним набором терміналів, кожний з яких має певну кількість буферів. Пакети, що очі- кують у такому буфері можуть представ- ляти собою пакети даних, обсяги енергії або людей, що очікують на обслуговуван- ня. Один або декілька серверів обслугову- ють пакети на даному терміналі, після чого пакет покидає мережу або іде на інший термінал. Пакети прибувають до буферів терміналу з джерел які також можна вва- жати частиною мережі в разі, якщо має місце зворотний зв'язок. В цьому разі джерела отримують оброблені пакети, що виходять з «робочої» частини мережі. У роботі [8] було розглянуто мо- дель окремого сервера з протидією. За основу було взято звичайну потокову модель, яку було узагальнено для враху- вання атакуючих дій. Нагадаємо основні моменти. Нехай динамічна система опису- ється лінійним диференціальним рівнян- ням: )()()()( )( ttCvtButAq dt tdq α+−+= , (1) де фазовий вектор nRtq +∈)( описує (як правило) час затримки різних ланок мере- жі, керування гравців – вимірні функції які приймають значення з компактних мно- жин U і V відповідно: mRUtu ⊂∈)( , lRVtv ⊂∈)( . Векторна функція nRR →⋅α :)( описує потік пакетів у момент часу t і вважається невідомою обом гравцям і обмеженою у часі величиною maxα . CBA ,, – дійсні матриці розмірністю nn × , mn × і ln × , відповідно. Умовою закінчення гри будемо вважати виконання рівності 0)( =tq . Гра відбувається наступним чи- ном: у кожний момент часу 0≥t гравці обирають свої керування )(tv і )(tu , при- чому перший гравець прагне збільшити черги в мережі, а другий якомога швидше звести їх до нуля. Прикладне програмне забезпечення 68 Якщо 0)( ≡α t , тоді рівняння пере- творюється на звичайний конфліктно- керовний процес [9] )()()( )( tCvtButAq dt tdq −+= . (2) Задачі конфлікту двох учасників за- початкували створення теорії диференціа- льних ігор. Дослідженню процесів типу (2) присвячені численні роботи починаючи з Р. Айзекса, Л.С. Понтрягіна та М.М. Кра- совського. В даній роботі буде використо- вуватися ідея першого прямого методу Л.С. Понтрягіна [10, 11], який був розроб- лений у 1965 р. Особливість цього методу полягає у тому, що він вимагає суттєвої переваги одного гравця над іншим та фак- тично зводить гру до задачі оптимального керування. У даній роботі розглядається моде- лювання обслуговування користувачів одним сервером. Опишемо загальну модель системи (рис. 1). Джерела (в загальному випадку їх може бути N) мають обробити на сервері певну кількість запитів. При цьому вони можуть впливати на порядок надсилання шляхом вибору функції )(tiα , Ni ,..,1= , яка описує частоту надсилання пакетів. Джерела )(1 tα )(2 tα )(1 tu )(2 tu )(1 tq Сервер Буфер + Рис. 1. Загальна модель системи Кожне джерело намагається мінімі- зувати час обробки своїх завдань на серве- рі. Після надсилання пакети потрапляють в буфер сервера, який описується чергою )(1 tq . У залежності від схеми обробки пакети можуть бути класифіковані за дже- релами або ні. В останньому разі вони розглядаються сервером як однакові. Величина буфера може бути обме- жена, в цьому випадку можливі перепов- нення і надсилання пакетів протягом пев- ного часу стає неможливе. Схема обробки пакетів )(tu має описувати роботу сервера та забезпечувати найбільш ефективне використання наяв- них ресурсів для виконання задач користу- вачів. Загальна задача полягає у знахо- дженні умов при яких роботу системи можна стабілізувати, конструюванні стра- тегії )(tu та аналізу роботи системи за умов конфлікту. Розглянемо модель системи у дифе- ренціальній формі: )()( 1 tutq N i i +α=∑ = & , (3) де +∈ Rtq )( 0 , µ≤)(tu і стратегія )(tu взагалі кажучи вимірна функція. Пакети від джерел N...1 надходять до загального буфера )(tq та виконуються на сервері з частотою )(tu . Доповнимо цю модель додатковими припущеннями: (i) частота надсилання пакетів може змінюватися з часом. Позначимо )(tα – частоту потоку пакетів у момент часу t ; (ii) буфер )(tq будемо вважати об- меженим, іншими словами max)(0 qtq ≤≤ ; (iii) можливості сервера обмежені величиною µ : µ≤)(tu . При цьому вважається, що система захисту в момент часу t володіє інформа- цією про всі )(tiα , Ni ,..,1= та про )(tq . Будемо розглядати наступні типи обмежень для функції )(tα . 1. Геометричні обмеження. Цей тип обмежень описує обмеженість каналу зв’язку джерела з сервером і описується наступним чином: max)(0 α≤α≤ t . 2. Інтегральні обмеження. Ці обме- ження відображають той факт, що кіль- кість пакетів, яка може бути надіслана протягом періоду роботи системи є обме- женою. Даний тип обмежень описується нерівністю: int 0 )( α≤α∫ ∞ t dtt . Прикладне програмне забезпечення 69 Задача полягає у знаходженні умов які б гарантували наведення вектора )(tq у точку )0,0( зі стану 0q при будь-яких протидіях суперника не пізніше ніж за час ∞<)( 0qT . Якщо 0)0(2 =q і 0)( ≡tv , 1=N max)( α≡α t , то система (3) зводиться до відомої задачі керування [4], яка має розв’язок при виконанні умови maxα>µ . Оптимальне (у сенсі задачі швидкодії) керування задається формулою )0),(()( 1 tutu = , де    = >µ = 0)(,0 0)(, )( 1 1 1 tq tq tu . Час вичерпання черги дорівнює max 1 )0( α−µ q . Твердження 1. Розглянемо динамі- чну систему: )()( 1 tutq N i i +α=∑ = & з обмеженнями 1) max)(0 ii t α≤α≤ , Ni ,..,1= . 2) int 0 )( it i dtt α≤α∫ ∞ , Ni ,..,1= . Якщо µ<α∑ = N i i 1 max , то для будь якого )( 0tq , та функцій )(⋅αi існує мінімальний момент часу +∞<T , такий, що 0)( =Tq . Якщо µ≥α∑ = N i i 1 max , то для початко- вих положень, що задовольняють наступ- ній нерівності:       α αµ+α−≤ ∑ = max int 1 int max0 max)( i i i N i iqtq , існує момент часу +∞<T , такий, що 0)( =Tq . Доведення. Якщо 0)( 0 =tq , то 0tT = . Нехай тепер 0)( 0 >tq . Розглянемо розв’язок рівняння (3): ∫∑∫ ττ+ττα+= = t t N i t t i dudtqtq 00 )()()()( 1 0 . (4) Для стратегії    = >µ− = 0)(,0 0)(, )( tq tq tu рівняння (4) приймає вигляд tdtqtq N i t t i µ−ττα+= ∑∫ =1 0 0 )()()( . Застосуємо обмеження 1, 2 та отри- маємо наступний результат:       α α>α α α≤α ≤ττα∫ ., ,, )( max int int max int max 0 i i i i i i t t i t tt d Введемо позначення max int i i iT α α= та i i TT maxmax = , i i TT minmin = . Нехай minTt ≤ , тоді tttqtq N i i µ−α+≤ ∑ =1 max 0)()( . Якщо µ<α∑ = N i i 1 max то 0)( =Tq для ∑ = α−µ ≤ N i i tq T 1 max 0)( . При цьому виконується max0)()( qtqtq ≤≤ . Якщо ],[ maxmin TTt ∈ , то ≤−++≤ ∑ ∑ tttqtq ii µαα intmax 0)()( ttq N i i µα −+≤ ∑ =1 int 0)( . Остання нерівність вірна і для maxTt > . Отже для minTt > виконується max)( qtq ≤ , в разі якщо: .max)( max int 1 int max0       +−≤ ∑ = i i i N i iqtq α αµα У результаті 0)( =Tq для µ α+ ≤ ∑ = N i itq T 1 int 0)( . Для великих значень int iα та µ<α∑ = N i i 1 max отримуємо результат близький до моделі одного сервера. Однак інтегральні обме- ження допускають можливість стабілізації Прикладне програмне забезпечення 70 системи і при µ≥α∑ = N i i 1 max . Виявляється, що в цьому випадку 0)( =Tq за час не біль- ший за µ α+∑ = N i itq 1 int 0)( . Доведення завершене. Для ілюстрації поведінки системи (3) при різних значеннях параметрів було використано середовище моделювання мереж OMNet++. Розроблено модель по- ведінки черги за наявністю інтегральних обмежень. Результати моделювання пока- зані на рис. 2. Рис. 2. Графік черги динамічної системи 2. Конфліктно-керована модель У даному розділі буде розглядатися розширення моделі (3) на конфліктний випадок. Розглянемо динамічну систему з початковою умовою ))(),(()( 21 tqtqtq = , яка описується системою лінійних диференці- альних рівнянь: )()()()( 12 1 1 tutqkttq N i i −⋅+α=∑ = & , )()()( 22 tutvtq −=& , 0≥t . (5) Фазовий стан системи (5) описується ве- ктором 2 21 ))(),(()( Rtqtqtq ∈= , де +∈ Rtq )(1 – довжина або час черги в буфе- рі в момент часу t . Буфер обмежений: max 11 )(0 qtq ≤≤ для всіх 0≥t . Параметр +∈ Rtq )(2 пов'язаний з нападником, який намагається погіршити роботу мережі (максимізувати )(1 tq інши- ми словами ) використовуючи керування )(tv , 0)( ≥tv , ν≤)(tv . Обираючи функцію )(tv в момент часу t нападник встановлює потужність атаки (частоту атакуючих пакетів ) )(2 tq , значення якої підкоряється нерівності: )(0 2 tq≤ для всіх 0≥t . Параметр )(2 tq впливає на чергу )(1 tq лінійно з коефіцієнтом 0≥k . Гра починається з початкової умови ))0(),0(()0( 21 qqq = . Інший гравець – захи- сник, розподіляє свої ресурси керування за двома напрямками )(1 tu – для обробки поточних запитів користувачів і пакетів атаки (будемо вважати що вони заванта- жують мережу однотипними пакетами) та )(2 tu – для виявлення і відсічення джерел атаки. На керування захисника наклада- ється природне обмеження 0)(1 ≥tu , 0)(2 ≥tu , µ≤+ )()( 21 tutu . При цьому вва- жається, що захисник у момент часу t володіє інформацією про )(tiα , )(tv і )(tq . Функції n i RR →⋅α :)( , які описують потік пакетів від джерел у момент часу t , вважаються додатними і обмеженими числами max iα відповідно. Крім цього зага- льна кількість пакетів обмежена: int 0 )( it i dtt α≤α∫ ∞ , Ni ,..,1= . Задача полягає у знаходженні умов які б гарантували наведення вектора )(tq в точку )0,0( зі стану 0q при будь-яких протидіях суперника не пізніше ніж за час ∞<)( 0qT . Схема роботи системи (5) показана на рис. 3. Покажемо, що ця модель може бути ста- білізована для v≥µ при умові, що почат- ковий вектор задовольняє нерівності       α αµ+α−≤ ∑ = max int 1 int max0 max)( i i i N i iqtq . Прикладне програмне забезпечення 71 Джерела )(1 tu )(1 tα )(2 tα )(1 tq Сервер Буфери + )(tv )(2 tq k )(2 tu Рис. 3. Система в умовах конфлікту Для розв’язання задачі слід зазна- чити допустиму стратегію ))(),(,( tvtqtu та момент часу T такі, що 0))(,( =tutq для всіх Tt ≥ . Цей результат має досягатись за всіх допустимих функцій )(tiα , Ni ,..,1= , та довільної функції )(tv . Запишемо систему рівнянь (5) у стандар- тній формі. Позначимо       = 00 0 k A , тоді       −         α+= ∑ = )( )( )( )( )()( 2 1 1 tu tu tv t tAqtq N i i& . (6) Множини керування мають вигляд }:{ 21 2 µ≤+∈= + uuRuU , },)(:{ 2 1 1 2 ν≤α=∈= ∑ = + vtvRvV N i i . Використаємо при конструюванні стратегії протидії ідею першого прямого методу Л.С. Понтрягіна [10, 11]. Теорема. Нехай для системи (6) ви- конуються умови 1) ν≥µ ; 2) max 1 1 int 2 2 1 ))0(( 2 )0( q qk q N i i ≤α+ ν−µ + ∑ = . Тоді існує стратегія )(tu , яка гаран- тує закінчення гри не пізніше моменту часу ))0((qT . Доведення. Без втрати загальності можемо вважати, що )0,0()0( ≠q . Введемо позначення для моментів часу: }0)(:0min{ 1* =>= tqtT ; }0)(:0min{ 2 * =≥= tqtT . Визначимо стратегію )(tu    ∈− ∈− = ],[)),(),(( ],0[),,0( )( * * * TTttvtv Tt tu µ µ (7) Покажемо, що стратегія )(tu , допу- стима. Дійсно, )(tu визначена для всіх 0≥t і на проміжку часу ],0[ 1T виконується µ=+ )()( 21 tutu . При цьому 0)(1 ≥tu , 0)(2 ≥tu для всіх 0≥t , оскільки викону- ється умова 1. Підставимо керування (7) в систему (6). Для ],0[ Tt ∈ )()()( 2 1 1 tqkttq N i i ⋅+α=∑ = & , µ−= )()(2 tvtq& . Для ],[ * TTt ∈ µ−α+= ∑ = N i i ttvtq 1 1 )()()(& , 0)(2 =tq& . Отже не пізніше за час ν−µ = )0(ˆ 2q T виконується 0)(2 =tq . Або, іншими слова- ми TT ˆ* ≤ . При цьому виконуються насту- пні співвідношення: =ττα+ττ+= ∫∑∫ = t N i i t ddkqqtq 0 10 211 )()()0()( +τµ−τ++= ∫ t dvktkqq 0 21 ))(()0()0( ∫∑ ττα+ = t N i i d 0 1 )( , ∑ = α+ν−µ−+≤ N i i t ktkqqtq 1 int 2 211 2 )()0()0()( , − − +≤ νµ 2 2 1 * 1 ))0(( )0()( q kqTq ∑ = +      − −− N i i q k 1 int 2 2 )0( 2 1 )( α νµ νµ , max 1 * 1 )( qTq ≤ . Прикладне програмне забезпечення 72 Остання нерівність випливає з умо- ви 2. В момент часу T відбувається пере- ключення керування. Оскільки 0)(2 =tq , Tt ≥ , то розглядаємо далі тільки )(1 tq +τµ−τα+τ−= ∫ t T dvTqtq * ))()(()()( * 11 ∫∑ ττα+ = t T N i i d * 1 )( , ∑ = α+−ν−µ−≤ N i iTtTqtq 1 int** 11 ))(()()( , ν−µ ν−µ+α+ ≤ ∑ = * 1 int* 1 )()( TTq t N i i . Таким чином, має місце наступна оцінка для T ≤+      ν−µ + ν−µ ≤ 2 21 * )0( 2 )0( T qkq T ∑ = α+      ν−µ + ν−µ + ν−µ ≤ N i i qkqq 1 int 2 221 )0( 2 )0()0( . Отже, не пізніше як у момент часу *T гру буде завершено при будь-яких діях суперника )(tv . Теорема доведена. Висновки У роботі досліджувалась модель сервера, що обслуговує користувачів без виділення окремих каналів зв’язку. За основу взято потокову модель, та узагаль- нено її для врахування конфлікту. Описана поведінки нападника і захисника у термі- нах диференціальної гри. Проведена фор- мальна постановка й аналіз отриманої гри. Знайдені умови на можливості гравців і початковий стан системи, при яких гра може бути закінчена за скінчений час. 1. Huitema C. Routing in the Internet. Prentice- Hall, Inc., Englewood Cliffs, NJ, 1999. 2. Willinger W., Paxson V. and other. Long- range dependence and data network traffic // Theory and applications of long-range dependence. – 2003. – N 4. – P. 373–407. 3. Floyd S., Jacobson V. Random early detection gateways for congestion avoidance. // IEEE/ACM Trans. Netw. – 1993. – N 1(4). – P. 397–413. 4. Meyn S. Control Techniques for Complex Networks. – Cambridge University Press, 2007. – 582 p. 5. Anderson E. J., Nash P. Linear program-ming in infinite-dimensional spaces. – Wiley- Interscience Series in Discrete Mathematics and Optimization. – 1987. – 472 p. 6. Андон П.І, Ігнатенко О.П. Протидія атакам на відмову в мережі Інтернет: концепція під- ходу // Проблеми програмування. – 2008. – № 2-3. – С. 564 – 574. 7. Андон П.І., Ігнатенко О.П. Атаки на від- мову в мережі Інтернет: опис проблеми та підходів щодо її вирішення. – Київ, 2008. – 50 с. – Препринт / НАН України. Ін-т програмних систем. 8. Ігнатенко О.П. Конфліктна задача взаємодії двох гравців у відкритому інформаційному середовищі // Проблеми програмування. – 2009. – № 1. – С. 56 – 65. 9. Чикрий А.А. Конфликтно управляемые процессы. – Киев: Наук. думка, 1992. – 384 с. 10. Никольский М.С. Первый прямой метод Л.С. Понтрягина в дифференциальных играх. – М.: Изд-во МГУ, 1984. – 65 с. 11. Понтрягин Л.С. Избранные научные труды. – М.: Наука, 1988. – 2. – 576 с. Отримано 04.06.2009 Про автора: Ігнатенко Олексій Петрович, кандидат фізико-математичних наук, старший науковий співробітник, докторант. Місце роботи автора: Інститут програмних систем НАН України, 03187, Київ – 187, Проспект Академіка Глушкова, 40. Тел.: 526 6025. e-mail: o.ignatenko@gmail.com

Моделювання обслуговування користувачів у мережі з одним сервером за умов конфлікту

Репозитарії

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