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

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

Печурін Сергій Миколайович

УДК 004.724.4

МЕТОДИ І ЗАСОБИ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ТРАНСПОРТНОЇ СЛУЖБИ ЛОКАЛЬНИХ КОМП’ЮТЕРНИХ МЕРЕЖ

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

Автореферат

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

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

Київ – 2007

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

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

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

Луцький Георгій Михайлович,

Національний технічний університет України

“Київський політехнічний інститут”,

завідувач кафедри обчислювальної техніки.

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

Додонов Олександр Георгієвич,

Інститут проблем реєстрації інформації НАН

України, заступник директора

з наукової роботи,

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

Баранов Володимир Леонідович,

Інститут проблем моделювання в енергетиці

ім. Г. Є. Пухова НАН України, провідний

науковий співробітник відділення гібридних

моделюючих та керуючих систем в енергетиці.

Захист відбудеться “ 29 ” жовтня 2007р. о 1430 годині на засіданні спеціалізованої вченої ради Д 26.002.02 у Національному технічному університеті України “Київський політехнічний інститут”, м. Київ, проспект Перемоги, 37, корп. 18, ауд. 306.

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

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

Автореферат розісланий “ 28 ” вересня 2007 р.

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

спеціалізованої вченої ради Орлова М.М.

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

Актуальність теми. Одним із напрямів вдосконалення обчислювальної техніки, що дозволяє підвищити ефективність комп’ютерних систем і мереж, є створення теоретичної бази проектування та експлуатації найбільш поширених їх складових. Сьогодні інтеграція комп’ютерних систем досягла такого рівня, що грань між їхніми складовими (скажімо, LAN-MAN-WAN) стає все більш умовною. Тим не менш, з огляду на бажання дослідника отримати науковий результат, маючий практичну цінність, слід для аналізу вибрати конкретну складову, яка піддається дослідженню в розумні терміни. В даній роботі розглядається найбільш поширена складова комп’ютерних мереж, – локальна комп’ютерна мережа. Під локальною комп’ютерною мережею (далі – LAN) розуміємо комп’ютерну систему, яка має обмежений географічний розмір і об’єднує множину окремих комп’ютерних чи іншого типу пристроїв обробки даних, що звичайно знаходяться в деякому операційному вузлі. В свою чергу, аналізу піддано складову LAN, що її в даній роботі названо транспортною службою (далі – ТС LAN), і під якою розуміємо службу, яка виконує функції транспортування даних, а також пов’язані з транспортуванням даних: початкове встановлення каналу зв’язку; передача даних; кінцеве вивільнення каналу зв’язку; об’єднання ланок даних в єдину мережу (маршрутизація); встановлення з’єднання на рівні ланки даних. Таке розширення традиційного набору функцій, що їх звичайно не покладають на LAN, з однієї сторони обумовлено зростанням потужності обчислювальної техніки і її подальшою мініатюризацією. А з іншого боку, практика впровадження дуже комфортного для користувача, але в такій же мірі обмеженого з точки зору пропускної здатності, середовища передачі даних, - радіоефіру, показує, що ресурси підвищення ефективності на рівні ланки даних вже вичерпано. Таким чином, розширення функцій, що вони покладаються на LAN і її служби, можуть створити резерви підвищення ефективності мережі в цілому. В свою чергу, резерв підвищення ефективності самої транспортної служби локальних комп’ютерних мереж, криється в тому, що ТС LAN, як і любу службу, традиційно прийнято розглядати як уокремлену, автономну систему, яка виконує чітко обумовлений, обмежений набір функцій. В той же час врахування взаємозв’язків з іншими, зовнішніми по відношенню до ТС LAN, системами (службами), в тому числі системами постачання даних, може дозволити побудувати більш ефективну систему процедур (засобів) реалізації функцій. Зокрема, визначення методів і способів формування даних від зовнішніх систем для використання в процедурах реалізації функцій служби, може дозволити досягти найкращих показників, скажімо, з огляду на відомий критерій “витрати/ефективність”. Науковим завданням дисертації є пошук теоретичних основ для підвищення ефективності тільки що охарактеризованої транспортної служби локальних комп’ютерних мереж. І з огляду на сказане вище, ця проблема доволі актуальна. Для ілюстрації застосувань методів і засобів, що відшукуються в даному дослідженні, вибрано комп’ютерні мережі університетських містечок, кампусів (далі - ККМ).

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках науково-технічних (галузевих) програм МОН України, а також плану наукових досліджень, що проводились на кафедрі обчислювальної техніки і в НДІ системних технологій Національного технічного університету України “Київський політехнічний інститут”. Зокрема, в наступних НДР:

