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

№

ОфНА ЛЕШ ИНСТИТУТ ПРОБИВ! УПРАВЛЕНИЯ, (автоматом я телекюсагакя)

На правах рухопхсв

КйЕЯДЦЗБ Паяя Алгхсеевяа

УДК 681.32

ВМВДОВЯШ Я РАЗРАБОТКА КЕТОДС8 ШОДШЯОСШРОВАНЙЯ ЮШШЫХ ВЫЧИСЛ5ПЕЯШЫХ СЕТЕЙ

Специальность 05.13.13 - Вычислительные машины,

коишексы, системы ж сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Носква - 1989

/Ъ ) , . . • /

V >-' .'/i '/ -

Работа выполнена в ордена Ленина Институте проблем управления (автоматики и телемеханики) Минприйора и АН СССР *

Научный руководитель: член-корреспондент АН СССР П.П.Пархоменко

Официальные оппоненты: доктор технических наук В.А.Ведешенков,

кандидат технических наук . A.B.Лобанов

Ведущая организация: Дальневосточный филиал НИИ "Аргон*-

.Защита состоится • ^ " г.. в_

.щс} на заседании специализированного совета 9 2 Д002.68.01 ' 'Института проблем управления по адресу: 117342, Москва, Профсоюзная ул., 65.

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

Автореферат разослан "Л " Зеоз/^Хе- 1Э/9г.

Ученый секретарь специализированного совета д.т.н., проф.

В.В.Игнатуценхо

..... /

" ''■»»«! ]

- 0Щ.4Я ХАРАКТЕРИСТИКА РАЕОГЛ

Актуальность темы диеееугашта. Одт;н кз важнейших требований, предъявляемых к распределенным микропроцессорным системам (РМС), и, в "частности, к локалькюл сетям (ЛС), является обеспечение их отказоустойчивости. * Для повышения надежности и отказоустойчивости ЛС чрезвнчайгув важность имеет достоверное репекие задач обнаружения ошгбок и поиска неисправностей, составляющих задачу диагностирования. Сложность и многоуровневое» лскалышх сетей обусловливая! целесообразность прове-дезтя их диагшг'трования на системном уровне. Достоверность подученного диагноза ЛС в значительной степени зависит от правильного выбора диагностических моделей сети, а танке от учета специфики реальных ЛС при построении алгоритмов диагностирования.

Анализ суцествущвх зональных сетей ЭВМ показывает, что практически в Еаэдой действующей сети имеется центр управления, . осучествяящкЯ ее тестирование и получение диагноза. Диагностирование ЛС вкеютплн, по отношению к сети, средствам в ряде случаев прпеияеко, но не всегда оправдано ,т-за у сложения сети, сшшенля ео про и з в одите л ьно ст, $ н необходимости гарантированного обеспеташя надеяной работы этих средств. Поэтому представляет безусловны!! интерес и лвляется актуальной разработка методов диагностирования ЛС средствами самой сети. Существуете, в кастосцее время методы, в основном, носят .-теоретический характер, и вопрос применения полученных результатов _ в реальных системах не является до конца репейным.

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

Цельа диссертационной работы является разработка новьк диагностических моделей локальных сетей производной и ппнной конфигурации; исследование-применения этих моделей для адаптивного диагностирования, а такке построение на основе предложенных моделей алгоритмов са'.годиагностирования ЛС и использование полученных теоретических результатов для разработки диагностического обеспечения реальной локальной сети.

Метод» исследования базируется на применении теории и методов технической диагностики, теории графов, теории множеств, теории вероятностей и комбинаторики.

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

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

Реализация и внедрение результатов. Подученные в работе результаты использованы в договорной научно-исследовательской работе, проводимой совместно Институтом проблем управления в НПО "Промавтоматика", г.Грозный, по проведет® исследований по дальнейшему повышению надежности, быстродействия я определен») целесообразных областей применения локальной управляющей сети.

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

- Ш Всесоюзной конференции по локальным вычислительным сетям ЛОКСЕТЬ-88, г.Рига, 1968 р.;

- ХШУ конференции молодых ученых йнстятута проблем управления, г.Москва, 1988 г.;

- семинарах лабораторий Института проблем управления, г.Москва, 1986-1989 гг.

