Програмно-апаратна організація GRID-систем на основі технології віртуальних мереж

Размещено на http://www.allbest.ru/

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

"КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ"

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

УДК 004.04 (043.3)

Автореферат

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

Програмно-апаратна організація GRID-систем на основі технології віртуальних мереж

Спеціальність 05.13.05 - Комп'ютерні системи та компоненти

Кулаков Олексій Юрійович

Київ - 2010

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

Робота виконана на кафедрі обчислювальної техніки Національного технічного університету України "Київський політехнічний інститут".

Науковий керівник: доктор технічних наук, професор Луцький Георгій Михайлович НТУУ "КПІ", завідувач кафедри обчислювальної техніки.

Офіційні опоненти: доктор технічних наук, професор Додонов Олександр Георгійович Інститут проблем реєстрації інформації НАН України, заступник директора з наукової роботи.

кандидат технічних наук, старший науковий співробітник Чемерис Олександр Анатолійович, Інститут проблем моделювання в енергетиці ім. Г. Є. Пухова НАН України, вчений секретар.

Захист дисертації відбудеться 22 листопада 2010 р. о 14:30 на засіданні спеціалізованої вченої ради Д 26.002.02 в НТУУ “КПІ” (м. Київ, пр. Перемоги, 37, корп. 18, ауд. 306).

Відгуки на автореферат у двох екземплярах, завірені печаткою установи, просимо надсилати на адресу: 03056, м Київ, пр. Перемоги, 37, вченому секретарю НТУУ "КПІ".

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

Автореферат розісланий 21 жовтня 2010 р.

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

спеціалізованої ради,

кандидат технічних наук, доцент М.М. Орлова

програмний grid сервер віртуальний

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

Суть наукової задачі, що вирішується у рамках дисертаційної роботи, полягає в розробці способу та засобів підвищення ефективності GRID-системи. Вирішення даної задачі базується на основі технології віртуальних приватних мереж (Virtual Private Network - VPN), за допомогою якої в рамках GRID-системи формується множина віртуальних приватних GRID-систем (Virtual Private GRID - VPG). Це дозволяє організувати процес динамічної реконфігурації GRID-системи, а також забезпечити ефективне управління GRID-системою на основі агентної технології.

Актуальність роботи. В Україні прийнята і виконується Державна цільова науково-технічна програма по розробці і впровадженню GRID-технологій в 2009-2013 роках (постанова Кабінету Міністрів України від 23 вересня 2009 р. № 1020). Розширення сфери використання GRID-систем пред'являє нові, більш високі вимоги до рівня сервісу, що надається користувачам GRID-систем. Це у свою чергу підвищує вимоги до ефективності функціонування GRID-систем, їх масштабованості, розподілу ресурсів і організації ефективного методу доступу до географічно розподілених ресурсів.

Питанням побудови GRID-систем, у тому числі підвищенню ефективності їх функціонування, присвячені роботи ряду зарубіжних вчених, в першу чергу Я.Фостера, К.Кессельмана, Ф.Бермана, Г.Фокса, а також роботи українських учених А.Е.Дорошенко, А.І.Петренко, А.Г.Загороднего, Г.М.Зиновьева та інших. В основному, ці роботи спрямовані на розробку інфраструктури GRID-системи, програмного забезпечення проміжного рівня, нових і вдосконаленню відомих методів планування задач в GRID-системах. При цьому більшість відомих методів планування не враховують динаміку змін обсягу ресурсів GRID-системи. У свою чергу, постійна зміна доступних ресурсів GRID-системи, а також її топології істотно впливає на якість планування завдань і ефективність функціонування всієї системи в цілому. У зв'язку з цим виникає необхідність у розробці та аналізі ефективних способів організації та функціонування GRID-систем.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася на кафедрі обчислювальної техніки Національного технічного університету України "Київський політехнічний інститут" у рамках науково-дослідних робіт:

1. № IT506-2007 "Створення національної GRID-інфраструктури для забезпечення наукових досліджень" (№ державної реєстрації 0107U007931), що проводилася у рамках державної цільової програми "Інформаційні та комунікаційні технології в освіті й науці на 2006-2010 роки" (Постанова КМ України №1153 від 7 грудня 2005 року).