1. Створення інтегрованого комплексу програмного забезпечення та розробка керівних матеріалів по впровадженню Internet в освітніх закладах України (звіт про НДР - в УкрІНТЕІ, інв. № 0298U003086, Київ, 1998). Рівень участі – виконавець.

2. Розробка технології проблемно-орієнтованої обробки запитів в SQL-середовищі з використанням технології Internet (звіт про НДР - в УкрІНТЕІ, інв. № 0298U003085, Київ, 1998). Рівень участі – виконавець.

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

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

Для досягнення поставленої мети необхідно вирішити наступні задачі:

1. визначити склад і структуризувати засоби формалізованого опису комп’ютерних мереж;

2. розробити метод визначення ефективного набору інструментальних засобів реалізації функцій ТС LAN;

3. розробити метод і засіб, який дозволяє підвищити ефективність процедур, що вони реалізуються в транспортній службі, за рахунок використання особливостей процесів вводу в ТС LAN і переробки даних, які доставляються з зовнішніх систем;

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

5. розробити засоби врахування взаємної залежності даних, що вводяться і переробляються в ТС LAN, а також їх динаміки.

Об’єктом дослідження є процеси перетворення інформації, що вони виконуються ТС LAN, і породжують проблему підвищення ефективності транспортної служби.

Предметом дослідження є методи і засоби організації процесів перетворення інформації, впровадження яких розвязує проблему підвищення ефективності ТС LAN.

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

Наукова новизна одержаних результатів визначається наступними положеннями:

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

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

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

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

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

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

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

Теоретичні і практичні результати дисертаційної роботи використані та впроваджені:

- при створенні варіантів проекту комп’ютерної мережі Національного технічного університету України “Київський політехнічний інститут”;

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

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

Результати дисертаційної роботи було використано в наукових дослідженнях НДІСТ при НТУУ “КПІ”.

Особистий внесок здобувача. У наукових працях, опублікованих у співавторстві, здобувачеві належать: нелінійна модель розвитку комп’ютерного інформаційного центру [2]; спосіб оцінки точності рішення оптимізаційної задачі [3]; виявлена властивість оптимального рішення по структурі базової мережі передачі даних [4]; спосіб формування множини ефективних рішень оптимізаційної задачі [5]; модифікований метод морфологічного аналізу комп’ютерної мережі [6]; спосіб оцінки зміщення значення цільової функції, що розрахується при розв’язуванні оптимізаційної задачі [7]; метод, який дозволяє підвищити ефективність процедури керування телекомунікаційними системами в беспровідних комп’ютерних мережах) [8]; метод формалізованого опису комп’ютерних мереж кампусів, основаних на безпровідних технологіях) [9]; результати моделювання комп’ютеризованої університетського інформаційного центру [11]; відомості про особливості інформаційних потоків в академічних комп’ютерних системах) [12]; метод оцінки точності розрахунку вартості локальної інформаційної мережі [13].