Публикации. По материалам диссертационной работы опубликованы 4 печатных работа.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и приложения. Общий объем: ^*Тстр., 26 рис., I табл., 168 наименований библ.

ССЩЗРЕШИЕ РАБОТЫ

Во апедстл обосновгшз актуальность темы диссертации, сформулирована цель диссертационного исследования, дана краткая характеристика паучнэй и практической ценное?;: работы.

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

В проблем/ сиетешэго диагностирования К.!С включены сле-дущие вззтгосвязашпте задачи: "построение диагностической модели В'С; выбор способа диагностирования; определение класса неисправностей, подеяарс обнаружению и поис::у; выбор тестов; ...акааяз результатов тестирования; построение атгоритмов дизг-настпроваетя.

Р&ссмотргш каздую из этих задач в отдельности.

Построен и е'даагности ческой неделя РНС. Дяя представления РМС в качестве объекта скстекного диагностирования необходим построить ее мз-емати-чзокуя ¡модель. Базовой моделью шляется графовая модель, предложенная Препарата, Метцом и Ченон (ШП-модель). Идеи, подо-ггешше в основу этой подога, полущШ! дальнейазе развитие в работах многкх авторов. В диссертации цреддонека классификация существующих диагностических моделей по раздал.! признакам: по фор:*е предстазяеннл - на графо-теоретические и алгебраические коделя; ко зкачноэтя алфавита оценки результатов тестирования - на модели с двузначной и многозначной логикой; по стратегпи тестирования - на модели с взашотестированисм модулей л со сравнением результатов тестовых задач; по степени детерминкз- " ка - на детерминированные и вероятностные модели; по свойствам графа системы - на модели, отражающие структуру проверочных связей, структуру тестов и взинаоттгепэния кеаду неисправностей и теста.™. В работе приедим примеры каждого типа моделей. . 1 ,

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

следовательный. D работе рассмотрены разные меры диагностируемое»! , предложенные для параллельного и последовательного диагностирования систем, представленных ШМ-моделью.

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

Определение класса неисправностей, подлежащих обнаружению и поиску. Все существующие диагностические модели рассчитаны на возможное наличие в системе неисправностей трех видов: устойчивых, неустойчивых и гибридных. Характерным для процедуры диагностирования' систем с неустойчивыми неисправностями -является то, что оценка исправными модулями технического состояния 'ко дулей. с неустойчивыми неисправностями может быть неверной. cho обусловливает необходимость повторных выполнений тестов и предъявление более жестких требований к структуре проверочных связей системы. В работе приведены диагностические модели с учетом кандого вида неисправностей.

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

Системный уровень диагностирования прсдеповагает наличие полных относительно заданного класса ноиспра^^я&тей тестов, но ввиду усложнения аппаратуры распределение 'систем построение тестов, полностью проверяющих эту аппаратуру, становится очень сложным и дорогим. "Кроме того, некоторые неисправности проявляются только при наховдении системы "в определенном состоянии. Следовательно, для обеспечения высокой надежности FMC необходимо исследовать задачу их диагностирования неполными тестами. Приведены работы, в которых рассмотрена эта задача.

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

-Б -

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

Анализ результатов тестирования. Данную задачу можно разделить на две взаимосвязанные подзадачи: выбора метода и создания алгоритмов дешифрации • синдрома.

В ШН-иодслм и во многих ее модификациях используется метод сосредоточенной дешифрации синдрома, согласно- которому анализ синдрома выполняется"" в'помощью заведомо исправных' средств, не входящих в диагностируемую систему. Метод распределенной дешифрации предполагает анализ синдрома средствам! самой системы.

Целью работы алгоритмов дешифрации синдрома является нахождение набора неисправных модулей системы, не противоречащего заданному синдрому. Из известных в настоящее время алгоритмов наиболее универсальным является алгоритм Дахбуря, Мас-сона, имеющий сложность 0( ntJ), где п. - общее число модулей системы. Другими авторами предложены более простые алгоритмы, предназначенные для более узкого класса систем и кмер-q»ie сложность 0( IЕI ), где |Е| - число проверЬчннх связей системы.

