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

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

ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

РАДІОЕЛЕКТРОНІКИ

УДК 681.32:519.713

Абу Занунех І.М. Халіль

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

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

АВТОРЕФЕРАТ

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

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

Харків 2001

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

Робота виконана в Харківському державному технічному університеті радіоелектроніки, Міністерство освіти і науки України.

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

Офіційні опоненти: доктор технічних наук, професор Хажмурадов Манап Ахмадович, Національний науковий центр “Харківський фізико-технічний інститут”, начальник відділу математичного забезпечення;

кандидат технічних наук Рустинов Володимир Олексійович, ТОВ НВП “Харківенергоремонт”, начальник відділу компьютерних технологій

Провідна установа:Національний університет “Львовська політехніка”, Міністерство освіти і науки України, м. Львів

Захист відбудеться 3 липня 2001 року о 14 годиі на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському державному технічному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

З дисертацією можна ознайомитися в бібліотеці Харківського державного технічного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий 22 травня 2001 року

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

спеціалізованої вченої ради Безкоровайний В.В.

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

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

Для цих цілей використовуються сервісні засоби тестування (HP Network Advisor, Network General Sniffer, LANalyzer) і вимірювальні прилади (цифровий вольтметр, рефлектометр, розширений тестер кабелю, осцилограф, логічний і сигнатурний аналізатори). Згадані засоби дають можливість здійснювати моніторинг мережі, відслідковувати мережний трафик зі збором статистики, контролювати активність станцій, технічний стан кабельної системи, активного і пасивного устаткування, програмного забезпечення.

Актуальність теми. Використання сервісних засобів надає досвідченому адміністратору інформацію для визначення місця, причини і вигляду дефекту, якщо мережа досить проста і містить невелику кількість робочих станцій. Для мереж, що містять десятки і сотні комп'ютерів, з розвиненою структурою і різними технологіями виконання (Ethernet, Arcnet Token Ring) проблема формалізації діагностичного експерименту і його реалізації з метою контролю і пошуку дефектів є досить актуальною. На додаток до сказаного слід зазначити, що вимірювальні прилади і логічні аналізатори не мають інтелектуальних засобів у вигляді алгоритмів, методик, програм, які б дозволили адміністратору чи менш кваліфікованому користувачу здійснювати процедуру діагностування у випадку порушення працездатності мережі. Крім того, з огляду на фактор просторової розосередженості сетьових компонентів, підданих виникненню дефектів, доцільно максимально зменшити підозрювану дефектну область, після чого за мінімальне число зондувань, що пов'язані з переміщенням адміністратора в просторі, визначити місце, причину і вигляд дефекту з метою його наступного усунення і відновлення працездатності мережі.

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

У рамках запропонованої тематики виконаний аналітичний огляд публікацій, що стосується моделей і методів аналізу локальних мереж і цифрових систем, раціональних або неформальних процедур тестування і діагностування, які можна застосувати до рішення проблем сервісного обслуговування ЛОМ і їхніх компонентів. Дослідженням даної тематики займалися вчені: Пархоменко П.П., Лобанов А.В., Зайченко Е.Ю., Якубайтис Э.А., Гі К., Като М., Мартін Д., Чаллис Д., Нессер Д., Хейкс Д., Романкевич А.М., Убар Р.Й., Скобцов Ю.А., Дербунович Л.В., Breuer M., Abramovici M., Courtois B., Mueller S., Cellis J., Perkins C., Strebe M.

Зв'язок роботи з науковими програмами, планами, темами. Дослідження, проведені в дисертації, здійснювалися відповідно до планів виконання НДР, проведених у Харківському державному технічному університеті радіоелектроніки, і договорів, зазначених нижче:

522-1 - “Розробка учбово-методичного забезпечення і програмно-апаратних засобів для нових навчальних дисциплін з комп'ютерних наук і комп'ютерній інженерії”, № держ. реєстрації 0197U012176.

102 - “Розробка теоретичних основ нових інформаційних технологій в автоматизованому проектуванні, діагностиці засобів радіоелектронної апаратури й обчислювальної техніки”, № держ. реєстрації 0100U03417.

Університетська програма міжнародного співробітництва в області освіти, науки “Стратегічне партнерство” від 10.03.2000.

Договір про довгострокове науково-технічне співробітництво з фірмою Аldec Inc. (USA) від 6.06.1999 р.

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

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

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

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

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

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

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

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

