НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

«ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ»

Ель Саєд Абделааль Ельсаєд Мохамед

|

УДК 681.324

Розробка інформаційних технологій управління

ресурсами комп’ютерних мереж

В УМОВАХ САМОПОДІБНОГО ВХІДНОГО ПОТОКУ

Спеціальність 05.13.06 – інформаційні технології

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Харків - 2008

Дисертацією є рукопис.

Робота виконана в Національному технічному університеті «Харківський політехнічний інститут» Міністерства освіти і науки України.

Науковий керівник – доктор технічних наук, професор

Раскін Лев Григорович, Національний технічний університет “Харківський політехнічний інститут”, професор кафедри економічної кібернетики та маркетингового менеджменту.

Офіційні опоненти: доктор технічних наук, професор

Шаронова Наталія Валеріївна, Національний технічний університет «Харківський політехнічний інститут», завідувач кафедри інтелектуальних комп’ютерних систем;

доктор технічних наук, професор

Нефьодов Леонід Іванович, Харківський національний автомобільно-дорожній університет, завідувач кафедри автоматизації та комп’ютерно- інтегрованих технологій.

країни, м. Київ.

Захист відбудеться «19» червня 2008 року о 14-30 годині на засіданні спеціалізованої вченої ради Д 64.050.07 у Національному технічному університеті «Харківський політехнічний інститут», за адресою: 61002, Харків, вул. Фрунзе, 21.

З дисертацією можна ознайомитись у бібліотеці Національного технічного університету «Харківський політехнічний інститут», 61002, Харків, вул. Фрунзе, 21.

Автореферат розісланий «15» травня 2008 р.

Вчений секретар

спеціалізованої вченої ради Гамаюн І.П.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Повсюдне використання інформаційних систем і технологій - невід'ємний та все важливіший атрибут сучасності. Ефективність інформаційних систем, у тому числі комп'ютерних мереж (КМ), істотно залежить від якості управління їхніми ресурсами. Для рішення задач управління ресурсами КМ традиційно застосовується математичний апарат, який заснований на теорії масового обслуговування, яка використовує, як правило, марківські моделі функціонування систем. Разом з тим аналіз реальних потоків сполучень, що надходять на входи вузлів КМ, показує, що вони не є марківськими. Ці потоки нестаціонарні, неординарні, неоднорідні й мають післядію. У зв'язку із цим і процеси обслуговування пакетів не є марківськими. Математичний апарат дослідження таких систем розвинений недостатньо. Найбільш сильні результати для систем з довільним розподілом тривалості обслуговування, але пуассоновським входом належать Поллачеку Ф. і Хинчину А. Я. У роботах Кендала Д., Такача Л. розглянута задача аналізу систем, на вхід яких надходить потік з довільним розподілом інтервалу між сполученнями, але експоненціальним обслуговуванням. Дослідження таких систем проводилося з використанням методу вкладених ланцюгів Маркова.

Принципове обмеження для можливостей використання всіх цих методів полягає в тому, що вони одержані для одноканальних систем. Радикальний напрямок рішення проблеми немарківських потоків для багатоканальных реальних систем складається в розробці технологій марківських їхніх апроксимацій. Відомі роботи в цій області, що виконані Ріорданом Дж., розглядають окремі випадки проблеми та до вичерпних результатів не привели. Додаткові труднощі при рішенні задачі аналізу та управління ресурсами в КМ виникають внаслідок їхньої високої розмірності. Найбільш важливі результати, що пов'язані з подоланням "прокляття розмірності", одержані Кемені Дж. і Турбіним А.Ф. На жаль, вони застосовні тільки в спеціальних окремих випадках. Розгляд задач управління ресурсами комп'ютерних мереж проводився в дуже багатьох роботах Столлінгса В., Таненбаума Е., Оліфер В.Г. і Оліфер Н.А. та ін. Однак, у цих роботах міститься тільки якісне обговорення виникаючих тут проблем. Вони не містять формальних постановок задач управління як задач оптимізації. Тому пропоновані в них рекомендації носять загальний характер.

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

Зв’язок роботи з науковими програмами, планами, темами. Дослідження, які були виконані в рамках дисертаційної роботи, тісно пов'язані з темами науково-дослідних робіт кафедри економічної кібернетики та маркетингового менеджменту НТУ «ХПІ»: «Розробка інформаційних моделей для реалізації процедур структурного синтезу в комп’ютерно-інтегрованих системах» (ДР № 0103U001543), «Розробка математичних моделей та методів розв’язання задач управління виробництвом у нечітких умовах» (ДР № 0106U005166). Здобувач брав особисту участь у виконанні зазначених робіт як виконавець.

