Fluid models of dynamic scheduling in computer networks

This paper deals with the general problem of network control under a situation of conflict – the denial of service attack. Work focused on the problem of dynamic scheduling in fluid models and relationship between stochastic and fluid models. There is proposed network control strategy under denial o...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2025
1. Verfasser:	Іgnatenko, O.P.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	PROBLEMS IN PROGRAMMING 2025
Schlagworte:	UDC 004.7
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/849
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming
Завантажити файл:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-849
record_format	ojs
resource_txt_mv	ppisoftskievua/7d/e216c3eaf52bc86af61db0fb3fd9467d.pdf
spelling	pp_isofts_kiev_ua-article-8492025-09-08T13:41:18Z Fluid models of dynamic scheduling in computer networks Потоковые модели динамического планирования в компьютерных сетях Потокові моделі динамічного планування черг в комп’ютерних мережах умов конфлікту Іgnatenko, O.P. UDC 004.7 УДК 004.7 УДК 004.7 This paper deals with the general problem of network control under a situation of conflict – the denial of service attack. Work focused on the problem of dynamic scheduling in fluid models and relationship between stochastic and fluid models. There is proposed network control strategy under denial of service attack. There is found the conditions under which the game can be finished.Problems in programming 2010; 1: 88-95 Рассматривается общая проблема управления сетями в условиях конфликта – атаки на отказ. Основное внимание сосредоточено на задачах динамического планирования в потоковой модели. Рассмотрены вопросы взаимосвязи между стохастической и потоковой моделями. Для задачи управления найдена стратегия работы сети в условиях атаки на отказ. Определены условия и функции управления, которые гарантируют работоспособность системы не ниже заданного уровня.Problems in programming 2010; 1: 88-95 Розглядається загальна проблема керування мережами за умов конфлікту – атаки на відмову. Основну увагу зосереджено на задачі динамічного планування у потоковій моделі. Розглянуті питання зв’язку між стохастичною і потоковою моделями. Розглядається задача пошуку стратегії роботи мережі в умовах атаки на відмову. Знайдено умови та функції керування, які гарантують працездатність системи не нижче заданого рівня.Problems in programming 2010; 1: 88-95 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-09-08 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/849 PROBLEMS IN PROGRAMMING; No 1 (2010); 88-95 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2010); 88-95 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2010); 88-95 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/849/900 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-09-08T13:41:18Z
collection	OJS
language	Ukrainian
topic	UDC 004.7
spellingShingle	UDC 004.7 Іgnatenko, O.P. Fluid models of dynamic scheduling in computer networks
topic_facet	UDC 004.7 УДК 004.7 УДК 004.7
format	Article
author	Іgnatenko, O.P.
author_facet	Іgnatenko, O.P.
author_sort	Іgnatenko, O.P.
title	Fluid models of dynamic scheduling in computer networks
title_short	Fluid models of dynamic scheduling in computer networks
title_full	Fluid models of dynamic scheduling in computer networks
title_fullStr	Fluid models of dynamic scheduling in computer networks
title_full_unstemmed	Fluid models of dynamic scheduling in computer networks
title_sort	fluid models of dynamic scheduling in computer networks
title_alt	Потоковые модели динамического планирования в компьютерных сетях Потокові моделі динамічного планування черг в комп’ютерних мережах умов конфлікту
description	This paper deals with the general problem of network control under a situation of conflict – the denial of service attack. Work focused on the problem of dynamic scheduling in fluid models and relationship between stochastic and fluid models. There is proposed network control strategy under denial of service attack. There is found the conditions under which the game can be finished.Problems in programming 2010; 1: 88-95
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/849
work_keys_str_mv	AT ígnatenkoop fluidmodelsofdynamicschedulingincomputernetworks AT ígnatenkoop potokovyemodelidinamičeskogoplanirovaniâvkompʹûternyhsetâh AT ígnatenkoop potokovímodelídinamíčnogoplanuvannâčergvkompûternihmerežahumovkonflíktu
first_indexed	2025-09-17T09:25:40Z
last_indexed	2025-09-17T09:25:40Z
_version_	1843502661917212672
fulltext	Прикладне програмне забезпечення 88 УДК 004.7 О.П. Ігнатенко ПОТОКОВІ МОДЕЛІ ДИНАМІЧНОГО ПЛАНУВАННЯ ЧЕРГ В КОМПЮ’ТЕРНИХ МЕРЕЖАХ ЗА УМОВ КОНФЛІКТУ Розглядається загальна проблема керування мережами за умов конфлікту – атаки на відмову. Основну увагу зосереджено на задачі динамічного планування у потоковій моделі. Розглянуті питання зв’язку між стохастичною і потоковою моделями. Розглядається задача пошуку стратегії роботи мережі в умо- вах атаки на відмову. Знайдено умови та функції керування, які гарантують працездатність системи не нижче заданого рівня. Вступ Системи керування комунікаційни- ми мережами охоплюють велику кількість різноманітних моделей. Спільним у цих моделей є наявність спеціальних об’єктів, які називаються «користувачі», «роботи» або «пакети», що накопичуються в чергах і потребують опрацювання. Після обробки в одній черзі ці пакети переходять в іншу чергу згідно з топологією мережі. Після закінчення всіх призначених робіт пакети залишають мережу. Також задане правило, згідно з яким нові пакети потрапляють на вхід системи. Основним питанням дослідження поведінки таких мереж є стійкість. За яких умов кількість робіт у чергах зменшується до нуля або принаймі не зростає з часом? При відповіді на це питання немож- ливо обійти стороною важливий аспект організації роботи мережі – яким чином задані правила вибору наступного пакета з черги для його обробки. Іншими словами, яким чином здійснюється маршрутизація і керування обробкою пакетів. Очевидно, що існує безліч можли- вих варіантів. Можливо, найбільш приро- днім є схема FIFO (first-in-first-out) за якої перший пакет, що надійшов на вузол ме- режі отримує пріоритет на обробку. Ще одним відомим правилом є PS (processor sharing), коли всі ресурси вузла діляться порівну між усіма наявними роботами (тобто сервер надає частки свого робочого часу всім за чергою). Правила FIFO та PS називають зрі- внюючими в тому розумінні, що пакети в різних чергах або буферах отримують рівні умови за обробкою на даному вузлі мережі. Принципово іншою є схема статич- ного пріоритету SBP (static buffer priority), при якій кожному буферу задається пріо- ритет і пакети з вищим пріоритет обслуго- вуються у першу чергу. У межах одного буфера пакети об- слуговуються в порядку прибуття. Схема називається випереджувальною, якщо прибуття роботи з вищим пріоритетом перериває обробку поточної роботи з нижчим пріоритетом. Після обробки пріо- ритетної роботи виконання перерваної поновлюється. Пошук керувань, які б оптимізували час затримки, витрати на обслуговування мережі та інші характеристики інтенсивно досліджувалось протягом останніх десяти- літь. Звичайним підходом до вирішення цих проблем є використання теорії мар- ковських процесів прийняття рішень, який полягає у мінімізації відповідного функці- онала. Однак, цей підхід дозволяє рішення у явному вигляді лише невеликої кількості задач. Існує, звичайно, можливість розв’язати відповідні рівняння чисельно, за допомогою ітерацій, але, як правило, ситуація суттєво ускладнена наявністю необмеженого простору станів. Така ситуація спричинила інтерес до дослідження спрощених, ідеалізованих задача керування мережами. Ідея полягає у розв’язанні спрощеної задачі та спробува- ти перенести отримане оптимальне керу- вання на вихідний випадок. © О.П. Ігнатенко, 2010 ISSN 1727-4907. Проблеми програмування. 2010. № 1 Прикладне програмне забезпечення 89 Одним з таких перспективних під- ходів до дослідження проблеми знахо- дження керування мережами є потокові моделі. Потокова модель є дуже простим детерміністичним наближенням стохасти- чної мережі. Дискретні пакети тут замінені на «потоки пакетів», що рухаються за мережею згідно з тими самими правилами маршрутизації. Такі моделі завжди використовува- лися для дослідження питань стійкості мережі. Однак, з'ясувалося, що оптимальне керування потокової моделі та стохастич- ної мережі надзвичайно схожі [1, 2]. Після виявлення цього факту дослідження були зосереджені на пошуку зв’язків між цими керуваннями. Це дуже важливе питання, тому що оптимальне керування потокової моделі знаходиться в явному вигляді від- носно легко [3]. Принаймні, існують ефек- тивні алгоритми вирішення цієї проблеми. На сьогодні в цій області отримано ряд важливих результатів щодо зв’язку потокових та стохастичних стратегій керу- вання. Зокрема, Мейном показано [4], що ітеративний процес пошуку правил пове- дінки процесу сходиться асимптотично до оптимального розв’язку потокової моделі за умови стійкості розв’язку. На жаль, пряме перенесення оптимального керуван- ня потокової моделі на стохастичний ви- падок у цілому не є асимптотично оптима- льним. Проте, як було показано [5, 6], аси- мптотично оптимальне керування завжди може бути побудовано. Конструкція, за- пропонована Магларасом полягає у тому, що при керуванні мережею в певні дискре- тні моменти часу відбувається переоцінка стану системи і розрахунок стратегії на наступний проміжок часу здійснюється на базі лінійної моделі. Інша ідея висловлена в [6] спирається на той факт, що оптима- льне керування потокової моделі є кусково постійною функцією. Певна модифікація потокового оптимального керування на проміжках часу з постійними значеннями, дає змогу побудувати асимптотично опти- мальне керування. 1. Керування стохастичними мережами Нехай стан мережі описується век- тором черг ))(),...,(()( 1 tQtQtQ n= , іншими словами поведінка системи визначається завантаженістю n буферів. Визначимо множину індексів },...,1{ nI = , тоді )(tQi – обсяг черги з пакетів у i -му буфері в мо- мент часу t . Буфери iQ , Ii ∈ об’єднані у мере- жу за допомогою вузлів. Кожен вузол може містити один або більше буферів та надає їм спільний ресурс для обробки пакетів. Позначимо },...,1{ mS = – множину індек- сів вузлів мережі. Функція відповідності Sis ∈)( визначає приналежність буфера i до вузла )(is . Матриця відповідності С (constitu- ency matrix) визначається за правилом:    ≠ = = sis sis csi )(0 )(1 , IiSs ∈∈ , . Після обробки пакет залишає вузол мережі і може або покинути мережу або потрапити на інший вузол. Маршрутизація пакетів (яка в рамках даної роботи є дете- рміністичною) задається матрицею марш- рутизації 0R (routing matrix):    ≠ = = ijr ijr rij )(0 )(1 , Iij ∈, , де Ijr ∈)( – функція, що задає буфер, в який переходять пакети, які залишають буфер j . Знаходження функції керування для такої мережі представляє, взагалі ка- жучи, непросту задачу. Основними особ- ливостями її є стохастичність і дискрет- ність. Загальна динаміка системи визнача- ється наступним рекурентним співвідно- шенням: )()()1()()1( tAtUtBtQtQ +++=+ , (1) де 0)0( QQ = . При цьому вважаються ви- конаними наступні припущення [4]. Прикладне програмне забезпечення 90 1. Будемо казати, що U адаптована до трійки ),,( BAQ , якщо )(tU може бути виражена як функція від випадкових змінних )}(),...,0(),()...,0(),(),...,0({ tBBtAAtQQ для кожного 0≥t . Також наявні геометри- чні обмеження: Ω∈)(tU , де { }1,0: ≤≥∈=Ω CuuRu i n , 1 – n -мір- ний вектор з одиниць, а нерівність викону- ється порядково. 2. Фазовий вектор процесу (1) та- кож геометрично обмежений nRXtQ ⊂∈)( . 3. nn nR ×= 00 , тобто в системі немає циклів і кожний пакет може бути обробле- ний не більш як n раз. 4. )(tB – послідовність незалежних і однаково розподілених матриць, )(tA – послідовність незалежних і однаково роз- поділених векторів. При цьому [ ] )()( tMRItB T−−= , де )(tM – послідовність незалежних і однаково розподілених діагональних матриць. Модель (1) представляє стохастичне дискретне рівняння, розв’язком якого є функція керування )(tU . Оскільки марш- рутизація вважається фіксованою, то зна- ходження )(tU рівнозначне розв’язанню задачі планування. Одне з фундаментальних питань, яке виникає при розв’язанні задачі (1) – за яких умов взагалі існує функція )(tU , яка б забезпечувала приведення )(tQ в нуль? Важливу роль у дослідженнях цього пи- тання відіграють потокові моделі. 2. Потокові моделі керування мережами Позначимо [ ])(tAE=α , [ ])(tMEM = , де [ ])(tMEM iiii = , тобто M – постійна діагональна матриця. Тоді потокова мо- дель описується простим диференціальним рівнянням: )(tBuq +α=& , (2) де [ ]MRIB T−−= . Будемо казати, що модель (2) може бути стабілізована, якщо для будь-якого )0(q та функції )(tα існує керування )(tu і час 0≥T , такі, що 0)()0( 0 =ττ+α+ ∫ T dBuTq . При цьому мінімальний ))0((qT називається часом вичерпання черги. По- шук мінімального часу для системи (2) – це задача оптимального керування, яка має розв’язок для фіксованих функції )(tα та початкового вектора )0(q якщо викону- ється включення BUTTq ⋅∈α−)0( . (3) Включення (3) дає можливість визначити момент часу ))0((qT . Однак структура потоків керування задачі (2) описується матрицями B і C , що навіть для простих мереж ускладнює знаходжен- ня функції керування )(tu . У фундаментальній роботі [4] опи- саний проблемно-орієнтований підхід, що дозволяє отримати керування для кожного вузла у явному вигляді. Опишемо головну ідею цього підходу, яка полягає у введенні поняття завантаженості вузлів мережі. 1. Визначимо матрицю заванта- женості за допомогою наступного рів- няння: 111 ][ −−− −=−=Ξ TRIMCB , де M – невироджена діагональна матриця, а ∑∑ = ∞ = − ==− n k k k kT RRRI 00 1][ . Позначимо sξ , Прикладне програмне забезпечення 91 Ss ∈ – вектори-рядки, що утворюють матрицю Ξ . 2. Вектором завантаження назве- мо вектор αΞ=ρ . Введемо позначення s Ss ρ=ρ ∈• max , тоді вузьким місцем назива- ються такі вектори: sρ , що •ρ=ρs . Твердження. ([4], ст. 112). Модель (2) може бути стабілізована тоді і тільки тоді, коли 1<ρ• . При цьому мінімальний час вичерпання черги дорівнює s s Ss q qT ρ− ξ= ∈ 1 ),( max)( . Одним з можливих керувань, що забезпечують стабілізацію системи є век- тор       +α−= − ))0(( )0(1* qT q Bu . Проілюструємо ці результати на модельних прикладах, відомих з теорії черг. 2.1. Модель окремого сервера. По- токову модель окремого сервера можна представити у вигляді диференціального рівняння α+µ−= )(tuq& . Рівняння має розв’язок при вико- нанні умови α>µ . Оптимальне (у сенсі задачі швидкодії) керування задається формулою    = > = 0)(,0 0)(,1 )( tq tq tu . Час вичерпання черги дорівнює α−µ = )0( ))0(( q qT . 2.2. Моделі Клімова. Узагальнен- ням моделі з одним сервером є ситуація, коли пакети відрізняються за пріоритетом або вимагають суттєво різного часу оброб- ки. В цьому випадку можна вважати, що в системі існують m ліній обробки (можли- во віртуальних) і всі пакети, що потрапля- ють в систему класифікуються на m типів, та опрацьовуються у відповідній лінії. Загальна задача полягає у знаходженні функції керування ))(),...,(()( 1 tututu m= , яка визначає які ресурси спрямувати у момент часу t на обробку пакетів i -ої лінії на основі інформації про поточне заванта- ження системи. Загальна кількість ресурсів обме- жена, тому для кожного ],0[ Tt ∈ викону- ється: 1)( 1 ≤∑ = m i i tu . Розглянемо модель системи у дифе- ренціальній формі: α+= )(tBuq& . Матриця B має діагональний ви- гляд: ),...,( 1 ndiagB µµ−= , ]1,..,1[=C , ( )nt αα=α ,..,)( 1 . Модель Клімова для чотирьох черг показана на рис. 1. Рис. 1. Модель Клімова для чотирьох черг Модель Клімова може бути стабілі- зована, якщо і тільки якщо 1 1 < µ α ∑ = n i i i . Прикладне програмне забезпечення 92 Мінімальний час вичерпання черги дорівнює ∑ ∑ = = • µ α− µ= ρ− ξ= n i i i n i i iq q qT 1 1 1 )0( 1 ))0(,( ))0(( . 2.3. Модель з повторною оброб- кою. Потокова модель з повторною оброб- кою (рис. 2) описується матрицею B на- ступного вигляду:           µµ µ−µ µ− =−−= 32 21 1 0 0 00 )( MRIB T , де ( )321 ,, µµµ= diagM . При цьому вектор α має вигляд          α =α 0 0 1 . Рис. 2. Модель з повторною обробкою Використовуючи властивості мат- риці маршрутизації можна отримати, що ][ 211 TT RRIMB ++−= −− . Матриця Ξ складається з двох векторів       µµ µµµ+µ =      ξ ξ −− −−−− 01 2 1 2 1 3 1 3 1 3 1 1 2 1 .             µ α µ α+ µ α =αΞ=      ρ ρ 2 1 3 1 1 1 2 1 . Модель може бути стабілізована тільки у тому разі якщо виконуються нерівності 1 3 1 1 1 < µ α+ µ α та 1 2 1 < µ α . 3. Конфліктне керування У даному розділі буде розглядатися розширення моделі (2) на конфліктний випадок. Попередні роботи [7 – 9] розгля- дали ситуації окремого сервера та моделей Клімова. В даній роботі розглядається задача динамічного планування для зага- льного класу систем. Нехай в системі присутній ще один гравець (рис. 3). Джерела )(1 tu )(1 tα )(2 tα )(tq Сервер Буфери + )(tv )(tp k )(2 tu Рис. 3. Система в умовах конфлікту Цей гравець намагається вплинути на роботу системи шляхом вибору функції )(tv . Введемо в систему додатковий вірту- альний буфер )(tp , який буде описувати потужність атаки. Атака відбувається наступним чином – нападник збільшує потужність зі швидкістю )(tv , система захисту може відсікати джерела атаки зі швидкістю )(2 tu , при цьому якщо джерело атаки діє, то воно завантажує загальну систему сфальшованими пакетами з кое- фіцієнтом k . Прикладне програмне забезпечення 93 Будемо вважати величину )(tp – одномірною, )(tq , ))(),...,(()( 1 ttt nαα=α – n -вимірними векторами. Розглянемо динамічну систему з початковою умовою ))0(),0(( pq , яка опи- сується системою лінійних диференціаль- них рівнянь: )()()()( 1 tButpkttq +β⋅⋅+α=& , )()()( 2 tutvtp µ−=& , 0≥t . (4) Вектор β має вигляд ( )0,...,1,..,0=β , тобто пакети атаки потрапляють на один з входів мережі. Фазовий стан системи (4) описується вектором ))(),(()( tptqtw = . Буфери вважаємо обмеженими: max)(0 ii qtq ≤≤ для всіх 0≥t , Ii ∈ . Параметр +∈ Rtp )( пов'язаний з на- падником, який намагається погіршити роботу мережі (максимізувати )(tq інши- ми словами ) використовуючи керування )(tv , 0)( ≥tv , ν≤)(tv . Обираючи функцію )(tv в момент часу t нападник встановлює потужність атаки (частоту атакуючих пакетів ) )(tp . Параметр )(tp впливає на вхідний буфер системи )(tq лінійно з коефіцієнтом 0≥k , вектор β задає буфер, на який потрапляють пакети. Гра починається з початкової умови )0(w . Інший гравець – захисник, розподі- ляє свої ресурси керування за двома на- прямками )(1 tu – для обробки поточних запитів користувачів і пакетів атаки (буде- мо вважати, що вони завантажують мере- жу однотипними пакетами) та )(2 tu – для виявлення і відсічення джерел атаки. На керування захисника наклада- ється природне обмеження 0)(1 ≥tu , 0)(2 ≥tu , 11 ≤Cu , та 12 1 1 ≤+∑ = uu n i i . При цьому вважається, що захисник у момент часу t володіє інформацією про )(tiα , )(tv і )(tw . Функції n i RR →⋅α :)( , які описують потік пакетів від джерел у момент часу t , вважаються додатними і обмеженими числами max iα відповідно. Крім цього зага- льна кількість пакетів обмежена: int 0 )( it i dtt α≤α∫ ∞ , Ni ,..,1= . Задача полягає у знаходженні умов які б гарантували наведення вектора )(tq в точку )0,0( зі стану 0q при будь-яких протидіях суперника не пізніше ніж за час ∞<)( 0qT . Покажемо, що ця модель може бути стабілізована для v>µ . Якщо додатково виконується умова, що початковий вектор задовольняє нерівності maxint 2 max ))0(( 2 )0( q pk q i ≤α+ ν−µ + , (5) то max)( qtq < для всіх 0≥t , тобто атака на відмову не досягла своєї мети. Співвідно- шення (4) встановлює зв'язок між обслуго- вуванням користувачів, наявними в систе- мі обмеженнями і ресурсами. Для розв’язання задачі слід зазна- чити допустиму стратегію ))(),(,( tvtqtu та момент часу T , такі, що 0))(,( =tutq для всіх Tt ≥ та max)( qtq < при 0≥t . Цей результат має досягатись за всіх допусти- мих функцій )(tiα , Ni ,..,1= , та довільної функції )(tv . Множини керування мають вигляд }1,1:{ 12 1 1 1 ≤≤+∈= ∑ = + + CuuuRuU n i in , }),(:{ 21 1 ν≤α=∈= + + vtvRvV n . Використаємо при конструюванні стратегії протидії ідею першого прямого методу Л.С. Понтрягіна [10 – 12]. Теорема. Нехай для системи (4) ви- конуються такі умови: ν>µ ; maxint 2 max ))0(( 2 )0( q pk q i ≤α+ ν−µ + . Тоді існує стратегія )(tu , яка гаран- тує закінчення гри не пізніше моменту часу ))0((qT та виконання нерівності max)( qtq < при 0≥t . Прикладне програмне забезпечення 94 Доведення. Без втрати загальності можемо вважати, що 0)0( ≠q . Введемо позначення для моментів часу: }0)(:0min{* =>= tqtT ; }0)(:0min{* =≥= tptT . Визначимо стратегію )(tu наступ- ним чином:    ∈ ∈µ− = ],,[)),(),(( ],,0[),,0( )( * ** * TTttvtu Tt tu (6) де       α+ α+−=∗ ))(( )( )( max* max* TqW Tq Btu , де ))(( tqW – час вичерпання черги з ну- льовим значенням )(tα причому ресурси тепер визначаються матрицею M)( ν−µ . Покажемо, що стратегія )(tu , допустима. Дійсно, )(tu визначена для всіх 0≥t і на проміжку часу ],0[ 1T виконується µ=+ )()( 21 tutu . При цьому 0)(1 ≥tu , 0)(2 ≥tu для всіх 0≥t , оскільки викону- ється умова 1. Підставимо керування (6) в систему (4). Для ],0[ Tt ∈ )()()( 2 tqkttq ⋅+α=& , µ−= )()( tvtp& . Для ],[ * TTt ∈ )())(()()( * tutvttq −µ−α=& , 0)( =tp& . Отже не пізніше за час ν−µ = )0(ˆ p T виконується 0)( =tp . Або, іншими слова- ми TT ˆ* ≤ . При цьому виконуються насту- пні співвідношення: =ττα+τβτ+= ∫∫ tt ddkpqtq 00 )()()0()( +τβµ−τ+β+= ∫ t dvktkpq 0 ))(()0()0( ∫ ττα+ t d 0 )( , int 2 max 2 )()0()0()( i t ktkpqtq α+ν−µ−+≤ , − ν−µ +≤ 2 * )0( )0()( p kqTq int 2 max )0( 2 1 )( i p k α+      ν−µ ν−µ− , max* )( qTq ≤ . Остання нерівність випливає з умо- ви (5). В момент часу T відбувається переключення керування. Оскільки 0)( =tp , Tt ≥ , то розглядаємо далі тільки )(tq [ ]( ) +τµ−τ+= ∫ t T duvBTqtq * ** ))(()()( ∫ ττα+ t T d * )( . Як випливає з твердження – існує такий час *T , що гру буде завершено при будь-яких діях суперника )(tv . Теорема доведена. Висновки У роботі досліджувалась загальна задача динамічного планування у мережах. За основу взято потокову модель, та уза- гальнено її для врахування конфлікту. Описана поведінки нападника і захисника у термінах диференціальної гри. Проведе- на формальна постановка й аналіз отрима- ної гри. Знайдені умови на можливості гравців і початковий стан системи, при яких гра може бути закінчена за скінчений час. 1. Bauerle N., Rieder U. Optimal control of single-server fluid networks // Queueing Systems. – 2000. – N 35. – P. 185 – 200. 2. Atkins D, Chen H. Performance evaluation of scheduling control of queueing networks: fluid model heuristics // Queueing Systems. – 1995. – N 21. – P. 391 – 413. 3. Avram F, Bertsimas D. and Ricard M. Fluid models of sequencing problems in open queueing networks: an optimal control approach // Stochastic Networks IMA Прикладне програмне забезпечення 95 Volumes in Mathematics and its Applications, Springer-Verlag, New York. – 1995. – P. 199–234. 4. Meyn S. Control Techniques for Complex Networks. – Cambridge University Press, 2007. – 582 p. 5. Maglaras C. Dynamic scheduling in multiclass queueing networks: stability under discrete-review policies // Queueing Systems. – 1999. – N 31. – P. 171 – 206. 6. Bauerle N. Asymptotic optimality of Tracking-policies in stochastic networks // Annals of Applied Probability. – 2000. – N 10. – P. 1065 – 1083. 7. Андон П.І., Ігнатенко О.П. Протидія атакам на відмову в мережі Інтернет: концепція під- ходу // Проблеми програмування. – 2008. – № 2-3. – С. 564 – 574. 8. Андон П.І., Ігнатенко О.П. Атаки на від- мову в мережі Інтернет: опис проблеми та підходів щодо її вирішення. – Київ, – (Препр./ Ін-т програмних систем НАН України, 2008 – 50 с.) 9. Ігнатенко О.П. Конфліктна задача взаємодії двох гравців у відкритому інформаційному середовищі // Проблеми програмування. – 2009. – № 1. – С. 56 – 65. 10. Чикрий А.А. Конфликтно управляемые процессы. – Киев: Наук. думка, 1992. – 384 с. 11. Никольский М.С. Первый прямой метод Л.С. Понтрягина в дифференциальных иг- рах. – М.: Изд-во МГУ, 1984. – 65 с. 12. Понтрягин Л.С. Избранные научные тру- ды. – М.: Наука, 1988. – 2. – 576 с. Отримано 17.12.2009 Про автора: Ігнатенко Олексій Петрович, кандидат фізико-математичних наук, старший науковий співробітник, докторант. Місце роботи автора: Інститут програмних систем НАН України, 03187, Київ – 187, Проспект Академіка Глушкова, 40. Тел.: 526 6025. e-mail: o.ignatenko@gmail.com

Fluid models of dynamic scheduling in computer networks

Institution

Ähnliche Einträge