3) Розробки алгоритмів умовного пошуку дефектів у ЛОМ на основі використання топологічної структури мережі з метою мінімізації числа зондувань при досягненні наперед заданої глибини діагностування.

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

Наукова новизна отриманих результатів, що виносяться на захист:

1) Математична модель ЛОМ на основі використання булевої алгебри, що удосконалена для аналітичного і компактного опису структури і логіки роботи мережі з метою забезпечити можливість генерації тестів перевірки справного стану і моделювання несправностей.

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

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

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

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

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

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

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

Наукові і практичні результати у вигляді програмного додатка використовуються на підприємствах: ЗАТ “Енергозбереження”, Харків (довідка про впровадження від 15.01.2001); АТ “Маріупольський порт”, Маріуполь (акт про впровадження від 25.12.2000); а також у навчальному процесі Харківського державного технічного університету радіоелектроніки (акт про впровадження від 18.02.2001) і Національного технічного університету “Харківський політехнічний інститут” (довідка про впровадження від 15.03.2001).

Особистий внесок здобувача. Всі основні результати отримані автором особисто. У роботах, опублікованих спільно, автору належать: [2] - формалізація моделей дефектів фізичного рівня і їхні характеристики; [3] - моделі фізичних дефектів і реакції ЛОМ при їхньому виникненні; [4] - формальна постановка задачі діагностування ЛОМ; [5] - процедура побудови тестів за булевими рівняннями; [6] - алгоритми моделювання для побудови таблиць несправностей; [7] - аналітичне представлення структур ЛОМ у формі булевих рівнянь; [8] - формалізація процедури діагнозу дефектів фізичного рівня; [9] - моделювання дефектів за аналітичною моделлю мережі; [10-12] - побудова і верифікація логічної моделі для діагностування мережі.

Апробація результатів наукових досліджень здійснювалася на: п'ятої міжнародної конференції “Теорія і техніка передачі, прийому й обробки інформації”, Туапсе, 1999; 13-й Міжнародної школі-семінарі “Перспективні системи керування на залізничному, промисловому і міському транспорті”, Алушта, 2000; VI-th Conference CADSM 2001 “The Experience of Designing and Application of CAD System in Microelectroncs, Lviv - Slavsko, 2001; IV міської науково-технічної конференції “Актуальні проблеми сучасної науки в дослідженнях молодих учених Харківщини”, Харків, 2001; VII міжнародної науково-технічної конференції “Інформаційні технології: техніка, технологія, освіта, здоров'я: MicroCAD-99", Харків,1999; конференціях професорсько-викладацького складу ХТУРЕ (1998-2001).

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

Структура й обсяг дисертації. Дисертаційна робота містить 170 сторінок, 40 рисунків (на 18с.), 4 таблиці (на 2с.). Її структура включає: вступ, 4 розділи, висновок, список використаних джерел з 138 назв (на 12с.), 2 додатки (на 26с.).

локальна обчислювальна мережа дефект

ЗМІСТ РОБОТИ

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

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

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

1) Створення моделі мережі для генерації тестів і моделювання дефектів у вигляді функціональних режимів і відповідних їм реакцій при відсутності несправностей:

2) Визначення області підозрюваних дефектів у мережі за її реакцією на тестові режими в одному терміналі:

3) Зменшення області підозрюваних дефектів у мережі за її реакціями на тестові режими в доступних терміналах:

В іншому розділі представлена концепція опису сетьового сегмента у вигляді сукупності параметрів S,t,F, що визначають ступінь подробиці завдання структури і різноманіття форм: 1) функціональне завдання локальної обчислювальної мережі ; 2) структурно-функціональне ; 3) графова структура ; 4) часова модель ; 5) функціонально-часова ; 6) структурно-часова ; 7) найбільш повна модель з урахуванням усіх параметрів.

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

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

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

Орієнтована дуга , що зв'язує дві вершини в графі, де - джерело, - стік, називається імплікативним відношенням.

Якщо - безлічі вершин або дуг, що належать графу G, тобто диз'юнкція чи об'єднання цих множин.

