Оцінка ефективності комутованої Еthernet параметричними сітями Петрі

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

ОДЕСЬКА НАЦІОНАЛЬНА АКАДЕМІЯ ЗВ'ЯЗКУ ім. О.С. ПОПОВА

УДК 621.39, 004.7

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

Автореферат

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

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

ОЦІНКА ЕФЕКТИВНОСТІ КОМУТОВАНОЇ ETHERNET ПАРАМЕТРИЧНИМИ СІТЯМИ ПЕТРІ

Шмельова Тетяна Рудольфівна

Одеса - 2008

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

Робота виконана в Одеській національній академії зв'язку ім. О.С. Попова, Міністерство транспорту та зв'язку України

Науковий керівник - доктор технічних наук, професор Зайцев Дмитро Анатолійович, Одеська національна академія зв'язку ім. О.С. Попова, професор кафедри мереж зв'язку

Офіційні опоненти: доктор технічних наук, доцент Лемешко Олександр Віталійович, Харківський університет Повітряних сил ім. Івана Кожедуба, доцент кафедри бойового застосування вузлів зв'язку та радіотехнічного забезпечення і бортових радіоелектронних комплексів ХУ ПС

доктор технічних наук, професор Слєпцов Анатолій Ілліч, Київський національний педагогічний університет ім. М. П. Драгоманова, професор кафедри управління та євроінтеграції

Захист відбудеться 17 жовтня 2008 р. о 10 годині на засіданні спеціалізованої вченої ради Д 41.816.02, Одеська національна академія зв'язку ім. О.С. Попова, вул. Ковальська, 1, 65029, м. Одеса.

З дисертацією можна ознайомитись у бібліотеці Одеської національної академії зв'язку ім. О.С. Попова, вул. Ковальська, 1, 65029, м. Одеса.

Автореферат розісланий 12 вересня 2008 р.

Вчений секретар спеціалізованої вченої ради А. Г. Ложковський



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

Актуальність теми. На теперішній час технологія Ethernet домінує в секторі локальних мереж. Стандарт 10Gb Ethernet застосовується в магістральних мережах, оскільки оператори зв'язку широко використовують рішення типу «Ethernet поверх DWDM». Зазначені застосування дозволяють позиціонувати Ethernet як універсальну мережну технологію.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана частково в рамках науково-дослідної роботи «Розробка імітаційних моделей магістральних мереж з комутацією позначок» (№ держ. реєстрації 0107U007642) з ВАТ Укртелеком, 2007 рік, в сумісних наукових дослідженнях за проектом «Верифікація складних мережних протоколів» з Технічним університетом Кошице (Словаччина) 2007-2008 рр.

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

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

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

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

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

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

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

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

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

- розроблено параметричну модель комутованої Ethernet, що містить фіксовану кількість вершин;

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

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

Практичне значення одержаних результатів. Практичне значення отриманих результатів полягає у використанні: розробленої типової параметричної моделі комутованої Ethernet в програмних системах автоматизації проектування мереж; розробленої бібліотеки модифікацій типової моделі для урахування специфічних вимог сфери застосування; розробленої бібліотеки вимірювальних фрагментів для експрес-оцінок продуктивності в процесі імітаційного моделювання. Результати верифікації і бібліотеки моделей можуть бути використані як складова частина систем автоматизації проектування мереж. Розроблені методи використовуються у ВАТ Укртелеком в рамках науково-дослідної роботи «Розробка імітаційних моделей магістральних мереж з комутацією позначок» (№ держ. реєстрації 0107U007642), в науково-виробничому об'єднанні СІГМА-Т.

Особистий внесок здобувача. Всі основні положення і результати дисертаційної роботи, які виносяться на захист, отримані здобувачем самостійно. У побудові моделей вимірювальних фрагментів комутованих мереж брав участь Д.А. Зайцев. У побудові моделі комутатора, що реалізовує алгоритм покриваючого дерева (STA) брав участь М.Ф. Байков.

Апробація результатів дисертації. Результати роботи представлені на 10-ій ювілейній міжнародній конференції з фізики і технології тонких плівок, Івано-Франківськ, Україна, 2005; 1-ій міжнародній науково-технічній конференції «Моделювання і комп'ютерна графіка» Донецьк, Україна, 2005; Міжнародною Середньо-східної науково-технічної конференції з моделювання, Олександрія, Єгипет, 2006; на 3-ій міжнародній науково-технічній конференції «Сучасні проблеми радіотехніки і телекомунікацій «РТ-2007», Севастополь, Україна, 2007; на 3-ій міжнародній науково-технічній конференції «Сучасні інформаційно-комунікаційні технології «COMINFO'2007», Лівадія, Україна, 2007.

