Ім'я файлу: 2020_M_EOM_Bazylskyi_A_A.pdf
Розширення: pdf
Розмір: 1184кб.
Дата: 03.12.2022
скачати
Пов'язані файли:
Дипломна робота Магістр - 2022 (2).docx
Курс лекцій_Інформатика.docx
Аналіз обчислювальних мереж Новик ІН-302 (1).docx
система управління інформвційної безпеки.pdf
Розширення: pdf
Розмір: 1184кб.
Дата: 03.12.2022
скачати
Пов'язані файли:
Дипломна робота Магістр - 2022 (2).docx
Курс лекцій_Інформатика.docx
Аналіз обчислювальних мереж Новик ІН-302 (1).docx
система управління інформвційної безпеки.pdf
Міністерство освіти і науки України
Харківський національний університет радіоелектроніки Факультет комп’ютерної інженерії та управління
(повна назва) Кафедра електронних обчислювальних машин
(повна назва)
АТЕСТАЦІЙНА РОБОТА Пояс нюв а льна записка
Рівень вищої освіти другий (магістерський)
Моделі представлення елементів систем масового обслуговування з міжагентним інформаційним обміном тема)
Виконав: студент
II курсу, групи
КСМм-19-1
Базильський А.А.
(прізвище, ініціали)
Спеціальність
123 – Комп’ютерна інженерія код і повна назва спеціальності) Тип програми освітньо-професійна
(освітньо-професійна або освітньо-наукова)
Освітня програма
Комп’ютерні системи та мережі
(повна назва освітньої програми)
Керівник: доц. Янковський О.А. посада, прізвище, ініціали)
Допускається до захисту Зав. кафедри ЕОМ
Коваленко А.А.
(підпис)
(прізвище, ініціали)
2020 р.
Харківський національний університет радіоелектроніки
ЗАТВЕРДЖУЮ: Зав. кафедри
(підпис)
“”
20 р.
ЗАВДАННЯ НА АТЕСТАЦІЙНУ РОБОТУ студентові
Базильському Антону Андрійовичу
(прізвище, ім’я, по батькові)
1. Тема роботи Моделі представлення елементів систем масового обслуговування з міжагентним інформаційним обміном затверджена наказом по університету від “ 30 ” жовтня
2020 р. № 1487 Ст
2. Термін подання студентом роботи до екзаменаційної комісії
14 грудня 2020 р. Вхідні дані до роботи мережі Петрі використання статистики UDP
СМО
4. Перелік питань, що потрібно опрацювати в роботі
Методи аналітичного, імітаційного та натурного моделювання
Моделювання обчислювальних мереж на основі мереж Петрі Синтез моделі Факультет комп’ютерної інженерії та управління Кафедра електронних обчислювальних машин
Рівень вищої освіти другий (магістерський)
Спеціальність
123 – Комп’ютерна інженерія код і повна назва) Тип програми освітньо-професійна
(освітньо-професійна або освітньо-наукова)
Освітня програма
Комп’ютерні системи та мережі
(повна назва)
5. Перелік графічного матеріалу із зазначенням креслеників, схем, плакатів, комп’ютерних
ілюстрацій (слайдів) арк. ф. А 6. Консультанти розділів роботи (заповнюється за наявності консультантів згідно з наказом, зазначеним у п )
Найменування розділу Консультант посада, прізвище, ім’я, по батькові)
Позначка консультанта про виконання розділу підпис дата
КАЛЕНДАРНИЙ ПЛАН
№
Назва етапів роботи
Термін виконання етапів роботи
Примітка
1
Аналіз завдання
06.11.2020-12.11.2020 2
Аналіз науково-технічної літератури
13.11.2020-23.11.2020 3
Вивчення концепції імітаційного моделювання 24.11.2020-01.12.2020 4
Розробка моделі
02.12.2020-05.12.2020 5
Оформлення пояснювальної записки
06.12.2020-10.12.2020 6
Оформлення графічної частини
11.12.2020-12.12.2020 7
Представлення роботи науковому керівнику
13.12.2020-14.12.2020 Дата видачі завдання 3 листопада 2020 р. Студент
(підпис)
Керівник роботи доц. Янковський О.А.
(підпис) посада, прізвище, ініціали)
РЕФЕРАТ
Пояснювальна записка атестаційної роботи: 67 с, 10 рис, 6 табл, 1 дод., 15 джерел. СИСТЕМА МАСОВОГО ОБСЛУГОВУВАННЯ, МЕРЕЖА ПЕТРІ,
ОБЧИСЛЮВАЛЬНА СИСТЕМА,
ІМІТАЦІЙНА МОДЕЛЬ,
ІНФОРМАЦІЙНИЙ ОБМІН.
Метою атестаційної роботи є аналіз моделей представлення елементів систем масового обслуговування з використанням мереж Петрі. У роботі запропоновано механізм побудови мереж Петрі для основних об'єктів обчислювальних систем, формалізовані функції мережевих об'єктів у вигляді примітивних функціоналів з використанням мереж Петрі. Запропоновані операції над мережами Петрі, що дозволяють легко конструювати модель обчислювальної системи. Для демонстрації побудованої моделі, наведено приклад побудови мережі Петрі для фрагмента локальної мережі, розглянуті питання маршрутизації в імітаційній моделі, запропонований узагальнений алгоритм роботи імітаційної моделі.
ABSTRACT
Master’s thesis: 67 pages, 10 figures, 6 tables, 2 appendices, 15 sources.
CUSTOM SERVICE SYSTEM, PETRI NETWORK, COMPUTER
SYSTEM, SIMULATION MODEL, INFORMATION EXCHANGE.
The purpose of the certification work is to analyze the models of representation of elements of queuing systems using Petri nets. The mechanism of construction of Petri nets for the basic objects of computer systems is offered in the work, functions of network objects in the form of primitive functionals with use of
Petri nets are formalized. Operations on Petri nets are offered, which allow to easily construct a model of a computer system. To demonstrate the constructed model, an example of constructing a Petri net for a fragment of a local network is given, routing issues in a simulation model are considered, a generalized algorithm of simulation model operation is proposed.
ЗМІСТ
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ, СИМВОЛІВ, ОДИНИЦЬ,
СКОРОЧЕНЬ І ТЕРМІНІВ ..................................................................................... ВСТУП ..................................................................................................................... 9 1 МОДЕЛЮВАННЯ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ ................................... 10 1.1 Методи моделювання мережевого трафіку .............................................. 10 1.2 Методи аналітичного, імітаційного і натурного моделювання ............. 14 1.3 Аналітичне моделювання на основі теорії систем масового обслуговування .................................................................................................. 16 1.4
Інструментальні засоби
імітаційного моделювання обчислювальних мереж .................................................................................... 24 2 МОДЕЛЮВАННЯ ОБЧИСЛЮВАЛЬНИХ МЕРЕЖ НА ОСНОВІ МЕРЕЖ ПЕТРІ ...................................................................................................... 32 2.1 Інформаційна модель обчислювальної мережі ........................................ 32 2.2 Математична модель ОС на основі МП .................................................... 34 2.2.1 Основні визначення ............................................................................... 35 2.2.2 Подання основних пристроїв мережі ................................................... 37 2.3 Приклади побудови мереж Петрі для різних ОС ..................................... 41 2.3.1 МП для робочої станції з одним мережевим інтерфейсом ................ 41 2.3.2 МП для вузла-концентратора ................................................................ 42 2.3.3 МП для вузол - міст ............................................................................... 43 2.3.4 МП для вузол - маршрутизатора .......................................................... 43 2.3.5 МП для полудуплексного каналу з втратами ...................................... 45 2.3.6 МП для дуплексного каналу з втратами .............................................. 47 3 СИНТЕЗ МОДЕЛІ І МОДЕЛЮВАННЯ ЇЇ РОБОТИ ..................................... 49 3.1 Алгоритм роботи побудованої моделі на основі МП .............................. 49 3.2 Загальні принципи застосування моделі .................................................. 50 3.3 Апробація моделі ........................................................................................ 53
ВИСНОВКИ ........................................................................................................... 58
ПЕРЕЛІК ДЖЕРЕЛ ПОСИЛАННЯ .................................................................... 59
ДОДАТОК А .......................................................................................................... 61
Графічний матеріал атестаційної роботи ............................................................ 61
8
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ, СИМВОЛІВ, ОДИНИЦЬ, СКОРОЧЕНЬ І ТЕРМІНІВ
GMP – узагальнені модульовані випадкові процеси
MMP – пуассоновский процес з марковської модуляцією
MMP –процес з марковської модуляцією ЛОМ – локальна обчислювальна мережа
МПД – мережа передачі даних
МП – мережа Петрі ОС – обчислювальна система
СМО – системи масового обслуговування
ВСТУП У наш час постійний розвиток комп'ютерних технологій дозволяє вирішувати все більш складні завдання. Зараз існує велика кількість важко вирішуваних завдань - це такі завдання, для вирішення яких потрібна значна кількість обчислювальних комп'ютерів і обчислювальних мережа також велика кількість часу.
Однією з актуальних важко вирішуваних ззадач є завдання моделювання комп'ютерних мереж. Це завдання включає в себе тестування різних мережевих компонентів, визначення найкращої топології проектованих комп'ютерних мереж, проведення досліджень в області мережевих технологій і т.і.
Сьогодні до комп'ютерних мереж як до обчислювальної платформи підприємства пред'являються все більш жорсткі вимоги надійності, швидкості та ефективності. Мережа розглядається як важливий, іноді навіть критично важливий ресурс, який повинен бути використаний максимально ефективно при мінімальних витратах. Високі вимоги до якості роботи мережі забезпечують інтерес до моніторингу та моделювання обчислювальних мереж. Засоби моніторингу доступні сьогодні в широкому асортименті, починаючи від системних консольних утиліт і закінчуючи програмними комплексами з можливістю управління і з застосуванням експертних систем. В області моделювання обчислювальних систем (ОС) інша справа, оскільки тут потрібні не тільки технічні знання, ай розуміння теоретичних основ процесів передачі та обробки даних, що відбуваються в обчислювальних мережах. У даній роботі представлений імітаційний підхід до моделювання ОС на базі мереж Петрі, в якому використовуються і аналітичні методи, що дозволяє оптимальним чином вирішувати широкий спектр завдань моделювання.
10 1 МОДЕЛЮВАННЯ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ
1.1 Методи моделювання мережевого трафіку
Останнім часом в мережах передачі даних (МПД) з комутацією пакетів проявляється тенденція до збільшення обсягу переданого трафіку, що призводить до необхідності ретельного планування мережевих ресурсів при побудові та експлуатації МПД. Рішення подібних завдань неможливо без побудови моделей [1], що дозволяють з мінімальними витратами проводити оцінку ефективності функціонування досліджуваної мережі.
Сучасні МПД являють собою складний комплекс елементів, що взаємодіють між собою на різних логічних рівнях. У загальному випадку модель МПД повинна включати в себе сукупність їх моделей, що функціонують в загальній мережевому середовищі. Моделі окремих елементів мережі створюються на підставі аналізу алгоритмів їх роботи, а також результатів тестових випробувань реальних пристроїв, каналів зв'язку та інших елементів мережевої інфраструктури. При комплексному підході до моделювання МПД обчислення цільових показників виробляються на підставі вихідних даних про мережевий навантаженні (трафіку), створюваної усіма споживачами мережевого ресурсу. Тому важливість адекватного моделювання мережевого трафіку складно переоцінити, тому що інформація, отримана в результаті, використовується потім в якості вихідних даних для розрахункових алгоритмів, використовуваних в загальній мережевий моделі. Таким чином, завдання створення досконалих універсальних моделей трафіку мережевих додатків є однією з ключових завдань в рамках розвитку моделювання МПД.
Методи моделювання мережевого трафіку, концептуально можна розділити на два класи - аналітичні і імітаційні. Аналітичне моделювання
11
передбачає формальний опис модельованих об'єктів і процесів у вигляді сукупності математичних рівнянь і виразів. Дані моделі зручні для проведення теоретичних досліджень і формальних маніпуляцій, однак, в більшості випадків побудова адекватної аналітичної моделі для багатьох видів мережевого трафіку є практично нездійсненним завданням.
У тому випадку, якщо моделювання ставить перед собою завдання обчислення (оцінку) робочих характеристик (параметрів), що моделюється, найкращим є використання імітаційних моделей. Імітаційні моделі являють собою набір алгоритмів (зазвичай реалізуються за допомогою програмного забезпечення), які крок за кроком відтворюють події, що відбуваються в реальній системі. Суть імітаційного моделювання трафіку полягає в створенні алгоритму (методу, який дозволив би генерувати послідовності величин схожі з послідовностями значень інтенсивності трафіку, що спостерігаються в досліджуваній МПД. На сьогоднішній день можна виділити чотири класи моделей, що застосовуються для моделювання мережевого трафіку:
- використовують класичні моделі потоків, що застосовуються в теорії масового обслуговування;
- засновані на так званих модульованих випадкових процесах;
- враховують статистичне самоподобу деяких видів трафіку
(фрактальні моделі);
- будують імітаційні послідовності за зразком трафіку [2].
Найбільш перспективними на сьогоднішній день вважаються моделі на основі узагальнених модульованих випадкових процесів (Generaly Modulated
Process - GMP) [3] і фрактальні моделі на основі хаотичних відображень
(Chaotic Map - CMAP) [4,5].
Моделі на основі узагальнених модульованих випадкових процесів. В основі GMP лежить ідея управління (модуляції) законом розподілу за допомогою допоміжного стохастичного процесу. При цьому джерело може перебувати водному з безлічі станів, які задають параметри випадкового
12
процесу генерації навантаження. Перехід між станами обумовлюється додатковим модульованим випадковим процесом.
Окремим випадком класу GMP є узагальнені процеси з детермінованою модуляцією (Generaly Modulated Deterministic Process - GMDP) і процеси з марковської модуляцією (Markov Modulated Process - MMP). У GMDP моделях джерело трафіку може бути водному з N станів. Система залишається в i-му стані протягом інтервалу часу ti, при цьому джерело генерує навантаження з інтенсивністю λi. Величини ti розподілені по геометричному закону [6]. У MMP моделях керуючий процес є марковским процесом M = {M (t)} t∞ 0 з безперервним часом і дискретною безліччю станів {0,1 ... m}. В цьому випадку для MMP, поточний закон розподілу надходження пакетів повністю визначається поточним станом k процесу M (рисунок.
Також знаходять застосування моделі (Markov Modulated Poisson
Process - MMPP), що представляють собою різновид процесів з марковської модуляцією, в яких джерело генерує пуассоновским навантаження з
інтенсивністю λk, коли допоміжний процес M знаходиться в стані k.
Важливою різновидом MMPP є MMPP-2. У MMPP-2 є всього 2 стану - одному з яких відповідає нульова інтенсивність джерела. Тобто в залежності від стану допоміжного процесу M джерело або генерує пуассоновский потік, або не діє. Рисунок 1.1 – Модель MMPP-2
13
p1, p2 - ймовірності переходу λ1 і λ2 інтенсивності пуассоновского потоку, створюваного джерелом, що знаходиться в належному стані.
Допускається нульове значення однієї з інтенсивностей
Останні дослідження мереж з комутацією пакетів говорять про статистичному самоподобу деяких видів трафіку та наявності ефекту довгострокової залежності (Long Range Dependency - LRD) [7].
Самоподібний трафік має наступні статистичні властивості, важливими з точки зору моделювання:
- розподілу часових проміжків надходження пакетів повільно зменшуються і мають т.зв. «важкі хвости»;
- розподілу часових проміжків надходження пакетів мають нескінченними моментами (починаючи з деякого порядку
- повільною швидкістю (n-1) зменшення дисперсії обчисленої на основі зразка трафіку при збільшенні довжини зразка.
Слід зазначити, що в умовах самоподібного трафіку класичні методи розрахунку параметрів комп'ютерної мережі (пропускної спроможності каналів, ємності буферів та ін.), Засновані на пуассонівських потоках, часто дають невиправдано оптимістичні рішення і призводять до недооцінки навантаження.
Фрактальні моделі. Найбільш поширеними моделями, призначеними для імітації фрактального трафіку, є
- хаотичні відображення;
- фрактальное броунівський рух (ФБД) (Fractional Brown Motion -
FBM);
- фрактальний гауссовский шум (ФГШ) (Fractional Gaussian Noise -
FGN);
- ФГШ - стаціонарний в широкому сенсі стохастичний процес X = {X
(t)} t ∞ 1 із середнім значенням μx, дисперсією σ2x і автокорреляционной функцією ρ.
- ФГШ є процесом, самоподібним у вузькому сенсі (з параметром
14
самоподібності Н.
- ФГШ з нульовим середнім використовується в якості процесу збільшень в ФБД.
- ФБД - гауссовский процес з нульовим середнім і безперервним часом
B H = {B H (t)} t∞ 0
- ФГШ і ФБД успішно використовувалися в гідрологічних дослідженнях, звідки їх застосування було перенесено в область моделювання трафіку. Складнощі їх використання в даній області обумовлені визначенням найкращих для наближення до характеристик вихідного трафіку значень параметрів μx, σ2x і H.
Найбільш поширеними і концептуально простими моделями, що дозволяють генерувати самоподібний трафік, є моделі, побудовані на так званих хаотичних відображеннях (CMAPs). Ці моделі використовують менше число параметрів, ніж ФГШ і ФБД, і їх вибір має більш наочну трактування.
Вперше використання хаотичних відображень в якості моделей трафіку було запропоновано Erramilli в 1990 році [8].
1.2 Методи аналітичного, імітаційного і натурного моделювання
Моделювання являє собою потужний метод наукового пізнання, при використанні якого досліджуваний об'єкт замінюється простішим об'єктом, званим моделлю. Основними різновидами процесу моделювання можна вважати два його види - математичне і фізичне моделювання. При фізичному натурному) моделюванні досліджувана система замінюється відповідною їй
іншою матеріальною системою, яка відтворює властивості досліджуваної системи зі збереженням їх фізичної природи. Прикладом цього виду моделювання може служити пілотна мережа, за допомогою якої вивчається принципова можливість побудови мережі на основі тих чи інших комп'ютерів, комунікаційних пристроїв, операційних систем і додатків.
Можливості фізичного моделювання досить обмежені. Воно дозволяє
15
вирішувати окремі завдання при завданні невеликої кількості поєднань досліджуваних параметрів системи. Дійсно, при натурному моделюванні обчислювальної мережі практично неможливо перевірити її роботу для варіантів з використанням різних типів комунікаційних пристроїв - маршрутизаторів, комутаторів і т.п. Перевірка на практиці близько десятка різних типів маршрутизаторів повязана не тільки з великими зусиллями і тимчасовими витратами, але і з чималими матеріальними витратами.
Але навіть і в тих випадках, коли при оптимізації мережі змінюються не типи пристроїв і операційних система тільки їх параметри, проведення експериментів в реальному масштабі часу для величезної кількості всіляких поєднань цих параметрів практично неможливо за доступне для огляду час.
Навіть проста зміна максимального розміру пакета в будь-якому протоколі вимагає переконфігуруванні операційної системи в сотнях комп'ютерів мережі, що вимагає від адміністратора мережі проведення дуже великої роботи. Тому, при оптимізації мережу багатьох випадках переважним виявляється використання математичного моделювання. Математична модель являє собою сукупність співвідношень (формул, рівнянь, нерівностей, логічних умов, що визначають процес зміни стану системи залежно від її параметрів, вхідних сигналів, початкових умов і часу.
Особливим класом математичних моделей є імітаційні моделі. Такі моделі являють собою комп'ютерну програму, яка крок за кроком відтворює події, що відбуваються в реальній системі. Стосовно до обчислювальних мереж їх імітаційні моделі відтворюють процеси генерації повідомлень додатками, розбиття повідомлень на пакети і кадри певних протоколів, затримки, пов'язані з обробкою повідомлень, пакетів і кадрів всередині операційної системи, процес отримання доступу комп'ютером до розділяється мережевому середовищі, процес обробки вступників пакетів маршрутизатором і т.д. При імітаційному моделюванні мережі не потрібно купувати дороге обладнання - його роботи імітується програмами, досить
точно відтворюють всі основні особливості і параметри такого устаткування.
Перевагою імітаційних моделей є можливість підміни процесу зміни подій в досліджуваній системі в реальному масштабі часу на прискорений процес зміни подій в темпі роботи програми. В результаті за кілька хвилин можна відтворити роботу мережі протягом декількох днів, що дає можливість оцінити роботу мережі в широкому діапазоні змінних параметрів. Результатом роботи імітаційної моделі є зібрані в ході спостереження за протікають подіями статистичні дані про найбільш важливі характеристики мережі: часах реакції, коефіцієнтах використання каналів і вузлів, ймовірності втрат пакетів і т.п.
Існують спеціальні мови імітаційного моделювання, які полегшують процес створення програмної моделі в порівнянні з використанням універсальних мов програмування. Прикладами мов імітаційного моделювання можуть служити такі мови, як SIMULA, GPSS, SIMDIS.
Існують також системи імітаційного моделювання, які орієнтуються на вузький клас досліджуваних систем і дозволяють будувати моделі без програмування.
1.3 Аналітичне моделювання на основі теорії систем масового обслуговування При аналітичному моделюванні дослідження процесів або об'єктів замінюється побудовою їх математичних моделей і дослідженням цих моделей. В основу методу покладено ідентичність форми рівнянь і однозначність співвідношень між змінними в рівняннях, що описують оригінал і модель. Оскільки події, що відбуваються в локальних обчислювальних мережах, носять випадковий характер, то для їх вивчення найбільш відповідними є імовірнісні математичні моделі теорії масового обслуговування. Об'єктами дослідження в теорії масового обслуговування є системи масового обслуговування (СМО) і мережі масового обслуговування
17
(Мемо).
Системи масового обслуговування класифікуються за такими ознаками:
- закону розподілу вхідного потоку заявок
- числу обслуговуючих приладів;
- закону розподілу часу обслуговування в обслуговуючих приладах;
- числу місць в черзі;
- дисципліни обслуговування. Для стисЛОМті запису при позначенні будь СМО прийнята система кодування A/B/C/D/E, де на місці букви ставляться відповідні характеристики СМО: А - закон розподілу інтервалів часу між надходженнями заявок. Найбільш часто використовуються наступні закони розподілу: експоненціальне (М, ерланговський (Е, гиперекспониціональне Н, гамма-розподіл (Г, детерміноване (D). Для позначення довільного характеру розподілу використовується символ G; В - закон розподілу часу обслуговування в приладах СМО. Тут прийняті такі ж позначення, як і для розподілу інтервалів між надходженнями заявок С - число обслуговуючих приладів. Тут прийняті наступні позначення: для одноканальних систем записується 1, для багатоканальних в загальному випадку - l (число каналів); D - число місць в черзі. Якщо число місць в черзі не обмежена, то дане позначення може опускатися. Для кінцевого числа місць у черзі в загальному випадку прийняті позначення r або n (число місць); Е - дисципліна обслуговування. Найбільш часто використовуються наступні варіанти дисципліни обслуговування: FIFO першим прийшов першим вийшов), LIFO (останнім прийшов - першим вийшов), RANDOM (випадковий порядок обслуговування). При дисципліни обслуговування FIFO дане позначення може опускатися.
Приклади позначень:
- ММ - СМО з одним обслуговуючим приладом, нескінченної чергою, експонентними законами розподілу інтервалів часу між
18
надходженнями заявок і часу обслуговування, дисципліною обслуговування
FIFO;
- Е/Н/l/r/ LIFO - СМО з кількома обслуговуючими приладами, кінцевою чергою, ерланговським законом розподілу інтервалів між надходженнями заявок, гиперекспониціональним розподілом часу обслуговування в приладах, дисципліною обслуговування LIFO;
- G/G/l - СМО з кількома обслуговуючими приладами, нескінченної чергою, довільними законами розподілу часу між надходженнями заявок і часу обслуговування, дисципліною обслуговування FIFO. Для моделювання ЛОМ найбільш часто використовуються наступні типи СМО:
- одноканальні СМО з очікуванням представляють собою один обслуговуючий прилад з нескінченною чергою. Дана СМО є найбільш поширеною при моделюванні. З тією або іншою часткою наближення з її допомогою можна моделювати практично будь-який вузол ЛОМ ;
- одноканальні СМО з втратами - представляють собою один обслуговуючий прилад з кінцевим числом місць у черзі. Якщо число заявок перевищує число місць в черзі, то зайві заявки втрачаються. Цей тип СМО може бути використаний при моделюванні каналів передачі в ЛОМ ;
- багатоканальні СМО з очікуванням представляють собою кілька паралельно працюючих обслуговуючих приладів із загальною нескінченної чергою. Даний тип СМО часто використовується при моделюванні груп абонентських терміналів ЛОМ , що працюють в діалоговому режимі;
- багатоканальні СМО з втратами - представляють собою кілька паралельно працюючих обслуговуючих приладів із загальною чергою, число місць в якій обмежено. Ці СМО, як і одноканальні з втратами, часто використовуються для моделювання каналів зв'язку в ЛОМ ;
- одноканальні СМО з груповим надходженням заявок представляють собою один обслуговуючий прилад з нескінченною чергою. Перед обслуговуванням заявки групуються в пакети за певним правилом
19
- одноканальні СМО з груповим обслуговуванням заявок представляють собою один обслуговуючий прилад з нескінченною чергою. Заявки обслуговуються пакетами, які складаються за певним правилом.
Останні два типи СМО можуть використовуватися для моделювання таких вузлів ЛОМ , як центри (вузли) комутації. Локальна обчислювальна мережа в цілому може бути представлена у вигляді мережі масового обслуговування. Розрізняють відкриті, замкнуті і змішані мережі.
Відкритою називають мережу масового обслуговування, що складається з М вузлів, причому хоча б в один з вузлів мережі надходить ззовні вхідний потік заявок, і є стік заявок з мережі. Для відкритих мереж характерно те, що інтенсивність надходження заявок в мережу не залежить від стану мережі, тобто від числа заявок, вже надійшли в мережу. Відкриті мережі використовуються для моделювання ЛОМ , що працюють в неоперативному режимі. Кожна заявка надходить на вхід відповідного вузла комутації, де визначається місце її обробки. Потім заявка передається на "свій" сервер або по каналу зв'язку - на "сусідній" сервер, де обробляється, після чого повертається до джерела і покидає мережу. Замкнутою називаєть мережу масового обслуговування з безліччю вузлів М без джерела і стоку, в якій циркулює постійне число заявок.
Замкнені Мемо використовуються для моделювання таких ЛОМ , джерелами
інформації для яких служать абонентські термінали, що працюють в діалоговому режимі. У цьому випадку кожна група абонентських терміналів представляється у вигляді багатоканальної системи масового обслуговування з очікуванням і включається до складу пристроїв мережі.
Розрізняють простий і складний режими роботи діалогових абонентів. У простому режимі абоненти не проводять ніяких дій, крім посилки завдань у ЛОМ і обмірковування отриманої відповіді.
Абоненти з терміналів посилають запити, які по каналах зв'язку надходять на вузли комутації, а звідти - на обробку на "свій" або "" сусідній
сервер. Подальша обробка здійснюється так само, яку відкритій мережі. При складному режимі діалогу робота абонентів представляється у вигляді сукупності операцій деякого процесу, званого технологічним процесом. Кожна операція технологічного процесу моделюється відповідної
СМО. Частина операцій передбачає звернення до ЛОМа частина операцій може такого звернення не передбачати. Алгоритм роботи самої ЛОМ такий же, як для замкнутої мережі.
Змішаної називається мережу масового обслуговування, в якій циркулює кілька різних типів заявок (трафіку), причому щодо одних типів заявок мережа замкнута, а щодо інших типів заявок мережа відкрита. За допомогою змішаних Семо моделюються такі ЛОМ , частина абонентів яких працює в діалоговому, а частина - в неоперативне режимі. Для діалогових абонентів також розрізняють простий і складний режим роботи. Часто змішані Семо моделюють ЛОМ , в яких сервер додатково завантажується завданнями, які розв'язуються на тлі роботи самої мережі. Алгоритм роботи мережі для діалогових абонентів аналогічний алгоритму роботи замкнутої мережі, а алгоритм роботи мережі для неоперативних абонентів - алгоритму роботи відкритої мережі.
Розрізняють експоненті і неекспонентні моделі ЛОМ .
Експонентні моделі засновані на припущенні про те, що потоки заявок, що надходять в ЛОМ, є пуассоновским, а час обслуговування в вузлах ЛОМ має експоненційний розподіл. Для таких мереж отримані точні методи для визначення їх характеристик трудомісткість отримання рішення залежить в основному від розмірності мережі.
Однак в більшості мереж (і локальних мереж зокрема) потоки не є пуассоновским. Моделі таких мереж називаються неекспоненціальнимі. При аналізі неекспоненціальних мереж в загальному випадку відсутні точні рішення, тому найбільше застосування тут знаходять наближені методи. Одним з таких методів є метод дифузійної апроксимації. Використання
21
дифузійної апроксимації дозволило, до теперішнього часу отримати наближені аналітичні залежності для визначення характеристик всіх типів
СМО, розглянутих вище. При цьому не потрібно точного знання функцій розподілу випадкових величин, пов'язаних з даною СМО (інтервалів між надходженнями заявок часом обслуговування в приладах), а досить лише знання першого
(математичного очікування) і другого (дисперсії або квадрата коефіцієнта варіації - ККВ) моментів цих величин.
Застосування дифузійної апроксимації при аналізі ЛОМ засноване на наступному:
- по кожному типу заявок обчислюється інтенсивність надходження заявок даного типу у вузли мережі так, як якщо б цей потік заявок циркулював в мережі тільки один
- за певним правилом, залежному від типу СМО і дисципліни обслуговування, складаються потоки заявок від усіх джерел;
- за певним правилом визначається середній час обслуговування в кожному вузлі ЛОМ ;
- отримані значення підставляються у відповідну дифузійну формулу і визначаються характеристики вузлів ЛОМ ;
- визначаються характеристики ЛОМ в цілому. Постановка завдання аналізу ЛОМ при цьому приймає наступний вигляд. Дано
- число вузлів ЛОМ ;
- тип кожного вузла ЛОМ (тип СМО, що моделює даний вузол);
- дисципліна обслуговування в кожному вузлі ЛОМ ; загальне число типів джерел заявок, що працюють в діалоговому режимі;
- загальне число типів джерел заявок, що працюють в неоперативне режимі;
- для діалогових джерел у випадку складного режиму роботи число
22
технологічних процесів кожного типу, число операцій в кожному технологічному процесі, середнє і ККВ часу виконання кожної операції, матриця ймовірностей передач між операціями, а також наявність або відсутність на кожній операції звернення до ЛОМ ; для діалогових джерел у разі простого режиму роботи число джерел (терміналів) кожного типу, середнє і ККВ часу реакції абонента на відповідь мережі; для неоперативних абонентів - середня інтенсивність надходження заявок і ККВ часу між надходженнями заявок по кожному типу заявок (діалогового і геоперативного) середня інтенсивність обслуговування в кожному вузлі ЛОМ , ККВ часу обслуговування в вузлах ЛОМ та матриця ймовірностей передач між вузлами.
Потрібно знайти: середнє значення і дисперсію (або стандартне відхилення) часу затримки заявки кожного типу в ЛОМ в цілому; середнє значення і дисперсію (або стандартне відхилення) часу затримки в вузлах ЛОМ ; завантаження вузлів ЛОМ ; ймовірність втрати заявки у вузлі ЛОМ для вузлів, що моделюються СМО з втратами).
Обмеження можуть бути наступними:
- завантаження вузлів неповинна перевищувати 1;
- ймовірність втрати заявки неповинна перевищувати 1;
- все характеристики повинні бути позитивні.
Іноді становить інтерес визначення такого показника, як максимальний час затримки заявки кожного типу в ЛОМ. Максимальний час це такий час, перевищення якого припустиме лише для деякого, наперед заданого відсотка заявок кожного типу. Для визначення загальної тривалості використовується методика, заснована на апроксимації функції розподілу часу затримки в мережі ерланговський або гиперекспониціональне розподілом, при цьому необхідно ставити частку (відсоток) заявок, для яких розраховується максимальний час.
Використовувані в даний час в локальних мережах протоколи канального рівня використовують методи доступу до середовища, засновані
на її спільне використання декількома вузлами за рахунок розділення в часі. У цьому випадку, як і у всіх випадках поділу ресурсів з випадковим потоком запитів, можуть виникати черги. Для опису цього процесу зазвичай використовуються моделі теорії масового обслуговування.
Механізм поділу середовища протоколу Ethernet спрощено описується найпростішою моделлю типу M / M / 1 - одноканальної моделлю з пуассоновским потоком заявок і показовим законом розподілу часу обслуговування. Вона добре описує процес обробки випадково вступників заявок на обслуговування системами з одним обслуговуючим приладом з випадковим часом обслуговування і буфером для зберігання вступників заявок на час, поки обслуговуючий прилад зайнятий виконанням іншого заявки (малюнок 1.2). Передає середовище Ethernet представлена в цій моделі обслуговуючим приладом, а пакети відповідають заявкам. Рисунок 1.2 – Застосування моделі теорії масового обслуговування
M/M/1 для аналізу трафіку в мережі Ethernet
24
Введемо позначення: l - інтенсивність надходження заявок, в даному випадку це середнє число пакетів, які претендують на передачу в середовищі в одиницю часу, b - середній час обслуговування заявки (без урахування часу очікування обслуговування), тобто середній час передачі пакета в середовищі з урахуванням паузи між пакетами в 9.6 мкс, r - коефіцієнт завантаження обслуговуючого приладу, в даному випадку це коефіцієнт використання середовища, r = lb. У теорії масового обслуговування для даної моделі отримані наступні результати: середній час очікування заявки в черзі (час очікування пакетом доступу до середовища) W дорівнює
W = pb/(1 – p)
1.4 Інструментальні засоби імітаційного моделювання обчислювальних мереж
Аналізатори протоколів незамінні для дослідження реальних мереж, але вони не дозволяють отримувати кількісні оцінки характеристик для ще не
існуючих мереж, що знаходяться в стадії проектування. У таких випадках можна використовувати засоби моделювання, за допомогою яких розробляються моделі, що відтворюють інформаційні процеси, що протікають в мережах.
Моделювання являє собою потужний метод наукового пізнання, при використанні якого досліджуваний об'єкт замінюється простішим.
Існують спеціальні, орієнтовані на моделювання обчислювальних мереж програмні системи, в яких процес створення моделі спрощений. Такі програмні системи самі генерують модель мережі на основі вихідних даних про її топології і використовуваних протоколах, про интенсивностях потоків запитів між комп'ютерами мережі, протяжності ліній зв'язку, про типах
25
використовуваного обладнання і додатків. Програмні системи моделювання можуть бути вузько спеціалізованими і досить універсальними, що дозволяють імітувати мережі найрізноманітніших типів. Якість результатів моделювання в значній мірі залежить від точності вихідних даних про мережі, переданих в систему імітаційного моделювання.
Програмні системи моделювання мереж - інструмент, який може стати в нагоді будь-якому адміністратору корпоративної мережі, особливо при проектуванні нової мережі або внесенні кардинальних змін в уже існуючу.
Продукти цієї категорії дозволяють перевірити наслідки впровадження тих чи інших рішень ще до оплати придбаного обладнання. Звичайно, більшість з цих програмних пакетів коштують досить дорого, але і можлива економія може бути теж вельми відчутною.
Програми імітаційного моделювання мережі використовують в своїй роботі інформацію про просторове розташування мережі, зокрема вузлів, конфігурації зв'язків, швидкостях передачі даних, що використовуються протоколах і типі обладнання, а також про виконувані в мережі додатках.
Зазвичай імітаційна модель будується не з нуля. Існують готові
імітаційні моделі основних елементів мереж найбільш поширених типів маршрутизаторів, каналів зв'язку, методів доступу, протоколів і т.п. Ці моделі окремих елементів мережі створюються на підставі різних даних: результатів тестових випробувань реальних пристроїв, аналізу принципів їх роботи, аналітичних співвідношень. В результаті створюється бібліотека типових елементів мережі, які можна налаштовувати за допомогою заздалегідь передбачених в моделях параметрів.
Системи імітаційного моделювання зазвичай включають також набір засобів для підготовки вихідних даних про досліджувану мережі - попередньої обробки даних про топологію мережі і измеренном трафіку. Ці кошти можуть бути корисні, якщо моделируемая мережа являє собою варіант
існуючої мережі і є можливість провести в ній вимірювання трафіку і інших параметрів, потрібних для моделювання. Крім того, система забезпечується
26
коштами для статистичної обробки отриманих результатів моделювання.
Yаведені характеристики декількох популярних систем імітаційного моделювання різного класу - від простих програм, призначених для установки на персональному комп'ютері, до потужних систем, що включають бібліотеки більшості наявних на ринку комунікаційних пристроїв і дозволяють в значній мірі автоматизувати дослідження досліджуваної мережі.
Сьогодні до комп'ютерних мереж як до обчислювальної платформі підприємства пред'являються все більш жорсткі вимоги надійності, швидкості та ефективності. Мережа розглядається як важливий, іноді навіть критично важливий ресурс, який повинен бути використаний максимально ефективно при мінімальних витратах. Найчастіше до основних параметрів роботи мережі відносять [9]:
- пропускну здатність (ємність);
- швидкість;
- надійність.
Високі вимоги до якості роботи мережі забезпечують інтерес до моніторингу та моделювання обчислювальних мереж. Засоби моніторингу доступні сьогодні в широкому асортименті, починаючи від системних консольних утиліт і закінчуючи програмними комплексами з можливістю управління і з застосуванням експертних систем (HP OpenView NNM,
NetView (Tivoli) від IBM, Spectrum від Cabletron). В області моделювання ВС
інша справа, оскільки тут потрібні не тільки технічні знання, ай розуміння теоретичних основ процесів передачі та обробки даних, що відбуваються в обчислювальних мережах. До групи засобів, що моделюють роботу мереж, можна віднести
ComNet від CACI Products Company, OPNET від OPNET Technologies (раніше
- MIL3), NetCracker, OMNeT ++, NS-2, NS-3 і інші (таблиця 1.2).
27
Таблиця 1.1 – Порівняльний аналіз програмних засобів моделювання ОС Продукт
COM
NET
Net
Maker
OPNet OMNeT
++
SES
/Strategizer
NS-
2
NET
Cracker
Виробник
+
+
+
+
+
+
+
Наявність бібліотеки пристроїв
+
+
+
+
+
+
+
Налаштування бібліотеки пристроїв
+
+
-
+
+
+
-
Покрокове трасування
+
-
-
+
+
+
+
Генерація звітів
+
+
-
+
+
-
+
Кожна з цих систем призначена для вирішення конкретних завдань різного ступеня абстракції. Проект COMNET позиціонувався як система моделювання ВС з розвиненими засобами візуалізації і модульною структурою, що дозволяє полегшити працю системних адміністраторів.
Серед основних підсистем COMNET можна виділити блок стохастичного моделювання, підсистему швидкого тимчасового аналізу Predictor, підсистему моніторингу Enterprise Profiler, пакет аналізу продуктивності мережі NETWORK. В даний час пакет COMNET не підтримується, компанія розвиває симуляції пакет SIMPROCESS. Система Opnet Modeler оперує вузлами трьох типів - процесорними вузлами, вузлами-маршрутизаторами і комутаторами. Вузли можуть приєднуватися за допомогою портів до комунікаційних каналах будь-якого типу, від каналів локальних мереж до супутникових ліній зв'язку. Вузли і канали можуть характеризуватися середнім часом напрацювання на відмову і
28
середнім часом відновлення для моделювання надійності мережі.
Моделюється не тільки взаємодія комп'ютерів в мережі, але і процес поділу процесора кожного комп'ютера між його додатками. Канали зв'язку моделюються шляхом завдання їх типу, а також двох параметрів -пропускной здатності і вноситься затримки поширення. Одиницею переданих по каналу даних є кадр. Пакети при передачі по каналах сегментируются на кадри.
Кожен канал характеризується мінімальним і максимальним розміром кадру, накладними витратами на кадр і інтенсивністю помилок в кадрах.
Робоче навантаження створюється джерелами трафіку. Кожен вузол може бути з'єднаний з декількома джерелами трафіку різного типу. Джерела планованої навантаження генерують дані, використовуючи залежне від часу розклад. При цьому джерело генерує дані періодично, використовуючи певний закон розподілу інтервалу часу між порціями даних. Джерела
«клієнт-сервер» дозволяють задавати не трафік між клієнтами і сервером, а додатки, які породжують цей трафік. До сильних сторін OPNET Modeler можна віднести графічні засоби побудови моделі ВС. Система дозволяє вирішувати наступні завдання: планування та оптимізація мережі; створення і перевірка аналітичних моделей мережі; створення і перевірка протоколу зв'язку. До недоліків відносяться відсутність трасування моделей і недостатня гнучкість: використовується власна, нерозширювана бібліотека пристроїв і обмежений набір звітів. З безкоштовних пакетів для задач імітаційного моделювання можна відзначити такі кошти зарубіжних розробників, як jist / swans, NS-2, NS-3,
GloMoSim, Parsec.
NS-2 (Network Simulator 2) - безкоштовний пакет, ядро якого реалізовано на мові C ++. Характерною властивістю програмного забезпечення OSS є можливість модифікації ядра програми і гнучке налаштування відповідно до вимог конкретного користувача, а також мультиплатформеність - працездатність існуючих версій для SunOS, Solaris,
29
Linux, FreeBSD, Windows 5/98 / ME / NT / 2000.
Також потрібно від користувача наявність навичок програмування на C
++ і OTcl (Object oriented Tool Command Language), який використовується в якості інтерпретатора. За рахунок використання дворівневого програмування забезпечується висока ступінь настройки моделі. Серед слабких місць пакету відзначають також складність використання OTcl, проблеми переносимості коду, обмежені можливості ефективного використання пам'яті при моделюванні, недостатня розвиненість режиму трасування і засобів збору статистики при роботі моделі, а також слабку візуалізацію.
Висока вартість, складність впровадження і інтеграції, обмежені можливості деяких існуючих програмних продуктів, в сукупності з існуючим попитом, змушує дослідників шукати нові рішення для аналізу і моделювання ВС. Один з них, досить простий і зручний у використанні, - ППП "ДІФАР". В основу його побудови покладені викладені вище положення моделювання систем і мереж масового обслуговування.
- Пакет ДІфАР призначений для аналітичного моделювання та оптимізації систем, мереж масового обслуговування та мережевих систем.
Він дозволяє розраховувати ймовірно-тимчасові характеристики СМО, Мемо і мережевих систем, задаючи в якості параметрів два моменти вхідних потоків і обслуговування, що дозволяє досліджувати поведінку систем в широкому діапазоні змін як середніх значень, так і дисперсій потоків і обслуговування, а також знайти оптимальне побудова мережевих систем за значеннями ймовірнісно-часових характеристик
(ВВХ), адекватних фактичним розподілом.
- Пакет ДІФАР забезпечує розрахунок:
- системних характеристик для одноканальних і багатоканальних систем масового обслуговування без обмежень на ємності буферних накопичувачів (середнє значення і дисперсія часу перебування, максимальний час перебування для r відсотків заявок, завантаження);
30
системних характеристик для одноканальних і багатоканальних систем масового обслуговування, які враховують обмеження на ємності буферних накопичувачів (середнє значення і дисперсія часу перебування, максимальний час перебування для r відсотків заявок, ймовірність відмови в обслуговуванні, завантаження); системних характеристик для одноканальних систем масового обслуговування з груповим надходженням заявок або груповим обслуговуванням заявок (середнє значення і дисперсія часу перебування заявки, максимальний час перебування для r відсотків заявок, завантаження); системних і мережевих характеристик відкритих неоднорідних мереж масового обслуговування з вузлами різних типів (середнє значення і дисперсія часу перебування в мережі, максимальний час перебування в мережі для r відсотків заявок, середнє значення і дисперсія часу перебування в кожному вузлі мережі, максимальний час перебування в кожному вузлі для r відсотків заявок, завантаження вузлів мережі, ймовірності відмов в обслуговуванні у вузлах);
- системних і мережевих характеристик замкнутих і змішаних неоднорідних мереж масового обслуговування з вузлами різних типів, з простим режимом роботи діалогових абонентів (середнє значення і дисперсія часу перебування в мережі заявки кожного типу, максимальний час перебування в мережі для r відсотків заявок кожного типу, середнє значення і дисперсія часу перебування в кожному вузлі мережі, завантаження вузлів мережі, ймовірності відмов в обслуговуванні у вузлах);
- системних і мережевих характеристик замкнутих і змішаних неоднорідних мереж масового обслуговування з вузлами різних типів зі складним режимом роботи діалогових абонентів (середнє значення і дисперсія часу циклу технологічного процесу роботи кожного діалогового абонента, максимальний час циклу для r відсотків технологічних процесів кожного типу, середнє значення і дисперсія часу перебування в мережі заявки кожного типу, максимальний час перебування в мережі для r відсотків
заявок кожного типу, середнє значення і дисперсія часу перебування в кожному вузлі мережі, завантаження вузлів мережі, ймовірності відмов в обслуговуванні у вузлах);
- показників ефективності мережевих систем, в якості моделей яких використовуються відкриті, замкнуті і змішані мережі масового обслуговування
(локальні обчислювальні мережі,
інформаційно- обчислювальні мережі, центри комутації пакетів і ін.). Пакет програм дозволяє проводити аналіз мережевих систем, що включають від 30 (замкнуті і змішані мережі зі складним режимом роботи діалогових абонентів) до 500 вузлів СМО (відкриті, замкнуті і змішані мережі з простим діалогом).
32 2 МОДЕЛЮВАННЯ ОБЧИСЛЮВАЛЬНИХ МЕРЕЖ НА ОСНОВІ МЕРЕЖ
ПЕТРІ
2.1 Інформаційна модель обчислювальної мережі
Будемо розглядати обчислювальну мережу, що складається з пристроїв різних типів, в якій циркулюють пакети даних. Модель обчислювальної мережі, в загальному вигляді, можна уявити в нотації RDF [7] (Рисунок 2.1). Рисунок 2.1 – Інформаційна модель мережі Тут представлені основні інформаційні об'єкти і зв'язки між ними.
Об'єкт Мережа описує реальну ВС і може включати в себе як підмережі інші об'єкти цього типу.
Об'єкт «Мережевий прилад» моделює пристрої, що входять до складу мережі. Це абстрактний об'єкт, функцією якого є обробка пакетів, тобто
33
затримка у пристрій на деякий час і можлива модифікація пакета (наприклад, зміна його типу. Кожен екземпляр об'єкта характеризується в першу чергу значенням свого параметра тип. Типами мережевого пристрою можуть бути: робочі станції, комунікаційне, периферійне устаткування, канали передачі даних. Тип визначає конкретну структуру «Мережевого приладу».
Об'єкт Блок обробки пакетів» характеризує основний елемент мережевого пристрою, відповідальний за швидкість і дисципліну обробки мережевих пакетів. Для однопроцесорних мережевих пристроїв Блок обробки» моделює роботу центрального процесора і містить дані про його потужності (в операціях в секунду. Для багатопроцесорних пристроїв кожен Блок обробки» характеризує один процесор. Для мережевих каналів передачі даних Блок обробки» є віртуальним об'єктом і характеризує швидкість передачі даних (байт (біт) / секунда.
Об'єкт Блок отримання/передачі» входять до складу «Мережевого приладу» і служить для опису входу і виходу потоку мережевого трафіку. Блок отримання/передачі для мережевих вузлів пов'язаний з їх мережевими
інтерфейсами.
Власне досліджуваний мережевий трафік описується об'єктами Тип трафіку», «Джерело трафіку», Поток трафіку» і Пакет.
Об'єкт Тип трафіку» містить інформацію про групу потоків повідомлень в мережі, що володіють загальними параметрами. До цих параметрів відносяться:
- використовувані протоколи;
- служби або програми, що створюють цей трафік (наприклад, службовий, передача відео, ftp-трафік);
- пріоритет даного типу трафіку;
- коефіцієнт затримки, пов'язаний з обслуговуванням даного типу трафіку (наприклад, sql-запити можуть обслуговуватися довше, ніж службовий трафік навіть при однаковому розмірі пакетів);
- закон розподілу, що характеризує кількість пакетів, згенерованих в
34
одиницю часу
- закон розподілу, що характеризує розмір пакетів, згенерованих в одиницю часу.
Об'єкт «Джерело трафіку» є відправною точкою декількох потоків однотипного трафіку з одного пристрою до кількох. Джерело трафіку характеризується Блоком прийому-передачі» пристрою, з яким він пов'язаний, Типом трафіку» а також моментом початку генерації повідомлень, який може здаватися статично або визначатися в момент роботи пристрою. Всі повідомлення, згенеровані «Джерелом трафіку», в загальному випадку з різною ймовірністю надходять до декільком адресатам (якщо адресат один, то і ймовірність надходження кожного повідомлення до нього відповідно дорівнює 1).
Об'єкт Поток трафіку» служить для загального опису всіх повідомлень, згенерованих одним «Джерелом трафіку» і спрямованих до одного Блоку прийому-передачі» вузла по одному маршруту, тобто через деяку однозначно визначену в певний момент часу послідовність
«Мережевих пристроїв».
Об'єкт Пакет описує один мережевий пакет потоку. Деталізація до цього рівня необхідна тільки при імітаційному моделюванні, оскільки її запуск пов'язаний з відстеженням шляху кожного пакета. В результаті формується статистика по трафіку в цілому.
2.2 Математична модель ОС на основі МП Для моделювання використовуються ієрархічні розфарбовані МП з тимчасовим механізмом [4, 6], де колір (тип міток) відповідає типу трафіку.
Мітки можуть бути двох типів - «повідомлення» і «службові маркери», які означають факт зайнятості ресурсу обробкою меток- «повідомлень».
Кількість міток в позиціях відповідає стану мережі, переходи змінюють цей стан, переміщаючи мітки в інші позиції.
Час в моделі приймається дискретним і вимірюється тактами.
Протягом одного такту мітка може зробити не більше одного переміщення через дозволений перехід. У класичних МП без тимчасових затримок один такт відповідає спрацьовування одного (будь-якого) дозволеного переходу. Але оскільки МП цінні саме для моделювання паралельних систем, в більшості інтерпретацій і розширень МП такт розуміється ширше - як проміжок, протягом якого спрацьовують всі дозволені в початковому стані переходи. Кожен мережевий об'єкт (робоча станція, канал передачі, комунікаційний пристрій) моделюється як підмережа
Петрі.
2.2.1 Основні визначення
Теоретико-множинне визначення МП можна представити в наступному вигляді [4, 6]:
1 2 3
скачати
Міністерство освіти і науки України
Харківський національний університет радіоелектроніки Факультет комп’ютерної інженерії та управління
(повна назва) Кафедра електронних обчислювальних машин
(повна назва)
АТЕСТАЦІЙНА РОБОТА Пояс нюв а льна записка
Рівень вищої освіти другий (магістерський)
Моделі представлення елементів систем масового обслуговування з міжагентним інформаційним обміном тема)
Виконав: студент
II курсу, групи
КСМм-19-1
Базильський А.А.
(прізвище, ініціали)
Спеціальність
123 – Комп’ютерна інженерія код і повна назва спеціальності) Тип програми освітньо-професійна
(освітньо-професійна або освітньо-наукова)
Освітня програма
Комп’ютерні системи та мережі
(повна назва освітньої програми)
Керівник: доц. Янковський О.А. посада, прізвище, ініціали)
Допускається до захисту Зав. кафедри ЕОМ
Коваленко А.А.
(підпис)
(прізвище, ініціали)
2020 р.
Харківський національний університет радіоелектроніки
ЗАТВЕРДЖУЮ: Зав. кафедри
(підпис)
“”
20 р.
ЗАВДАННЯ НА АТЕСТАЦІЙНУ РОБОТУ студентові
Базильському Антону Андрійовичу
(прізвище, ім’я, по батькові)
1. Тема роботи Моделі представлення елементів систем масового обслуговування з міжагентним інформаційним обміном затверджена наказом по університету від “ 30 ” жовтня
2020 р. № 1487 Ст
2. Термін подання студентом роботи до екзаменаційної комісії
14 грудня 2020 р. Вхідні дані до роботи мережі Петрі використання статистики UDP
СМО
4. Перелік питань, що потрібно опрацювати в роботі
Методи аналітичного, імітаційного та натурного моделювання
Моделювання обчислювальних мереж на основі мереж Петрі Синтез моделі Факультет комп’ютерної інженерії та управління Кафедра електронних обчислювальних машин
Рівень вищої освіти другий (магістерський)
Спеціальність
123 – Комп’ютерна інженерія код і повна назва) Тип програми освітньо-професійна
(освітньо-професійна або освітньо-наукова)
Освітня програма
Комп’ютерні системи та мережі
(повна назва)
5. Перелік графічного матеріалу із зазначенням креслеників, схем, плакатів, комп’ютерних
ілюстрацій (слайдів) арк. ф. А 6. Консультанти розділів роботи (заповнюється за наявності консультантів згідно з наказом, зазначеним у п )
Найменування розділу Консультант посада, прізвище, ім’я, по батькові)
Позначка консультанта про виконання розділу підпис дата
КАЛЕНДАРНИЙ ПЛАН
№
Назва етапів роботи
Термін виконання етапів роботи
Примітка
1
Аналіз завдання
06.11.2020-12.11.2020 2
Аналіз науково-технічної літератури
13.11.2020-23.11.2020 3
Вивчення концепції імітаційного моделювання 24.11.2020-01.12.2020 4
Розробка моделі
02.12.2020-05.12.2020 5
Оформлення пояснювальної записки
06.12.2020-10.12.2020 6
Оформлення графічної частини
11.12.2020-12.12.2020 7
Представлення роботи науковому керівнику
13.12.2020-14.12.2020 Дата видачі завдання 3 листопада 2020 р. Студент
(підпис)
Керівник роботи доц. Янковський О.А.
(підпис) посада, прізвище, ініціали)
РЕФЕРАТ
Пояснювальна записка атестаційної роботи: 67 с, 10 рис, 6 табл, 1 дод., 15 джерел. СИСТЕМА МАСОВОГО ОБСЛУГОВУВАННЯ, МЕРЕЖА ПЕТРІ,
ОБЧИСЛЮВАЛЬНА СИСТЕМА,
ІМІТАЦІЙНА МОДЕЛЬ,
ІНФОРМАЦІЙНИЙ ОБМІН.
Метою атестаційної роботи є аналіз моделей представлення елементів систем масового обслуговування з використанням мереж Петрі. У роботі запропоновано механізм побудови мереж Петрі для основних об'єктів обчислювальних систем, формалізовані функції мережевих об'єктів у вигляді примітивних функціоналів з використанням мереж Петрі. Запропоновані операції над мережами Петрі, що дозволяють легко конструювати модель обчислювальної системи. Для демонстрації побудованої моделі, наведено приклад побудови мережі Петрі для фрагмента локальної мережі, розглянуті питання маршрутизації в імітаційній моделі, запропонований узагальнений алгоритм роботи імітаційної моделі.
ABSTRACT
Master’s thesis: 67 pages, 10 figures, 6 tables, 2 appendices, 15 sources.
CUSTOM SERVICE SYSTEM, PETRI NETWORK, COMPUTER
SYSTEM, SIMULATION MODEL, INFORMATION EXCHANGE.
The purpose of the certification work is to analyze the models of representation of elements of queuing systems using Petri nets. The mechanism of construction of Petri nets for the basic objects of computer systems is offered in the work, functions of network objects in the form of primitive functionals with use of
Petri nets are formalized. Operations on Petri nets are offered, which allow to easily construct a model of a computer system. To demonstrate the constructed model, an example of constructing a Petri net for a fragment of a local network is given, routing issues in a simulation model are considered, a generalized algorithm of simulation model operation is proposed.
ЗМІСТ
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ, СИМВОЛІВ, ОДИНИЦЬ,
СКОРОЧЕНЬ І ТЕРМІНІВ ..................................................................................... ВСТУП ..................................................................................................................... 9 1 МОДЕЛЮВАННЯ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ ................................... 10 1.1 Методи моделювання мережевого трафіку .............................................. 10 1.2 Методи аналітичного, імітаційного і натурного моделювання ............. 14 1.3 Аналітичне моделювання на основі теорії систем масового обслуговування .................................................................................................. 16 1.4
Інструментальні засоби
імітаційного моделювання обчислювальних мереж .................................................................................... 24 2 МОДЕЛЮВАННЯ ОБЧИСЛЮВАЛЬНИХ МЕРЕЖ НА ОСНОВІ МЕРЕЖ ПЕТРІ ...................................................................................................... 32 2.1 Інформаційна модель обчислювальної мережі ........................................ 32 2.2 Математична модель ОС на основі МП .................................................... 34 2.2.1 Основні визначення ............................................................................... 35 2.2.2 Подання основних пристроїв мережі ................................................... 37 2.3 Приклади побудови мереж Петрі для різних ОС ..................................... 41 2.3.1 МП для робочої станції з одним мережевим інтерфейсом ................ 41 2.3.2 МП для вузла-концентратора ................................................................ 42 2.3.3 МП для вузол - міст ............................................................................... 43 2.3.4 МП для вузол - маршрутизатора .......................................................... 43 2.3.5 МП для полудуплексного каналу з втратами ...................................... 45 2.3.6 МП для дуплексного каналу з втратами .............................................. 47 3 СИНТЕЗ МОДЕЛІ І МОДЕЛЮВАННЯ ЇЇ РОБОТИ ..................................... 49 3.1 Алгоритм роботи побудованої моделі на основі МП .............................. 49 3.2 Загальні принципи застосування моделі .................................................. 50 3.3 Апробація моделі ........................................................................................ 53
ВИСНОВКИ ........................................................................................................... 58
ПЕРЕЛІК ДЖЕРЕЛ ПОСИЛАННЯ .................................................................... 59
ДОДАТОК А .......................................................................................................... 61
Графічний матеріал атестаційної роботи ............................................................ 61
8
ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ, СИМВОЛІВ, ОДИНИЦЬ, СКОРОЧЕНЬ І ТЕРМІНІВ
GMP – узагальнені модульовані випадкові процеси
MMP – пуассоновский процес з марковської модуляцією
MMP –процес з марковської модуляцією ЛОМ – локальна обчислювальна мережа
МПД – мережа передачі даних
МП – мережа Петрі ОС – обчислювальна система
СМО – системи масового обслуговування
Однією з актуальних важко вирішуваних ззадач є завдання моделювання комп'ютерних мереж. Це завдання включає в себе тестування різних мережевих компонентів, визначення найкращої топології проектованих комп'ютерних мереж, проведення досліджень в області мережевих технологій і т.і.
Сьогодні до комп'ютерних мереж як до обчислювальної платформи підприємства пред'являються все більш жорсткі вимоги надійності, швидкості та ефективності. Мережа розглядається як важливий, іноді навіть критично важливий ресурс, який повинен бути використаний максимально ефективно при мінімальних витратах. Високі вимоги до якості роботи мережі забезпечують інтерес до моніторингу та моделювання обчислювальних мереж. Засоби моніторингу доступні сьогодні в широкому асортименті, починаючи від системних консольних утиліт і закінчуючи програмними комплексами з можливістю управління і з застосуванням експертних систем. В області моделювання обчислювальних систем (ОС) інша справа, оскільки тут потрібні не тільки технічні знання, ай розуміння теоретичних основ процесів передачі та обробки даних, що відбуваються в обчислювальних мережах. У даній роботі представлений імітаційний підхід до моделювання ОС на базі мереж Петрі, в якому використовуються і аналітичні методи, що дозволяє оптимальним чином вирішувати широкий спектр завдань моделювання.
10 1 МОДЕЛЮВАННЯ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ
1.1 Методи моделювання мережевого трафіку
Останнім часом в мережах передачі даних (МПД) з комутацією пакетів проявляється тенденція до збільшення обсягу переданого трафіку, що призводить до необхідності ретельного планування мережевих ресурсів при побудові та експлуатації МПД. Рішення подібних завдань неможливо без побудови моделей [1], що дозволяють з мінімальними витратами проводити оцінку ефективності функціонування досліджуваної мережі.
Сучасні МПД являють собою складний комплекс елементів, що взаємодіють між собою на різних логічних рівнях. У загальному випадку модель МПД повинна включати в себе сукупність їх моделей, що функціонують в загальній мережевому середовищі. Моделі окремих елементів мережі створюються на підставі аналізу алгоритмів їх роботи, а також результатів тестових випробувань реальних пристроїв, каналів зв'язку та інших елементів мережевої інфраструктури. При комплексному підході до моделювання МПД обчислення цільових показників виробляються на підставі вихідних даних про мережевий навантаженні (трафіку), створюваної усіма споживачами мережевого ресурсу. Тому важливість адекватного моделювання мережевого трафіку складно переоцінити, тому що інформація, отримана в результаті, використовується потім в якості вихідних даних для розрахункових алгоритмів, використовуваних в загальній мережевий моделі. Таким чином, завдання створення досконалих універсальних моделей трафіку мережевих додатків є однією з ключових завдань в рамках розвитку моделювання МПД.
Методи моделювання мережевого трафіку, концептуально можна розділити на два класи - аналітичні і імітаційні. Аналітичне моделювання
11
передбачає формальний опис модельованих об'єктів і процесів у вигляді сукупності математичних рівнянь і виразів. Дані моделі зручні для проведення теоретичних досліджень і формальних маніпуляцій, однак, в більшості випадків побудова адекватної аналітичної моделі для багатьох видів мережевого трафіку є практично нездійсненним завданням.
У тому випадку, якщо моделювання ставить перед собою завдання обчислення (оцінку) робочих характеристик (параметрів), що моделюється, найкращим є використання імітаційних моделей. Імітаційні моделі являють собою набір алгоритмів (зазвичай реалізуються за допомогою програмного забезпечення), які крок за кроком відтворюють події, що відбуваються в реальній системі. Суть імітаційного моделювання трафіку полягає в створенні алгоритму (методу, який дозволив би генерувати послідовності величин схожі з послідовностями значень інтенсивності трафіку, що спостерігаються в досліджуваній МПД. На сьогоднішній день можна виділити чотири класи моделей, що застосовуються для моделювання мережевого трафіку:
- використовують класичні моделі потоків, що застосовуються в теорії масового обслуговування;
- засновані на так званих модульованих випадкових процесах;
- враховують статистичне самоподобу деяких видів трафіку
(фрактальні моделі);
- будують імітаційні послідовності за зразком трафіку [2].
Найбільш перспективними на сьогоднішній день вважаються моделі на основі узагальнених модульованих випадкових процесів (Generaly Modulated
Process - GMP) [3] і фрактальні моделі на основі хаотичних відображень
(Chaotic Map - CMAP) [4,5].
Моделі на основі узагальнених модульованих випадкових процесів. В основі GMP лежить ідея управління (модуляції) законом розподілу за допомогою допоміжного стохастичного процесу. При цьому джерело може перебувати водному з безлічі станів, які задають параметри випадкового
12
процесу генерації навантаження. Перехід між станами обумовлюється додатковим модульованим випадковим процесом.
Окремим випадком класу GMP є узагальнені процеси з детермінованою модуляцією (Generaly Modulated Deterministic Process - GMDP) і процеси з марковської модуляцією (Markov Modulated Process - MMP). У GMDP моделях джерело трафіку може бути водному з N станів. Система залишається в i-му стані протягом інтервалу часу ti, при цьому джерело генерує навантаження з інтенсивністю λi. Величини ti розподілені по геометричному закону [6]. У MMP моделях керуючий процес є марковским процесом M = {M (t)} t∞ 0 з безперервним часом і дискретною безліччю станів {0,1 ... m}. В цьому випадку для MMP, поточний закон розподілу надходження пакетів повністю визначається поточним станом k процесу M (рисунок.
Також знаходять застосування моделі (Markov Modulated Poisson
Process - MMPP), що представляють собою різновид процесів з марковської модуляцією, в яких джерело генерує пуассоновским навантаження з
інтенсивністю λk, коли допоміжний процес M знаходиться в стані k.
Важливою різновидом MMPP є MMPP-2. У MMPP-2 є всього 2 стану - одному з яких відповідає нульова інтенсивність джерела. Тобто в залежності від стану допоміжного процесу M джерело або генерує пуассоновский потік, або не діє. Рисунок 1.1 – Модель MMPP-2
13
p1, p2 - ймовірності переходу λ1 і λ2 інтенсивності пуассоновского потоку, створюваного джерелом, що знаходиться в належному стані.
Допускається нульове значення однієї з інтенсивностей
Останні дослідження мереж з комутацією пакетів говорять про статистичному самоподобу деяких видів трафіку та наявності ефекту довгострокової залежності (Long Range Dependency - LRD) [7].
Самоподібний трафік має наступні статистичні властивості, важливими з точки зору моделювання:
- розподілу часових проміжків надходження пакетів повільно зменшуються і мають т.зв. «важкі хвости»;
- розподілу часових проміжків надходження пакетів мають нескінченними моментами (починаючи з деякого порядку
- повільною швидкістю (n-1) зменшення дисперсії обчисленої на основі зразка трафіку при збільшенні довжини зразка.
Слід зазначити, що в умовах самоподібного трафіку класичні методи розрахунку параметрів комп'ютерної мережі (пропускної спроможності каналів, ємності буферів та ін.), Засновані на пуассонівських потоках, часто дають невиправдано оптимістичні рішення і призводять до недооцінки навантаження.
Фрактальні моделі. Найбільш поширеними моделями, призначеними для імітації фрактального трафіку, є
- хаотичні відображення;
- фрактальное броунівський рух (ФБД) (Fractional Brown Motion -
FBM);
- фрактальний гауссовский шум (ФГШ) (Fractional Gaussian Noise -
FGN);
- ФГШ - стаціонарний в широкому сенсі стохастичний процес X = {X
(t)} t ∞ 1 із середнім значенням μx, дисперсією σ2x і автокорреляционной функцією ρ.
- ФГШ є процесом, самоподібним у вузькому сенсі (з параметром
14
самоподібності Н.
- ФГШ з нульовим середнім використовується в якості процесу збільшень в ФБД.
- ФБД - гауссовский процес з нульовим середнім і безперервним часом
B H = {B H (t)} t∞ 0
- ФГШ і ФБД успішно використовувалися в гідрологічних дослідженнях, звідки їх застосування було перенесено в область моделювання трафіку. Складнощі їх використання в даній області обумовлені визначенням найкращих для наближення до характеристик вихідного трафіку значень параметрів μx, σ2x і H.
Найбільш поширеними і концептуально простими моделями, що дозволяють генерувати самоподібний трафік, є моделі, побудовані на так званих хаотичних відображеннях (CMAPs). Ці моделі використовують менше число параметрів, ніж ФГШ і ФБД, і їх вибір має більш наочну трактування.
Вперше використання хаотичних відображень в якості моделей трафіку було запропоновано Erramilli в 1990 році [8].
1.2 Методи аналітичного, імітаційного і натурного моделювання
Моделювання являє собою потужний метод наукового пізнання, при використанні якого досліджуваний об'єкт замінюється простішим об'єктом, званим моделлю. Основними різновидами процесу моделювання можна вважати два його види - математичне і фізичне моделювання. При фізичному натурному) моделюванні досліджувана система замінюється відповідною їй
іншою матеріальною системою, яка відтворює властивості досліджуваної системи зі збереженням їх фізичної природи. Прикладом цього виду моделювання може служити пілотна мережа, за допомогою якої вивчається принципова можливість побудови мережі на основі тих чи інших комп'ютерів, комунікаційних пристроїв, операційних систем і додатків.
Можливості фізичного моделювання досить обмежені. Воно дозволяє
15
вирішувати окремі завдання при завданні невеликої кількості поєднань досліджуваних параметрів системи. Дійсно, при натурному моделюванні обчислювальної мережі практично неможливо перевірити її роботу для варіантів з використанням різних типів комунікаційних пристроїв - маршрутизаторів, комутаторів і т.п. Перевірка на практиці близько десятка різних типів маршрутизаторів повязана не тільки з великими зусиллями і тимчасовими витратами, але і з чималими матеріальними витратами.
Але навіть і в тих випадках, коли при оптимізації мережі змінюються не типи пристроїв і операційних система тільки їх параметри, проведення експериментів в реальному масштабі часу для величезної кількості всіляких поєднань цих параметрів практично неможливо за доступне для огляду час.
Навіть проста зміна максимального розміру пакета в будь-якому протоколі вимагає переконфігуруванні операційної системи в сотнях комп'ютерів мережі, що вимагає від адміністратора мережі проведення дуже великої роботи. Тому, при оптимізації мережу багатьох випадках переважним виявляється використання математичного моделювання. Математична модель являє собою сукупність співвідношень (формул, рівнянь, нерівностей, логічних умов, що визначають процес зміни стану системи залежно від її параметрів, вхідних сигналів, початкових умов і часу.
Особливим класом математичних моделей є імітаційні моделі. Такі моделі являють собою комп'ютерну програму, яка крок за кроком відтворює події, що відбуваються в реальній системі. Стосовно до обчислювальних мереж їх імітаційні моделі відтворюють процеси генерації повідомлень додатками, розбиття повідомлень на пакети і кадри певних протоколів, затримки, пов'язані з обробкою повідомлень, пакетів і кадрів всередині операційної системи, процес отримання доступу комп'ютером до розділяється мережевому середовищі, процес обробки вступників пакетів маршрутизатором і т.д. При імітаційному моделюванні мережі не потрібно купувати дороге обладнання - його роботи імітується програмами, досить
Перевагою імітаційних моделей є можливість підміни процесу зміни подій в досліджуваній системі в реальному масштабі часу на прискорений процес зміни подій в темпі роботи програми. В результаті за кілька хвилин можна відтворити роботу мережі протягом декількох днів, що дає можливість оцінити роботу мережі в широкому діапазоні змінних параметрів. Результатом роботи імітаційної моделі є зібрані в ході спостереження за протікають подіями статистичні дані про найбільш важливі характеристики мережі: часах реакції, коефіцієнтах використання каналів і вузлів, ймовірності втрат пакетів і т.п.
Існують спеціальні мови імітаційного моделювання, які полегшують процес створення програмної моделі в порівнянні з використанням універсальних мов програмування. Прикладами мов імітаційного моделювання можуть служити такі мови, як SIMULA, GPSS, SIMDIS.
Існують також системи імітаційного моделювання, які орієнтуються на вузький клас досліджуваних систем і дозволяють будувати моделі без програмування.
1.3 Аналітичне моделювання на основі теорії систем масового обслуговування При аналітичному моделюванні дослідження процесів або об'єктів замінюється побудовою їх математичних моделей і дослідженням цих моделей. В основу методу покладено ідентичність форми рівнянь і однозначність співвідношень між змінними в рівняннях, що описують оригінал і модель. Оскільки події, що відбуваються в локальних обчислювальних мережах, носять випадковий характер, то для їх вивчення найбільш відповідними є імовірнісні математичні моделі теорії масового обслуговування. Об'єктами дослідження в теорії масового обслуговування є системи масового обслуговування (СМО) і мережі масового обслуговування
17
(Мемо).
Системи масового обслуговування класифікуються за такими ознаками:
- закону розподілу вхідного потоку заявок
- числу обслуговуючих приладів;
- закону розподілу часу обслуговування в обслуговуючих приладах;
- числу місць в черзі;
- дисципліни обслуговування. Для стисЛОМті запису при позначенні будь СМО прийнята система кодування A/B/C/D/E, де на місці букви ставляться відповідні характеристики СМО: А - закон розподілу інтервалів часу між надходженнями заявок. Найбільш часто використовуються наступні закони розподілу: експоненціальне (М, ерланговський (Е, гиперекспониціональне Н, гамма-розподіл (Г, детерміноване (D). Для позначення довільного характеру розподілу використовується символ G; В - закон розподілу часу обслуговування в приладах СМО. Тут прийняті такі ж позначення, як і для розподілу інтервалів між надходженнями заявок С - число обслуговуючих приладів. Тут прийняті наступні позначення: для одноканальних систем записується 1, для багатоканальних в загальному випадку - l (число каналів); D - число місць в черзі. Якщо число місць в черзі не обмежена, то дане позначення може опускатися. Для кінцевого числа місць у черзі в загальному випадку прийняті позначення r або n (число місць); Е - дисципліна обслуговування. Найбільш часто використовуються наступні варіанти дисципліни обслуговування: FIFO першим прийшов першим вийшов), LIFO (останнім прийшов - першим вийшов), RANDOM (випадковий порядок обслуговування). При дисципліни обслуговування FIFO дане позначення може опускатися.
Приклади позначень:
- ММ - СМО з одним обслуговуючим приладом, нескінченної чергою, експонентними законами розподілу інтервалів часу між
18
надходженнями заявок і часу обслуговування, дисципліною обслуговування
FIFO;
- Е/Н/l/r/ LIFO - СМО з кількома обслуговуючими приладами, кінцевою чергою, ерланговським законом розподілу інтервалів між надходженнями заявок, гиперекспониціональним розподілом часу обслуговування в приладах, дисципліною обслуговування LIFO;
- G/G/l - СМО з кількома обслуговуючими приладами, нескінченної чергою, довільними законами розподілу часу між надходженнями заявок і часу обслуговування, дисципліною обслуговування FIFO. Для моделювання ЛОМ найбільш часто використовуються наступні типи СМО:
- одноканальні СМО з очікуванням представляють собою один обслуговуючий прилад з нескінченною чергою. Дана СМО є найбільш поширеною при моделюванні. З тією або іншою часткою наближення з її допомогою можна моделювати практично будь-який вузол ЛОМ ;
- одноканальні СМО з втратами - представляють собою один обслуговуючий прилад з кінцевим числом місць у черзі. Якщо число заявок перевищує число місць в черзі, то зайві заявки втрачаються. Цей тип СМО може бути використаний при моделюванні каналів передачі в ЛОМ ;
- багатоканальні СМО з очікуванням представляють собою кілька паралельно працюючих обслуговуючих приладів із загальною нескінченної чергою. Даний тип СМО часто використовується при моделюванні груп абонентських терміналів ЛОМ , що працюють в діалоговому режимі;
- багатоканальні СМО з втратами - представляють собою кілька паралельно працюючих обслуговуючих приладів із загальною чергою, число місць в якій обмежено. Ці СМО, як і одноканальні з втратами, часто використовуються для моделювання каналів зв'язку в ЛОМ ;
- одноканальні СМО з груповим надходженням заявок представляють собою один обслуговуючий прилад з нескінченною чергою. Перед обслуговуванням заявки групуються в пакети за певним правилом
19
- одноканальні СМО з груповим обслуговуванням заявок представляють собою один обслуговуючий прилад з нескінченною чергою. Заявки обслуговуються пакетами, які складаються за певним правилом.
Останні два типи СМО можуть використовуватися для моделювання таких вузлів ЛОМ , як центри (вузли) комутації. Локальна обчислювальна мережа в цілому може бути представлена у вигляді мережі масового обслуговування. Розрізняють відкриті, замкнуті і змішані мережі.
Відкритою називають мережу масового обслуговування, що складається з М вузлів, причому хоча б в один з вузлів мережі надходить ззовні вхідний потік заявок, і є стік заявок з мережі. Для відкритих мереж характерно те, що інтенсивність надходження заявок в мережу не залежить від стану мережі, тобто від числа заявок, вже надійшли в мережу. Відкриті мережі використовуються для моделювання ЛОМ , що працюють в неоперативному режимі. Кожна заявка надходить на вхід відповідного вузла комутації, де визначається місце її обробки. Потім заявка передається на "свій" сервер або по каналу зв'язку - на "сусідній" сервер, де обробляється, після чого повертається до джерела і покидає мережу. Замкнутою називаєть мережу масового обслуговування з безліччю вузлів М без джерела і стоку, в якій циркулює постійне число заявок.
Замкнені Мемо використовуються для моделювання таких ЛОМ , джерелами
інформації для яких служать абонентські термінали, що працюють в діалоговому режимі. У цьому випадку кожна група абонентських терміналів представляється у вигляді багатоканальної системи масового обслуговування з очікуванням і включається до складу пристроїв мережі.
Розрізняють простий і складний режими роботи діалогових абонентів. У простому режимі абоненти не проводять ніяких дій, крім посилки завдань у ЛОМ і обмірковування отриманої відповіді.
Абоненти з терміналів посилають запити, які по каналах зв'язку надходять на вузли комутації, а звідти - на обробку на "свій" або "" сусідній
СМО. Частина операцій передбачає звернення до ЛОМа частина операцій може такого звернення не передбачати. Алгоритм роботи самої ЛОМ такий же, як для замкнутої мережі.
Змішаної називається мережу масового обслуговування, в якій циркулює кілька різних типів заявок (трафіку), причому щодо одних типів заявок мережа замкнута, а щодо інших типів заявок мережа відкрита. За допомогою змішаних Семо моделюються такі ЛОМ , частина абонентів яких працює в діалоговому, а частина - в неоперативне режимі. Для діалогових абонентів також розрізняють простий і складний режим роботи. Часто змішані Семо моделюють ЛОМ , в яких сервер додатково завантажується завданнями, які розв'язуються на тлі роботи самої мережі. Алгоритм роботи мережі для діалогових абонентів аналогічний алгоритму роботи замкнутої мережі, а алгоритм роботи мережі для неоперативних абонентів - алгоритму роботи відкритої мережі.
Розрізняють експоненті і неекспонентні моделі ЛОМ .
Експонентні моделі засновані на припущенні про те, що потоки заявок, що надходять в ЛОМ, є пуассоновским, а час обслуговування в вузлах ЛОМ має експоненційний розподіл. Для таких мереж отримані точні методи для визначення їх характеристик трудомісткість отримання рішення залежить в основному від розмірності мережі.
Однак в більшості мереж (і локальних мереж зокрема) потоки не є пуассоновским. Моделі таких мереж називаються неекспоненціальнимі. При аналізі неекспоненціальних мереж в загальному випадку відсутні точні рішення, тому найбільше застосування тут знаходять наближені методи. Одним з таких методів є метод дифузійної апроксимації. Використання
21
дифузійної апроксимації дозволило, до теперішнього часу отримати наближені аналітичні залежності для визначення характеристик всіх типів
СМО, розглянутих вище. При цьому не потрібно точного знання функцій розподілу випадкових величин, пов'язаних з даною СМО (інтервалів між надходженнями заявок часом обслуговування в приладах), а досить лише знання першого
(математичного очікування) і другого (дисперсії або квадрата коефіцієнта варіації - ККВ) моментів цих величин.
Застосування дифузійної апроксимації при аналізі ЛОМ засноване на наступному:
- по кожному типу заявок обчислюється інтенсивність надходження заявок даного типу у вузли мережі так, як якщо б цей потік заявок циркулював в мережі тільки один
- за певним правилом, залежному від типу СМО і дисципліни обслуговування, складаються потоки заявок від усіх джерел;
- за певним правилом визначається середній час обслуговування в кожному вузлі ЛОМ ;
- отримані значення підставляються у відповідну дифузійну формулу і визначаються характеристики вузлів ЛОМ ;
- визначаються характеристики ЛОМ в цілому. Постановка завдання аналізу ЛОМ при цьому приймає наступний вигляд. Дано
- число вузлів ЛОМ ;
- тип кожного вузла ЛОМ (тип СМО, що моделює даний вузол);
- дисципліна обслуговування в кожному вузлі ЛОМ ; загальне число типів джерел заявок, що працюють в діалоговому режимі;
- загальне число типів джерел заявок, що працюють в неоперативне режимі;
- для діалогових джерел у випадку складного режиму роботи число
22
технологічних процесів кожного типу, число операцій в кожному технологічному процесі, середнє і ККВ часу виконання кожної операції, матриця ймовірностей передач між операціями, а також наявність або відсутність на кожній операції звернення до ЛОМ ; для діалогових джерел у разі простого режиму роботи число джерел (терміналів) кожного типу, середнє і ККВ часу реакції абонента на відповідь мережі; для неоперативних абонентів - середня інтенсивність надходження заявок і ККВ часу між надходженнями заявок по кожному типу заявок (діалогового і геоперативного) середня інтенсивність обслуговування в кожному вузлі ЛОМ , ККВ часу обслуговування в вузлах ЛОМ та матриця ймовірностей передач між вузлами.
Потрібно знайти: середнє значення і дисперсію (або стандартне відхилення) часу затримки заявки кожного типу в ЛОМ в цілому; середнє значення і дисперсію (або стандартне відхилення) часу затримки в вузлах ЛОМ ; завантаження вузлів ЛОМ ; ймовірність втрати заявки у вузлі ЛОМ для вузлів, що моделюються СМО з втратами).
Обмеження можуть бути наступними:
- завантаження вузлів неповинна перевищувати 1;
- ймовірність втрати заявки неповинна перевищувати 1;
- все характеристики повинні бути позитивні.
Іноді становить інтерес визначення такого показника, як максимальний час затримки заявки кожного типу в ЛОМ. Максимальний час це такий час, перевищення якого припустиме лише для деякого, наперед заданого відсотка заявок кожного типу. Для визначення загальної тривалості використовується методика, заснована на апроксимації функції розподілу часу затримки в мережі ерланговський або гиперекспониціональне розподілом, при цьому необхідно ставити частку (відсоток) заявок, для яких розраховується максимальний час.
Використовувані в даний час в локальних мережах протоколи канального рівня використовують методи доступу до середовища, засновані
Механізм поділу середовища протоколу Ethernet спрощено описується найпростішою моделлю типу M / M / 1 - одноканальної моделлю з пуассоновским потоком заявок і показовим законом розподілу часу обслуговування. Вона добре описує процес обробки випадково вступників заявок на обслуговування системами з одним обслуговуючим приладом з випадковим часом обслуговування і буфером для зберігання вступників заявок на час, поки обслуговуючий прилад зайнятий виконанням іншого заявки (малюнок 1.2). Передає середовище Ethernet представлена в цій моделі обслуговуючим приладом, а пакети відповідають заявкам. Рисунок 1.2 – Застосування моделі теорії масового обслуговування
M/M/1 для аналізу трафіку в мережі Ethernet
24
Введемо позначення: l - інтенсивність надходження заявок, в даному випадку це середнє число пакетів, які претендують на передачу в середовищі в одиницю часу, b - середній час обслуговування заявки (без урахування часу очікування обслуговування), тобто середній час передачі пакета в середовищі з урахуванням паузи між пакетами в 9.6 мкс, r - коефіцієнт завантаження обслуговуючого приладу, в даному випадку це коефіцієнт використання середовища, r = lb. У теорії масового обслуговування для даної моделі отримані наступні результати: середній час очікування заявки в черзі (час очікування пакетом доступу до середовища) W дорівнює
W = pb/(1 – p)
1.4 Інструментальні засоби імітаційного моделювання обчислювальних мереж
Аналізатори протоколів незамінні для дослідження реальних мереж, але вони не дозволяють отримувати кількісні оцінки характеристик для ще не
існуючих мереж, що знаходяться в стадії проектування. У таких випадках можна використовувати засоби моделювання, за допомогою яких розробляються моделі, що відтворюють інформаційні процеси, що протікають в мережах.
Моделювання являє собою потужний метод наукового пізнання, при використанні якого досліджуваний об'єкт замінюється простішим.
Існують спеціальні, орієнтовані на моделювання обчислювальних мереж програмні системи, в яких процес створення моделі спрощений. Такі програмні системи самі генерують модель мережі на основі вихідних даних про її топології і використовуваних протоколах, про интенсивностях потоків запитів між комп'ютерами мережі, протяжності ліній зв'язку, про типах
25
використовуваного обладнання і додатків. Програмні системи моделювання можуть бути вузько спеціалізованими і досить універсальними, що дозволяють імітувати мережі найрізноманітніших типів. Якість результатів моделювання в значній мірі залежить від точності вихідних даних про мережі, переданих в систему імітаційного моделювання.
Програмні системи моделювання мереж - інструмент, який може стати в нагоді будь-якому адміністратору корпоративної мережі, особливо при проектуванні нової мережі або внесенні кардинальних змін в уже існуючу.
Продукти цієї категорії дозволяють перевірити наслідки впровадження тих чи інших рішень ще до оплати придбаного обладнання. Звичайно, більшість з цих програмних пакетів коштують досить дорого, але і можлива економія може бути теж вельми відчутною.
Програми імітаційного моделювання мережі використовують в своїй роботі інформацію про просторове розташування мережі, зокрема вузлів, конфігурації зв'язків, швидкостях передачі даних, що використовуються протоколах і типі обладнання, а також про виконувані в мережі додатках.
Зазвичай імітаційна модель будується не з нуля. Існують готові
імітаційні моделі основних елементів мереж найбільш поширених типів маршрутизаторів, каналів зв'язку, методів доступу, протоколів і т.п. Ці моделі окремих елементів мережі створюються на підставі різних даних: результатів тестових випробувань реальних пристроїв, аналізу принципів їх роботи, аналітичних співвідношень. В результаті створюється бібліотека типових елементів мережі, які можна налаштовувати за допомогою заздалегідь передбачених в моделях параметрів.
Системи імітаційного моделювання зазвичай включають також набір засобів для підготовки вихідних даних про досліджувану мережі - попередньої обробки даних про топологію мережі і измеренном трафіку. Ці кошти можуть бути корисні, якщо моделируемая мережа являє собою варіант
існуючої мережі і є можливість провести в ній вимірювання трафіку і інших параметрів, потрібних для моделювання. Крім того, система забезпечується
26
коштами для статистичної обробки отриманих результатів моделювання.
Yаведені характеристики декількох популярних систем імітаційного моделювання різного класу - від простих програм, призначених для установки на персональному комп'ютері, до потужних систем, що включають бібліотеки більшості наявних на ринку комунікаційних пристроїв і дозволяють в значній мірі автоматизувати дослідження досліджуваної мережі.
Сьогодні до комп'ютерних мереж як до обчислювальної платформі підприємства пред'являються все більш жорсткі вимоги надійності, швидкості та ефективності. Мережа розглядається як важливий, іноді навіть критично важливий ресурс, який повинен бути використаний максимально ефективно при мінімальних витратах. Найчастіше до основних параметрів роботи мережі відносять [9]:
- пропускну здатність (ємність);
- швидкість;
- надійність.
Високі вимоги до якості роботи мережі забезпечують інтерес до моніторингу та моделювання обчислювальних мереж. Засоби моніторингу доступні сьогодні в широкому асортименті, починаючи від системних консольних утиліт і закінчуючи програмними комплексами з можливістю управління і з застосуванням експертних систем (HP OpenView NNM,
NetView (Tivoli) від IBM, Spectrum від Cabletron). В області моделювання ВС
інша справа, оскільки тут потрібні не тільки технічні знання, ай розуміння теоретичних основ процесів передачі та обробки даних, що відбуваються в обчислювальних мережах. До групи засобів, що моделюють роботу мереж, можна віднести
ComNet від CACI Products Company, OPNET від OPNET Technologies (раніше
- MIL3), NetCracker, OMNeT ++, NS-2, NS-3 і інші (таблиця 1.2).
27
Таблиця 1.1 – Порівняльний аналіз програмних засобів моделювання ОС Продукт
COM
NET
Net
Maker
OPNet OMNeT
++
SES
/Strategizer
NS-
2
NET
Cracker
Виробник
+
+
+
+
+
+
+
Наявність бібліотеки пристроїв
+
+
+
+
+
+
+
Налаштування бібліотеки пристроїв
+
+
-
+
+
+
-
Покрокове трасування
+
-
-
+
+
+
+
Генерація звітів
+
+
-
+
+
-
+
Кожна з цих систем призначена для вирішення конкретних завдань різного ступеня абстракції. Проект COMNET позиціонувався як система моделювання ВС з розвиненими засобами візуалізації і модульною структурою, що дозволяє полегшити працю системних адміністраторів.
Серед основних підсистем COMNET можна виділити блок стохастичного моделювання, підсистему швидкого тимчасового аналізу Predictor, підсистему моніторингу Enterprise Profiler, пакет аналізу продуктивності мережі NETWORK. В даний час пакет COMNET не підтримується, компанія розвиває симуляції пакет SIMPROCESS. Система Opnet Modeler оперує вузлами трьох типів - процесорними вузлами, вузлами-маршрутизаторами і комутаторами. Вузли можуть приєднуватися за допомогою портів до комунікаційних каналах будь-якого типу, від каналів локальних мереж до супутникових ліній зв'язку. Вузли і канали можуть характеризуватися середнім часом напрацювання на відмову і
28
середнім часом відновлення для моделювання надійності мережі.
Моделюється не тільки взаємодія комп'ютерів в мережі, але і процес поділу процесора кожного комп'ютера між його додатками. Канали зв'язку моделюються шляхом завдання їх типу, а також двох параметрів -пропускной здатності і вноситься затримки поширення. Одиницею переданих по каналу даних є кадр. Пакети при передачі по каналах сегментируются на кадри.
Кожен канал характеризується мінімальним і максимальним розміром кадру, накладними витратами на кадр і інтенсивністю помилок в кадрах.
Робоче навантаження створюється джерелами трафіку. Кожен вузол може бути з'єднаний з декількома джерелами трафіку різного типу. Джерела планованої навантаження генерують дані, використовуючи залежне від часу розклад. При цьому джерело генерує дані періодично, використовуючи певний закон розподілу інтервалу часу між порціями даних. Джерела
«клієнт-сервер» дозволяють задавати не трафік між клієнтами і сервером, а додатки, які породжують цей трафік. До сильних сторін OPNET Modeler можна віднести графічні засоби побудови моделі ВС. Система дозволяє вирішувати наступні завдання: планування та оптимізація мережі; створення і перевірка аналітичних моделей мережі; створення і перевірка протоколу зв'язку. До недоліків відносяться відсутність трасування моделей і недостатня гнучкість: використовується власна, нерозширювана бібліотека пристроїв і обмежений набір звітів. З безкоштовних пакетів для задач імітаційного моделювання можна відзначити такі кошти зарубіжних розробників, як jist / swans, NS-2, NS-3,
GloMoSim, Parsec.
NS-2 (Network Simulator 2) - безкоштовний пакет, ядро якого реалізовано на мові C ++. Характерною властивістю програмного забезпечення OSS є можливість модифікації ядра програми і гнучке налаштування відповідно до вимог конкретного користувача, а також мультиплатформеність - працездатність існуючих версій для SunOS, Solaris,
29
Linux, FreeBSD, Windows 5/98 / ME / NT / 2000.
Також потрібно від користувача наявність навичок програмування на C
++ і OTcl (Object oriented Tool Command Language), який використовується в якості інтерпретатора. За рахунок використання дворівневого програмування забезпечується висока ступінь настройки моделі. Серед слабких місць пакету відзначають також складність використання OTcl, проблеми переносимості коду, обмежені можливості ефективного використання пам'яті при моделюванні, недостатня розвиненість режиму трасування і засобів збору статистики при роботі моделі, а також слабку візуалізацію.
Висока вартість, складність впровадження і інтеграції, обмежені можливості деяких існуючих програмних продуктів, в сукупності з існуючим попитом, змушує дослідників шукати нові рішення для аналізу і моделювання ВС. Один з них, досить простий і зручний у використанні, - ППП "ДІФАР". В основу його побудови покладені викладені вище положення моделювання систем і мереж масового обслуговування.
- Пакет ДІфАР призначений для аналітичного моделювання та оптимізації систем, мереж масового обслуговування та мережевих систем.
Він дозволяє розраховувати ймовірно-тимчасові характеристики СМО, Мемо і мережевих систем, задаючи в якості параметрів два моменти вхідних потоків і обслуговування, що дозволяє досліджувати поведінку систем в широкому діапазоні змін як середніх значень, так і дисперсій потоків і обслуговування, а також знайти оптимальне побудова мережевих систем за значеннями ймовірнісно-часових характеристик
(ВВХ), адекватних фактичним розподілом.
- Пакет ДІФАР забезпечує розрахунок:
- системних характеристик для одноканальних і багатоканальних систем масового обслуговування без обмежень на ємності буферних накопичувачів (середнє значення і дисперсія часу перебування, максимальний час перебування для r відсотків заявок, завантаження);
30
системних характеристик для одноканальних і багатоканальних систем масового обслуговування, які враховують обмеження на ємності буферних накопичувачів (середнє значення і дисперсія часу перебування, максимальний час перебування для r відсотків заявок, ймовірність відмови в обслуговуванні, завантаження); системних характеристик для одноканальних систем масового обслуговування з груповим надходженням заявок або груповим обслуговуванням заявок (середнє значення і дисперсія часу перебування заявки, максимальний час перебування для r відсотків заявок, завантаження); системних і мережевих характеристик відкритих неоднорідних мереж масового обслуговування з вузлами різних типів (середнє значення і дисперсія часу перебування в мережі, максимальний час перебування в мережі для r відсотків заявок, середнє значення і дисперсія часу перебування в кожному вузлі мережі, максимальний час перебування в кожному вузлі для r відсотків заявок, завантаження вузлів мережі, ймовірності відмов в обслуговуванні у вузлах);
- системних і мережевих характеристик замкнутих і змішаних неоднорідних мереж масового обслуговування з вузлами різних типів, з простим режимом роботи діалогових абонентів (середнє значення і дисперсія часу перебування в мережі заявки кожного типу, максимальний час перебування в мережі для r відсотків заявок кожного типу, середнє значення і дисперсія часу перебування в кожному вузлі мережі, завантаження вузлів мережі, ймовірності відмов в обслуговуванні у вузлах);
- системних і мережевих характеристик замкнутих і змішаних неоднорідних мереж масового обслуговування з вузлами різних типів зі складним режимом роботи діалогових абонентів (середнє значення і дисперсія часу циклу технологічного процесу роботи кожного діалогового абонента, максимальний час циклу для r відсотків технологічних процесів кожного типу, середнє значення і дисперсія часу перебування в мережі заявки кожного типу, максимальний час перебування в мережі для r відсотків
- показників ефективності мережевих систем, в якості моделей яких використовуються відкриті, замкнуті і змішані мережі масового обслуговування
(локальні обчислювальні мережі,
інформаційно- обчислювальні мережі, центри комутації пакетів і ін.). Пакет програм дозволяє проводити аналіз мережевих систем, що включають від 30 (замкнуті і змішані мережі зі складним режимом роботи діалогових абонентів) до 500 вузлів СМО (відкриті, замкнуті і змішані мережі з простим діалогом).
32 2 МОДЕЛЮВАННЯ ОБЧИСЛЮВАЛЬНИХ МЕРЕЖ НА ОСНОВІ МЕРЕЖ
ПЕТРІ
2.1 Інформаційна модель обчислювальної мережі
Будемо розглядати обчислювальну мережу, що складається з пристроїв різних типів, в якій циркулюють пакети даних. Модель обчислювальної мережі, в загальному вигляді, можна уявити в нотації RDF [7] (Рисунок 2.1). Рисунок 2.1 – Інформаційна модель мережі Тут представлені основні інформаційні об'єкти і зв'язки між ними.
Об'єкт Мережа описує реальну ВС і може включати в себе як підмережі інші об'єкти цього типу.
Об'єкт «Мережевий прилад» моделює пристрої, що входять до складу мережі. Це абстрактний об'єкт, функцією якого є обробка пакетів, тобто
33
затримка у пристрій на деякий час і можлива модифікація пакета (наприклад, зміна його типу. Кожен екземпляр об'єкта характеризується в першу чергу значенням свого параметра тип. Типами мережевого пристрою можуть бути: робочі станції, комунікаційне, периферійне устаткування, канали передачі даних. Тип визначає конкретну структуру «Мережевого приладу».
Об'єкт Блок обробки пакетів» характеризує основний елемент мережевого пристрою, відповідальний за швидкість і дисципліну обробки мережевих пакетів. Для однопроцесорних мережевих пристроїв Блок обробки» моделює роботу центрального процесора і містить дані про його потужності (в операціях в секунду. Для багатопроцесорних пристроїв кожен Блок обробки» характеризує один процесор. Для мережевих каналів передачі даних Блок обробки» є віртуальним об'єктом і характеризує швидкість передачі даних (байт (біт) / секунда.
Об'єкт Блок отримання/передачі» входять до складу «Мережевого приладу» і служить для опису входу і виходу потоку мережевого трафіку. Блок отримання/передачі для мережевих вузлів пов'язаний з їх мережевими
інтерфейсами.
Власне досліджуваний мережевий трафік описується об'єктами Тип трафіку», «Джерело трафіку», Поток трафіку» і Пакет.
Об'єкт Тип трафіку» містить інформацію про групу потоків повідомлень в мережі, що володіють загальними параметрами. До цих параметрів відносяться:
- використовувані протоколи;
- служби або програми, що створюють цей трафік (наприклад, службовий, передача відео, ftp-трафік);
- пріоритет даного типу трафіку;
- коефіцієнт затримки, пов'язаний з обслуговуванням даного типу трафіку (наприклад, sql-запити можуть обслуговуватися довше, ніж службовий трафік навіть при однаковому розмірі пакетів);
- закон розподілу, що характеризує кількість пакетів, згенерованих в
34
одиницю часу
- закон розподілу, що характеризує розмір пакетів, згенерованих в одиницю часу.
Об'єкт «Джерело трафіку» є відправною точкою декількох потоків однотипного трафіку з одного пристрою до кількох. Джерело трафіку характеризується Блоком прийому-передачі» пристрою, з яким він пов'язаний, Типом трафіку» а також моментом початку генерації повідомлень, який може здаватися статично або визначатися в момент роботи пристрою. Всі повідомлення, згенеровані «Джерелом трафіку», в загальному випадку з різною ймовірністю надходять до декільком адресатам (якщо адресат один, то і ймовірність надходження кожного повідомлення до нього відповідно дорівнює 1).
Об'єкт Поток трафіку» служить для загального опису всіх повідомлень, згенерованих одним «Джерелом трафіку» і спрямованих до одного Блоку прийому-передачі» вузла по одному маршруту, тобто через деяку однозначно визначену в певний момент часу послідовність
«Мережевих пристроїв».
Об'єкт Пакет описує один мережевий пакет потоку. Деталізація до цього рівня необхідна тільки при імітаційному моделюванні, оскільки її запуск пов'язаний з відстеженням шляху кожного пакета. В результаті формується статистика по трафіку в цілому.
2.2 Математична модель ОС на основі МП Для моделювання використовуються ієрархічні розфарбовані МП з тимчасовим механізмом [4, 6], де колір (тип міток) відповідає типу трафіку.
Мітки можуть бути двох типів - «повідомлення» і «службові маркери», які означають факт зайнятості ресурсу обробкою меток- «повідомлень».
Кількість міток в позиціях відповідає стану мережі, переходи змінюють цей стан, переміщаючи мітки в інші позиції.
Протягом одного такту мітка може зробити не більше одного переміщення через дозволений перехід. У класичних МП без тимчасових затримок один такт відповідає спрацьовування одного (будь-якого) дозволеного переходу. Але оскільки МП цінні саме для моделювання паралельних систем, в більшості інтерпретацій і розширень МП такт розуміється ширше - як проміжок, протягом якого спрацьовують всі дозволені в початковому стані переходи. Кожен мережевий об'єкт (робоча станція, канал передачі, комунікаційний пристрій) моделюється як підмережа
Петрі.
2.2.1 Основні визначення
Теоретико-множинне визначення МП можна представити в наступному вигляді [4, 6]: