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

Дуравкін Євген Володимирович

УДК 681.5:629.39.5

МЕТОДИКА МОДЕЛЮВАННЯ ПРОТОКОЛІВ ІНФОРМАЦІЙНОГО ОБМІНУ З ВИКОРИСТАННЯМ АПАРАТІВ Е-МЕРЕЖ ТА ЙМОВІРНОСНО-ЧАСОВИХ ГРАФІВ

05.12.02 – Телекомунікаційні системи та мережі

АВТОРЕФЕРАТ

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

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

Харків–2003

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

Робота виконана в Харківському військовому університеті

Міністерства оборони України.

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

Лосєв Юрій Іванович,

Харківський військовий університет,

професор кафедри ХВУ

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

Поповський Володимир Володимирович

Харківський Національний університет

радіоелектроніки

завідуючий кафедрою “Телекомунікаційні системи”

кандидат технічних наук, старший

науковий співробітник

Кучеренко Юрій Федорович,

Науковий центр бойового застосування

Військово-Повітряних Сил ЗС України,

начальник науково-дослідного відділу

(проблем автоматизації управління авіації).

Провідна установа: Одеська національна академія зв’язку ім. О.С. Попова

Державного комітету зв’язку та інформатизації

України, кафедра “Мережі зв’язку”.

Захист відбудеться “16” жовтня 2003 року о 14 годині на засіданні спеціалізованої вченої ради Д64.820.01 Української державної академії залізничного транспорту за адресою: 61050, м. Харків, пл. Фейєрбаха, 7.

З дисертацією можна ознайомитись у бібліотеці Української державної академії залізничного транспорту за адресою: 61050, м. Харків, пл. Фейєрбаха, 7.

Автореферат розісланий “15” жовтня 2003 року.

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

Спеціалізованої вченої ради Книгавко М.В.

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

Актуальність теми дисертаційної роботи. 

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дійсна робота виконувалась відповідно до досліджень з НДР “Кодо-грамма-2” та “Нить”, що проведені у Харківському військовому університеті.

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

Основна задача роботи – зробити функціональний та структурний опис системи протоколів інформаційного обміну засобами Е-мереж та ЙЧГ. По розробленим графам провести автоматичну генерацію математичного опису, що буде початковими даними при проведенні комплексного аналізу.

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

Предметом дослідження є методи аналізу ефективності телекомунікаційних систем на основі комплексного використання Е-мереж та ЙЧГ.

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

Відповідно до поставленої мети необхідно вирішити часткові задачі:

1. Розробити методи функціонального опису протоколів інформаційного обміну засобами Е-мереж та ЙЧГ для різних вхідних даних.

2. Визначити набір алгоритмічних властивостей Е-мереж і розробити способи їх аналізу для забезпечення можливості перевірки коректності моделей (методи якісного аналізу).

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

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

5. Розробити програмний комплекс, що дозволяє автоматизувати процеси розробки, перевірки коректності моделей, проведення імітаційного моделювання (для Е-мереж), перетворення та одержання результуючих аналітичних залежностей (для ЙЧГ).

Наукова новизна отриманих результатів.

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

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

3. Вдосконалено метод використання апарата ЙЧГ як засобу аналітичного аналізу протоколів інформаційного обміну. Розроблено метод аналізу ЙЧГ, для яких неможливе застосування еквівалентних перетворень.

4. Вперше розроблена методика аналізу системи протоколів інформаційного обміну при комплексному використанні засобів Е-мереж і ЙЧГ, що дозволяє підвищити повноту аналізу систем протоколів інформаційного обміну.

Практичне значення отриманих результатів.

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

Розроблена методика моделювання може бути застосована:

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

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

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

Матеріали дисертаційної роботи використані у НДР “Кодограмма-2”, “Нить” та в навчальному процесі Харківського військового університету.

Особистий внесок здобувача. В [1] автором особисто запропоноване розширення апарату Е-мереж для функціонального та структурного опису протоколів, обґрунтовані принципи такого опису; в [2] автором розглянута можливість використання алгоритмічних властивостей Е-мереж, як засобу перевірки коректності імітаційних моделей; в [3] автором, за допомогою розробленої методики моделювання, перевірена коректність алгоритмів маршрутизації, що запропоновані; в [4] сформульована методика розробки й аналізу моделей протоколів інформаційного обміну та розроблений метод аналізу ЙЧГ, для яких не можливе застосування методу еквівалентних перетворень; в [5] розроблені алгоритми, які дозволяють створити програмний пакет, що реалізує запропоновану методику моделювання.

