“Львівська політехніка”

На правах рукопису

УДК 519.68

ДЕМИДОВИЧ

Олександр Вікторович

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

Спеціальність 01.05.02 - Математичне моделювання

та обчислювальні методи

Автореферат

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

Львів-2001

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

Робота виконана в Львівському національному університеті імені Івана Франка

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

Цегелик Григорій Григорович,

Львівський національний університет імені Івана Франка,

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

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

Пасічник Володимир Володимирович,

Національний університет “Львівська політехніка”,

завідувач кафедри “Інформаційні системи та мережі”;

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

Саченко Анатолій Олексійович,

Тернопільська академія народного господарства,

директор Інституту комп’ютерних інформаційних технологій (м. Тернопіль),

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

Провідна установа: - Державний науково-дослідний інститут інформаційної інфраструктури Державного комітету зв’язку та інформатизації і НАН України.

Захист відбудеться “30” листопада 2001 р. о 15 год. на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” за адресою: 79013, м. Львів, вул. С. Бандери, 12.

З дисертацією можна ознайомитись у науково-технічній бібліотеці Національного університету “Львівська політехніка” (79013, м. Львів, вул. Професорська, 1)

Автореферат розіслано “30” жовтня 2001 р.

Вчений секретар спеціалізованої вченої ради,

кандидат технічних наук, доцент С.П. Ткаченко

Загальна характеристика роботи

Актуальність теми. Бурхливий розвиток технологій передачі, обробки та зберігання інформації зумовив значне збільшення числа комп’ютерів, об’єднаних в обчислювальні мережі. Відповідно до Концепції Національної програми інформатизації у державі створюється, розробляється або планується розробити декілька відомчих та міжвідомчих систем: Міністерства транспорту, Міністерства фінансів, Міністерства енергетики та деяких інших міністерств і відомств України. Більшість корпоративних автоматизованих систем відрізняються між собою з огляду як на апаратне, так і на програмне забезпечення. Тому забезпечення взаємного обміну між органами державної влади оперативною інформацією через її неструктурованість є досить складною проблемою. Основні сили повинні бути спрямовані насамперед на створення національної інформаційно-телекомунікаційної системи, розвиток системи національних інформаційних ресурсів. Першочергові пріоритети надаються передусім оптимізації діючої мережі магістралей передавання даних, будівництву нових сучасних каналів, включаючи волоконно-оптичні та супутникові системи зв'язку; формуванню комп'ютерної мережі освіти, науки та культури як частини загальносвітової мережі INTERNET. Отже, оптимізація обчислювальних мереж є актуальним об’єктом наукових досліджень на сучасному етапі.

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

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

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

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

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

Зв’язок з науковими програмами, планами, темами. За основними напрямами дослідження робота відповідає Концепції Національної програми інформатизації України, схваленої Законом України “Про Концепцію Національної програми інформатизації” від 4 лютого 1998 року №75/98-ВР. Частина робіт виконана в рамках держбюджетної теми Пв-667Б “Розробка математичного і програмного забезпечення системи автоматизованого проектування оптимального розподілу інформаційних ресурсів серед вузлів обчислювальних мереж”, номер державної реєстрації 0193V041612 на кафедрі обчислювальної математики Львівського національного університету імені Івана Франка.

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

-

-

-

-

-

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

Наукова новизна одержаних результатів:

-

-

-

-

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

Практичне значення одержаних результатів. Найсуттєвіші практичні результати дисертації такі:

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

Розроблено зручні для реалізації на ЕОМ алгоритми знаходження розв’язків задач математичного програмування до яких зводяться побудовані математичні моделі.

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

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

Впровадження результатів роботи. Результати дисертаційних досліджень впроваджені при оптимізації інформаційно-обчислювальних систем у Львівській дирекції Відкритого акціонерного товариства “Укртелеком” та Товариства з обмеженою відповідальністю “Інтернет-Україна”, що підтверджено відповідними актами. Основні результати використані при виконанні науково-дослідних робіт з теми Пв-667Б “Розробка математичного і програмного забезпечення системи автоматизованого проектування оптимального розподілу інформаційних ресурсів серед вузлів обчислювальних мереж”.

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

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

в [2] – спосіб зведення задачі оптимального розподілу програм і файлів до послідовного розв’язування двох задач: задачі оптимального розподілу програм і задачі оптимального розподілу файлів;

в [3] – формулювання і доведення теореми “Критерій для визначення максимального числа копій кожного файла в розподіленій базі даних з копіями;

в [4] – побудова математичних моделей, зведення їх до вигляду, зручного для реалізації та модифікація евристичного алгоритму для випадку фіксованого числа копій кожного файла;

в [5] – модифікація евристичного алгоритму;

в [6] – усі результати отримані здобувачем одноосібно;

в [7] – формулювання і доведення теореми “Необхідна й достатня умова розширення виду під час роботи генетичного алгоритму” та критерії зупинки алгоритму.

Апробація результатів дисертації. Основні положення і результати роботи доповідались і обговорювались на дев’яти наукових конференціях:

1.

2.

3.

4.

5.

6.

7.

8.

9.

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

Структура та обсяг роботи. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків, списку літератури та додатків. Робота містить 140 сторінок без додатків, 10 рисунків на 10 сторінках. У додатках наведено акти впровадження дисертаційних досліджень. Список літератури включає 114 назв.

Основний зміст дисертації

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

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