Апробація результатів дисертації. Матеріали дисертації доповідались на конференціях і симпозіумі: Міжнародній науково-технічній конференції “Авіа-2007”, 20-22 квітня 2007р., Київ; Міжнародній науково-технічній конференції “Авіа-2006”, 23-29 квітня 2006р., Київ; Науковій конференції “Комп’ютерні системи та мережні технології”, 22-24 березня 2007р., Київ; VI Міжнародній науковій конференції студентів та молодих вчених “Політ”, 2006р., м. Київ; ІV Міжнародної науково-практичної конференції студентів, аспірантів та молодих вчених “Системний аналіз та інформаційні технології”, 1-3 липня 2002р., м.Київ; Першій міжнародній науково-практичній конференції “Відкриті інформаційні системи”, 26-27 квітня 2002р., Київ; Українсько-польському симпозіумі “Проблеми трансформації в гуманітарній, соціально-економічній та науково-освітній сферах”, 16-20 червня 1997р., м. Тернопіль.

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

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

Структура та обсяг дисертації. Дисертація складається із вступу, чотирьох розділів основного тексту, висновків, списку використаних літературних джерел з 84 найменувань на 8 сторінках і додатку. Повний обсяг дисертації складає 156 сторінок, вона містить 13 ілюстрацій, 6 таблиць, 16 сторінок додатку.

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

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

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

Пропонується наступна процедура класифікації засобів формалізованого опису ТС LAN . В якості прикладу застосування розглянуто ККМ.

1). На множині М конкретних формалізованих описів ТС LAN ККМ ( далі для скорочення – моделей ККМ) вводиться бінарне відношення R . В якості цього відношення пропонується використати таке: “мають однаковий рівень абстрагування в описі ККМ ”. Встановити це бінарне відношення можна методом аналітичної ієрархії АНР. Наприклад, формалізований опис конкретної процедури SMTP і такий же для WAP знаходяться у згаданому відношенні. Те ж справедливо стосовно опису процедури ТС LAN і процедури служби транспортного рівня моделі OSI/ISO. Тоді R породжує на М множину класів МК. В залежності від способу побудови R це можуть бути, наприклад, класи (рівні) Еталонної моделі, або класи моделі DEC тощо.

2). Введення відображення В: МКМСК, де МСК – множина існуючих класів інструментальних засобів формалізованого опису комп’ютерних мереж. Для цього кожній парі елементів, і з МК та елементу j з МСК, приписується Cij – оцінка значення функції приналежності елемента і з множини МК до елементу j з множини МСК. Значення Cij знову, як і вище, можна оцінити методом АНР. Наприклад, якщо індекс і відповідає процедурі реалізації функції встановлення зв’язку ТС LAN, а індекс j – модулярній арифметиці, то значення Cij наближається до нуля.

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

Аналітичний огляд літератури, що має відношення до застосувань формальних методів, який зроблено в розд.1, підтвердив корисність використання запропонованої процедури класифікації засобів формалізованого опису ТС LAN ККМ. В якості елементів МСК розглянуто інструменти: теорії множин; функціональні і матричні; теорії відношень; алгебраїчні; теорії ймовірностей; теорії нечіткіх множин; теорії нечіткіх відношень; теорії (детермінованих) графів; дерев; мережеві; типу алгебраїчних рівнянь; типу диференційних рівнянь; стохастичних графів; лінійного програмування; лінійного цілочисельного програмування; квадратичного програмування; нелінійного програмування; геометричного програмування; динамічного програмування; стохастичного програмування; теорії ігор; теорії черг (масового обслуговування); імітаційні дискретні; імітаційні неперервні.

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

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

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

Маємо такий зв’язок між системою (службою), яка поставляє дані в ТС LAN, і самою ТС LAN:

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

2. перетворення fгд даних з г в д;

3. процедура д , яка використовує дані про стан елементу; наприклад, процедура розрахунку ефективного маршруту за алгоритмом Дейкстри (рис.1):

Рис. 1. Процедура вводу даних в ТС LAN.