Символ вершини є формула алгебраїчної форми графа (АФГ). 1) Символ 1 є позначення псевдовершини і є також формулою АФГ. 2) Якщо - формули АФГ, те і також є формулами. 3) Формули використовують відкриваючу і закриваючу дужки. 4) Упорядкована сукупність вершин, що з'єднана знаками імплікації, називається термом АФГ. 5) Алгебраїчною формою графа є вирази, побудовані відповідно до зазначеного вище визначенням.

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

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

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

Генератор тестів (ГТ) - вузол мережі Ci, функціональне призначення якого - передача вхідних стимулів і одержання реакции ЛОМ на них з метою тестування і діагностування інших компонентів мережі.

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

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

Диз'юнктивна нормальна форма тестування мережі (ДНФ ТМ) - є булева функція, де терми представляють шляхи в ЛГТМ від вершини ГТ до кожного з інших вузлів мережі, що підлягає тестуванню .

Для структури, представленої на рис.1, булева функція тестування мережі описується рівнянням

(1)

де {Ya, Yб}Y = {0,1}; 1 (0) - ідентифікатор працездатного (непрацездатного ) стану мережі.

Для проектування логічної схеми тестування мережі (ЛС ТС) по ДНФ ТС варто здійснити синтез першої на основі використання примітивних елементів (і/ чи). Схемна реалізація булевой функції (1), що відповідає ЛГТС (див.рис.1), представлена на рис.2.

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

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

Структурний алгоритм умовного діагностування, не дифференцируемый строго на процедури контролю і пошуку дефектів, описується узагальненим рівнянням діагнозу несправностей: де g, g*- еталонна й експериментальна реакції ліній, що спостерігаються; F, T,-- функціонал, що перевіряє тест, наперед задані дефекти.

Використання логічного аналізу визначає елементарну перевірку Pi=g*(T,F,Di) як одержання реакції на обраній лінії ЛОМ при подачі тесту, що перевіряє, T. Перевірка Pi вважається позитивної, якщо в точці контролю i еталонна реакція, обчислена при відсутності несправностей у схемі, дорівнює експериментальної: Якщо ж, перевірка Pi негативна. У загальному випадку стан зондування визначається виразом

Точкою контролю Рi є доступна для спостереження лінія активного чи пасивного устаткування ЛОМ. Два логічних результати перевірки задають альтернативні шляхи пошуку дефекту за структурою чи визначення технічного стану об'єкта: де D0 - справний технічний стан; D - передбачувана область існування дефектів; D+ (D-) - область несправностей, що обумовлена позитивною (негативною) перевіркою Р+ (Р-).

Реалізація алгоритму зворотнього простежування ефекту прояву несправності за структурою мережі орієнтована на послідовне виконання перевірок ліній логічної моделі мережі з метою відновлення її працездатності. Модель несправностей ЛОМ визначена наступною множиною станів об'єкта: ={D0, D1, D2, D3, D4, D5, D6, D7, D8, D9, D10, D11}, де D0 - сегмент мережі працездатний; D1 - усі з'єднання в концентраторі працюють; D2 - помилка з'єднання в концентраторі; D3 - немає з'єднання між сетьовим адаптером і кабелем; D4 - несправний порт; D5 - несправний кабель; D6 - несправний сетьовий адаптер; D7 - несправний ПК; D8 - немає з'єднання між кабелем і портом комутатора; D9 - немає зв'язку між ПК і мережним адаптером; D10 - немає зв'язку між сегментами; D11 - немає зв'язку між сусідніми ПК.

Для викладу стратегії половинного розподілу вводиться вектор моделювання несправної області M = (M1, M2, ..., Mi, ..., Mn), де n - загальне число точок контролю об'єкта діагностування. Підмножина вихідних контактів, що спостерігаються, пристрою позначається у вигляді

Значення координати вектора формується відповідно до виразу;

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

(2)

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

Процедура структурного моделювання.

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

2) Вхідні лінії t підозрюються несправними, якщо існує вихідна дефектна лінія:

При відсутності несправного виходу усі вхідні лінії вважаються справними.

3) При різних технічних станах (справне і несправне) входів-галузей різних вузлів t і f значення лінії розгалуження - стовбура підозрюється дефектним:

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

Процедура вибору контрольної точки.

Для викладання стратегії вибору чергового контакту для зондування ЛОМ кількість одиничних координат у векторі-рядку попередників для точки контролю i матриці Q=||Qij|| досягнень позначається через Ai = card(Qij)| j =1,n; у векторі-стовпці спадкоємців - через Вi = card(Qji)| j =1,n.

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