Публікації. Результати роботи опубліковані в 10 статтях в наукових журналах і збірниках наукових праць, з них 5, вказаних в переліку ВАК України, 5 - в матеріалах і тезах конференцій.

Дисертаційна робота обсягом 143 сторінки складається з вступу, чотирьох розділів, висновків, списку використаних джерел із 86 найменувань на 9 сторінках, 4 додатків на 18 сторінках. Дисертація містить 39 ілюстрацій, 9 таблиць.

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

У першому розділі - «Методи оцінки продуктивності мереж Ethernet» виконано аналіз сучасних аналітичних і імітаційних методів оцінки продуктивності телекомунікаційних систем, обґрунтовано необхідність розробки спеціальних моделей Петрі і методів для оцінки продуктивності та верифікації комутованої Ethernet.

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

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

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

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

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

Побудовані моделі комутатора дозволяють подати модель комутованої Ethernet як нескінченне бінарне дерево. При цьому з'єднання комутаторів виконується шляхом сполучення (об'єднання) контактних позицій портів, , і , . Порт 1 використано для зв'язку з комутатором вищестоящого рівня (uplink); порти 2, 3 - для зв'язку з парою комутаторів рівня, який розташовано нижче (або з термінальними пристроями для останнього рівня). Досліджено повні бінарні дерева, але отримані результати можуть бути узагальнені на часткові дерева.

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

На кожному -му рівні міститься наступна кількість компонентів: на першому рівні - 1 компонент, на другому - 2, на третьому - 4. Таким чином, загальна кількість комутаторів на -му рівні дорівнює , загальна кількість комутаторів в дереві дорівнює для будь-якого натурального . Далі результати отримані для довільного , що дозволяє говорити про побудову, а в подальшому дослідженні, нескінченних моделей. На рис. 2 зображено модель деревоподібної мережі з комутатором N1 (індекси комутаторів мають вигляд i.j).

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

Основою верифікації телекомунікаційних протоколів за допомогою сітей Петрі є інваріантний аналіз моделей. Модель ідеального телекомунікаційного протоколу відповідно до робіт Ж. Берселота і М. Діаза має бути p- і t- інваріантною; сильніші вимоги припускають також живість сіті, або, принаймні, відсутність тупиків.

Запропоновано наступні принципи побудови нескінченних систем рівнянь на прикладі системи обчислення інваріантів позицій:

1. Побудувати один (або декілька) базових фрагментів для композиції моделі.

2. Сформулювати правила композиції нескінченної моделі з базових фрагментів.

3. Ввести певну нумерацію базових фрагментів нескінченної системи.

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

5. Встановити особливі угоди в нумерації контактних і крайових позицій (переходів).

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

7. Доповнити систему рівняннями, відповідними крайовим базовим фрагментам з нестандартною нумерацією у разі потреби.

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

Рівняння відповідають наступному порядку вибору переходів моделі комутатора: .

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

Побудований параметричний розв'язок системи (1) має вигляд:

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

Загальна кількість розв'язків (2) системи (1) для будь-якого дорівнює:

, де

- два розв'язки (змінної довжини) містять всі позиції обмежувачі () та буферні позиції портів і комутаторів ();

- () загальна кількість пар (буфер, обмежувач буфера) розв'язків ;

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

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

Лема. Матриця (2) є поданням розв'язків системи (1) для будь-якого натурального .

Теорема. Матриця (2) дозволяє побудувати лінійну комбінацію розв'язків з усіма натуральними компонентами.

Слідство. Нескінченна деревоподібна сіть Петрі з компонентою N1 р-інваріантна.

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

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

У третьому розділі - «Побудова параметричних моделей» представлено методику побудови параметричних моделей комутованої Ethernet у формі розфарбованих сіток Петрі в середовищі моделюючої системи CPN Tools.

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

Результат здобуто за рахунок введення спеціального тегу (рис. 5), який містить номер і параметри i-го екземпляра компоненти типу j.

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

Основні принципи параметризації моделей мереж у формі розфарбованих сітей Петрі:

1. Кожну компоненту мережі Ethernet (комутатор, сервер, робоча станція) подано в одному екземплярі.

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

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