Виявлено, що дані, які знімає агент NMS в системі г, і опосередковано використовуються в системі д ТС LAN, мають такі особливості: параметри елементів LAN, що їх моніторить агент NMS змінюються в часі; значення параметрів, що їх моніторить агент NMS, мають як неперервний (фізична довжина ланки в мобільних мережах), так і дискретний (стан зв’язності ланки ) характер. Для потреб даного дослідження робимо допущення 1: значення параметрів елементів LAN, що їх моніторить агент NMS, представляються випадковою величиною; допущення 2: значення параметрів елементів LAN, що їх моніторить агент NMS і заносить у відповідну базу, носять дискретний характер.

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

В результаті маємо (нескінченну, точніше на період життєвого циклу ТС LAN) послідовність значень параметра, що його моніторять агенти NMS і заносять в відповідну базу: X1, X2 , …, Xi , … Xn ,… Xlc .

Тут Xlc відповідає моменту завершення життєвого циклу ТС LAN. Робимо

допущення 3: для життєвого циклу ТС LAN lc > ? .

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

Обгрунтування: для ТС LAN ККМ, що є предметом вивчення в роботі, маємо:

[період життєвого циклу ТС LAN ККМ] >> [такт опитування стану пристроїв] .

Звичайно такт 1/щд роботи служби д не співпадає з тактом 1/щг служби г : 1/щд ? 1/щг .

Тоді за час 1/щд маємо дані з вибірки довжиною n : X1, X2 , …, Xi , … Xn .

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

процедура А.

Формується вибірку для д шляхом застосування перетворення fгд для кожного значення Xi (i є {1,n}). Тут і далі ( i є {1,n} ) означає, що i послідовно набуває значень від 1 до n.

Для fгд робимо допущення 4 , яке слідує з допущення 1: перетворення fгд величини Xi (i є {1,n}) дає результатом випадкову величину (в загальному випадку – з іншим, невідомим законом розподілу). Ясно що якщо Xi є випадковою величиною, то fгд(Xi ) також є випадковою величиною. Ця умова не виконується, наприклад, тоді, коли Xi є не випадковою, а квазівипадковою величиною; тоді можна (штучно) створити таке перетворення даних fгд(Xi ), для якого умова допущення 4 не виконується.

В результаті маємо вибірку: (fгд (X1), fгд (X2), …, fгд (Xi), …, fгд (Xn)), для якої застосовуємо процедуру оцінки найбільш ймовірного, в такті довжиною 1/щд , значення Ave (fгд (X)). В разі зняття допущення 2 можна використати формулу

Ave (fгд (X)) = fгд (X)) (fгд (X))) (fгд (X))), де (fгд (X)) – функція щільності розподілу ймовірностей fгд (X) ; для лінійних fгд (X) тип цієї функції співпадає з аналогічною функцією для Х.

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

В роботі використано в якості показника ефективності процедури ТС LAN класичний показник “витрати / продуктивність”, який інтерпретовано в “обчислювальна складність процедури / точність процедури”. З огляду на цей показник процедура А в практиці ТС LAN інколи становиться неприйнятною: обчислювальна трудомісткість перетворення (fгд(Xi ), i є {1,n}) і розрахунку Ave (fгд (X)) є зростаючою функцією від n. У зв’язку з цим в практиці побудови процедур транспортної служби LAN використовується процедура В.

Для системи д формується не вибірка довжиною n > 1:

(fгд (X1), fгд (X2), …, fгд (Xi), …, fгд (Xn)), як це має місце в процедурі типу А, а

перетворюється лише єдине значення з вибірки X1, X2 , …, Xi , … Xn , припустимо - Xn. Тобто замість Ave (fгд (X)) маємо fгд (Xn).

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

Процедура В має значно меншу трудомісткість, ніж процедура типу А, але ступінь наближення fгд (Xn) до Ave (fгд (X)) залежить від автокореляційних характеристик величини Х(t), а також від типу перетворення fгд .

