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

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

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

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

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

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

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

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

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

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

Найбільш ефективною у смислі Парето представляється наступна послідовність розроблених в дисертації процедур аналізу:

1 - перевірка первинної специфікації, представленої засобами мови таблиць подій;

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

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

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

5 - моделювання поведінки протокольної системи.

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



Мал. 2 Структура таблиці подій

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

,

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

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

де

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

.

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

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

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

.

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

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

(поступова композиція).

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

,

де k - номер розбивки у впорядкованому переліку розбивок ПА,

- усереднена потужність множини станів підавтоматів k-ої розбивки,

- усереднена кількість відокремлених при побудові k-ої розбивки підавтоматів.

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

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

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

,

де - вектор-рядок процесів, -я компонента якого рівняється , якщо існує допустимий процес, і рівна - в іншому випадку.

- матриця переходів ПА. Елемент матриці рівняється , якщо в ПА є переходи з стану в стан , і , якщо такий перехід відсутній;

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

Алгоритм реалізації методу зводиться до рішення матричного рівняння

,

де - одинична матриця, для якої , якщо i=j і eij= , якщо i?j;

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

де ,

Aji і означають, відповідно, алгебраїчне доповнення елемента aij і визначника матриці А.

Обчислення Aji і здійснюється за звичайними правилами, але з дотриманням процедур формування протилежного і зворотного елементів для si =; ). Ці співвідношення дозволяють проінтерпретувати такі операції над елементами матриці як віднімання та ділення.

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

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

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

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

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

З метою здійснення оцінок характеристик алгоритмів, що досліджуються, було розроблено аналітичну модель мережі, що дозволяє отримувати порівняльні оцінки алгоритмів та вказувати граничні значення критерію ефективності функціонування алгоритмів (у нашому разі середнього часу доставки повідомлень адресату). Були прийняті наступні припущення: 1) параметри (потік інформації від якого-небудь вузла мережі, надійність вузла і надійність каналів) однакові для всіх елементів мережі; 2) вузли мережі функціонально однорідні; 3) кожний вузол генерує потік керуючої інформації, який являє собою випадкову у часі послідовність повідомлень, причому довжина повідомлення також випадкова величина; 4) послідовність повідомлень пріоритету k утворить пуасоновський випадковий процес з інтенсивністю k повідомлень в одиницю часу; 5) довжина повідомлення k-го пріоритету розподілена згідно з показовим законом з відомим середнім значенням l одиниць інформації, так що потік Fk повідомлень k-го пріоритету з вузла рівний , а сумарний потік

і його інтенсивність

;

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

Оцінка середнього часу Tk доставки повідомлення k- го пріоритету адресату проводиться на основі співвідношення,

,

де S - середнє число трансляцій повідомлень від джерела до адресата; tk - середній час перебування повідомленням k-го пріоритету у вхідному буфері k; - середній час трансляції повідомлення.

Визначаючи

S=1/Q,

де Q- ймовірність того, що повідомлення, вміщене випадковим чином у систему, буде доведене до адресату за одну трансляцію, та конкретизуючи топологію МІО, легко отримати уточнену залежність Tk=Tk(,Q,) для будь-якої структури РТС:

.

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

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

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

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

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

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

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

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

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

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

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

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

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

За цими даними автоматично формується система п рівнянь вигляду

,

де Ri () - об'єднання послідовностей протокольних подій, які приводять ПА із початкового стану q до стану i;

Xij () - ідентифікатор елементарної події, надходження якої переводить ПА із стану i в стан j ( якщо і - в протилежному випадку);

n - кількість виділених в початковій протокольній специфікації станів взаємодій.

Рішенням системи рівнянь є регулярне вираз Rk, що специфікує один із взаємодіючих об'єктів протоколу. Специфікація поведінки K взаємодіючих протокольних об'єктів визначається в загальному випадку системою K регулярних виразів (R1,R2,…,RK).

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

,