f = max|i [min (Ai, Bi)].

Якщо існує кілька однакових значень функціоналів f, то для однозначності вибирається точка контролю з меншим індексом i.

У випадку негативної перевірки на лінії Pk область несправностей задається множиною попередників {Ak} поточної матриці досягнень Q=||Qij||, а при позитивної - різницею між вихідною множиною та попередниками для лінії Pk:

Для реалізації алгоритму безумовного діагностування діагностична інформація надана у вигляді багатозначних таблиць несправностей: D=||Dij||, визначеної на безлічі вхідних тестових послідовностей T=(T1, T2, ..., Ti, ..., Tk), для кожної з який заданий вектор-рядок Di=(Di1,Di2, ..., Dij, ..., Din,), що перевіряються ОКН. Координата Dij визначена на алфавіті A={0,1,X,}. Dij=0(1), якщо тест-вектор Ti перевіряє несправність 0(1) на лінії j. Символ X означає одночасну перевірку несправностей нуля й одиниці. Значення Dij= визначає відсутність перевіряються на лінії j несправностей тестом Ti.

Матриця експериментальної перевірки (МЕП) V=||Vir|| приймає значення з множини {0,1}; r=n'+1,n; n' - число невихідних ліній; ny=n-n'+1 - довжина вектора ліній; i=1,k; k - довжина тесту. Координата Vir=1, якщо , Z=||Zir|| - матриця очікуваних двійкових станів ліній, що спостерігаються; Vir=0, якщо Tir=Zir. З огляду на специфіку аналізу структури об'єкта, пов'язану з послідовним моделюванням подграфів ЛОМ, як форму опису структури використовуються списки векторів вхід-вихідних ліній (Xt,Yt), за умови, що j(Ytj=f(Xt)), де ; p - число функціональних ПЭ.

Матриця дійсних дефектів (МДД) M=||Mij||, Mij={0,1}, де Mij =1, якщо дефект Dij не суперечить рядку Vi МЕП, за форматом відповідає структурі ||Dij|| і є змодельованою формою завдання, що обчислюється, графа ліній об'єкта діагностування.

Інакше, при Mij=1 стан лінії j на тесті Ti підозрюється в наявності несправності, що транспортується до виходів, які спостерігаються, і формує реакцію, не суперечливу стосовно рядка Vi. Якщо Mij=0, то дефект (при наявності його в МТН), обумовлений координатою Dij, не здатний створити значення компонентів вектора Vi, тому він повинний бути виключений зі списку підозрюваних несправностей.

У результаті діагностичного експерименту по виходах, що спостерігаються, формується МЕП V=||Vij||. Для кожного рядка обчислюється підграф (рядок Mi) ліній об'єкта, несправності яких можуть сформувати двійковий вектор технічного стану виходів, що спостерігаються, Vi. Побудова таблиці M для заданої матриці експериментальної перевірки V з використанням графа об'єкта засновано на модифікації процедури структурного моделювання, орієнтованої на обробку МТН: стану координат ліній, що спостерігаються, визначаються за виразом іr(Mir=Vir) і не можуть бути модифіковані; координати МТН підозрюються несправними, якщо існує дефектна лінія, що спостерігається: j(Mij(Xt)=1) при j(Mij(Yt)=1); при різних технічних станах вхідних координат стан лінії, що спостерігається, підозрюється дефектним. З урахуванням наведених визначень процедура обчислення станів ліній-координат матриці М - включає два пункти:

- визначення значень зовнішніх виходів, що спостерігаються, як результатів порівняння експериментальної й очікуваної реакцій ЛОМ на тест:

- послідовна обробка примітивів об'єкта методом зворотнього простежування від зовнішніх виходів схеми до входів з метою визначення станів усіх координат Mij на основі правил структурного моделювання.

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

Вектор одиночних константних дефектів Ds визначається векторною різницею між перетинанням координат стовпців матриці Dj, відзначених одиничними значеннями відповідних Mij, і об'єднанням всіх інших координат за стовпцями матриці D. Для виконання різниці між двома координатами Drj\D існують правила: 0\0 = , 0\1 = 0, 0\X = , 1\0 = 1, 1\1 = , X\0 = 1, X\1 = 0, X\X =. Одержання вектора кратних несправностей Dm задається різницею об'єднання координат стовпців матриці Dj, що відзначені одиничними значеннями відповідних Mij, і об'єднанням всіх інших координат за стовпцями матриці D.

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

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

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