Построение алгоритмов диагностирования РМС. Алгоритт^диагностирогаз'.ч.'» определяют общую стратегию проведения процедур*1 диагностирования. Условно известные в литературе алгоритмы можно разделить на алгоритмы диагностирования однородных и неоднородных систем. Под однородностью РМС понимается однотипность е; модулей. Естественно, что структура связей системы может существенно влиять на построение алгоритмов ее диагностирования. В работе приведены пр:меры алгоритмов для однородных системе иин-ной, кольцевой, древовидной и произвольной топологией. Следует заметить, что РКС специализированного применения в основном являэтея неоднородными, т.е. состоят из модулей разных типов с разными уровнями надежности л разными возможностями по диагностированию. Однако в литературе главный акцент делается на разработку алгоритмов диагностирования однородных сис- . тем. Алгоритму диагностирования неоднородных систем базирувт-ся на основных принципах организации алгоритмов, созданных для однородных систём.

- б -

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

Во второй главе предложены новые диагностические модели локальных сетей, основанные на сравнении результатов выполнения тестовых задач, полученных однотипными модулями сети. Най-•дены необходимые и достаточные условия ¿"-диагностируемости систем ( ё - максимальное число одновременно неисправных модулей) за один шаг, которые используются для синтеза структур с оптимальным числом связей сравнения. Исследована возможность адаптивного диагностирования локальных сетей.

Метод сравнения является простым, гибким, независимым от . структуры сети и требует незначительной временнсЯ избыточности. Известны работы, рассматривающие диагностирование систем, представленных ПМЧ-моделыо с использование« метода сравнения» В этих системах £ ¿¡Ц"-И/2], где 1а]~ излбольЕво целое, на