Типова параметрична модель комутованої Ethernet подана на рис. 6.

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

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

Топологія мережі подана маркіруванням позицій Attach і SwitchLink. Сполучена позиція Attach (AttachWS, AttachS) містить інформацію про підключення термінальних пристроїв та вказує для кожної MAC-адреси номер комутатора і номер порту. Позиція SwitchLink містить описи зв'язків між комутаторами та вказує номер комутатора і номер порту для кожного з двох кінців лінії зв'язку.

Таблиці комутації всіх комутаторів подано маркіруванням позиції swtab. Позиція buffer моделює внутрішній буфер комутатора. Позиція rqWS містить таблицю запитів робочих станцій до серверів, задану указівкою пар MAC-адрес. Позиція ownWS перелічує MAC-адреси робочих станцій.

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

Початкове маркірування позицій моделі (рис. 6) подане в табл. 1 і відповідає мережі диспетчерського центру (ДЦ) залізниці, зображеної на рис. 7.



Таблиця 1 - Параметри моделі

Ім'я позиції	ownWS	ownS	inPorts, outPorts	Topology AttachWS AttachS	Topology SwichLink	Topology swtab	rqWS
Опис	Список МАС-адрес робочих станцій	Список МАС-адрес серверів	Вхідні (вихідні) порти комутатора	МАС-адреса пристрою, номер порту, номер комутатора до якого він підключений	Зв'язки між комутаторами: номер комутатора і номер порту для кожного з двох кінців лінії зв'язку	Таблиця комутації: МАС-адреса пристрою, номер порту, номер комутатора до якого він підключений	МАС-адреси робочої станції і сервера до якого він посилає запити
Маркірування для мережі	1`1++ 1`2++ 1`3++ 1`4++ 1`5++ 1`7	1`6++ 1`8	1`avail(1,1)++ 1`avail(1,2)++ 1`avail(1,3)++ 1`avail(1,4)++ 1`avail(2,1)++ 1`avail(2,2)++ 1`avail(2,3)++ 1`avail(2,4)++ 1`avail(3,1)++ 1`avail(3,2)++ 1`avail(3,3)++ 1`avail(3,4)	1`(1,1,1)++ 1`(2,2,1)++ 1`(3,3,1)++ 1`(4,1,2)++ 1`(5,2,2)++ 1`(6,3,2)++ 1`(7,2,3)++ 1`(8,3,3)	1`(1,3,4,1)++ 1`(3,1,1,4)++ 1`(2,4,3,4)++ 1`(3,4,2,4)	1`(1,1,1)++1`(2,2,1)++ 1`(3,3,1)++1`(4,1,2)++ 1`(5,2,2)++1`(6,3,2)++ 1`(7,2,3)++1`(8,3,3)++ 1`(4,4,1)++1`(5,4,1)++ 1`(6,4,1)++1`(7,4,1)++ 1`(8,4,1)++1`(1,4,2)++ 1`(2,4,2)++1`(3,4,2)++ 1`(7,4,2)++1`(8,4,2)++ 1`(1,1,3)++1`(2,1,3)++ 1`(3,1,3)++1`(4,4,3)++ 1`(5,4,3)++1`(6,4,3)	1`(1,6)++ 1`(1,8)++ 1`(2,6)++ 1`(2,8)++ 1`(3,6)++ 1`(3,8)++ 1`(4,6)++ 1`(4,8)++ 1`(5,6)++ 1`(5,8)++ 1`(7,6)++ 1`(7,8)

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

Таблиця 2 - Оцінка кількості компонентів

Тип моделі	Кількість комутаторів	Кількість портів	Кількість серверів	Кількість робочих станцій	Всього вершин
Модель ДД	1	6	2	5	14
Модель ДЦ	3	24	2	6	35
Параметрична модель	1	2	1	1	5

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

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

У четвертому розділі - «Побудова вимірювальних фрагментів параметричних моделей» отримав подальший розвиток метод вимірювальних фрагментів з урахуванням специфіки параметричних моделей для оцінки функціональних характеристик моделі в процесі імітації динаміки сіті Петрі. Розроблено вимірювальні фрагменти параметричної моделі комутованої Ethernet для оцінки пропускної спроможності (трафіку), якості обслуговування (часу доставки кадру), а також розмірів внутрішніх буферів комутаторів. Крім того, для підтвердження адекватності побудованих моделей розроблено методику вимірювання зазначених характеристик на реальних мережах.

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

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