Мета і задачі дослідження. Метою роботи є підвищення ефективності процесу управління ресурсами комп'ютерних мереж високої розмірності з немарківським самоподібним вхідним потоком. Для досягнення зазначеної мети в роботі вирішуються наступні основні задачі:

- розробка моделі немарківського потоку сполучень, що надходять на вхід вузла комп'ютерної мережі, яка враховує нестаціонарний, неординарний і самоподібний його характер, а також наявність післядії;

- розщеплення композиційного самоподібного неоднорідного вхідного потоку на складові;

- марківська апроксимація складових композиційного немарківського потоку з використанням розподілу Ерланга;

- декомпозиція марківського ланцюга високої розмірності на основі процедур групування станів;

- розробка методів управління обслуговуванням черг і раціонального розподілу ресурсів комп'ютерної мережі з обліком розходжень пріоритетів черг.

Об'єкт дослідження - процеси обробки сполучень у комп'ютерних мережах.

Предмет дослідження – інформаційна технологія управління процесом обробки сполучень у КМ із немарківським неоднорідним вхідним потоком.

Методи дослідження: Теорія випадкових процесів для розробки математичної моделі нестаціонарного, неординарного самоподібного випадкового процесу з післядією, що надходить на виходи вузлів КМ; методи математичної статистики для розробки методу розщеплення композиційного вхідного потоку на складові; теорія ймовірностей для розробки марківських апроксимацій немарківського вхідного потоку, а також для побудови декомпозиційної процедури групування станів марківського ланцюга; теорія оцінювання для дослідження адекватності розроблених моделей вхідного потоку; методи математичного програмування для рішення задач управління обслуговуванням черг і раціонального розподілу ресурсів комп'ютерної мережі.

Наукова новизна одержаних результатів. У ході рішення поставлених задач були одержані нові наукові результати.

уперше – розроблено метод побудови марківської моделі немарківської системи обслуговування, що дозволяє оцінити ефективність системи, на вхід якої надходить суперпозиція немарківських потоків сполучень різної довжини.

удосконалено – метод фазових укрупнень станів марківського ланцюга, що дозволяє на відміну від відомого, здійснити розрахунок розподілу ймовірностей станів ланцюга надвисокої розмірності.

одержали подальший розвиток – метод розщеплення неоднорідного потоку на складові, що дозволяє представити вхідний потік у вигляді суперпозиції потоків Ерланга; методи управління обслуговуванням черг, які на відміну від відомих, установлюють раціональний розподіл ресурсу системи обробки по сукупності критеріїв: середні довжини черг із урахуванням пріоритетів, середні тривалості очікування початку обслуговування, імовірність того, що довжина максимальної із черг не перевершить критичну.

Практичне значення одержаних результатів полягає в наступному: проведені дослідження й одержані наукові результати являються теоретичною основою для розробки простих і адекватних марківських моделей функціонування вузлів у КМ в умовах нестаціонарного, неординарного, неоднорідного, самоподібного вхідного потоку. Використання цих моделей дозволяє вирішувати задачі аналізу та оцінки ефективності реальних комп'ютерних мереж, а також задачі управлння обслуговуванням черг у таких мережах з метою підвищення їхньої ефективності.

Розроблені методи практично були використані: у Центрі нових інформаційних технологій при розв’язанні задач управління ресурсами корпоративної комп’ютерної мережі НТУ «ХПІ»; при оцінці відмовостійкості програмного забезпечення комп’ютерної мережі обласної студентської лікарні м. Харкова. Методи побудови адекватних марківських моделей немарківських систем, що надають теоретичну основу розв’язання задач, сформульованих у роботі, можуть бути ефективно використані при розв’язанні широкого класу інших задач управління складними системами.

Особистий внесок здобувача. Всі основні результати, які винесені на захист дисертаційної роботи, одержані здобувачем особисто. Серед них: метод побудови марківських моделей немарківських систем; метод розщеплення багатокомпонентного неоднорідного потоку на складові; метод управління дисципліною обслуговування черг в КМ.

