Методи та засоби підвищення ефективності розподілених систем на основі багатоканальних зв'язків

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

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

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

(Республіка Польща)

УДК 004.04

Спеціальність 05.13.13 - Обчислювальні машини, системи та мережі

АВТОРЕФЕРАТ

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

Методи та засоби підвищення ефективності розподілених систем на основі багатоканальних зв'язків

Хайдер Мирослав Ричард

Київ - 2006 р.

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

Робота виконана в Національному технічному університеті України "Київський політехнічний інститут", на кафедрі обчислювальної техніки та в Жешувському політехнічному інституті (Республіка Польща) на кафедрі розподілених систем.

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

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

доктор технічних наук, професор Жуков Ігорь Анатолійович, Національний авіаційний університет Міністерства освіти і науки України, директор Інституту комп'ютерних технологій;

доктор технічних наук, професор Мельник Анатолій Олексійович, Національний університет "Львівська політехніка" Міністерства освіти і науки України, завідувач кафедри електронних обчислювальних машин.

Провідна установа Інститут кібернетики ім. В.М. Глушкова НАН України, відділ 205 "мікропроцесорної техніки".

Захист відбудеться " 26 " червня 2006 р. о 15:00 на засіданні спеціалізованої ради Д 26.002.02 у НТУУ "КПІ" (м. Київ, пр. Перемоги, 37, корп. 18, ауд. 306).

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

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

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

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

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

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

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

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

Ефективність використання комп'ютерних систем і мереж в значній мірі залежить від якості процесу проектування, функціональних можливостей складових елементів та експлуатаційних процедур, які передбачаються на етапі проектування і гарантують можливість діагностики та реконфігурації. За останні декілька років в розпорядженні проектувальників і адміністраторів комп'ютерних систем і мереж з'явився ряд нових можливостей, які дозволяють більш ефективно розв'язувати проблеми проектування і експлуатації. Ці можливості в основному пов'язуються з використанням дуалізму топологічних організацій, завдяки чому стало можливим співіснування цілого ряду незалежних топологій зв'язків. Іншими словами, якщо раніше зв'язки між вузлами базувалися на фізичних каналах, то в даний час вони базуються на логічних каналах. Технічні засоби побудови розподілених комп'ютерних систем на основі логічних каналів, які були представлені в роботах Фрімана, Хельда, Хальсала, на жаль, не забезпечувалися новими методами проектування та способами їх експлуатації. В зв'язку з цим виникали втрати якості проектування і ефективності експлуатації комп'ютерних систем і мереж, а це, в свою чергу, призводило до зниження рівня використання доступних ресурсів і якості обслуговування користувачів. Особливе значення з точки зору підвищення ефективності становить:

Розробка способів формального опису багатоканальних систем зв'язків та топологічної ієрархії;

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

Розробка методів проектування топології зв'язків різного рівня ієрархії;

Розробка і дослідження методів підвищення ефективності використання комунікаційних ресурсів комп'ютерних систем і мереж;

Розробка методів підвищення стійкості комп'ютерних систем і мереж до відмов;

Розробка методів, які враховують нечіткості при розв'язанні задач проектування.

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