Апробація результатів дисертації проводилася на 3-х науково-технічних конференціях: 1-му МРЕФ ХНУРЕ м. Харків 2002р., 1-й та 2-й науково-практичних конференціях молодих вчених ХВУ м. Харків 2002р. та 2003р.

Публікації. За темою дисертації надруковано 5 наукових статей, тези доповідей на 2-х науково-технічних конференціях, 2 звіти про НДР.

Структура й обсяг дисертації. Робота складається з вступу, 4-х розділів, висновків, списку використаної літератури, 7-и додатків. Повний обсяг дисертації складає 220 сторінок, у тому числі 150 сторінок основного тексту, 61 малюнок, список використаних джерел з 100 найменувань на 9 сторінках.

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

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

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

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

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

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

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

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

Досвід використання Е-мереж як засобу розробки моделей протоколів інформаційного обміну виявив їх деякі недоліки. Для їх усунення, а також спрощення процесу розробки моделей у дисертації були введені доповнення в апарат Е-мереж. Множина переходів доповнена переходами J’, F’, М2, M2’, для яких умови збудження мають вигляд:

J’: ,

де L – пряма функція інцидентності; D – зворотня функція інцидентності; М(рi) – розмітка місця рi, m – кількість вхідних місць.

F’: ,

де n – 1 – кількість вихідних місць.

M2:р1L(M2){M(p1)=1}р2L(M2){M(p2)=1} р3D(M2){M(p3)=0}.

M2’:(р1L(M2){M(p1)=1}р2L(M2){M(p2)=1}) р3D(M2){M(p3)=0}.

Процедура переходів М2 і М2’:

Rij={M(p1(R(i)) M(p2R(i))):= M(p3R(i))},

відповідає операції додавання по mod2 для елементів i вектора атрибутів міток, які знаходяться у вхідних місцях р1 і р2.

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

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

Відповідно до рекомендацій МККТТ на етапах специфікації і проектування протоколи повинні бути представлені у виді SDL-діаграм або схем алгоритмів. Отже, дані засоби і були прийняті як джерела початкових даних для розроблювальної методики. При формуванні Е-мережі, коли в якості вихідних даних використовуються схеми алгоритмів роботи, за основу прийнята відома методика, розроблена для апарата мереж Петрі. У дану методику внесено зміни, що дозволяють врахувати специфіку Е-мереж (наявність розходжень у топології й описі апарата і т.п.). Порівняльний аналіз SDL-діаграм і Е-мереж як засобів формального опису протоколів інформаційного обміну показав, що безпосередній перехід неможливий. Для усунення даного недоліку запропонована послідовність дій, що дозволяє здійснити перехід від SDL-діаграми до Е-мереж.

1. По елементах множини вершин “стан і рішення” (sr) утворити місця.

2. По відношенням предшествовання і проходження станів утворити переходи мережі:

f:(S I {0;1}) ((I О Р) (О S R Р) {0;1})

(R (О S R Р) {0;1});

g: ( I S {0;1}),

де f — функція проходження; g — функція предшествування; I - кінцева множина символів ВХІД; О - кінцеву множину символів ВИХІД; S - кінцева множина символів СТАН; R - кінцева множина символів РІШЕННЯ; Р - кінцева множина символів ЗАДАЧА.

3. Встановити між ними відношення інцидентності:

F(sri) = fm(sri) = {sri}; G(srj) = gm(srj) = {srj}.

4. Вершинам ВХІД та ВИХІД, що знаходяться між сусідніми вершинами “стан і рішення”, утворити дуги до підмережі зовнішнього середовища:

L(bi,hk)=1; D(hk,bi)=1,

де L – пряма функція інцидентності; D – зворотна функція інцидентності; hk H – перехід Е-мережі; bi B – периферійне місце.

5. Присвоїти атрибути і визначити процедури переходів мережі.

6. Визначити вектор атрибутів мітки.

7. Встановити початкову розмітку.

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

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