де . Якщо не еквівалентна ні одній з вже одержаних похідних для RK, їй зіставляється стан ПА і формується перехід із стану до стану під впливом елементарної події zi. При цьому послідовності елементарних подій p та q належать протокольній події E(Rk). Отримувані внаслідок синтезу таблиці переходів протокольного автомата мають одну важливу властивість: вони мінімальні по числу станів автомата.

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

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

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

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

1 - формування початкової специфікації;

2 - перевірка повноти специфікації і її внутрішньої несуперечності;

3 - перевірка логічної коректності протоколу;

4 - моделювання протоколу на тестових послідовностях;

5 - генерація початкового коду програмної реалізації протоколу на мові З++;

6 - верифікація програмної реалізації;

7 трансляція з С++ в конкретне командне середовище.

Виявлені в процесі реалізації етапів 2,3,4 і 6 нештатні ситуації супроводяться коментарями, адресованими проектувальнику. Аналіз інформації, представленої системою проектування, дозволяє проектувальнику зробити необхідну корекцію початкової специфікації протоколу і наново запустити систему.

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

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

1) організувати діалог “проектувальник-система” при формуванні початкової специфікації протоколу;

2) здійснювати перевірку повноти і внутрішньої несуперечності початкової специфікації;

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

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

Мал. 3 Структурна схема СА(ПР)2РС

Висновки

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

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

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

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

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

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

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

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

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

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

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

9. Розроблено систему моделювання поведінки ПА, які входять до СПВ будь-якого рівня протокольної організації РТС, яка дозволяє оцінити якість функціонування СПВ (правильність, ефективність, реактивність). Запропонована система тестування протоколів представляє собою інструментальні засоби активного моніторингу РТС.

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

11. Розроблені інформаційні технології і інструментальні засоби побудови автоматизованих систем управління РТС використовувались при проектуванні спеціалізованих мережених систем в ряді науково-дослідницьких організацій, в том числі Науково-дослідницькому інституті систем зв'язку та управління НВО “КВАЗАР” (м. Москва), науково-дослідницькому центрі “Державний океанаріум” (м. Севастополь), науковому центрі ВМС України (м. Севастополь).

Список опублікованних робіт по темі дисертації

1. Апраксин Ю.К. Теория и проектирование ЭВМ. Синтез управляющих автоматов. Учеб. пособие. - К.: ИСИО МО Украины, 1993. - 80 с.

2. Апраксин Ю.К. Основы теории и проектирования цифровых автоматов: Учеб. пособие для вузов. Рекомендовано МОиН Украины. - Севастополь: Изд-во СевГТУ, 2001. - 345 с.

3. Apraksin Y.K. Computer network protocol and interface design. - Helsinki University of Technology. Report HTKK - TKO - B58. - 1984. - 36 p.

4. Апраксин Ю.К., Запевилин А.А. Перспективы развития системного математического обеспечения сетей ЭВМ. - К.: Знание, 1984. - 16 с.

5. Апраксин Ю.К., Кирюхин В.В. Некоторые задачи надежностного проектирования дискретных управляющих систем // Электронное моделирование. - Киев - 1981. - № 1. - С. 62-66.

6. Апраксин Ю.К. О перечислении элементарных сечений в сети связи ЭВМ // Автоматика и вычислительная техника. - Рига.-1981.- № 4. - С. 62-66.

7. Апраксин Ю.К., Запевалин А.А., Кирихин В.В. Алгоритмы маршрутизации для сетей с коммутацией сообщений // Автоматика и вычислительная техника. - Рига. - 1982. - № 2. - С. 87 - 92.

8. Апраксин Ю.К. К вопросу автоматизации проектирования протоколов вычислительных сетей на основе конечноавтоматной модели // Автоматика и вычислительная техника. - Рига. - 1987. - № 2. - С. 12-19.

9. Апраксин Ю.К., Запевалин А.А Спецификация сетевых протоколов с функциями внутренних замеров // Автоматика и вычислительная техника. - Рига. - 1989. - № 5. - С. 44-45.

10. Апраксин Ю.К., Запевалин А.А., Козлова Е.В. Релейное управление информационными потоками в промышленных сетях передачи данных // Приборостроение. Киев: Высш. шк. - 1990. - Выпуск 42.- С. 102-108.

11. Апраксин Ю.К., Гуревич И.М. Метод анализа конечных дискретных динамических систем // Техника средств связи. Серия СС. М.: - 1991. - Вып. 4. - С. 3 -13.

12. Апраксин Ю.К., Гуревич И.М. Матрично-лингвистический метод анализа конечных дискретных динамических систем //Динамические системы. - Киев: 1992. - Вып. 11. - С. 100-105.

13. Апраксин Ю.К. Конечноавтоматная модель протоколов распределенных вычислительных систем // Вестник СевГТУ. Вып. 10: Информатика, электроника, связь: Сб. научн. тр. - Севастополь. - 1998. С. 86-91.

14. Апраксин Ю.К. Декомпозиционный метод определения логической корректности сложных динамических систем // Вестник СевГТУ. Вып. 14: Автоматизация процессов и управления: Сб. научн. тр. Севастополь. - 1998. - С. 85-90.

15. Апраксин Ю.К. Моделирование поведения взаимодействующих объектов распределенных систем // АСУ и приборы автоматики. Всеукраин. межвед. науч.-техн. сб.- Харьков: ХНУРЭ. - 1999. - Вып.110. - С. 3-6.

16. Апраксин Ю.К., Кокуш К.Е., Некрут В.В. Автоматизированная система проектирования сетевых протоколов, ориентированных на программную реализацию //Вестник СевГТУ. Вып. 18: Информатика, электроника, связь: Сб. научн. тр. - Севастополь. - 1999. - С. 95-99.

17. Апраксин Ю.К. Спецификация протоколов управления информационным обменом в распределенных технических системах // Вестник СевГТУ. Вып. 26: Информатика, электроника, связь: Сб. научн. тр. - Севастополь. - 2000. - С. 16-21.

18. Апраксин Ю.К. Алгебраическая верификация протоколов управления информационным обменом в распределенных технических системах // Вестник СевГТУ. Вып. 27: Автоматизация процессов и управление: Сб. научн. тр. - Севастополь. - 2000. - С. 41-47.

19. Апраксин Ю.К. Приложение теории регулярных событий к анализу и синтезу протоколов распределенных систем //АСУ и приборы автоматики: Всеукраин. межвед. науч.-техн. сб. - Харьков: ХНУРЭ. - 2000. - Вып. 111. - С. 3-9.

20. Апраксин Ю.К. Спецификация сетевых протоколов средствами языка таблиц событий. // Вестник СевГТУ. Вып. 31: Информатика, электроника, связь: Сб. научн. тр. - Севастополь. - 2001. - С. 4-8.

21. Апраксин Ю.К. Об одном методе проектирования надежных распределенных технических систем // Вестник СевГТУ. Вып. 32: Информатика, электроника, связь: Сб. научн. тр. - Севастополь. - 2001. - С. 14-19.

22. Апраксин Ю.К., Качинский А.С. Программная реализация протоколов распределенных технических систем //Вестник СевНТУ. Вып. 41. Информатика, электроника, связь: Сб. научн. тр. - Севастополь. - 2002. - С. 155-158.

23. Апраксин Ю.К. Организация управления взаимодействием объектов в распределенных технических системах //Сб. научн. тр. Сев.ИЯЭиП. Вып.7: Информационные системы и технологии. - Севастополь. - 2003. - С. 214-220.

24. Апраксин Ю.К., Волкова Т.В. Аппаратная реализация протоколов распределенных технических систем //Вестник СевНТУ. Вып. 47. Информатика, электроника, связь: Сб. науч. тр. - Севастополь. - 2003. - С. 71-75.

25. Апраксин Ю.К., Запевалин А.А. Спецификация сетевых протоколов с функциями внутренних замеров //ЦИОНТ ПИК ВИНИТИ. М.: - 1989, - №7. - 10 с. - Деп. в ВИНИТИ, № 733-В89.

26. Апраксин Ю.К., Запевалин А.А. Алгоритмы адаптивной маршрутизации для децентрализованных сетей с коммутацией сообщений //Тезисы докладов всесоюзной научн.- техн. конф. “Исследование и проектирование систем связи”. - М. - 1980. - С.31-32.

27. Апраксин Ю.К., Козлова Е.В. Об одном подходе к автоматизации логического проектирования протоколов сетей передачи данных //Тезисы докладов всесоюзной научн.-техн. конф. “Пути повышения эффективности использования вычислительной техники”. - Таллин. - 1989. - С. 72-74.

28. Апраксин Ю.К. Автоматизация процедуры декомпозиции протоколов систем управления связью //Тезисы докладов III всесоюзной научн.-техн. конф. “Проблемы, методы и опыт создания автоматизированных систем управления связью”. - М.- 1990. - С.101-102.

29. Апраксин Ю.К. Применение конечно-автоматной модели к исследованию и проектированию распределенных систем //Сб. тр. II международной науч.- практ. конф. ИНФОТЕХ-99. - Севастополь. - 1999. - С.36-42.

30. Апраксин Ю.К. Определение логической корректности протокольных систем информационного взаимодействия //Материалы международной науч.- практ конф. ИНФОТЕХ 2002: Информационные технологии и информационная безопасность в науке, технике и образовании. - Киев - Севастополь. - 2002. - С.20-22.

31. Кудашев Е.С., Апраксин Ю.К. Автоматное управление параллельными процессами, протекающими в нерегулярном времени //Материалы 10 международной конференции по автоматическому управлению “Автоматика-2003”. - Севастополь. - 2003. - С. 58-59.

Анотацiя

Апраксiн Ю.К. Автоматизоване управління інформаційною взаємодією у розподілених технічних системах на основі специфікованих протокольних автоматів. - Рукопис.

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

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

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

Аннотация

Апраксин Ю.К. Автоматизированное управление информационным взаимодействием в распределенных технических системах на основе специфицированных протокольных автоматов. - Рукопись.

Диссертация на соискание ученой степени доктора технических наук по специальности 05.13.06 - автоматизированные системы управления и прогрессивные информационные технологии. - Севастопольский национальный технический университет, Севастополь, 2004.

Диссертация посвящена решению проблемы повышения эффективности функционирования территориально распределенных технических систем (РТС) за счет совершенствования управления информационным обменом между объектами системы.

Рассмотрены общие принципы организации РТС, позволяющие выделить основные направления исследований, связанных с проектированием эффективных алгоритмов управления системой. Общую структуру РТС любого назначения предлагается рассматривать как совокупность оконечных пунктов (комплексы аппаратных и программных средств “абонента” и “сервера”, обменивающихся между собой информацией через сеть информационного обмена). Предложена организационная модель управления РТС и классификация функций управления, реализация которых определяется техническим состоянием РТС (управление маршрутизацией, если состояние стабильно; управление нагрузкой при нестабильном состоянии; управление системой, если состояние критическое). Разработана схема оперативного управления в РТС, характерная для всех процессов управления, распределенных по иерархически подчиненным уровням системы управления. Каждый уровень при этом рассматривается как соответствующий процесс управления и взаимодействующий с ним протокол информационного обмена (объект системы протокольного взаимодействия).