За результатами попереднього розгляду, що його зроблено в розд.1, маємо виявлену особливість ККМ, яка заключається в періодичності інформаційного навантаження (трафіку) в ланках даних. Тобто якщо величина Х(t) характеризує поточний трафік в ланці даних, вона має для кожного фіксованого t статистичну характеристику типу Ave (Х(t)) = A1 + A2·sin (2р·щdl ·t + цdl), де A1, A2, щdl , цdl – параметри зміни трафіку в ланці даних.

Припустивши, як і раніше, що за час (n·1/щг) формується послідовність значень

X1, X2 , …, Xi , … Xn , можно сформувати твердження 1: при умові 1/щdl = n·1/щг тотожність Ave (Х) = A1 + A2·sin (2р·щdl ·t+ цdl) має місце тоді і тільки тоді, коли значення Xn відповідає таким значенням для t :

t = n/(2· щг ) – (цdl ·n)/( 2р·щг) або n/щг – (цdl ·n)/( 2р·щг) .

З цього слідує твердження 2: при умовах твердження 1 і парного n має місце співвідношення: [Оцінка ймовірності того, що для довільного Xi , виконується умова

Ave (Х) = A1 + A2·sin (2р·щdl · ti + цdl)] = 2/n.

З цього слідує твердження 3: в реальних ТС LAN ККМ, де n набуває достатньо великих значень, дія твердження 2 розповсюджується і на непарні значення n.

Умови тверджень 1, 2, 3 використано для підвищення ефективності процедури типу А за згаданим критерієм. Тоді маємо (процедуру С) як модифікацію процедури В:

в процедурі В використовується з вибірки X1, X2 , …, Xi , … Xn одне фіксоване значення Xn , що значно, щонайменше в n разів, зменшує обчислювальну складність процедури. Але при цьому, як це тільки що показано, у 8/n випадків з n, тобто у 80%, маємо відхилення від найточнішої оцінки вихідних даних. Підвищити ефективність тут пропонується наступним чином. Вводимо етап попереднього розрахунку значень t згідно твердження 1. Тоді знаменник у виразі для критерію ефективності зменшується у середньому на 80 відсотків. Якщо при цьому обчислювальна складність етапу відшукання значень щг , цdl значно зростає, то пропонується процедура D. Тут пропонується використовувати з вибірки одне, як і в процедурі В, значення Xi , але воно не є фіксованим в даній послідовності, а вибирається випадковим (рівномірний в інтервалі закон розподілу ймовірностей) або генеруємо квазівипадкові величини. Це аналогічно попередньому розрахунку Ave(Х).

В розділі показано приклад застосування даного способу для маршрутизації MPLS. Скориставшись програмною системою , за допомогою якої реа-лізується алгоритм розрахунку мінімально-го часу доставки всього повідомлення, і використовуючи як вхідні дані Ave[час доставки пакетів між кож-ною парою маршрутизаторів], тобто за процедурою D, отримаємо значення очікуваного часу доставки повідомлення, яке на 10% не співпадає (менше) з дійсним, тобто отриманим за процедурою А. Якщо критерієм ефективності вибрати критерій “точність процедури”, то для даного прикладу треба застосовувати процедуру А, а якщо критерій “обчислювальна складність процедури / точність процедури”, то - D.

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

Припустимо, що граф без петель і паралельних ребер G=(U,V), де U-множина вершин потужністю n (n>2), задано матрицею суміжності М. Будемо називати довжиною маршруту в графі кількість ребер, що в нього (маршрут) входять.

Тоді справедлива Теорема 1.

Для того, щоб граф G, що представляє топологію ККМ, був зв’язним, достатньо, щоб довільна матриця Мi з {М, М2, М3,…, Мn-2, Мn-1} не містила нульових елементів поза головною діагоналлю.