Апробація результатів дисертації. Основні результати дослідження доповідалися на: XII–й і XIII–й Міжнародних науково-практичних конфе-ренціях «Інформаційні технології: наука, техніка, технологія, освіта, здоров’я» (м. Харків, 2004, 2005 рр.), I-й Міжнародній науково-технічній конференції «Гарантоздатні системи, сервіси та технології» (м. Полтава, 2006 р).

Публікації. За результатами наукових досліджень опубліковано 7 наукових праць, з них 6 статей – у фахових наукових виданнях ВАК України.

Структура та обсяг дисертації. Дисертація складається із вступу, 4-х розділів, висновків і додатків. Повний обсяг дисертації складає 198 сторінки. Робота містить 20 ілюстрацій по тексту; 1 таблиця по тексту; 12 ілюстрацій на 6 сторінках; 1 додаток на 1 сторінці; 73 найменування використаних джерел на 6 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність теми дисертації, сформульовано основну мету та задачі дослідження, охарактеризовано наукову новизну, наукове та практичне значення одержаних результатів, наведено інформацію про впровадження результатів роботи, їхню апробацію та публікації.

У першому розділі роботи проведено короткий аналіз відомих результатів по розробці моделей систем обробки в умовах немарківського вхідного потоку й немарківського обслуговування, а також сформульовані задачі дослідження.

Другий розділ присвячений аналізу мережного трафіка. Традиційні технології аналізу й оцінки ефективності функціонування комп'ютерних мереж засновані на використанні математичних моделей систем масового обслуговування (СМО). При цьому найбільш істотні результати цієї теорії пов'язані з використанням марківських моделей випадкового процесу, який описує вхідний потік, а також процеси обслуговування й очікування.

Однак дослідження останніх років показали, що реальний потік не є стаціонарним і, крім того, він має післядію. Ця принципова властивість потоку даних, що надходять на вхід комп'ютерної мережі, є наслідком специфічної якості потоку - самоподоби.

Властивість самоподоби проявляється в тім, що середнє поводження процесу на короткому проміжком часу не відрізняється від поводження на тривалому проміжку часу, тобто самоподібний процес інваріантний щодо змін масштабу.

Реальний трафік у локальній мережі НТУ "ХПІ", демонструє властивість самоподоби. На рис. 1 наведений розподіл довжини пакетів на вході мережі, які отримані за результатами обробки даних про трафік, накопичених за два місяці роботи мережі (з 11.09.2006 по 6.11.2006).

На рис. 2 наведено цей же розподіл, який отриманий за результатами обробки даних за один тиждень (з 11.09.2006 по 16.09.2006). На наступному рис. 3 відображений розподіл довжини пакетів, що відповідають трафіку протягом двох годин одного робочого дня (11.09. 2006). Близькість характеру цих розподілів не викликає сумнівів.

Далі в роботі запропонована процедура формування послідовності моментів надходження пакетів на вузол мережі. Довжини проміжків між сусідніми надходженнями в цій послідовності утворять сукупність корельованих випадкових величин з післядією, що відповідає самоподібному потоку з параметром самоподоби, рівним H.

При побудові імітаційної моделі використаний метод особливих станів.

Відповідно до логіки роботи імітаційної моделі її алгоритм складається із двох модулів: модуля, що реалізує дії, що ініціюються надходженням у систему чергової заявки, і модуля, що реалізує дії, які необхідно здійснити у зв'язку зі звільненням каналу. Черговість роботи модулів визначається координуючим елементом моделі, яким є календар подій.

Побудована імітаційна модель використовувалася для аналізу ефективності функціонування системи обробки даних залежно від характеру й параметрів вхідного потоку. Результати дослідження наведені на рис. 4 - 5.

Аналіз наведених на рис. 4-5 кривих переконливо демонструє негативний вплив явища самоподоби.

У роботі розглядається ще одна реальна ситуація, що приводить до появи потоків з "важким хвостом". У багатьох корпоративних комп'ютерних системах передача даних від периферійних вузлів до центрального організована шляхом послідовного встановлення сеансів зв'язку при їхньому почерговому опитуванні. При цьому кількість сполучень, накопичених для передачі в кожному інтелектуальному периферійному вузлі до моменту опитування, є випадковим. Відповідно до цього випадковими є тривалості сеансів, а також моменти надходження виникаючих "групових заявок" на центральний вузол. Якщо інтенсивності передачі даних від різних крайових вузлів приблизно однакові, то можна вважати, що потік групових заявок є пуассоновським з деякою інтенсивністю, що розраховується підсумовуванням інтенсивностей потоків, що утворять суперпозицію.