2. № 2102-ф "Розробка засобів підвищення ефективності роботи гетерогенних кластерних систем на базі кластера НТУУ "КПІ" (№ державної реєстрації НДР 0108U000511).

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

Основні задачі дослідження у відповідності з поставленою метою полягають в наступному:

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

2. Аналіз впливу структурно-топологічних характеристик віртуальних приватних GRID-систем на обсяг службового трафіку, необхідного для організації та функціонування VPG.

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

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

5. Розробка способу організації розподіленої системи управління GRID-системою, що сприяє зменшенню обсягу службового трафіку в процесі функціонування GRID-системи.

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

Об'єкт дослідження. Об'єктом дослідження є процес функціонування GRID-систем.

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

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

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

Автором одержані наступні нові наукові результати:

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

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

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

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

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

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

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

Результати дисертаційної роботи використано при розробці структури та організації обчислювальних процесів в GRID-системі Інституту теоретичної фізики ім. М.М. Боголюбова НАН України.

Результати дисертаційної роботи використано в науково-дослідній роботі з інтеграції кластеру НТУУ «КПІ» в середовище GRID.

Теоретичні та практичні результати дисертаційної роботи використовуються фірмою Nokia Siemens Netwoks для підвищення продуктивності телекомунікаційних систем.

Результати дисертаційної роботи в галузи мережевих та GRID технологій використовуються в учбовому процесі НТУУ «КПІ» при викладанні дисципліни «Комп'ютерні мережі».

Особистий внесок здобувача. Усі результати, що складають основній зміст дисертаційної роботи, отримані автором самостійно. За результатами наукових досліджень опубліковано 3 самостійні статті [1-3]. У роботах, надрукованих у співавторстві, здобувачу належить: [4] - спосіб формування маршрутів у розподілених системах; [5] - спосіб формування структури розподіленої системи управління трафіком; [6] - спосіб формування віртуальних дерев VPN в GRID-системах; [7] - алгоритм планування завдань в DESKTOP GRID-системах; [8] - алгоритм формування структури GRID-системи; [9] - спосіб створення віртуальних GRID-систем для вирішення розподілених задач; [10] - спосіб організації розподіленої системи управління на основі агентної технології; [11] - алгоритм конструювання трафіку у розподілених системах; [12] - спосіб організації децентралізованої моделі управління даними в GRID-системах; [13] - алгоритм формування структури розподіленої системи управління трафіком в GRID-системах; [14] - аналіз ефективності функціонування розподілених систем; [15] - алгоритм планування завдань в мобільних GRID-системах.

Апробація результатів дисертації. Матеріали дисертації доповідались на: науково-практичній конференції "Комп'ютерні системи і мережеві технології" (Київ, 2007-2008 р.р.); VІІІ Міжнародній науково-технічній конференції "АВІА-2007" (Київ, 2007 р.); ІІІ Міжнародній науково-практичній конференції "Військова освіта та наука: сьогодення та майбутнє" (Київ, 2007 р.); Науково-практичній конференції молодих учених та аспірантів "Інтегровані інформаційні технології та системи" (Київ, 2007 р.); IX Міжнародній науково-практичній конференції "Сучасні інформаційні і електронні технології" (Одеса, 2008 р.); VIIІ Міжнародній науковій конференції молодих вчених, аспірантів та студентів "Політ-2008" (Київ, 2008 р.); 21st International CODATA Conference (Київ, 2008 р.); International Sentific Conference (Болгарія, Габрово, 2009 р.).

Публікації. Основні результати дисертаційної роботи опубліковані в 15 наукових роботах, серед яких 9 [1-9] наукових статей в журналах, затверджених ВАК, і 6 [10-15] публікацій в матеріалах конференцій.

Структура та обсяг дисертації. Дисертаційна робота складається із вступу, чотирьох глав, висновків, які включають основні результати роботи, списку використаних джерел з 128 найменувань, трьох актів впровадження, трьох додатків, 61 малюнка і 8 таблиць - всього на 164 сторінках машинописного тексту. Основний текст дисертації викладено на 130 сторінках.

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

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

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

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

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

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

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