Доведення. Матриця М за визначенням не містить від’ємних елементів. Звідсіля слідує, що довільний доданок з суми М+М2+М3+…+Мn-2+Мn-1 не містить від’ємних елементів (доданки суть скалярні добутки М). Таким чином, якщо довільний доданок не містить нульових елементів, то В = М+М2+М3+…+Мi+…+Мn-2+Мn-1, теж не містить нульових елементів. А в такому випадку граф G є зв’язним. Що і вимагалось довести.

Теорема 2. Для того, щоб G був зв’язним, достатньо, щоб існувала підмножина D множини {М, М2, М3,…,Мi,…, Мn-2, Мn-1} така, щоб матриця E= ?i Мi (Мi е D) містила поза головною диагоналлю відмінні від нуля елементи. Доведення аналогічне.

Використовуючи ці твердження, в розд.2 запропоновано наступний (модифікований) алгоритм перевірки зв’язності графу, що представляє топологію LAN.

1.

i =0, С=0 (0-матриця n·n ). Граф незв’язний.

2.

3.

4.

5.

Показано, що (статистично) процедура ТС LAN, побудована на основі запропонованого алгоритму, є більш ефективною, по зрівнянню з класичним, за критерієм “обчислювальна складність процедури / точність процедури”.

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

В розділі розглянуто резерви підвищення ефективності ТС LAN за рахунок змінення принципів декомпозиції. Відповідно до стандартів OSI \ ISO комп’ютерна мережа піддається декомпозиції, що закладає резерви підвищення ефективності однієї з її складових – транспортної служби. Кожна складова відповідає за виконання об-меженого набору функцій, запрошуючи ресурси для виконання деяких своїх функцій у зовнішніх підсистем, безпосередньо або опосеред-ковано. Проблема неточності вхідних даних для ТС LAN, про що йшла мова в розд.2, і які використовуються в практичній реалізації алгоритмів, обумовлена, зокрема, і декомпозицією. Пропонується зменшити ймовірність помилок, пов’язаних з декомпозицією за ознаками Еталонної моделі, шляхом порушення в деяких випадках розмежувань функцій по рівнях.

В розділі отримано спосіб визначення найбільш ефективних процедур для реалізації основних функцій ТС LAN на основі морфологічного аналізу задачі. Складність створення системи процедур заключається в тому, що від вибраного способу реалізації i – ї функції залежить вибір способу реалізації j – ї функції. Наприклад, від способу організації сбору даних для маршрутизації в NMS (має місце централізований спосіб або децентралізований), залежить вибір способу реалізації функції маршрутизації в ТС LAN: (алгоритм Беллмана-Форда, Дейкстри або інші). З цієї причини сам набір функцій повинен бути повним для ТС LAN і одночасно, по можливості, таким, що функції були б якнайменше пов’язані між собою на предмет способів їх реалізації. Далі для кожної функції формується перелік методів її реалізації. При цьому таке формування відбувається автономно, без врахування зв’язків, що вони існують стосовно інших функцій. Такий підхід значно спрощує задачу пошуку рішень з причини спрощення первинної задачі і зняття обмежень, які обумовлені зв’язками між задачами. В результаті потужність множини можливих ( спочатку - не обов’язково допустимих) варіантів розв’язань первинної задачі розширюється.

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

1. формування набору функцій ТС LAN.