превышающее в . В предлагаемой работе исследовано применена© этого метода для диагностирования ЛС, представленных новой диагностической моделью, которая хоропга сочетается с локальными сетями. В данной модели диагностируемая система представлена набором однотипных модулей и, ... , , имеющих возможность выполнить набор тестовых задач J~{ít^ Мощность этого набора зависит от требуемой полнота проверки модулей. Каядый модуль и^Ц вгаолняет задач;: из ынокестеа J и хранит сигнатуры полученных результатов.

Граф сравнения & ~(?-1, £}представляет собой ноерютиро-занный граф, в котором зерзлкаи соответствует модули и(<И, а ребрам - мегаоду.тьше связи сравнения С ,..._/ ,

где г£у представляет связь пар модулей ui и , результаты

которых сравниваются ме^лу собой. Вес *t(j ребра Oy опрег деляется следующим образом: i^j-Oli) , если сравниваемые результаты, принадлежащие модулям «,• и ttj , совпали (не совпали). Синдром систем по результатам сравнения образуется объединением в вектор бзсоз всех ребер. Процедура диагностирования на основе сравнения дает возможность выявлять не только устойчивые неисправности модулей, но и неустойчивые неисправности, есхп они проявляется при выполнении модулями некоторой задачи из множества «Г.

На основе вероятностного- анализа показано, что вероятность получения одинаковых неправильных результатов всех задач мно~-жества J" , обеспечивающего требуемую полноту проверки, парой неисправных модулей - незначительная величина и в предложенной модели принимается равной 0. Учитывая сложность задач я достаточную мощность множества J , считается, что наличие а модуле '• неисправности из заранее определенного класса рассматриваешь? неисправностей проявляется во время выполнения хотя бы одной задач:» JJ £«7". Следовательно, получение в графе сравнения ребра с весом 0 однозначно определяет исправность модулей, соот- . ветстЕугщих инцидентным этому ребру вершинам. Получение реора с весом I свидетельствует о наличии хотя бы одного неисправного модуля в сравниваемой паре.

Исследованы возможности диагностирования систем, представленных приведенной выше моделью.

Утверждение 2.1. Система S , состоящая из /г модулей и представленная графом С = ( И , С)» является одноиагозо i -диагностируемой, где £ — z((r) - п-- 2 ^

Утверждение 2.2. Для i -диагностируемое!1!! системы S » £ £ zfGJ, представленной графом сравнения при т(&)^тг , необходимо выполнение следующих условий:

I. IrMIbt, Vvc€ и ; г. r(ui)*r(uj) , ,

где Г(и;} ={uj: c,j eCJ у /ffui)/ - мощность гкэяеетеа

Следствие 2.1. Система S , прсдстг.^.tv:nm громом ераате-ния &-(21,С), является ¿"-диагностпкуег:сЯ га один саг при i - п-2 тогда и только тогда, когда гргф €■ ползай?. ■ Ввиду того, "что при сястекнон дпагкостяровипп! ЛС ва>шое . зкапекяе имеет сокращение времекл, еп&денного на диагности-рагжпз, ясследовапн еоакоетветя доагкоетароййняя систем, пред-

ставленн"х приведенной моделью и неполный графой сравнения. Рассмотрен случай, когда V(С) -п -3 .

Утверждение 2.3. При т(С) , необходимыми и достаточными условиями i -диогностируеиости за один шаг системы S , представленной графом сравнения при Z (G) - п. - 3 , являются следующие:

l.lrfUi)M tVu,eU.

2. Г(ч)ФГ(и,), Vu^ujtll ;

3. Г(1ц)® r(uj) Ф u¡ U Uj, V щ ,uj e U , где

Г(ч!<в r(uj) г(и,)) U(r(uj) \ r(uj).

Условия утверждения 2.3 были использованы для установления структуры проверочных связей (связей сравнения) в одноша-гово i -диагностируем!':: системах. Согласно следствию 2.1 при { - п.-2 граф должен быть полным. В случае t é¡ п~3 граф С должен бить по меньшей мере i -связным. Ниже приво-.•дятс1? правила синтеза структур для разных значений п и i .

1. Пусть п. - нечетное число, i - четное, t - 2 . Организуются связи мезду модулями ( U¿, u¡)€ Z¿ ; i - i £ /

J 4 i + í (moc/n)' ¿ , J ftj. .

2. Пусть п. и i - нечетные числа, t ~ 2 1. Организуются связи сравнения мевду модулями { v¡ ,uj ) е IÍ _

l-&¿j{t + l (trtoJ п.) , и для модулей с номерами i /2}t

(UiJUj)eZ¿:j=¿*(n-í)/2 . ¿,j-.{s7¿} .

3. Пусть n - четное число, i - нечетное, t-2& + i . Организуются связи сравнения ыевду модулями ( Щ :

L-íájú Íj+_& (мое/п.) и jz:L*n/2 {mocf п.)-i n.}.

Структуры, построенные для случаев I и 3, являются оптимальными, т.к. общее число связей сравнения составляет nt¡2.

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

ограничений» представляет определенный интерес. Характерной ссобенлостьэ описошой втае модели является возможность однозначного определения кеправяоета кодуля, соответствующая вершка которого шпщдектна ребру с весом 0. Этот факт мокно эффективно использовать для решения первого этапа задачи адаптивного диагностирования, состоящего в обнаружении хотя бы одного исправного модуля.

В работе предложен модифицированный вариант описанной зыпе модели со сравнением и исследованы возможности решения задачи адаптивного диагностирования. По модифицированной модели в графе сравнения -(11г С')вершинам соответствуют модули Щ,

I -{4, п.], а дугам - межмодульные связи сравнения = ■=(..., , ... J, где является совокупностью неори-

ентированных связей мекду тройкой модулей щ , г/,- и ^ , -- результаты работы которых сравниваются мевду собой. В каздой тройке с^й выделяется т.н. средний модуль, скалем Ну , которому остальные два модуля Ис я и^. пересылают собственные сигнатуры. Связь Сс& графически представляет?^ в виде дпух ребер Г/у и . Модуль щ цо связка Cij и ^ проводит сравнение результатов модулей тройки и выясняет веса связываниях их ребер , , Сщ . Следовательно, вес ребра С^ г:о~е? устанавливаться без реального использования связи содузгеп Щ ' и Щ путем непосредственного сравнения еоотпетствущт* результатов в среднем модуле и,- . 2то позволяет уменьшить общее число межмодульных обменов, что и является основной причиной рассмотрения модифицированной модели со • сравнением. Заметим, -что каждый модуль тройки Ц-, е,- , щ одновременно шнет входить в состав других троег., ь которых любой из них ксиет выступать в качестве среднего модуля. Аппаратное и'программное обеспечение всех модулей, задействованное в операциях сравнения сигнатур, долено быть загедсмо исправным и' следовательно, получаекыз веса ребер - достоверный!, \,.2Г.'.о-дульные связи такте считается исправшмть

В еноте:'.е, представленной модифицированной модельа со сравнением, можно обеспечить ^ -диагностируе:... егь„ £ £х(С)% при Г (СУ . При = п-2, гак п презда, синдром скс-

тегы долг.еп быть полным. Рассмотрен случг.3, когда г(0'] =п. З при неполном синдроме.

Исходя 'пз особенностей адаптивного диагностирования и рассматриваемой гяд&Т.зцзрэЕгяной коделя со сравнением, для выяс-

«

нения технического состояния системы в целом, необходимо обнаружить в графе С одно ребро с весом 0. Время, затраченное ' на решение этой задачи и, следовательно, на диагностирование системы в целом, в значительной мерс зависит от выбранного покрытия графа системы тройками вершин. С учетом того, что при £ - п-3 не менее, чем 3 любых модуля могут быть исправными, математически задача определения необходимых межмодульных связей сравнения формулируется следующим образом: задано множество п, вершин Ы = {щ , ... , Осуществить мини-

мальное покрытие множества Н. тройками вершины так, чтобы выполнялось условие: в любой тройке хотя бы две вершины связаны между собой.

По-видимому* в общем случае поставленная задача является МР -полной и может быть решена, на языке таблиц покрытий путем получения минимальны* решений известными способами. В работе д9ны не. требупцие полного перебора предложения по построению графов' с требуемыми свойствами, хотя и не всегда минимальных по числу связей.

На заданных п. ( п ьЗ) вершинах строятся треугольники, не имеющие общих ребер. Назовем такие треугольники независимыми. На рис.1 приведен пример построения независимых треугольников для п,ш 5. Связи между модулями, не используемые ■

Рис.1. Пример независимых треугольников для п.ж 5.

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

гсм. Подучен простой алгоритм решения задачи для случаев, когда число модулей кратно 3, т.е. п. - 3 & , & * 2,3,... . Суть предложенного алгоритма построения графов, в которых гарантируется получение хотя бы одного ребра с весом 0, состоит в следующем: для 4 -4, разделить все множество вершин на Г&/37 число подмножеств (при выделить два подмно-

жества), мощности которых кратны 3, а путем построения независимых треугольников получить полные подграфы (с учетом от- " сутствуифк ребер). При неполучении ребра с весом 0 выделить тройки подмножеств и построением независимых треугольников строить полные подграфы на вершинах двух подмножеств в тройке.' Выделение троек подмножеств продолжить до получения искомого ребра с весом 0. Приведено детальное описание алгоритма для п. = ¿6,9,12,15^ .

На ряс.2 показан пример графа для /1=9.

Рис.2. Пример графа, игкщего хотя одно 0-ребро, для л»9,

Оценена оптимальность полученных структур по числу сея-зей сравнения. Обозначим одело независимых треугольников, построенных на п вершинах, . Анализ юкгзииает, что верхняя граница значения пря кспользосании припеде!по-но еылз алгоритма определяется формулой:

После креобразовштй этого шракения с учатоы условия об

"отсутствий" одного ребра в каждом треугольника, верхняя гра-

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

кратном 3, равна //< üdsglii. Анализ показывает, что зта

J

оцакка пглвгэрмо, соетед&ет с оцегкой» полученной для адаптивно даагкеатийгешх сиетеы, представленных ЕШ-ыэдеяьэ.

rgaae раешатривавтея однородные ЛС с широко paaapaeTpiKéssioa тссологкгй - шишей. Предложена диагностическая модель здких сетей, пгпольаущал описашшй в предыдущей главе способ пнтерпретацкк раэультатов взшшояроверхи модулей и на основе stoSt иодсан разработьна алгоритм'диагностирования.

Однородность ьбэнеигов и евш&н топологий обуеловливзот определенную специфику сота, шгадуа целесообразно учесть при разработке ее диагностического обеспечения. С одной стороны, однотипность модулей позволяет применить одинаковые тестовые 2сгдо5стЕйя днл их дягпгасЕфовьния. Кроме того, можно вскеэ-чкть необходимость хранения ехалонных ответов на тестошо воздействия. С датой сторона, цри представлении сети с гокоцгл) грсфзвой модели винная организация соответствует далноеваанкфг граф- с двунаправленные: дугаа. Таяка образом, каядай коду«ь сети потенциально имеет возможность црзварять лэбой друга'* uo-дуль.

Диагностическая модель рйсскатраьгетж сетей прздетаакг-ка чзтвархой: ( а , «fs ír3 » Здесь:

&jh j - «hcsssctso расшяршшнк шше-правностса сета, где - неисправность модуля « .. .»Д. -неисправность иедаая Ч,. &1адовагеяьпо, AF/st* Под кеас-прагаовтьэ асийкаэтея vasna модуля цравияьно выполнять

возложенные на Héi'o функции»

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

совпадают с правилами, принятыми в ШЧ-ыодели.

!&<•••< массив возможных совокупностей одновременно присутствующих в системе неисправностей. На основе исследования свойств сети, представленной рассматриваемой диагностической моделью, установлено, что л* ~ / -р-п -1. Массив *Р можно представить в виде ыатрягр размером т. я п., в которой строкам соответствуют совокупности неисправностей , £ -{4 у а столбцам неисправности £ , V - матрица технического состояния сети размером п *Г1,-.строка?! и столбцам которой соответствуют модули «£ , Элемент Уц матриц представляет собой оценку технического состояния'модуля и} модулем «; . Следовательно, строке I матрицы V соответствует п. -разрядная вектор-строка V} , отражающая техническое состояние сети по "мнения" модуля и,- , а столбцу J - п. -разрядный вектор-столбец ^ , представляющий оценку технического состояния модуля

всеми остальными модулями.

С учетом особенностей элементов предложенной диагностической модели тоес сфорлулиро я .-ни принципы, положенные в основу диагностической процедуры:

1. Полный диагностический граф сети дает возмозетость каждому модулю провести проверку любого другого модуля сети.

2. Поправке модули правильно оценивают техническое состояние сети.'

3. Оценка технического состоя:ня сета неисправными модулям ыозет быть неверной.

4. Каждый модуль считает собственное техническое состояние испрапныи.

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

6. Рассматривается только устойчивая неисправности моду" лей. .

7. В ходе диагностической процедуры предполагается неиэ-аекнкм тксге!~сс:го.з состояние сети, т.з. ис:<лгчается появление кс2нх уетойсшсг нзиспр^хкостеЗ.

8. Лрзглолаг&этея, что обз^тй канал сета - исправен.

Наследована диагностические возможности сети, представленной описанной вше моделью с учетом принятых принципов шстроашш диагностической процедуры. Установлены необходимые и достаточна© условия Ь -диагностируемое™ сети при п ъ3 а Ьйп-2.

Определим поразрядную операцию кубического пере сечена л

двоичных векторов следущиы образом:

0П0-0, 1ПО-0,

0П1 » 0, 1П1.1,

где 0 - пустой символ.

Кубическое перасеченае рщх п-разрядаси дзоичшх век-С к е> определяется еяедугацж! образом:

с* П с3 = 0 , если хота бы для одного разряда . % П

€ГПС- (с/Пс/, С* ПсХ) с противном слу-

чае.

Два иодугя (¿¿к Ц/ одинаково оценивает техническое состояние сети тогда :: только тогда, когда соответствующие п. -разр-^ише дзоичные векторы \{ и матрицы V совпадет, т.е. выполняется условие:

И

Приведенное усяо'вие использоезно для-доказательства следующего утверждения.

Утверждение 3.1. Необходимая и достаточны* условлен для епределешш сущестпукцой в системе совокупное?:; неисправностей , /Ч '"Уяедязгея наличие в штряце У хотя бы двух векторов и Ь^ , удовлетвор/ау-х условна:

Уг ПЦ * 0 ,

Доказана следующая леагма: Б катрйцз V огрстаует ие более одного ьгкоаестаа совпадашщ векторов.

На основе этой лемггы и с учетом принятых принципов построения диагностической процедуры доказываются следущне утверждения:

Утверждение 312. Сеть, содернащая ^ 3 абонентов и имеющая шинную топологии, представленная моделью (, , <р , V), диагностическая процедура для которой построена на основе принципов 1-8, является t -диагностируемой щи

Утверждение 3.3. В ¿-диагностируемой ( {-бп-2) сети, представленной диагностической моделью ( &, 3" % Ф , V), достаточным для однозначного определения исправности модуля и,- , является выполнение .следующего условия: для

соответствующего вектор-столбца V4 матрицы V выполняется: ^ Уу = 0, где V - знак логической операции "ИЛИ".

На базе приведенной диагностической модели предложены 4 алгоритма диагностирования ЛС, имеющие слоиность О (п.3) л состоящие из следующих основных шагов:

1. Инициализация выполнения и выполнение тестовых программ параллельно' всеми модулями 1С.

2. Широковещательное последовательное распространение полученных результатов на тестовые программы X всеми модулями с//,

3. Параллельный анализ полученных результатов в каздом модуле гц&и , ¿-/У,/г/на основе кх сравнения с собственными результатам! тестовых программ. При совпадении сравниваема величин, соответствующие модули считаются исправными и получают оценку.О. В противном случае ставится оценка I. Таким образом, каддый модуль гц £ ^ получает вектор У1 , отражается "мивйие" о техническом состоянии сети.

4. Широковещательное последовательное распространение векторов всеми модулями

5. Параллельное создание и анализ «уяряци V в каждом

модуле г/, е Н. Выдача результатов дкапгастирозашя операто-« •

В алгоритмах предложены разные правда сиздазмя а анализа матрицы У.

Положительным свойством алгорятмоз является то, что в тгх гЗДеятивио кспользочг-зяз предосгае.-лг;г;:о локалыплп сетя-кя вез»5»астя! пояносптакость и пгфог.с^сцзл'еаьни« передачи пта гочгной чюпалегяя, санэтестароЕакяв аЗокпнтскс.1 шшияату-ТЯ1, одкоро.пиость бозоталозз'пя сцомка ¿хзульта.оь

•тссткрсяг:п.т. Требусипе струг-гур::^; кз.&ло<;нсз?:> - аб-рсбатег^ет-ет!! ж^сгагц/п: дгг.т гтол^ ••.'"„•:! :а точного диагноза сослепа (по-5от.кякоста) до Z ЛС, с:с*о:гзвс из но-бопьгягч *!иеха модулей, вероятное:-ь излучеюл оператором не-едкоенг-торо дизгноза растет, т.к. рс-алько растет вероятность совладения векторов технического состояния, прикадле-

зкацих неиспрашшм иодугям.

В четвертой главе разработано диагностическое обеспечение (ДО) локальной управляющей сети СЛУС) Приоритет", создаваемой в Институте проблей управления совместно с НПО "Промавтоыаткка" (г. Грозный). На основе рассмотренных в предыдущей главе теоретических моделей и алгоритмов диагностирования, предложены процедур! диагностирования ЛУС.

ШС "Приоритет" имеет айкнув топологии. В качестве канала используется ксазси&яьшй кабель длиной до 3 кы, мак-скзишгьноз число подключаемых абонентов - 120. В качестве абензшюв используются ыикро-ЗВМ "Электрснкка-60", которые подключаются к каналу через сетевые контроллера (СК). Для связи абонента с собственным СК используется двунаправленный программно-управляемый байтный интерфейс ИН1Р, через который передаются команды, данные и признаки завершения.

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

В сетевой режиме осуществляется взаимосвязь модулей друг с другом чорез канал. В паузах иевду сеансами связи осуществляется сашдиагкостирзвагше СК.

Определен класс подлежащих обнаружен:© дефектов. Обеспечивается проверка аппазжув* абонентов; С1, какала езязи, программного обеспечений я абонентов, задействованного при интерактивных, грушояшг, ппрогсвещатслышх взазаодействиях модулей» а тплгш ыехагзшга кркоратстнаго доступа к каналу при одинакова и разных приоритетах модулей. Таким образом, класс дефектов, обнаруживаемых в результате работы предложенного ДО, включает аппаратурные дефекты абонентов, СК, линий связи, а также ошибки программного обеспечения сети и абонентов, нарушающие правильную организацию различных связей через канал.

С учетом многоуровневости ЛУС "Приоритет" предложено процедуру ее полной проверки разделить 3 основных этапа:

1. проверку абонентов в автономном режиме;

2. проверку СК в автономном режиме;

3. проверку модулей в сетевом реяиме.

Каждый следующий этап проверки проводится с участием аппаратурных и программных средств, проверенных на предыдущих этапах.

Проверка абонентов в автономном реяиме состоит -в выполнении стандартных тестовых программ микро-ЭВМ "Электроника--60й.

На втором этвпе проверяются только те СК, абонентская аппаратура которгк успешно прошла проверчу в автоношоы ре-

Проверка СК в Автономном реяиме включает реализацию тестовых микропрограмм ОС, входшцос в программное обеспечение СК, и тестовых nporpaj.ni, предназначенных для проверки правильности выполнения команд автономного реяима ОС и тем самым задействованной при выполнений этих программ аппаратуры СК.

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

Процедура проверки модулей в сетевом режиме построена по принципу распределенного ядра и из-за сложности функций, реализуемых в этом режиме, разделена на 3 подэтапа:

а) проверка интерактивных связей;

б) проверка групповых (широковещательных) связей;

в) проверка приориетного доступа к каналу при одинаковых и разных приоритетах модулей.

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

Модули, успешно пропедизе все три этапа пронерок, считается работоспособными.

На осипве предложенного диагностического обеспетапм.

сформулированы общие рекомендации для построения процедур длагдастарэвения ЛС. *

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБЭТЫ .

В работе разработаны и исследованы новые ;ц:агностичес-модели к на кх основе ноше оягортзы семодиагностиро-вания ЛС, учитеваащих специфику послед}!:ж как объектов диагностирования, б частности:

1. Выполнена классификация и д&ны характеристики методов и задач диагностирования распределенных микропроцессорных систеи (РЕЙ), достаточно полно схватывающих проблему системного диагностирования НС.

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

3. Для предложенной модели со сравнегаем результатов тестирования пар взаимодействующих модулей получены нзобхо- . димые и достаточные условия ¿■»дивтпостируемостя систем га один пат.

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

5. Предложена модифицированная модель, основанная та сравнении результатов работа специально вцдшшгшх троек модулей, н исследозаиа возмоеность рогекия задач:! гдапткгзлго диагностирования для систем, представкаЕшг отоЗ модели. Получена оценка Еерхней границы числа зедййеггепапгл: связей сравнения в предложенных структурах. ■ . .

6. Рассмотрено диагностирование однородных локальных сетей с шинной топологией. Предложена диагностическая модель и установлены необходимые и достаточные условия £ -диагностируемое™ таких сетей при Ъ ¿п.-2 , п , На основе этой модели предложены алгоритмы диагностирования, икевщие сложность 0(п *), в которых использованы предоставляемые локальными сетями возможности: полносвкзность п внроковегцатеяьиые передачи при пинной топологии, самотестирование абонентской аппаратуры, однородность тестов, безэталонная оценка результатов-тестирования.

Полученные теоретические результаты использованы ддк

.. -199

построения диагностического обеспечения реальной ДС промыя-ленного применения, создаваемой совместно Институтом проблем управления и НПО "Промавтоматика" (г. Грозный).

Справка о внедрении приведена в приложении к диссертации.

Основные результаты, полученные в диссертации, опубликованы в следующих работах.

1. Микеладзе М.А. Методы идентификации неисправностей для диагностируемых систем //Применение методов и средств технической кибернетики. - Тбилиси: Груз, политех, ин-т им. В.И.Ленина, 1986. - 8 (305). - С. 23-29.

2. Микеладзе U.A. Об организации самодиагностирования вычислительных систем//Применение методов и средств технической кибернетики. - Тбилиси: Груз, политех, ин-т им. В.Оекина, I98S. - » 8 (305). - С. 29-34.

3. Микеладзе М.А. Диагностирование локальных сетей с аикной топологией// Локальные вычислительные сети: Тезисы докладов третьей Всесоюзной конференции ЛОКСЕТЬ-88. - Рига: Институт электроники и вычислительной техники АН Латв.ССР, 1988. - Т.2. - С. 25-27.

4. Микеладзе М.А. Диагностирование однородных локальных сетей// Рук- дел. в ВИНИТИ, 1989, П 6642-889.