Для рішення задач аналізу динаміки функціонування протоколів інформаційного обміну і СОД у цілому проводиться імітаційне моделювання. Запропонована методика моделювання припускає сполучення стохастичної (зовнішнього середовища) і детермінованої частини (алгоритм, ресурси). Отримання значень показників якості на імітаційній моделі виробляється шляхом аналізу кількості міток у місцях-поглиначах та динаміки їх переміщення по мережі. Оцінка точності та вірогідності результатів імітаційного моделювання визначається за допомогою оцінки довірчого значення погрішності. Довірчу імовірність () і припустиму величину відносної помилки () запропоновано встановити: = 0,8 і = 0,5%. Обчислення вироблялися в припущенні, що частоти появи аналізованих подій розподілені по нормальному закону. Для забезпечення заданої точності параметри експерименту встановлене: k=100, m=10000, де k – число дослідів, m – число реалізацій у досліді (переданих пакетів).

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

Розробка моделей протоколів інформаційного обміну відбувається відповідно до 7-ми рівневої структури взаємодії відкритих систем (ВВС) (для розробки моделі протоколу (N+1)-го рівня використовуються результати, отримані на моделі протоколу N рівня). Даний підхід враховує взаємодію протоколів різних рівнів, а також знижує протиріччя між вимогами до адекватності і простоти моделей.

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

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

Для перевірки адекватності введеного розширення Е-мереж розроблена модель найбільш розповсюдженого протоколу канального рівня LAP-B у режимах встановлення з'єднання і передачі кадрів. На розроблених моделях отримані залежності часу встановлення з'єднання і часу доведення двох пакетів від рівня помилок у каналі зв'язку. Графічно ці залежності представлені на рис. 1 і 2.

Рис. 1. Графік часу встановлення з’єднання

Аналіз приведених залежностей показує, що розбіжність між результатами імітаційного (крива И. М.) і аналітичного (крива А. М.) моделювання не перевищує 5% на всьому інтервалі при описаних вище параметрах імітаційного моделювання. Отже, можна зробити висновок про адекватність введеного розширення Е-мереж.

Рис. 2. Графік часу доведення двох кадрів

За одиницю часу моделювання прийнята тривалість пакета (Тп). Отже, - середній відносний час встановлення з'єднання (рис.1) і середній відносний час доведення двох кадрів (рис. 2).

Розробка моделей відбувалася для наступних умов: імовірність помилки в каналі зв'язку ро= 10-3 – 10-5; помилки в каналі зв'язку некорельованні; у якості завадостійкого використовується циклічний код з поліномом, що породжує, х16+х12+х5+1; кількість перезапитів не обмежений; довжина кадру 128 біт. Інтервал зміни імовірності помилок у каналі зв'язку обумовлений характеристиками реальних каналів.

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

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

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

Запропонована методика дозволяє:

розробляти моделі відповідно до належності протоколу до визначеного рівня ВВС та особливостей функціонування;

для розробленої Е-мережі виконати перевірку її коректності й імітаційне моделювання;

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

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

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

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

Для розширення області застосування ЙЧГ розроблено метод аналізу графів, для яких неможливе застосування методу еквівалентних перетворень.

З огляду на специфіку використаних математичних апаратів (Е-мережі та ЙЧГ), прийняте рішення про необхідність розробки двох окремих програм: “Е-мережа” і “ЙЧГ”.

За допомогою програми “Е-мережа” реалізується можливість: побудови графа Е-мережі (моделі досліджуваної системи); автоматичного визначення функцій інцидентності для переходів сформованої Е-мережі; визначення параметрів (тимчасових характеристик, процедур переходів, предикатів для МХ- і MY-переходів) переходів; визначення параметрів взаємодії з зовнішнім середовищем (потоки пакетів (біт), які надходять із суміжного рівня чи каналу зв'язку); забезпечення можливості побудови ієрархічної структури моделей (аналогічно концепції побудови протоколів обміну даними); визначення параметрів імітаційного експерименту (тривалості моделювання, умов припинення моделювання, режиму роботи моделі); збору статистики; визначення алгоритмічних властивостей шляхом аналізу графа Е-мережі (оцінка якісних показників функціонування об'єкта, що моделюються).