Далі в розділі проведено дослідження процесу функціонування системи обробки даних, на вхід якої надходить груповий потік. Для розрахунку розподілу ймовірностей станів системи отримана виробляюча функція.

Розкладання цієї функції в ряд Тейлора по ступенях дає шуканий набір ймовірностей.

У третьому розділі роботи розглянуті методи аналізу неоднорідних марківських потоків на вході вузлів комп'ютерних мереж. Спочатку вирішується задача розщеплення неоднорідного потоку на складові для випадку, коли цей потік складений із двох потоків з релєївським розподілом довжини пакетів, параметри яких різні. Заявки із цих потоків надходять на вхід з відповідними невідомими ймовірностями.

Невідомі параметри , , відшукуються методом найменших квадратів.

Задачі власне розщеплення суміші зведені до відшукання вирішального правила, що дозволяє віднести кожний конкретний пакет до одного з потоків, що становлять результуючий потік.

Знайдене граничне значення , при перевищенні якого пакет потрібно віднести до першого потоку:

Далі викладена методика рішення задачі розщеплення композиційного потоку даних, що надходять на вхід вузла КМ, на елементарні складові застосована для випадку, коли довжини пакетів складових сумарного потоку мають розподілу Ерланга порядку та відповідно.

Аналогічно вирішується задача розщеплення неоднорідного потоку, що є суперпозицією трьох потоків, один їх яких являє собою потік коротких сполучень. Для опису потоку коротких пакетів використано експоненціальний розподіл, а для потоків середньої й великої довжини - розподіли Ерланга другого порядку з відповідними інтенсивностями.

Далі в розділі розглянута задача марківської апроксимації немарківського неоднорідного вхідного потоку, що вирішується у два етапи. На першому етапі неоднорідний потік розщеплюється на ерлангівські складові, а на другому здійснюється власне апроксимація. При цьому для опису процесу функціонування системи з ерлангівським вхідним потоком будується еквівалентна марківська система з пуассоновським потоком на вході, у якій переходи здійснюються тільки під впливом "мічених" подій, що утворять вихідний ерлангівський потік. Граф станів і переходів такої системи з ерлангівським процесом другого порядку на вході наведений на рис. 6.

Для отриманого графа станів і переходів формується система лінійних алгебраїчних рівнянь щодо невідомих ймовірностей станів системи. При цьому фінальний розподіл ймовірностей станів має вигляд:

Аналогічно може бути проведений аналіз системи, на вхід якої надходить потік Ерланга -го порядку. У цьому випадку в графі станів і переходів перед кожним правдивим станом необхідно ввести буферний стан, що описує переходи системи під впливом заявок, що відсіюються, які не впливають на число зайнятих каналів системи.

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

При цьому для прискорення відомої процедури вона вдосконалена в двох напрямках.

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

Ця процедура дозволяє аналізувати системи із числом станів до 20 ,далі з ростом розмірності задачі її реалізація стає скрутною.

З метою подальшого істотного підвищення ефективності методик укрупнення станів у роботі запропонована багатоетапна ієрархічна процедура.

Нарешті, описана вище технологія фазового укрупнення станів узагальнена та використана для аналізу систем, поведінка яких описується напівмарківським процесом (НМП).

У четвертому розділі роботи розглянута задача управління ресурсами в комп'ютерних мережах.

Принциповою особливістю процесу функціонування сучасних комп'ютерних мереж є нестаціонарність трафіку. Інтенсивність вхідного потоку сполучень має явно виражені сезонні й, особливо, добові коливання. При цьому навантаження системи в пікових режимах може багаторазово перевищувати середню. Зрозуміло, що при виборі технічних характеристик мережі орієнтація на пікову інтенсивність вхідного потоку привела б до надмірно завищених вимог, задоволення яких привело б до низької економічності системи. З іншого боку, система, характеристики якої обрані в припущенні про середні навантаження, не буде задовольняти вимогам до інформаційної гарантобезпеки. Для відшукання компромісного рішення в роботі запропоновано використати "тимчасову надмірність", якою володіє комп'ютерна мережа. При виникненні підвищеного навантаження на вході вузла утвориться й починає рости черга сполучень, які очікують початок обслуговування. При досягненні довжиною цієї черги деякого критичного значення виникає втрата сполучень, які поступають. Тривалість тимчасового інтервалу від моменту початку впливу пікового навантаження до моменту досягнення довжиною черги критичного значення становить своєрідний часовий резерв. Якщо протягом цього інтервалу вплив пікового навантаження припиниться, то негативні післядії її появи ніяк себе не виявлять. У роботі сформульована й вирішена задача обґрунтування вимог до технічних характеристик вузла мережі, при виконанні яких імовірність втрати повідомлень в умовах пікових навантажень не буде перевищувати задану з урахуванням тимчасового резерву.