На структурному рівні GRID-систему представлено у вигляді графа G(V, E, W), де V - множина вузлів GRID-системи, E - множина ребер графа G(V, E, W), відповідна каналам передачі даних, W={w_i,ji,j=1,2..n} - множина ваг ребер графа. Вага ребра є інтегральним показником, який характеризує основні параметри передачі інформації каналам. У випадку представлення GRID-системи у вигляді множини VPG граф G(V, E, W) розбивається на множину підграфів {G_i(V_i, E_i, W_i) | i=1,..,k}.

Формування структури GRID-системи і множини VPG, які входять до її складу, здійснюється з урахуванням відношення середнього значення інтенсивності інформаційного трафіку до середнього значення інтенсивності усього трафіку:

K_e = D_i/( D_i + S_oЧ F_r), (1)

де D_i - середнє значення інтенсивності інформаційного трафіку;

S_o - об'єм службового трафіку;

F_r - частота генерації службового трафіку.

При цьому для стійкої роботи GRID-систем повинна виконуватися умова 1/F_r > T₀, де T₀ - час оновлення службової інформації в VPG.

Об'єм службового трафіку в GRID-системі дорівнює:

де s_i - об'єм трафіку, що передається по одному каналу агентом VPG_i іншим агентам GRID-системи в процесі оновлення службової інформації;

s_j - об'єм трафіку, що передається вузлом v_j по одному каналу усередині VPG_i;

l_j - число каналів, по яких вузол v_j передає службову інформацію усередині VPG;

l_i - число каналів, по яких вузол v_i передає службову інформацію між VPG;

N_i - кількість вузлів в VPG_i;

N_g - кількість VPG в GRID-системі.

У загальному випадку S₀ залежить від протоколу обміну службовою інформацією, розміру і топології VPG. Зокрема, при використанні лавинного способу поширення службової інформації, число каналів, якими вузол v_j передає службову інформацію усередині VPG, дорівнює ступеню вузла.

Рис. 1. Залежність середньої кількості службових повідомлень від радіусу мережі і степені вузлів

На рис. 1 показано залежність середньої кількості службових повідомлень від радіусу мережі і степеня зв'язності вузлів. Така залежність характерна для протоколів обміну службової інформації усередині доменів, наприклад, протоколу RIP. Мінімальний степінь вузлів характерний для мінімального покриваючого дерева, у вигляді якого і запропоновано організувати структуру VPG.

У роботі показано, що обсяг службового трафіку в GRID-системі залежить від різниці радіусів VPG (рис. 2).

Рис. 2. Залежність кількості службових повідомлень від різниці радіусів VPG

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

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

, (3)

де - степінь зв'язності вершини ;

- відповідність k-го порядку мережевого оточення вершини ;

- зв'язок між суміжними вершинами і з максимальною степеню.

У роботі проведено аналіз залежності зміни розподілу мережевого оточення першого і другого порядків від змін топології VPG. В якості прикладу на рис. 3 приведено графіки зміни щільності мережевого оточення другого порядку для вершин v₂₃, v₂₅, v₃₀ і v₃₃ нерегулярного графа.

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

Вершини v₂₃, v₂₅, v₃₀ і v₃₃ мають однаковий степінь зв'язності, що дорівнює 7, проте, щільність мережевого оточення вершини v₃₀ більша. Як випливає з рис. 3, вершина v₃₀ більш стійка, розміщення агента управління в цій вершині забезпечує мінімальний потік службової інформації при зміні параметрів VPG.

За допомогою моделювання в середовищі OPNET проведено аналіз характеру зміни службового трафіку при різному виборі місця розташування агентів управляння VPG. На рис. 4. представлено результати моделювання завантаження усієї GRID-системи службовим трафіком при виборі агента управління на підставі значення щільності мережевого оточення (RIP_MyAgent), і на підставі степеня зв'язності вузлів (RIP_UsualAgent).

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

Рис. 4. Моделювання завантаження усієї GRID-системи службовим трафіком

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