Використана проста формула обчислення трафіку:

,

де n - кількість доставленої інформації, dt - інтервал часу вимірювання.

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

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

,

де - час доставки j-го кадру, q - загально кількість доставлених кадрів.

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

Організовано вимірювання на термінальних пристроях реальних мереж за допомогою аналізатора пакетів WinDump для операційних систем сімейства MS Windows (TCPDump для Unix). Результати вимірювань були також підтверджені за допомогою програмного забезпечення SoftPerfect Network Protocol Analyzer. Для перевірки адекватності моделей дамп кадрів був запущений на термінальних пристроях (робочих станціях і серверах) локальної мережі диспетчерського центру залізниці (рис. 7), оснащених системою ГІД Урал ВНІЇЖТ. Помилка оцінки середнього часу доставки за допомогою моделі складає не більше 5%, що підтверджує адекватність побудованих моделей.

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

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

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

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



ВИСНОВКИ

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

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

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

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

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

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



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

1. Шмелёва Т.Р. Верификация протоколов коммутируемой Ethernet с помощью бесконечных сетей Петри / Т.Р. Шмелёва // Вісник ДУІКТ, Спеціальний випуск. - 2007. - С. 96-102.

2. Шмелёва Т.Р. Оценка характеристик сетей Ethernet с помощью параметрических моделей Петри / Т.Р. Шмелёва, Д.А. Зайцев // Зв'язок. - 2007. - Т. 72, № 4. - С. 62-67.

3. Шмелёва Т.Р. Измерение характеристик одноуровневой коммутируемой сети с помощью параметрической модели Петри / Т.Р. Шмелёва, Д.А. Зайцев // Радиотехника: Всеукр. межведомств. науч.-техн. сб. - 2005. - Вып. 142. - С. 40-47.

4. Шмелёва Т.Р. Параметрическая модель Петри одноуровневой коммутируемой сети / Т.Р. Шмелёва, Д.А. Зайцев // Труды Одесской национальной академии связи им. А.С.Попова. - 2005. - № 1. - С. 33-40.

5. Шмелёва Т.Р. Моделирование коммутируемой локальной сети раскрашенными сетями Петри / Т.Р. Шмелёва, Д.А. Зайцев // Зв'язок. - 2004. - Т. 46, № 2. - С. 56-60.

6. Shmeleva T.R. Verification of switched Ethernet protocols using infinite Petri nets / T.R. Shmeleva // COMINFO'2007: Proceedings of Third International Scientific and Technical Conference - Modern Information and Communication Technologies, September 24-28, 2007. - Livadiya (Ukraine). - 2007. - Р.161-163.

7. Шмелёва Т.Р. Оценка эффективности алгоритма покрывающего дерева Ethernet с помощью раскрашенных сетей Петри / Т.Р. Шмелёва, М.Ф. Байков // Современные проблемы радиотехники и телекоммуникаций «РТ-2007»: Материалы 3-ей международной научно-технической конференции, 16-21 апреля, 2007. - Севастополь (Украина). - 2007. - С. 194.

8. Shmeleva T.R. Switched Ethernet Response Time Evaluation via Colored Petri Net Model / T.R. Shmeleva, D.A. Zaitsev // Proceedings of International Middle Eastern Multiconference on Simulation and Modelling, August 28-30, 2006. - Alexandria (Egypt). - 2006. - Р. 68-77.

9. Шмелёва Т.Р. Основы построения параметрических моделей Петри коммутируемых сетей / Т.Р. Шмелёва, Д.А. Зайцев // Моделирование и компьютерная графика: Материалы 1-й международной научно-технической конференции, 4-7 октября, 2005. - Донецк: ДонНТУ (Украина). - 2005. - С. 207-215.

10. Шмелёва Т.Р. Модели Петри телекоммуникационных сетей / Т.Р. Шмелёва, Д.А. Зайцев // Физика и технология тонких пленок: Материалы Юбилейной X Международной конференции, 16-21 мая, 2005. - Ивано-Франковск (Украина). - 2005. - том II. - С. 172-173.



АННОТАЦІЇ

Шмельова Т.Р. Оцінка ефективності комутованої Ethernet параметричними сітями Петрі. - Рукопис.

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

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

Ключові слова: комутована Ethernet, параметрична сіть Петрі, верифікація протоколів, оцінка продуктивності.