Сполучення приведених стратегій діагностування укладається в схему

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

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

Результати проведених експериментів (рис.3) на моделях ЛОМ різних топологий за стратегією, що сполучить послідовне виконання умовних і безумовних алгоритмів (KCE, KDD) пошуку дефектів, ілюструють істотне зменшення максимального числа зондувань (на 22%) у порівнянні з умовними (CE - зворотнє простежування, DD - половинний розподіл) при глибині діагностування до компонентів робочої станції.

Операційна система - Windows 95, 98, NT4.0. Обсяг пам'яті для EXE-модуля - 220 Кбайт. Обсяг вихідного тексту мовою З - більш 100 Кбайт. Кількість програмних модулів - 12. Середній година тестування сегмента (30 ПК) - 0,5 години. Час побудови алгоритмів пошуку дефектів - менш 1 с.

ВИСНОВКИ

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

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

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

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

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

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

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

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

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

1. Абу Занунех И.М. Халиль Структурно-логические модели локальных вычислительных сетей для контроля и поиска дефектов // Радиоэлектроника и информатика. - 2000.- - № 4. - С. 83-89.

2. Хаханов В.И., Ханько В.В., Абу Занунех Халиль И.М. Моделирование и тестирование корпоративных сетей для анализа надежности их функционирования // Управляющие системы и машины.- 2000.- № 5-6. - С. 88-100.

3. Ханько В.В., Абу Занунех И.М. Халиль. Дефекты локальных сетей и средства их диагностирования.- АСУ и приборы автоматики.-- Харьков: ХТУРЭ. - Вып.110. - 1999. - С. 88-104.

4. Хаханов В.И., Ханько В.В., Абу Занунех И.М. Халиль. Модели неисправностей корпоративных сетей и формулировка задач их диагностирования // Радиоэлектроника и информатика. -1999. - № 4. - С.49-56.

5. Хаханов В.И., Сысенко И.Ю., И.М. Абу Занунех Халиль. Проектирование тестов для структурно-функциональных моделей цифровых схем // Радиоэлектроника и информатика. - 1999. - №.3. - С. 51-59.

6. Хаханов В.И., Ханько В.В., Бабич А.В., Абу Занунех И.М. Халиль. Проектирование моделей локальной вычислительной сети для решения задач диагностирования // Радиоэлектроника и информатика. - 2000. -- № 2. - С. 81-85.

7. Хаханов В.И., Абу Занунех И.М. Халиль, Егоров А.А. Булева форма графовых моделей для описания цифровых систем и сетей // АСУ и приборы автоматики.- 2000.- Вып. 113.- С. 142-148.

8. Скворцова О.Б., Побеженко В.В., Алаиддин Одех С.А., Абу Занунех И.М. Халиль. Методы моделирования цифровых устройств. Материалы пятой международной конференции "Теория и техника передачи, приема и обработки информации".- Туапсе.- 1999.- Харьков: ХТУРЭ.- 1999.- С. 472-474.

9. Hahanov V.I., Babich A.V., Abu Zanuneh I.M. Halil. Desining of LAN models for diagnosis problem solving.- The Experience of Designing and Application of CAD System in Microelectroncs.- Proceeding of the VI-th Conference CADSM 2001.- Lviv - Slavsko.- P. 307-309.

10. Бабич А.В., Ханько В.В., Абу Занунех И.М. Халиль, Дробязко О.А. Модели неисправностей корпоративных сетей и формулировка задач их диагностирования. Материалы 13-й Международной школы-семинара "Перспективные системы управления на железнодорожном, промышленном и городском транспорте. - Алушта.- 2000. - Харьков: ХарГАЖТ. - 2000. - С. 95.

11. Хаханов В.И., Бабич А.В. Абу Занунех И.М. Халиль. Проектирование моделей локальной вычислительной сети для решения задач диагностирования. IV городская научно-техническая конференция “Актуальные проблемы современной науки в исследованиях молодых ученых Харьковщины”. - Харьков: ХГУ. - 2001. - С. 85-86