Кожна вершина v_i характеризується відповідним степенем D_i, який визначається числом суміжних ребер вершини v_i, і поточним пріоритетом P_i, який відповідає пріоритету кореневої вершини піддерева ST_j (V_j, E_j, W_j), в яке входить вершина v_i. За кореневу вершину v⁰_m піддерева ST_m (V_m, E_m, W_m) приймаємо вершину v_k, що має найбільший степінь серед усіх вершин v_i піддерева ST_m (V_m, E_m, W_m), тобто: v⁰_j ={ v_k | D_k ? D_i v_i V_m}.

На початку формування остового дерева поточний пріоритет P_i кожної з вершин v_i V дорівнює степеню D_i. На першому кроці формування мінімального остового дерева за допомогою ребер e_i,j E вершина v_i з'єднується з суміжною вершиною v_j з максимальним степенем D_j (рис. 5). При цьому поточний пріоритет P_i вершини v_i буде дорівнювати степеню D_j вершини v_j. Таким чином, формується деяка множина піддерев {ST_m(V_m, E_m W_m)| m=1,2..l; l<n}. Пунктирними лініями позначено ребра початкового графа, а суцільними лініями - ребра сформованих піддерев.

На другому і наступних кроках формування покриваючого дерева аналогічним чином відбувається об'єднання між собою окремих піддерев з множини {ST_m(V_m,E_m,W_m)| m=1,2..l; l<n}. Кожен вузол асинхронно опитує своїх сусідів, які визначаються топологією мережі. Якщо виявляється, що вузли відносяться до різних дерев, ці дерева об'єднуються (рис. 6).

Рис. 5. Перший крок формування покриваючого дерева

Рис. 6. Результуюче покриваюче дерево

Рис. 7. Покриваюче дерево в результаті видалення ребра e_i,j

Зміна топології GRID-систем призводить до зміни степеню окремих вершин підграфа G_s(V_s, E_s, W_s), внаслідок чого формується нове покриваюче дерево. Як приклад на рис. 7 представлено покриваюче дерево при видаленні ребра e₄₇. З метою аналізу тимчасових характеристик запропонованого алгоритму і порівняння його з відомими алгоритмами було розглянуто слабозв'язані графи з різною кількістю вузлів, які найбільш характерні для структури середовища CFG.

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

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

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

У третьому розділі розглядаються питання формування динамічної структури GRID-системи, що складається з оптимальної кількості VPG [2, 3]. Агенти управління VPG певним чином об'єднуються в оверлейну віртуальну мережу (Overlay Virtual Network - OVN). Структура OVN представлена у вигляді G⁰={V⁰, E⁰, W⁰} початкового графа G={V, E, W} GRID-системы, де - множина вершин підграфа, в яких розташовані агенти управління VPG, E⁰ - множина віртуальних каналів OVN. На основі аналізу базових топологій оверлейних мереж, в якості топології OVN пропонується використовувати топологію К-мінімального остового дерева, яка забезпечує мінімальний службовий трафік між агентами управління VPG.

У дисертації запропоновано наступний спосіб формування структури GRID-системи:

1. Проводиться ініціалізація системи, в процесі якої визначаються всі доступні ресурси і канали передачі даних.

2. Визначається кількість N_G VPG, що входять до складу GRID-системи.

3. Визначається середнє число N_ср вершин підграфів G_i(V_i, E_i, W_i) G(V, E, W): N_ср = N/ N_G.

4. За допомогою алгоритму покриваючого дерева на графі G(V, E, W) формується множина {VPG_i i=1,..,N_G }. Формування VPG_i закінчується при N_m N_ср.

5. На підставі значення степеню вершин і щільності мережевого оточення визначається місце розташування агентів управління. Формується множина вершин графа OVN.

6. За допомогою модифікованого алгоритму Дейкстри формується множина L = {l_i,j |i,j=1,…,m} віртуальних каналів між усіма вершинами v_i V⁰. У результаті формується граф G¹= {V⁰, L, W⁰}.

7. На графі G¹= {V⁰, L, W⁰} за допомогою алгоритму формування мінімального покриваючого дерева формується структура OVN у вигляді мінімального покриваючого дерева G⁰= {V⁰, L⁰, W⁰}, де L⁰ - множина ребер мінімального покриваючого дерева.