Шляхом обробки реальних статистичних даних про випадкову тривалість впливу пікових навантажень визначається щільність розподілу цієї випадкової величини. З іншого боку, технічні характеристики вузла мережі (число каналів обробки повідомлень - , інтенсивність обслуговування - , критична довжина черги - ) визначають закон розподілу тривалості функціонування системи до моменту, коли довжина черги в умовах пікового навантаження досягне критичного значення. Комплексування цих двох законів дозволило розрахувати ймовірність перевищення довжиною черги критичного значення. При цьому ймовірність того, що випадкова тривалість впливу пікового навантаження виявиться менше, ніж час досягнення довжиною черги критичного значення, дорівнює

.

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

Аналітичне вираження можна розглядати як рівняння щодо параметрів вузла, одержуване, якщо задати чисельно припустиме значення ймовірності .

Далі в розділі розглянута задача відшукання управління дисципліною обслуговування черг у комп'ютерних мережах, що забезпечує мінімізацію

максимальної довжини черги з урахуванням ваги відповідного потоку.

Нехай у вузол надходить різнотипних потоків з вагами відповідно , інтенсивністю й середньою інтенсивністю обслуговування . Уведемо вектор , компонента якого визначає частку часу від тривалості циклу обслуговування, виділюваного пакетам -го потоку,

У розділі показано, що мінімаксне управління розподілом ресурсу процесора, мінімізуючого в кожному циклі розподілу максимальну ймовірність того, що довжина черги буде не нижче критичної.

Чудова властивість одержаного управління полягає в тому, що вона не залежить від критичної довжини .

Близький результат виходить, якщо раціональний розподіл ресурсу шукати з використанням адитивного критерію - середнє число черг, довжина яких не нижче критичної.

Далі розглянута задача управління ресурсом, коли в якості критерію використовується середня довжина черги.

Потім у розділі одержано розподіл ресурсу процесора, оптимальний в значенні рівності середніх тривалостей очікування початку обслуговування.

Отримане досить громіздке вираження спрощується й легко трактується в окремому випадку, коли інтенсивності вхідних потоків пакетів, що утворять різні по довжині черги, рівні, тобто , .

З випливає, що справедлива частка ресурсу, виділюваного для обслуговування -ї черги, повинна бути пропорційна середньому часу обслуговування пакетів із цієї черги.

Далі в розділі розглянута задача управління обслуговуванням для випадку, коли вхідний потік вимог являє собою суперпозицію потоків з різними пріоритетами. При цьому -й потік має пріоритет перед -м потоком, якщо .

Для рішення задачі одержана система рівнянь щодо середніх тривалостей очікування початку обслуговування

Рішення цієї системи має вигляд .

З використанням імітаційної моделі оцінена ефективність раціонального розподілу ресурсу при обслуговуванні черг.

ВИСНОВКИ

У дисертаційній роботі розв’язано науково - прикладну задачу управління в комп'ютерних мережах високої розмірності з неоднорідним немарківським вхідним потоком. Основні результати роботи полягають у наступному.

1. Проведений аналіз реальних вхідних потоків сполучень у комп'ютерних мережах показав, що ці потоки мають специфічну властивість самоподоби, характерною рисою якої є довгострокова залежність процесу, спостережуваного на якому-небудь інтервалі, від значень цього процесу на попередніх інтервалах.

2. Побудовано імітаційну модель системи обробки даних із самоподібним вхідним потоком, яка дозволила знайти аналітичне співвідношення між визначальним параметром самоподібного потоку з післядією й параметрами розподілу Парето з "довгим хвостом", що забезпечує Парето-апроксимацію реального вхідного потоку.

3. З використанням побудованої імітаційної моделі проведено аналіз впливу параметра самоподоби вхідного потоку і його інтенсивності на основні характеристики системи обробки сполучень (довжина черги, час затримки, імовірність відмови). Показано, що ці характеристики в реальних ситуаціях за рахунок самоподоби погіршуються на порядок і більше.