12. Скворцова О.Б., Бедратый Р.В., Абу Занунех Халиль И.М. Алгоритмы диагностирования макродефектов в логических схемах. VII международная научно-техническая конференция “Информационные технологии: техника, технология, образование, здоровье” MicroCAD-99.- Харьков.- ХГПУ.- 1999.- С. 190-192.

АНОТАЦІЯ

Абу Занунех I.М. Халiль. Розробка моделей і алгоритмів діагностування при проектуванні локальних обчислювальних мереж.- Рукопис.

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

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

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

Ключові слова: локальна обчислювальна мережа, умовне і безумовне діагностування, пошук дефектів

АННОТАЦИЯ

Абу Занунех И.М. Халиль. Разработка моделей и алгоритмов диагностирования при проектировании локальных вычислительных сетей.- Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.12 - системы автоматизации проектных работ.- Харьковский государственный технический университет радиоэлектроники, Харьков, 2001.

Работа посвящена разработке моделей и алгоритмов диагностирования локальных вычислительных сетей и их компонентов на основе последовательного применения методологий безусловного и зондового поиска дефектов для уменьшения временных и материальных затрат восстановления работоспособности ЛВС.

Объект исследования - локальная вычислительная сеть и ее компоненты, представленные активным и пассивным оборудованием в виде серверов, рабочих станций, кабельной системы, рассредоточенных в пространстве.

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

Методы исследования: булева алгебра, теория множеств, кубическое исчисление - для описания моделей и процедур тестирования, теория графов - для структурно-логического описания поведения сети, техническая диагностика - для контроля и поиска дефектов, языки VHDL, C++ - для программной реализации алгоритмов диагностирования.

Получены следующие результаты, выносимые на защиту:

1) Математическая модель ЛВС на основе использования булевой алгебры, усовершенствованная для аналитического и компактного описания структуры и логики работы сети с целью обеспечить возможность генерации тестов проверки исправного состояния и моделирования неисправностей.

2) Модификация алгоритмов безусловного диагностирования, обеспечивающая возможность поиска дефектов в ЛВС различных топологий на основе использования многозначных таблиц неисправностей и структуры сети в целях минимизации области подозреваемых дефектов.

3) Модификация алгоритмов зондового поиска дефектов, обеспечивающая возможность построения процедур диагностирования в подозреваемой неисправной области ЛВС на основе использования топологической структуры сети, в целях минимизации числа зондирований с наперед заданной глубиной диагностирования, позволяющая уменьшить время восстановления работоспособности сети.

4) Разработка и практическое применение программного приложения, релизующего построение алгоритмов безусловного и зондового диагностирования ЛОМ в целях минимизации временных и материальных затрат поиска дефектов и восстановления работоспособности сети.

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

6) Внедрение моделей, алгоритмов и программных средств в учебный и технологический процессы в целях автоматизации подготовки и проведения диагностического эксперимента над локальной вычислительнойсетью.

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

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

Операционная система - Windows 95, 98, NT4.0. Объем памяти для EXE-модуля - 220 Кбайт. Объем виходного текста на языке С - более 100 Кбайт. Количество программних модулей - 12. Среднее время тестирования сегмента (30 ПК) - 0,5 часа. Время построения алгоритма поиска дефектов - менее 1 с.

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

ABSTRACT

Abu Zanuneh I.M. Halil. Model and Algorithm Diagnosys Development for LAN Design . - Manuscript.

Thesis for a candidate degree of technical sciences on speciality 05.13.12 - computer-aided design systems.- Kharkov state technical university of radio electronics, Kharkov, 2001.

The work is devoted to development of models and algorithms of the local area network diagnosing on the basis of sequential application of conditional and unconditional defect search methodologies for decrease temporary and material costs of the LAN service capability restoring. For reaching the purpose the tasks are solved: developments of LAN models based on using of the Boolean algebra, providing possibility of test generation of fault diagnosing; developments of unconditional diagnosing algorithms of the local area network of various topology on the basis of usage of results of fault simulation and network architecture with the purposes of minimization of area of suspected defects; developments of probe defect search algorithm in the local area network on the basis of usage of a topological network architecture with the purposes of minimization of probing control number for installation of the diagnosis; developments of the program application, realizing construction of unconditional and probe LAN diagnosing algorithms with the purposes of minimization temporary both material inputs of defect search and restoring of network service capability.

Key words: LAN, Guided Probe Testing, Fault Detection.

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