В результаті формується структура GRID-системи, що складається з OVN і множини VPG. Наприклад, для графа (рис. 5) при N_G = 2 будуть сформовані наступні мінімальні покриваючі дерева (рис. 9). В даному випадку V⁰ ={v₄, v₁₂}, l_1,2 =(e_4,7; e_7,12).

Рис. 9. Мінімальні покриваючі дерева

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

У дисертаційній роботі реалізовано наступну процедуру реконфігурації VPG:

1. Якщо, переходимо на 9, інакше 3.

2. Пошук найближчого VPG.

3. Якщо вузол входить у VPG_i, то перехід на 4, інакше 6.

4. Реєстрація нового вузла в VPG.

5. Оновлення таблиць маршрутизації, перехід на 9.

6. Формування нового VPG.

7. Перерозподіл вузлів GRID-системи.

8. Процес реконфігурації завершено.

На рис. 10 представлено процедуру обміну службовою інформацією при включенні вузла v₅ в VPG_j, що здійснюється за допомогою пакетів HELLO. Пакет HELLO містить таблицю суміжних вузлів для вузла v₅. Отримавши пакет HELLO, кожний вузол v_i корегує свою таблицю суміжних вузлів і за допомогою пакетів RE-HELLO розсилає інформацію про зміни у своїй таблиці суміжних вузлів. Вузол v₅ підключається до найближчого вузла v_iVPG_j, і стає для ньогоо дочірнім.

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

Размещено на http://www.allbest.ru/

Рис. 10. Процедура обміну службової інформації при включенні вузла v₅ в VPG_j

У четвертому розділі представлено програмно-апаратні засоби і структуру VPG, які розроблено у рамках дисертаційної роботи. До складу VPG входить множина VPN і сервер управління GRID-системою (Virtual Dynamic Host Configuration - VDHC). Множина VPN складається з декількох хостів і Нome-хоста. До програмних засобів хостів відносяться агенти хостів, що здійснюють формування структури VPN і агент Нome-хоста, що відстежує топологію своєї VPN. VDHC сервер забезпечує функціонування VPG і здійснює розподіл завдань по VPN.

У дисертаційній роботі реалізовано наступну процедура формування структури VPG [4]:

1. Агенти хостів запускаються на усіх вузлах VPG.

2. Здійснюється обмін службовою інформацією між суміжними агентами хостів, при цьому створюються віртуальні двонаправлені з'єднання (TCP) між хостами.

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

4. Нome-хост відстежує топологію VPN, визначає маршрут до будь-якого вузла VPG.

5. Здійснюється обмін службовою інформацією між суміжними Нome-хостами. Створюються віртуальні канали між Нome-хостами.

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

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

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

1. Попередній досвід.

2. Обсяг і місця розташування вільних ресурсів.

3. Параметри каналів зв'язку між ресурсами.

Рис. 11. Структура планувальника задач VDHC сервера

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

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

Результати моделювання (рис. 12) підтверджують ефективність запропонованого алгоритму корекції бази знань планувальника. Як видно з рис. 12, спочатку (1 та 2 задачі) коефіцієнт навантаження центрального процесора близький до одиниці, це означає, що система перенавантажена, але вже, починаючи з третьої задачі, коефіцієнт навантаження центрального процесора не перевищує відмітки 0.9, що свідчить про ефективність запропонованого методу.

Рис. 12. Коефіцієнти використання ресурсів вузлів

Також у роботі запропоновано спосіб групового планування завдань в DESKTOP GRID-системах, що дозволяє збільшити продуктивність GRID-системи в середньому на 10-15%. Планувальник групує ресурси за загальними характеристиками, що дозволяє застосовувати різні механізми для планування в кожній VPG.

У дисертаційній роботі запропоновано спосіб організації GRID-систем на базі мереж MPLS. Взаємодія вузлів GRID-системи з мережею MPLS здійснюється за допомогою внутрішніх маршрутизаторів (Customer Edge - CE) GRID-системи. В якості CE розглядається вузол GRID-системи, підключений до найближчого граничного маршрутизатора (Provider Edge - РЕ) мережі MPLS. В даному випадку задача формування VPG зводиться до задачі побудови мінімального покриваючого дерева на графі G(V, E, W), вершини якого ототожнюються з вузлами GRID-системи, граничними і внутрішніми маршрутизаторами мережі MPLS.