4. Проведено оцінку ефективності функціонування КМ із груповим вхідним потоком. Отримано співвідношення для розрахунку розподілу ймовірностей станів системи для довільного розподілу числа сполучень у групі.

5. Розглянуто задачу аналізу неоднорідного потоку на вході вузла КМ. Показано, що цей потік може бути розщеплено на елементарні складові для випадку, коли в якості складових композиційного процесу вибрані розподілен-

ня Ерланга.

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

7. Одержали подальший розвиток методи аналізу марківського та напівмарківського ланцюгів високої розмірності з використанням фазового укрупнення станів.

8. Для багатоканальної системи з обмеженням по довжині черги й заданою інтенсивністю вхідного потоку отримано співвідношення для розрахунку щільності розподілу тривалості роботи системи до влучення в критичний стан. Це співвідношення разом із щільністю розподілу тривалості впливу пікового навантаження використано для визначення ймовірності того, що за час існування пікового навантаження довжина черги не досягне критичної.

9. Запропоновано метод розрахунку мінімаксного управління обслуговуванням черг, що встановлює розподіл ресурсу процесора, який мінімізує максимальну з ймовірностей того, що довжина відповідної черги перевищить критичну. Показано, що характер розподілу ресурсу не залежить від значення критичної довжини черги.

10. Запропоновано метод раціонального розподілу ресурсу процесора для випадку, коли має місце розходження в пріоритетах заявок у різних чергах. Розглянуто наступні постановки задачі: максимізація середньозваженого числа черг, довжина яких не перевищує критичну; мінімізація максимально зваженої довжини черги; мінімізація максимальної тривалості очікування початку обслуговування.

11. Результати робіт впровадженні у ЦНІТ НТУ «ХПІ» та в обласній студентській лікарні м. Харкова.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Раскин Л.Г., Пустовойтов П.Е., Са’ди Ахмад Абдельхамид Саед Ахмад,

Эль Саед Абделаал Эльсаед Мохамед. Оценка эффективности полумарковских компьютерных сетей высокой размерностиВісник Національного технічного університету “ХПІ”.- Харків: НТУ «ХПІ».-2005. - № 56. – С.17-21.

Здобувачу належить напівмарківська модель комп’ютерної мережі.

2. Пустовойтов П.Е., Са’ди Ахмад Абдельхамид Саед Ахмад, Эль Саед Абделаал Эльсаед Мохамед. Управляемая марковская цепь – модель корпоративной компьютерной сети // Вісник Національного технічного університету “ХПІ”.- Харків: НТУ «ХПІ».-2005. - № 55. – С.167-171.

Здобувачу належить побудова моделі корпоративної комп’ютерної мережі методами теорії масового обслуговування.

3. Раскин Л.Г., Пустовойтов П.Е., Эль Саед Абделаал Эльсаед Мохамед.

Оценка эффективности компьютерной сети с потоком групповых заявок и неограниченной очередью // Вісник Національного технічного університету «ХПІ».- Харків: НТУ «ХПІ».-2005. - № 59.– С.26-31.

Здобувачу належить метод розрахунку розподілення ймовірностей станів системи в умовах групових заявок.

4. Пустовойтов П.Е., Эль Саед Абделаал Эльсаед Мохамед. Методтка обоснования требований к техническим характеристикам узла компьютерной сети для обеспечения информационной гарантобезопасности // Открытые информационные и компьютерные интегрированные технологии. – Х.: НАКУ «ХАИ». – 2006. – № 31. – С. 129-132.

Здобувачу належить модель функціонування вузла комп’ютерної мережі.

5. Пустовойтов П.Е., Эль Саед Абделаал Эльсаед Мохамед. Минимаксное управление дисциплиной обслуживания в компьютерных сетях // Вісник Національного технічного університету «ХПІ».- Харків: НТУ «ХПІ».-2006. - № 23. – С. 178-182.

Здобувачу належить метод мінімізації максимальної довжини черги в комп’ютерних мережах.

6. Пустовойтов П.Е., Эль Саед Абделаал Эльсаед Мохамед. Методика анализа многокомпонентных входных потоков в компьютерных сетях // Вісник Національного технічного університету «ХПІ».- Харків: НТУ «ХПІ».-2006. - № 40. – С. 157-164.

Здобувачу належить методика розщеплення багатокомпонентного неоднорідного потоку даних на елементарні складові.