За допомогою програми “ЙЧГ” реалізується можливість: побудови ймовірносно-часового графа, що описує систему, яка моделюється; формування матриць суміжності і інцидентності графа по графічному зображенню; проведення еквівалентних перетворень графа; за результатами перетворень формування результуючих функцій, що описують перехід системи з початкових станів у кінцеві чи задані.

Крім того в даному розділі розроблений метод аналізу так званих “графів, що не приводяться” (графи, топологію яких не вдається методом еквівалентних перетворень привести до виду, що містить тільки початковий і кінцевий стан). Розроблений метод передбачає на першому етапі за допомогою апарата ланцюгів Маркова розрахунок кількості тактів роботи системи, через яке вона виявиться в одному з кінцевих станів:

,

де Р – матриця перехідних імовірностей на k-м кроці;

N – вектор початкової розмітки;

Ск – вектор розподілу імовірностей між станами моделюємої системи на k-м кроці.

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

,

де i, j, l – номера кінцевих вершин; g – граничне значення сум імовірностей.

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

ВИСНОВКИ ПО РОБОТІ

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

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

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

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

5. Як методи кількісного аналізу моделей основним прийняте імітаційне й аналітичне моделювання. Для даного методу обрані показники якості протоколів різних рівнів ВОС, а так само описані способи їхнього одержання на Е-мережах і ЙЧГ.

6. Для підвищення точності моделей в апарат Е-мереж введені доповнення. Розширені: множина переходів введенням переходів J', F', M2 і M2'; множина місць – макромісцями-чергами Q і Q'; розширені можливості опису предикатів MX-, MY-переходів.

7. Розроблено метод аналізу ЙЧГ, що дозволяє отримувати значення показників якості на графах, для яких неможливе застосування методу еквівалентних перетворень. Розробка даного методу розширює область застосування апарата ЙЧГ.

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

9. При розробці моделі протоколу LAP-B зроблена перевірка адекватності введеного розширення Е-мереж. Отримані у ході моделювання значення показників якості функціонування показують узгодженість з відомими результатами.

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

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

програма побудови, перетворення й аналізу ЙЧГ.

11. У результаті застосування розробленої методики досягнута можливість поділу процесів побудови, аналізу, проведення імітаційного моделювання і написання моделюючої програми. Процес розробки моделі зведений до побудови її графа у відповідному програмному середовищі, а функції генерації математичного опису, перевірки коректності (для Е-мереж), проведення еквівалентних перетворень і одержання аналітичних співвідношень (для ЙЧГ) виконуються автоматично.

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

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

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ

1. Лосев Ю.И., Шматков С.И., Дуравкин Е.В. Применение Е-сетей для моделирования процесса функционирования СОД// Радиотехника: Всеукр. межвед. науч.-техн. сб. 2001. Вып. 123. С. 99-103.

2. Лосев Ю.И., Дуравкин Е.В. Применение методов анализа Е-сетей к моделям СОД// Радиотехника 2002. Вып 132. С. 189-202.

3. Лосев Ю.И., Польщиков К.А., Дуравкин Е.В. Адаптивная маршрутизация в телекоммуникационных сетях// Радиотехника 2002. Вып 128. С. 74-79.

4. Лосев Ю.И., Шматков С.И., Дуравкин Е.В. Методика моделирования протоколов канального и сетевого уровней с использованием Е-сетей и вероятностно-временных графов// Сборник научных трудов 1-го Междунароного радиоэлектронного форума “Прикладная радиоэлектроника. Состояние и перспективы развития” (МРФ-2002). – Часть 1. – Харьков: АН ПРЭ. – 2002. С. 409-412.

5. Лосев Ю.И., Дуравкин Е.В. Программная среда разработки и анализа моделей протоколов информационного обмена// Труды УННИРТ – 1. 2003г. с. 13-15.

АНОТАЦІЯ

Дуравкін Є. В. Методика моделювання протоколів інформаційного обміну з використанням Е-мереж та ймовірносно-часових графів. – Рукопис. Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.12.02 – Телекомунікаційні системи та мережі. Українська державна академія залізничного транспорту. Харків, 2003.

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

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

Для розширення області використання ЙЧГ розроблений метод аналізу графів до яких неможливе застосування методу еквівалентних перетворень.

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

зробити розробку моделі відповідно належності протоколу до визначеного рівня ВВС і особливостями функціонування;