Для оптимізації продуктивності комп’ютерних мереж існує низка спеціалізованих систем імітаційного моделювання. Вони розроблені іноземними компаніями. Найдешевші, відповідно найпримітивніші з них коштують близько 1,5 тисячі доларів США, найдорожчі – близько 70 тисяч доларів. Основний математичний апарат, що використовується для імітаційного моделювання обчислювальних мереж у цих системах – теорія черг. Імітаційні моделі відображають процеси генерації повідомлень прикладними програмами, розбиття повідомлень на пакети чи кадри певних протоколів, затримки, пов’язані з обробкою повідомлень, пакетів і кадрів, процеси отримання доступу комп’ютерів до розділених мережних ресурсів тощо. Результатом роботи імітаційної моделі є зібрані під час проведення експерименту статистичні дані про найбільш важливі характеристики мережі: час реакції, коефіцієнт використання каналів і вузлів, ймовірність втрати пакетів тощо.

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

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

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

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

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

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

1.

2.

3.

4.

5.

6.

7.

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

за умов   

(i=1,2,...,m);  

j=1,2,...,n);

i=1,2,...,m; 1,2,...,n).

Розроблено алгоритми розв'язування узагальненої задачі про призначення: евристичний алгоритм та метод поліпшення допустимого розподілу.

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

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

за умов    (i=1,2,...,m);  

j=1,2,...,n);

i=1,2,...,m; 1,2,...,n),

де

– середній об'єм довідкового запиту до файла , що надходить на термінал вузла ;

– середній об'єм даних, що становлять відповідь на довідковий запит до файла , з термінала вузла ;

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

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

– інтенсивність довідкових запитів до файла , які надходять на термінал вузла ;

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

– число копій файла (1n); –

об'єм пам’яті вузла , необхідної для зберігання файла ; –

максимальний об'єм пам’яті, відведеної у вузлі для зберігання файлів.

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

Як приклад практичного застосування математичних моделей оптимального розподілу копій файлів серед вузлів обчислювальних мереж розглянуто задачу оптимального розподілу файлів у локальних обчислювальних мережах на базі протоколу Ethernet. Подано програмне забезпечення “Система підтримки прийняття рішень при оптимальному розподілі файлів серед вузлів обчислювальної мережі” розроблене у Львівській дирекції ВАТ “Укртелеком”. Розглянуто основні етапи процесу оптимізації мережі: збір статистичних даних про використання файлів, аналіз топології мережі, побудова математичної моделі, знаходження оптимального розв’язку математичної моделі. Зазначено, що в результаті проведення оптимізації розподілу файлів серед серверів локальної мережі Львівської дирекції ВАТ “Укртелеком” за допомогою системи підтримки прийняття рішень при оптимальному розподілі файлів серед вузлів обчислювальної мережі загальна завантаженість мережі зменшилась більше ніж удвічі, а середній, по мережі, час завантаження основних пакетів прикладних програм з файл-сервера в оперативну пам’ять ПК знизився на 30 відсотків, про що свідчить акт про впровадження (див. додатки).

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

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

за умов

( i=1,2,...,N) – обмеження на число маршрутів до кожного вузла мережі;

(j=1,2,...,M) - обмеження на пропускну здатність каналів зв’язку;

де

N - число вузлів у мережі;

M - число вихідних каналів зв’язку вузла;

- середній час доставки повідомлення до і-го вузла j-м каналом;

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

- середня довжина повідомлень до і-го вузла;

- пропускна здатність j-го каналу зв’язку.

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

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

Основні результати роботи та висновки

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

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

2. Розроблено програмну систему підтримки прийняття рішень при оптимальному розподілі файлів серед вузлів локальних обчислювальних мереж, що дозволило на практиці переконатися в ефективності застосування запропонованого підходу для оптимізації обчислювальних мереж. Так, в результаті оптимізації розподілу файлів в локальних обчислювальних мережах, загальна завантаженість мережі зменшувалась більш ніж удвічі, а середній по мережі час завантаження основних пакетів прикладних програм з файл-серверів в оперативну пам’ять ПК знижувався на 30-35 відсотків.

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

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

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

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

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

Список опублікованих автором праць за темою дисертації

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

Анотація

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - Математичне моделювання та обчислювальні методи. – Національний університет “Львівська політехніка”, - Львів, 2001.

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

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

Abstract

Demydovych O.V. The mathematical models of optimal information resources allocation amongst nodes of computing networks and methods of their realization.

The thesis submitted for the degree of Candidate of engineering sciences, speciality 01.05.02 - mathematical modeling and computational methods. - National University “Lvivska Polytechnica”. - Lviv, 2001.

This thesis consist of mathematical modeling for optimal location of information resources amongst the nodes of computing networks and their respected algorithmic .

At presented dissertation there was resolved the problem of building mathematical models of optimal information resources allocation amongst nodes of computing networks. These models are applicable in most cases of distributed computer systems. The methods for realization of the received mathematical models are designed. There were obtained the new results that extend the theoretical base of using the genetic algorithms to tasks of mathematical programming. Also there was created The Computer Aid System for allocation of files on servers of local area computer network.

Keywords: computer networks, optimization, distributed database, optimal allocation, algorithm of routing, mathematical programming, genetic algorithm, convergence, Computer Aid System.

Аннотация

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

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 – Математическое моделирование и вычислительные методы. – Национальный университет “Львовская политехника”. – Львов, 2001.

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

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

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

В третьей части исследованы вопросы математического моделирования принятия оптимальных решений о маршрутизации в сетях передачи данных. Проанализированы различные виды сетей относительно протоколов сетевого уровня. Построены математические модели для принятия оптимальных решений о маршрутизации пакетов по каналам связи для сетей без установления соединений (на примере сетей DNA) и с установлением виртуальных соединений. Использование таких моделей в алгоритмах маршрутизации позволяет избегать перегрузок каналов связи в сети. Определен класс задач математического программирования, к которым сводятся построенные математические модели.

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

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