2. формування т. зв. часткових рішень по кожній з k функцій, тобто множин Мі (і є {1, …,k}, що представляють способи реалізації (нормативних) процедур ТС LAN.

3. формування множини Мнр несумісних рішень.

4. формування множини повних реалізуємих рішень, яка власне і утворює систему процедур ТС LAN:

Мі · Мі · Мі · Мі · \ Мнр .

5. Вибір оптимального варіанта з множини Мі · Мі · Мі · Мі · \ Мнр .

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

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

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

Припустимо, що величини, що складають вектор Х, не є незалежними, як це припускалось раніше. Маємо результати моніторингу LAN в тактовий для г період вже в вигляді матриці [xji] , в якій елемент xji (jє{1…m}, iє{1…n} представляє собою і –те в такті значення j-го параметра. При цьому індекс і використовується в тому ж значенні, що й в розд. 2, а індекс j відповідає j-му параметру, скажімо – в ланці даних. Позначення Xi тепер є вектором (стовбчиком) з [xji]. Аналіз сенсу складових Xi показує, що серед цих складових, які представляють параметри, що їх використовують процедури ТС LAN, є зв’язані між собою. Дійсно, для ланки даних час затримки і трафік є залежними одне від одного. Далі, якщо один й той же параметр, скажімо, - коефіцієнт завантаження ланки даних, - моніториться для різних ланок даних комп’ютерної мережі, то можна показати, що його значення пов’язані статистично між собою. У випадку, коли між величинами xj, xk маємо статистичний зв’язок, то для оцінки очікуваного значення xk пропонується використовувати вираз типу:

Ave (xk) = Kjk ·Ave (xk) + Ljk , де Kjk , Ljk – коефіцієнт (парної) кореляції, константа – відповідно.

В розділі наводяться приклади застосувань описаних схем для реальніх прикладів. Нехай параметрами Х є інтенсивності інформаційних потоків, що генерується в абонентських системах. Потік інформації генерується в кожній абонентській системі з інтенсивністю, яка представляється у вигляді функціональної залежності, що реалізується відповідною процедурою: , де , – значення параметрів, які враховують особливості i-ї абонентської системи, - загальномережевий параметр інтенсивності інформаційного потоку, він і є головною причиною наявності кореляційного зв’язку. Згідно з методами, розглянутими вище, для розрахунку hi використовується вираз вигляду: hi = f(Ave(), Ave(), Ave()).

Статистична залежність параметрів представляється матрицею, елементи якої визначаються співвідношенням:

= Ave((– Ave)( – Ave)), , {, , }.

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

Дані, що використовуються в процедурах ТС LAN, є динамічними, змінними в часі. У зв’язку з потактовим (дискретним) характером опитування стану складових LAN, маємо загублену інформацію в період часу 1/щг між опитуваннями. Описано спосіб підвищення релевантності даних що доставляються в ТС LAN – шляхом прогнозування значень вхідних даних для розрахунків в процедурах транспортної служби. Розроблено формальну модель прогнозування для використання в процесах вводу даних в ТС LAN ККМ. Підготовка вхідних для ТС LAN даних відбувається на основі розробленої математичної моделі, із застосуванням інструменту диференційних рівнянь. Період моніторингу [t0, tlc] представлено у вигляді ряда рівних інтервалів ( [t0, t1], [t1, t2], … [tn-1, tn],…[tlc-1, tlc] ).У кожному інтервалі [tn-1, tn] значення X(tn-1) змінюється на величину Д X(tn), пропорційну деякій функції B(tn,tn-1):

Д X(tn) = B(tn,tn-1)·Дt . Розв’язання диференціальних рівнянь моделі засновано на використанні одного із класичних методів.

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

ВИСНОВКИ

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

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

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

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

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

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

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

1. Печурін С.М. Модель статистичної оцінки вразливості проектних рішень по структурі інформаційної мережі // Адаптивні системи автоматичного управління.- 1998. - №1(21). - С.127-129.

2. Будя О.П., Кондратова Л.П., Печурін С.М. Модель системної динаміки розвитку комп’ютерного інформаційного центру університетської бібліотеки // Адаптивні системи автоматичного управління. – 1998. - №1(21). – С.123-127.

(Запропоновано нелінійну модель розвитку комп’ютерного інформаційного

центру)

3. Стєнін О.А., Кондратова Л.П., Печурін С.М. Стійкість рішень по структурі базової мережі передачі даних, що розвивається // Адаптивні системи автоматичного управління. – 1999. - №2. – С. 3-6.

(Запропоновано і досліджено спосіб оцінки точності рішення оптимізаційної задачі)

4. Печурін М.К.,