Шмелёва Т.Р. Оценка эффективности коммутируемой Ethernet параметрическими сетями Петри. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.12.02 - телекоммуникационные системы и сети. - Одесская национальная академия связи им. А.С. Попова, Одесса, 2008.

На основе теории классических и раскрашенных сетей Петри впервые предложены параметрические модели древовидной телекоммуникационной структуры с произвольным количеством устройств. Для верификации протоколов Ethernet предложена методика исследования свойств бесконечных сетей Петри с регулярной структурой; разработаны методы инвариантного анализа и эвристические алгоритмы построения параметрических решений бесконечных однородных систем в целых неотрицательных числах. Обнаружены взаимные блокировки коммутаторов с обязательной буферизацией кадров, приводящие к существенному снижению производительности сети. Разработана параметрическая модель коммутируемой Ethernet, которая содержит фиксированное число вершин раскрашенной сети Петри и инвариантна по отношению к топологии ЛВС, количеству подключенных сетевых и терминальных устройств, что не требует модификации её структуры и существенно снижает трудоёмкость разработки модели и оценки эффективности сетей. Построены измерительные фрагменты параметрической модели для оценки таких характеристик как пропускная способность (производительность) сети, время доставки кадров, время отклика сети и длины буферов коммутаторов непосредственно в процессе имитационного моделирования. Полученные в диссертации результаты нашли практическое применение при выполнении НИР и в учебном процессе.

Ключевые слова: коммутируемая Ethernet, параметрическая сеть Петри, верификация протоколов, оценка производительности.



Shmeleva T.R. Efficacy evaluation of switched Ethernet via parametrical Petri nets. - The manuscript.

The dissertation is competing for the degree of Ph.D. on a specialty 05.12.02 - telecommunication systems and networks. - Odessa National Academy of Telecommunication named after A.S. Popov, Odessa, 2008.

On the base of the theory of classical and colored Petri nets parametrical models of tree-like telecommunication structure with an arbitrary number of attached devices were introduced for the first time. For the verification of Ethernet protocols a tree-like Petri net was composed of Ethernet switch models supplied by models of terminal devices attached to the last level. The number of the tree-like structure levels is a parameter of the model. As far as the results were obtained for an arbitrary natural number of levels it was said that infinite Petri nets with regular tree-like structure were studied. A technique of infinite Petri nets with regular tree-like structure analysis was developed. For the calculation of p- and t-invariants infinite homogeneous linear systems of equations were composed. Solutions of infinite homogeneous linear systems of equations in non-negative integer numbers were constructed in parametrical form using a heuristic algorithm. The p- and t- invariance of the tree-like Petri net was proven for an arbitrary natural number of levels. But it was shown that the model is not a live Petri net because it contains deadlocks. Mutual blockings of switches with compulsory buffering of frames that lead to the considerable fall in the network performance were revealed.

A parametrical model of switched Ethernet in the form of colored Petri net which consists of a fixed number of nodes was developed. The model contains only one copy of each component: switch, workstation, server. LAN topology, software and hardware performance are parameters of the model represented by marking of definite places. It was achieved via special tag which contains description of the current location in a network. The tag was attached to token which models Ethernet frame. The value of the tag is changed regarding the topology of the network on its route from workstation to server and backwards. As the result the model is permanent regarding LAN topology, number of attached networking and terminal devices that does not require the modification of its structure and considerably decreases the laboriousness of the model development and the evaluation of the networks efficacy.

For the performance evaluation of given switched Ethernet networks the parametrical colored Petri net model was supplied with special measuring fragments. Measuring fragment is a fragment of colored Petri net which calculates a network functional characteristic directly in the process of simulation. Peculiarities of the parametrical model regarding the processing of tags were taken into consideration. A series of the basic parametrical model modifications for the dynamic address tables processing, STA algorithm, FIFO queue disciplines, cut-through possibilities were provided. Measuring fragments were constructed for the evaluation of such functional characteristics as the network bandwidth (performance), the frame delivery time, the network response time and the length of switches buffers directly in the process of simulation. Real-life networks especially for real time applications were modeled. The adequacy of constructed models was grounded by the comparison of the evaluations during simulation with the results of real-life networks measurement. Thus, constructed models can be applied in the model-driven development of networks, network hardware and software.

Obtained results were applied in scientific-research projects with communication statements as well as in the teaching of students.

Keywords: switched Ethernet, parametrical Petri net, protocols verification, performance evaluation.

Размещено на Allbest.ru

...