ГОЛОВНІ ВИСНОВКИ І РЕЗУЛЬТАТИ РОБОТИ

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

Основні наукові і практичні результати роботи полягають в наступному:

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

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

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

4. Розроблено спосіб оптимального розбиття GRID-системи на віртуальні приватні GRID-системи, що сприяє підвищенню ефективності планування задач в GRID-системі.

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

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

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

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

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

СПИСОК ПУБЛІКАЦІЙ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

За темою дисертації опубліковано 15 робіт, серед яких 9 наукових статей у журналах, затверджених ВАК, і 6 публікації матеріалів конференцій. Основні результати відображені у наступних публікаціях:

1. Кулаков А. Ю. Способ повышения эффективности GRID-систем на базе виртуальных сетей VPN / А. Ю. Кулаков // Вісник Національного технічного університету України “КПІ”: “Інформатика, управління та обчислювальна техніка” : зб. наук. праць. - 2008. - № 47. - С. 280-286.

2. Кулаков А. Ю. Способ повышения эффективности GRID-систем на базе сетей MPLS / А. Ю. Кулаков // Вісник Національного технічного університету України “КПІ”: “Інформатика, управління та обчислювальна техніка”: зб. наук. праць. - 2008. - № 49. - С. 117-121.

3. Кулаков А. Ю. Способ формирования структуры распределенной системы управления трафиком в GRID-системах / А. Ю. Кулаков // Проблеми iнформатизацiї та управлiння: зб. наук. праць. - 2009. - № 1 (25). - С. 98-102.

4. Кулаков А. Ю. Конструирование трафика в распределенных системах / И. Н. Давиденко, А. Ю. Кулаков // Вісник Черкаського державного технологічного університету. - Спецвипуск. - 2007. - С. 31-33. - Дисертантом запропоновано спосіб формування маршрутів у розподілених системах.

5. Кулаков А. Ю. Способ повышения эффективности конструирования трафика в распределенных системах / И. Н. Давиденко, А. Ю. Кулаков, С. В. Маненюк // Вісник Військового інституту Київського національного університету ім. Тараса Шевченка: зб. наук. праць. - 2007. - № 9. - С. 53-56. - Дисертантом запропоновано спосіб формування структури розподіленої системи управління трафіком.

6. Кулаков А. Ю. Формирование виртуальных деревьев VPN в GRID-системах / Г. М. Луцкий, А. Ю. Кулаков // Проблеми iнформатизацiї та управлiння: зб. наук. праць. - 2008. - № 1 (23). - С. 94-98. - Дисертантом запропоновано спосіб формування віртуальних дерев VPN в GRID-системах.

7. Кулаков А. Ю. Способ планирования задач в DESKTOP GRID-системах / Ю. А. Кулаков, А. Ю. Кулаков, В. В. Желудков // Проблеми iнформатизацiї та управлiння: зб. наук. праць. - 2009. - № 3 (27). - С. 94-98. - Дисертантом запропоновано алгоритм планування завдань в DESKTOP GRID-системах.

8. Кулаков А. Ю. Способ формирования структуры виртуальной GRID-системы / А. Ю. Кулаков, И. А. Клименко // Вісник Національного технічного університету України “КПІ”: “Інформатика, управління та обчислювальна техніка”: зб. наук. праць. - 2009. - № 50. - С. 117-121. - Дисертантом запропоновано алгоритм формування структури GRID-системи.

9. Кулаков О. Ю. Динамічне створення віртуальних GRID-систем для вирішення розподілених задач на основі менеджера ресурсів / О. Ю. Кулаков, С. М. Бролінський, Ю. М. Ашаев // Вісник Національного технічного університету України “КПІ”: “Інформатика, управління та обчислювальна техніка”: зб. наук. праць. - 2009. - № 51. - С. 125-129. - Дисертантом запропоновано спосіб організації віртуальних GRID-систем для вирішення розподілених задач.