для розробленої Е-мережі провести перевірку її коректності та імітаційне моделювання;

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

Адекватність методики моделювання преревірялась шляхом порівняння результатів моделювання з відомими.

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

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

АННОТАЦИЯ

Дуравкин Е. В. Методика моделирования протоколов информационного обмена с помощью аппаратов Е-сетей и вероятностно-временных графов. – Рукопись. Диссертация на соискание ученой степени кандидата технических наук по специальности 05.12.02 – Телекоммуникационные системы и сети. Украинская государственная академия железнодорожного транспорта. Харьков. 2003.

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

Для повышения адекватности разрабатываемых моделей в аппарат Е-сетей введены дополнения (расширены множества переходов, мест, расширены возможности определения предикатов МХ- и MY-переходов.). Для расширения области использования ВВГ разработан метод анализа графов, к которым невозможно применение метода эквивалентных преобразований.

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

Согласно рекомендациям МККТТ на этапах спецификации и проектирования протоколы должны быть представлены в виде SDL-диаграмм либо схем алгоритмов. Данные средства приняты в качестве источников входных данных для предлагаемой методики. При формировании Е-сети, когда в качестве исходных данных используются схемы алгоритмов работы, за основу принята известная методика, разработанная для аппарата сетей Петри. В данную методику внесены изменения, позволяющие учесть специфику Е-сетей (наличие различий в топологии и описании аппарата и т. п.).

Разработка моделей протоколов информацион-ного обмена производится в соответствии с 7-ми уровневой структу-рой ВОС (для разработки модели протокола (N+1)-го уровня используются ре-зультаты, полученные на модели протокола N уровня). Данный подход учитывает взаимодействие протоколов различных уровней, а также снижает противоречия между требованиями к адекватности и простоте моделей.

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

Разработанная методика моделирования позволяет:

произвести разработку модели в соответствии с принадлежностью протокола к определенному уровню ВОС и особенностями функционирования;

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

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

Адекватность разработанной методики моделирования проверялась путем сравнения результатов моделирования с уже известными.

Для реализации предлагаемой методики моделирования разработан программный комплекс в состав которого входят программы построения и анализа моделей, представленных в виде Е-сетей и ВВГ.

Ключевые слова: система обмена данными, математическое моделирование, Е-сети, вероятностно-временные графы, протоколы.

SUMMARY

Duravkin E. V. Methods of modeling protocol information exchange by means of Е-nets and probabilistic-temporary graphs. - Manuscript. The thesis on competition of scientific degree of candidate of the technical sciences on a specialty 05.12.02. - Telecommunication systems and networks. The Ukrainian State Academy of Railway Transport. Kharkiv, 2003.

The thesis is dedicated to development of the methods of modeling protocol information exchange which capable to race efficiency of their analysis. The analysis of the requirements to simular protocol information exchange is performed. For their satisfactions under development methods must be based on complex using analytical and simulation methods of modeling is shown, also. Е-nets and probabilistic-temporary graphs are used for the analysis.

For increasing of adequacy of the under development models in means Е-nets additions (the extended ensemble transition, places) is incorporated. For expansion of the range of usage probabilistic-temporary graphs the method of the analysis graphs for which impossible using the method of the equivalent transformations is designed.

The designed methods of modeling allows:

produce the development to models in accordance with attribute of the protocol to determined level of the architecture interacting opened systems and particularity of the operation;

for designed Е-nets execute check to its correctness and simulation modeling;

realize transition from simulation model to analytical.

The general method of modeling is based on partial methods modeling protocol separate level.

Adequacy of the designed methods of modeling was checked by comparisons result of modeling with known result.

For realization of the proposed methods of modeling the program complex which include the programs of the building and analysis of the models presented as Е-nets and probabilistic-temporary graphs is designed.

The Keywords: system of the exchange data, mathematical modeling, Е-nets, probabilistic-temporary graphs, protocols.

Підписано до друку 05.09.03. Формат 60х90 1/16

Обсяг: обл. вид. арк. 1,0 умов. друк. арк. 1,25. Наклад 100 прим.

____________________________________________________________

Надруковано у друкарні “ШТРІХ” ПП Шуст Ю.М.

М. Харків, вул. Бакуліна, 33

тел.: (0572) 19-49-29, 54-60-37