Зв`язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась відповідно до планів науково-дослідних робіт, що проводились на кафедрі розподілених систем Жешувського політехнічного інституту, на замовлення Комітету з наукових досліджень Міністерства Народної Освіти Республіки Польща в рамках:

НДР U-3242/BW, "Моделювання характеристик напівпровідникових приладів з гранично малими розмірами";

НДР U-3695/DS, "Розробка програми для лабораторних експериментів та занять з мережевого обладнання і приготування конспектів та допоміжних матеріалів”;

НДР U-3590/DS, "Дослідження однорідних обчислювальних середовищ в суперкомп'ютерних мережах";

НДР U-3589/DS, "Дослідження явищ в транспортних носіях і деградації електричних параметрів в субмікронових напівпровідникових приладах";

НДР U-3991/BW, "Проектування і моделювання напівпровідникових мікросхем ЗВІС, що призначаються для роботи в однорідних обчислювальних середовищах";

НДР U-4744/DS, "Методи синтезу та аналізу високошвидкісних обчислювальних структур";

НДР U-5176/BW, "Аналіз і синтез складних асинхронних систем, що виготовляються на основі технологій ЗВІС";

НДР U-5657/DS, "Високошвидкісні обчислювальні системи, що реконфігуруються";

НДР U-6181/BW, "Методи та засоби покращення функціональних параметрів систем паралельної обробки".

Крім того, виконувались наукові дослідження на кафедрі обчислювальної техніки Національного технічного університету України “Київський політехнічний інститут” у відповідності з науково-дослідними програмами НТУУ “КПІ” НДР № 0100U000703 “Розробка теорії, методів і засобів побудови обчислювальних систем з масовим розпаралелюванням обчислювального процесу” та НДР № 0201U006269 “Побудова високопродуктивних паралельних обчислювальних систем з архітектурою на основі розподіленої загальної пам'яті”.

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

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

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

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

Визначення факторів, які суттєво впливають на ефективність функціонування комп'ютерних систем і мереж;

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

Розробка формальних методів оцінки параметрів багатоканальних комп'ютерних систем і мереж;

Розробка структурної організації комп'ютерних систем і мереж з багатоканальністю та топологічною ієрархією;

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

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

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

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

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

Методи досліджень. Методи досліджень можна поділити на:

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

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

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

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

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

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

Розроблено методику оцінки характеристик багатоканальних розподілених комп'ютерних систем з топологічною ієрархією, яка дозволяє визначати ефективність функціонування систем даного класу. Запропонована методика перевірена в процесі проектування реальної системи “Безпроводної міської комп'ютерної мережі” в місті Жешув.

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

Розроблено нову математичну модель вартості побудови системи, яка враховує реальні витрати, що являються результатом використання реальних пристроїв і середовищ передачі. Модель перевірена експериментально.

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

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

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

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

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

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

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

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

мінімізувати часові затримки в системі;

ефективно реконфігурувати систему зв'язків у випадку відмови її елементів або зміни вимог, що ставляться перед нею;

враховувати нечіткості в процесі проектування.

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

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

Результати, одержані в роботі, використовувались також

при проектуванні Жешувської міської комп'ютерної мережі;

при проектуванні і експлуатації Жешувської системи “Безпровідної міської комп'ютерної мережі”;

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

при побудові комп'ютерної мережі Центру передачі сучасних технологій виробництва;

при проектуванні інформаційної системи Авіаційної Долини (м. Жешув);

при проектуванні інформаційної інфраструктури Підкарпатського воєводства.

Дисертаційна робота була технічно підтримана фірмами Alcatel, NextiraOne, Sun, Cisco.

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

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

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

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

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

нова архітектура багатоканальних комп'ютерних систем з реконфігурацією та її модель;

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

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

Апробація результатів дисертації. Основні результати дисертаційної роботи неодноразово доповідались на наукових семінарах кафедри обчислювальної техніки факультету інформатики та обчислювальної техніки Національного технічного університету України “Київський політехнічний інститут”, Інституту кібернетики НАН України, кафедри розподілених систем Жешувського політехнічного інституту та Жешувської вищої школи інформатики і управління, а також на міжнародних конференціях:

Duїe systemy komputerowe i sieci (Boguchwaіa: 1991, 1993);

Miejskie Sieci Komputerowe w Nauce i Gospodarce (Poznaс: 1994, 1995, 1996, 1997 );

Current Research Information Systems in Europe (Milan: 1995);

Mixed Design of VLSI Circuits (Krakуw: 1995);

Sympozjum Telekomunikacji (Bydgoszcz: 1995, 1998);

2nd International Scientific Colloquium - CAE Techniques (Bielefeld: 1995);

Systemy komputerowe i sieci (Rzeszуw: 1996, 1997,1998,1999,2000);

Zastosowanie Komputerуw w Elektrotechnice (Kiekrz: 1996);

Sixth International Conference Soft Computing and distributed processing (Rzeszуw 2002);

International Conference Scaleable computing systems (Ustroс: 2002);

X i XII Konferencji Sieci i systemy informatyczne (Јуdџ: 2002, 2004);

Polski Internet Optyczny: technologie, usіugi i aplikacje (Poznaс: 2002);

Miкdzyuczelnianej Konferencji Metrologуw (Јуdџ: 2001);

UKRPROG-2004 (Київ: 2004).

SCALNET-05 (Кременчук: 2005);

Sieci komputerowe (Zakopane: 2004, 2005)

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

Структура і обсяг дисертації. Дисертаційна робота складається із вступу, шести розділів і додатків. Загальний обсяг роботи становить 375 сторінок друкованого тексту, 125 рисунків та 9 таблиць і списку використаної літератури з 197 найменувань.



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

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

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

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

РКС з багатоканальними віртуальними зв'язками може бути побудована на основі довільної моделі обчислень. Проведений аналіз показав, що особливо ефективним є використання для цієї мети архітектур типу MPP (Massively Parallel Processor) і COW (Cluster of Workstations). Високою ефективністю характеризуються також макроконвейерні та гридоподібні РКС.

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

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

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

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

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

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

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

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

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

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

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

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

Функція щільності дає можливість ввести похідне відношення від відношення еквівалентності :

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

Під типами елементів множини в роботі використовуються такі комунікаційні типи як: фізична топологія, логічна топологія, фізичний маршрут, логічний маршрут, фізичний канал, логічний канал, віртуальні канали типу Sonet/SDH, IP/LLC і інші. Запропонована модель не накладає обмежень на ієрархічні зв'язки логічних каналів. Отже, IP/LLC можна занурювати як в VP/VCI, так і в довільний інший рівень ієрархії, наприклад, в фізичний маршрут.

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

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

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

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

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

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

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

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

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

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

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

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

з якого визначаються ймовірності розриву, що нас цікавлять.

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

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

Визначення 4. Ребра і в графі називаються подібними, якщо мають місце рівності і, тобто ивається вершинно симетричним, якщо довільні дві його вершини подібні і реберно симетричним, якщо довільні два його ребра подібні. Граф називається симетричним, якщо він вершинно і реберно симетричний.

Доведено, що коли відображення взаємно однозначне, то граф симетричний.

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

Крім того, в даному розділі проаналізовано часові параметри РКС з багатоканальними віртуальними зв'язками.

Далі визначається поняття життєвого циклу РКС з багатоканальними віртуальними зв'язками, класифіковано необхідні витрати, які відповідають етапам цього життєвого циклу. Для Жешувскої міської комп'ютерної мережі визначені значення цих витрат за період 1993-2005. Запропоновано також сукупність математичних моделей повних втрат функціонування РКС з багатоканальними віртуальними зв'язками для різних архітектур зв'язку РКС. На відміну від відомих моделей, запропоновані моделі враховують реальні умови побудови РКС і можуть використовуватись при удосконаленні і модернізації існуючих РКС.

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

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

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

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

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

В кінці даного розділу описані моделі вартості побудови РКС з пасивними багатоканальними зв'язками і з перемиканнями логічних каналів. Адекватність запропонованих моделей знайшла своє підтвердження емпірично.

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

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

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

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

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

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

Другий метод призначається для синтезу симетричних і регулярних топологій і ґрунтується на застосуванні алгебри неорієнтованих зв'язних графів.

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

де: - відповідно мінімальна і максимальна затримки. Формулу можна представити у вигляді:

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

Використовуючи вираз , визначимо середню затримку передачі для системи з маршрутизацією. Значення можна записати, використовуючи формулу:

Якщо припустити, що. Тоді можна записати, що:

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

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

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

клієнт віддає перевагу деякому серверу;

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

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

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

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

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

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

Третій метод покращення характеристик РКС зв'язаний з ієрархічним підходом до об'єднання логічних каналів зв'язку. Тут виділяються групи логічних магістралей, які об'єднують різні кількості обчислювальних вузлів (клієнтів і серверів). Останній із методів об'єднання ґрунтується на застосуванні інтегрованих способів об'єднання логічних магістралей. В обох методах, завдяки широким можливостям об'єднання обчислювальних елементів, можна ефективно визначати навантаження логічних магістралей.

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

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

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

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

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

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

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

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



ВИСНОВКИ

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

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

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