7. Пустовойтов П.Е., Эль Саед Абделаал Эльсаед Мохамед. Управление дисциплиной очередей в компьютерных сетях // Праці II Міжнародної науково-практичної конференції «Інтелектуальні системи прийняття рішень та інформаційні технології». – Чернівці, 2006.- С. 280-281.

Здобувачу належить метод визначення порядку обслуговування черг з урахуванням пріоритетів заявок.

АНОТАЦІЇ

Ель Саєд Абделааль Ельсаєд Мохамед. Розробка інформаційних технологій управління ресурсами комп’ютерних мереж в умовах самоподібного вхідного потоку. – Рукопис.

Дисертаційна робота на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 –інформаційні технології. – Національний технічний університет “Харківський політехнічний інститут”. Харків. – 2007.

Дисертаційна робота присвячена розв’язанню важливої наукової задачі управління в комп'ютерних мережах з урахуванням нестаціонарності, неординарності, неоднорідності та самоподоби вхідного потоку повідомлень.

У роботі проведений аналіз реальних вхідних потоків повідомлень у комп'ютерних мережах.

Побудовано імітаційну модель системи обробки даних із самоподібним вхідним потоком. З використанням побудованої імітаційної моделі проведено аналіз впливу параметра самоподоби вхідного потоку і його інтенсивності на основні характеристики системи обробки повідомлень (довжина черги, час затримки, імовірність відмови).

Розглянуто задачу аналізу неоднорідного потоку на вході вузла КМ. Показано, що цей потік може бути розщеплений на елементарні складові. Вирішено задачу оцінки параметрів складових для двох- і трикомпонентного потоку.

У роботі одержав подальший розвиток метод побудови марківської моделі неоднорідного немарківського потоку шляхом вкладення потоку Ерланга в пуассоновський потік.

Розглянуто задачу аналізу марківського ланцюга високої розмірності з використанням методу фазового укрупнення станів.

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

У роботі вирішено задачу раціонального розподілу ресурсу процесора для випадку, коли має місце розходження в пріоритетах заявок у різних чергах. Розглянуто наступні постановки задач: максимізацію середньозваженого числа черг, довжина яких не перевищує критичну; мінімізація максимальної зваженої довжини черги; мінімізація максимальної тривалості очікування початку обслуговування.

Розроблені математичні моделі й методи використаються при розв’язанні практичних задач управління ресурсами в комп'ютерній мережі НТУ "ХПІ", локальної комп'ютерної мережі Обласної студентської лікарні, а також у навчальному процесі кафедри економічної кібернетики і маркетингового менеджменту НТУ "ХПІ".

Ключові слова: трафік, самоподібний потік, груповий потік, марківська апроксимація немарківського потоку, фазове укрупнення станів марківського ланцюга, управління обслуговуванням черг.

Эль Саед Абделаал Эльсаед Мохамед. Разработка информационных технологий управления ресурсами компьютерных систем в условиях самоподобного входного потока. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 –информационные технологии. Национальный технический университет «Харьковский политехнический институт» Министерства образования и науки Украины, Харьков, 2007.

Диссертационная работа посвящена решению важной научной задачи управления в компьютерных сетях с учетом нестационарности, неординарности, неоднородности и самоподобия входящего потока сообщений.

В работе проведен анализ реальных входящих потоков сообщений в компьютерных сетях, который показал, что эти потоки обладают специфическим свойством самоподобия, характерной особенностью которого является долгосрочная зависимость процесса, наблюдаемого на каком-либо интервале, от значений этого процесса на предыдущих интервалах.

Построена имитационная модель системы обработки данных с самоподобным входящим потоком, которая позволила найти аналитическое соотношение между определяющим параметром самоподобного потока с последействием и параметрами распределения Парето с «длинным хвостом», обеспечивающего Парето-аппроксимацию реального входящего потока. С использованием построенной имитационной модели проведен анализ влияния параметра самоподобия входящего потока и его интенсивности на основные характеристики системы обработки сообщений (длина очереди, время задержки, вероятность отказа). Показано, что эти характеристики в реальных ситуациях за счет самоподобия ухудшаются на порядок и более.

Рассмотрена задача анализа неоднородного потока на входе узла КС. Показано, что этот поток может быть расщеплен на элементарные составляющие. Введено решающее правило, обеспечивающее расщепление потока. Предложенная процедура использована для случая, когда в качестве составляющих композиционного процесса выбраны распределения Эрланга. Решена задача оценки параметров составляющих для двух- и трехкомпонентного потока.