Предложено систему протокольного взаимодействия в РТС рассматривать как асинхронную систему взаимодействующих по фиксированным правилам процессов. При этом модель объекта протокольного взаимодействия (протокольній автомат - ПА) представляется инициальным детерминированным автоматом Рабина - Скотта, входной алфавит которого определяется множеством элементарных событий, связанных с приемом/передачей сообщения или выполнением процессом каких-либо внутренних действий. Использование событийной интерпретации предлагаемого подхода позволяет при построении спецификации системы избавиться от перечисления ее состояний. Это оказывается возможным в случае представления любого протокольного события множеством последовательностей элементарных событий, приводящих процесс взаимодействия от его начала к результативному завершению. Предложена методика формирования спецификаций ПА, которая сводится к решению характеристических уравнений в алгебре регулярных событий. Разработаны концептуальные основы технологического процесса проектирования ПА, ориентированного на применение автоматических процедур реализации всех этапов проектирования от построения формальной спецификации до реализации в ту или иную среду функционирования. Сформулированы требования к языковым средствам, позволяющим представить ПА на всех стадиях проектирования (язык таблиц событий, язык регулярных выражений, диаграммы переходов, схемы алгоритмов).

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

Разработана аналитическая модель сети информационного обмена РТС, необходимая для оценки алгоритмов информационного обмена с точки зрения лишь одного параметра - вероятности доставки сообщения адресату за одну трансляцию. С помощью выведенных математических зависимостей легко определить граничные значения критерия эффективности для “наихудшего” и “наилучшего” алгоритмов и, таким образом, указать на диапазон возможных значений этого критерия для всего множества исследуемых алгоритмов. Предложена унифицированная структура программных средств маршрутизации сообщений, обеспечивающая общесистемную совместимость программных и аппаратных средств на всех уровнях иерархической системы управления. Предлагаемая структура позволяет сосредоточить на любом уровне управления РТС целый набор алгоритмов, обеспечивающих адаптацию системы к условиям функционирования. Для исследования реакции протокола на заданные последовательности событий разработана эффективная процедура моделирования поведения ПА, которая может быть положена в основу организации процедур сертификации протоколов управления информационным обменом.

Разработано информационное, алгоритмическое и программное обеспечение, позволяющее автоматизировать процесс проектирования протоколов управления информационным обменом в РТС. Созданная автоматизированная система СА(ПР)2РС обеспечивает: а) доступность для участия в процессе проектирования протоколов лицам, не обладающим достаточной квалификацией в области разработки сложных программных систем; б) использование разработанной формы исходной спецификации протокола для ее непосредственного преобразования в текст программы на выбранном языке программирования высокого уровня; г) выполнение процедур проверки логической корректности протокола; д) проведение экспериментов над разработанными протоколами.

Внедрение предложенных разработок позволяет повысить эффективность систем управления РТС за счет использования высоконадежных, логически корректных протоколов управления информационным обменом.

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

Abstract

Apraksin Yu. K. Information distributed technical systems interconnection control on the base of specified protocol automata. - Manuscript.

Dissertation for obtaining the scientific doctor degree of technical science on specialty 05.13.06 - automatized control systems and progressive information technology. Sevastopol national technical university, Sevastopol, 2004.

The dissertation is dedicated to the solution of the functioning efficiency increasing problem of territorial distributed technical systems (DTS) for account of management perfection by information exchange between system objects. In dissertation are suggested the conceptual bases of structural organization of distributed multilevel control system DTS, each level which is determined by two processes: by control process and interactions organization process. A protocol model (protocol automata - PA) was suggested and investigated in which eventual interpretation of DTS processes was used. Primary specification tools (events tables language) were elaborated which allow, on one side, to reduce the specification process and, on the other side, - to automate the procedures of PA analysis and synthesis. A common mathematical model, fixed in PA analysis procedures basis of logical proper behavior, synthesis and simulation of PA, provided a creation possibility of automated design protocol system. A presence of such design tool guarantees elaboration, logically correct, with high performance protocols, proper to DTS organization principles. The libraries of protocols of any hierarchy DTS control allow to adapt the system in broad spectrum of possible conditions and application.

Key words: distributed system, control, information exchange, protocol, automata model, protocol automata, protocol interconnection system, specification, analysis, synthesis.

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