10. Кулаков А. Ю. Способ повышения эффективности конструирования трафика в распределенных системах / И. Н. Давиденко, А. Ю. Кулаков // Військова освіта та наука: сьогодення та майбутнє: ІІІ міжнар. наук.-практ. конф., 11-13 жовт. 2007 р.: тези допов. - К., 2007. - С. 44-47. - Дисертантом запропоновано спосіб організації розподіленої системи управління на основі агентної технології.

11. Кулаков А. Ю. Управление трафиком в распределенных системах на основе виртуальной сети интеллектуальных агентов / Г. М. Луцкий, А. Ю. Кулаков // Комп'ютерні системи і мережні технології: наук.-практ. конф., 20-22 бер. 2007 р.: тези допов. - К., 2007. - С. 67-68. - Дисертантом запропоновано алгоритм конструювання трафіку у розподілених системах.

12. Кулаков А. Ю. Способ организации децентрализованной модели управления данными в GRID-системах / А. Ю. Кулаков // Комп'ютерні системи і мережні технології: наук.-практ. конф., 21-23 вер. 2009 р.: тези допов. - К., 2009. - С. 74. - Дисертантом запропоновано спосіб організації децентралізованої моделі управління даними в GRID-системах.

13. Кулаков А. Ю. Способ формирования структуры распределенной системы управления трафиком в GRID-системах / Г. М. Луцкий, А. Ю. Кулаков // Интеллектуальный анализ информации : IX междунар. конф., 19-22 мая 2009 г.: сб. тр. - К., 2009. - С. 260-268. . - Дисертантом запропоновано алгоритм формування структури розподіленої системи управління трафіком в GRID-системах.

14. Kulakov A. Yu., The analysis of efficiency of remote data storage access protocols in distributed systems / Yu. A. Kulakov, O. I. Alenin, A. P. Rokovoy and A. Yu. Kulakov // 21st International CODATA Conference. - C. 122. - Дисертантом запропоновано аналіз ефективності функціонування розподілених систем.

15. Kulakov A. Task Planning in Mobile GRID / G. Lutsky, A. Kulakov // International Sentific Conference, 20 November 2009 : thesis. - Bulgaria, Gabrovo, 2009. - № 1. - Р. 438-440. - Дисертантом запропоновано алгоритм планування завдань в мобільних GRID-системах.

АНОТАЦІЯ

Кулаков О. Ю. Програмно-апаратна організація GRID-систем на основі технології віртуальних мереж. - Рукопис.

Дисертації на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - комп'ютерні системи та компоненти. Національний технічний університет України "Київський політехнічний інститут", м. Київ, 2010р.

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

Ключові слова: віртуальна GRID-система, мінімальне покриваюче дерево, агент управління, щільність мережевого оточення.

АННОТАЦИЯ

Кулаков А. Ю. Программно-аппаратная организация GRID-систем на основе технологии виртуальных сетей. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. Национальный технический университет Украины "Киевский политехнический институт", г. Киев, 2010 г.

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

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

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

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

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

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

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

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

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

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

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

Разработан способ группового планирования задач в DESKTOP GRID-системах, позволяющий увеличить производительность GRID-системы в среднем на 10-15%. Планировщик группирует ресурсы по общим характеристикам, это позволяет применять разные механизмы для планирования в каждой VPG.

В диссертационной работе предложен способ организация GRID-систем на базе сетей MPLS. Взаимодействие узлов GRID-системы с сетью MPLS осуществляется через граничные маршрутизаторы CE GRID-системы. В качестве CE рассматривается узел GRID-системы, подключенный к ближайшему граничному маршрутизатору РЕ сети MPLS. Предложен способ организация GRID-систем на базе сетей MPLS. В данном случае задача формирования VPG сводится к задаче построения минимального покрывающего дерева на графе G(V, E, W), вершины которого отождествляются с узлами GRID-системы, граничными и внутренними маршрутизаторами сети MPLS.

Ключевые слова: виртуальная GRID-система, минимальное покрывающее дерево, агент управления, плотность сетевого окружения.

ABSTRACT

Kulakov O.Y. The software-hardware organization of GRID-systems based on virtual networks technology. - Manuscript.

Dissertation for the scientific degree of Candidate of Technical Sciences on specialty 05.13.05 - computer systems and components. National Technical University of Ukraine “Kyiv Politechnic Institute”, Kyiv, 2010.

...