В работе получил дальнейшее развитие метод построения марковской модели неоднородного немарковского потока путем вложения потока Эрланга в пуассоновский поток. Показано, что для немарковской системы, на вход которой поступает суперпозиция потоков Эрланга, может быть построена эквивалентная марковская цепь с многомерным множеством состояний.

Рассмотрена задача анализа марковской цепи высокой размерности с использованием метода фазового укрупнения состояний. Известная технология усовершенствована за счет более обоснованного выбора начального распределения вероятностей состояний, а также использования более эффективной процедуры расчета промежуточных распределений вероятностей.

Для многоканальной системы с ограничением по длине очереди и заданной интенсивностью входящего потока получено соотношение для расчета плотности распределения продолжительности работы системы до попадания в критическое состояние. Это соотношение совместно с плотностью распределения продолжительности воздействия пиковой нагрузки использовано для определения вероятности того, что за время существования пиковой нагрузки длина очереди не достигнет критической.

Предложен метод расчета минимаксного управления обслуживанием очередей, устанавливающего распределение ресурса процессора, минимизирующего максимальную из вероятностей того, что длина соответствующей очереди превысит критическую. Показано, что характер распределения ресурса не зависит от значения критической длины очереди.

В работе решена задача рационального распределения ресурса процессора для случая, когда имеет место различие в приоритетах заявок в разных очередях. Рассмотрены следующие постановки задачи: максимизация средневзвешенного числа очередей, длина которых не превышает критическую; минимизация максимальной взвешенной длины очереди; минимизация максимальной продолжительности ожидания начала обслуживания.

Разработанные математические модели и методы используются при решении практических задач управления ресурсами в компьютерной сети НТУ «ХПИ», локальной компьютерной сети Областной студенческой больницы, а также в учебном процессе кафедры экономической кибернетики и маркетингового менеджмента НТУ «ХПИ».

Ключевые слова: трафик, самоподобный поток, групповой поток, марковская аппроксимация немарковского потока, фазовое укрупнение состояний марковской цепи, управление обслуживанием очередей.

El Sayed Abdelaal Elsayed Mohamed. Development of information technology of computer system resources management for self-similar input stream conditions. - Manuscript.

Thesis for a candidate’s degree by speciality 05.13.06 - information technologies. National Technical University «Kharkiv Politechnical Institute», Kharkiv. – 2008.

Thesis work is devoted to the decision of the important scientific problem of

management in computer networks with the account non-stability, eccentricity, heterogeneity and self-similarity of an incoming stream of messages.

In work the analysis of real incoming streams of messages in computer networks is done.

The problem of the analysis of a non-uniform stream on an input of КС unit is considered. It is shown, that this stream can be split on elementary components. The problem of an estimation of parameters of components for two and a three-componental stream is solved.

In work the method of construction of markovian models of non-uniform non-markovian stream by an investment of Erlang stream in Poisson stream was improved.

The problem of the analysis markovian circuits of high dimension with use of a method of phase integration of conditions is considered. The known technology is advanced for the account of more proved choice of initial distribution of probabilities of conditions, and also uses of more effective procedure of calculation of intermediate distributions of probabilities.

For multichannel system with restriction on length of turn and the set intensity of an entering stream the ratio for calculation of density of distribution of operation time of system before hit in a critical condition is received. This ratio together with density of distribution of duration of influence of peak loading is used for definition of probability of that during existence of peak loading the length of turn will not achieve a critical value.

The method of calculation of minimax management by service of the turns, a resource of the processor installing distribution, minimizing maximal of probabilities of is offered that the length of corresponding turn will exceed critical. It is shown, that character of distribution of a resource does not depend on value of critical length of turn.

In work the problem of rational distribution of a resource of the processor for a case when distinction in priorities of applications in different turns takes place is solved. The following statements of a problem are considered: maximization of the average number of turns, which length does not exceed critical; minimization of the maximal weighed length of turn; minimization of the maximal duration of expectation of the beginning of service.

The developed mathematical models and methods are used at the decision of practical problems of resource management in computer network of NTU "KhPI", a local computer network of Regional student's hospital, and also in educational process of faculty of economic cybernetics and marketing management NTU "KhPI".

Key words: the traffic, a self-similar stream, a group stream, markovian approximation non-markovian stream, phase integration of conditions markovian circuits, management of service of turns.