Устройство для исследования сетей

 

О П

ИЗОБРЕТЕН ИЯ

Союз Советских

Социалистических

Республик (tt> 717787

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву(22)Заявлено 03.10.77 (21) 2529911/18-24 (5) )Щ. Ц,д

6 06 Ь 7/122 с присоединением заявки Рф

Веудеретвениьй канитет

СССР яв делам изееретеиий я еткрытвя (23) Приоритет

Опубликовано 28 02.80 Бюллетень М7

Дата опубликования описания 25.02.80 (53) УДК 681.333. (088.8) А. Г. Додонов, О. Н. Голованова, В. А. Москвич, Я. Я. Фенюк и И. В. Федтов (72) Авторы изобретения (Институт электродинамики AH Украинской ССР

1. (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ СЕТЕЙ

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

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

Известно устройство для моделирова10 ния экстремальных путей на графе, которое выполнено на логических элемен-, тах, соединенных между собой в соответствии с структурой системы, и вычисли15 тельный процесс в них имеет аналоговый характер. Такое устройство обладает вы/ соким быстродействием, простотой и наглядностью процесса решения, алгоритм функционирования полностью или частич20, но заложен в их структуре, они прост ив обслуживании, имеют большие возможности резервирования и замены элементов fl).

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

Из известных устройств наиболее близким к изобретению по технической сущности является устройство, соpep- жащее генератор импульсов, выход которого подключен к первому входу блока управления, первый выход которого соединен с входом распределителя, выходы которого подключены к первь м входам моделей узлов, модели ветвей, блок ини подключен к выходу второго элемента задержки, первый вход которого соединен с выходом четвертого элемента И, второй вход которого подключен к выходу элемента ИЛИ, второй вход которого соединен с вторыми входами первого и шестого элементов И и подключен к первому выходу первого триггера, второй выход которого соединен с третьим входом пятого элемента И„. четвертый вход которого соединен с третьим входом шестого элемента И, с вторым входом второго элемента И и подключен к второму выходу третьего триггера, выходы

15 ° второго "пятого и шестого элементов И являются соответственно пятым, первым и третьим выходами блока управления, выход генератора одиночного импульса соединен с вторым входом первого триг30 гера, второго элемента задержки и третьего элемента И и является четвертым выходом блока управления, выходы третьего и восьмого элементов И подключены соответственно к второму и третье25 му входам второго триггера.

На фиг. 1 приведена блок-схема устройства; на- фиг. 2 — функциональная

: схема блока управления.

Устройство содержит модели 1 ветвей, генератор 2 импульсов, блок 3 управления, блок 4 индикации, модели 5 ,узлов, наборное поле 6, распределитель

7 импульсов, многовходовый элемент

ИЛИ 8, Каждая модель 1 ветвей содер35 жит формирователь 9 временного интервала, триггеры 10 и ll, элементы И

12- 15, инвертор 16, элементы И-НЕ

17 и 18, элемент 19 индикации, диоды

20 — 22, полюса 23-30, моделей выходы 31 моделей узлов выходы и входы

I. i.

32-39 блока управления вход 40 и выходы 41 распределителя, входы 42 и выходы 43 моделей 5 узлов, выходы 44-

45 46 генератора импульсов, входы 47 и 48 блока индикации.

Ьлок управления содержит триггеры

49-51, инвертор 52, элементы И 5360, элемент ИЛИ 61, элементы 63 и р 64 задержки, генератор 65 одиночного импульса.

Устройство работает следующим образом.

В исходном состоянии, перед решением задачи на устройстве, модели 1 ветвей и модели 5 узлов скоммутированы между собой на наборном поле 6 в соответствйи с топологией графа. В формирователи 9 временных интервалов моделей 1 ветвей

3 717787 4 дикации и дополнительные логические элементы (2).

Известное устройство не обеспечивает достаточную точность анализа систем сетевой структуры.

Пелью изобретения является повышение точности устройства, Поставленная цель достигается тем, что в устройство введены элемент ИЛИ и наборное поле, первые группы входов и выходов которого"соединены соответственно с первыми выходами и вторыми входами моделей узлов, вторые выходы которых подключены к входам" элемента

ИЛИ, выход которого соединен с вторым входом блока управления, третий вход которого подключен к выходу наборного поля, вторые группы входов и выходов которого соединены соответствэнно с первыми выходами и входами моделей ветвей, вторые, третьи и четвертые входы которых подключейы - соответственно к второму, третьему и четвертому выхо дам блока управления, пятый выход которого соединен с одним "входом блока индикации, другие входы которого подключены к вторым выходам моделей ветвей, пятые и шестые входы которых соединены с группой выходов генератора импульсов, кроме того блок управления содержит элементы И, элемент ИЛИ, триггеры, элемент НЕ, элементы задержки и генератор одиночного импульса, входы которого подключены соответственно к выходам первого элемента И и элемента задержки, вход которого соединен с перBbIMH входами второго и третьего элементов И и подключен к выходу элемента НЕ, вход которого соединен с пер-вым входом первого триггера и является вторым входом блока управления, первый вход которого подключен к первым входам четвертого и пятого элементов И, второй вход которого соединен с первым входом шестого элемента И и подключен к первому выходу второго триггера, второй выход которого соединей с первыми входами седьмого элемента И и элемен- та ИЛИ и является вторым выходом блока управления, второй вход седьмого элемента И соединен с первым входом восьмого элемента И и является третьим входом блока управления, второй вход восьмого элемента И подключен к первому выходу третьего триггера, первый вход которого соединен с выходом седьмого элемента И, второй вход третьего триггера соединен с первыми входами второго триггера и первого элемента, И

25

Если граф составлен и набран правильно, и не произошло отказа ни в одной из моделей 1 ветвей, то через некоторое время на выходных полюсах 29 моделей 1 ветвей, образуюших конец графа появляется сигнал логической единицы, который свидетельствует об отсутствии ошибок. Этот сигнал через вход 38 блока 3 управления поступает для останова всего устройства. В противоном случае, если в решаемой сети есть логические ошибки, такие как замкнутые контуры,, тупики, или произошел сбой в одной или нескольких моделях ветвей, сигнал в конце графа не появляется. Как указано

4О на фиг. 2 в графе будет граница, сосостояшая из несформированных узлов, блокируюших достижение конца графа.

Эта граница будет иметь всегда место, если не сформируется хотя бы одна ветвь

45 или узел из-за вышеуказанных ошибок.

5 71 записана в импульсной форме информация о длительностях ветвей. Триггеры всех моделей 1 ветвей сброшены в исходное нулевое состояние.

При подаче сигнала логической единицы с выхода 32 блока 3 управления на шину решения задачи о длинейшем пути на выходах 29 моделей 1 ветвей и на выходах 31 моделей 5 узлов будут сигналы нулевого логического уровня. После подачи сигнала решения задачи о длиннейшем пути, запускаются формирователи

9 временного интервала моделей 1 вет- вей, принадлежаших началу графа. Формирователи 9 временного интервала запушенных моделей 1 ветвей, отработав их длительность, со своих выходов выдают сигналы логической единицы, которые через элементы И 12 поступают на единичные входы триггеров 10. Сит папами логической единипы и единичных выходов триггеров 10 устанавливают ся в единичное состояние триггеры 11.

Перебросом триггера 11 меняется на ноль сигнал логической единицы с его нулевого выхода и входа элемента

И-НЕ 18, подключенного вторым входом к шине решения задачи о длиннейшем пути. На выходе элемента И-НЕ 18 появляется сигнал логической единицы, который поступает на подпор диода 21.

Диоды 21 моделей 1 ветвей, соединенных вместе своими выходными полюсами, образуют логическую схему И. Резисто- . ром этой схемы будут параллельно соединены выходные сопротивления элементов И-НЕ 17 или резистор на входе соответствуюшей модели 5 узла. Выходные полюсы 29 соединенных вместе моделейй 1 ветвей являются выходом скомму- ртированной схемы И и подсоединяются к входному полюсу 40 модели 5 узла. Когда срабатывают триггеры 11 всех моделей 1 ветвей, входящих в данный узел, на выходе 40 модели 5 узла появляется сигнал логической единицы с выхода вышеописанйой схемы И. Через выходной полюс 31 модели 5 узла единичный сигнал передается на входные полюсы 23 моделей 1 ветвей, исходяших дальше из данного узла. Но модели 1 ветвей, соединенные в данном узле, срабатывают не обязательно одновременно. В тех моделях 1 ветвей, которые срабатывают раньше других, на выходных полюсах 29 присутствует нулевой логический уровень, который через инвертор 16 поступает на вход элемента И 13 как разрешение

7787 6 на прохождение тактовых импульсов через элемент И 13, и сигналом логической единицы с выхода этого элемента происходит возврат в нулевое состояние три гера 10. Как только срабатывает модель 1 ветви, формируюшаяся последней в данном узле„ на входе 40 модели 5 узла и выходных полюсах 29 моделей 1 ветвей, подключенных к нему, появляется сигнал логической единицы, который через инверторы 16 блокирует. сброс в

"0" триггеров, 10. Триггер 10 модели 1 ветви, формирующейся последней в данном узле, останется в единичном состоянии, и будет сигнализировать о том, что эта ветвь принадлежит экстремальному дереву моделируемого графа. Вычислительщяй процесс протекает выше описанным образом дальше без вмешательства блока управления, подобно тому как это происходит в реальных процессах, путем формирования ветвей и срабатывания узлов.

Если через наперед заданное время „ задержки на входе 38 блока 3 управления не появляется. сигнал логической единицы с выходов моделей 1 ветвей, образуюших конец графа, то блок 3 управления снимает сигнал с шины решения задачи о длиннейшем пути и импульсы с его выхода 34 поступают на обший вход 40 распределителя 7 импульсов, который последовательно через входы 42 опрашивает модели 5 узлов. Если в модели

5 узла на выходном полюсе 31, и значит жением логической единицы с выходов элементов И-HE 18). Появление сигнала логической единицы на входе 40 модели 5 узла после окончания работы одной или одновременно нескольких моделей 1 ветвей, подключенных своими выходными полюсами 29 к нему, блокирует срабатывание элементов И 12 и 13 остальных, еще не отработавших моделей 1 ветвей, входящих в данный узел, так как на выходе инвертора 16 будет сигнал логического нуля. Триггеры 10 этих моделей 1 ветвей не установлены в единичное состояние потому, что эти ветви уже не несут никакой информации о кратчайших путях, проходящих через данный узел.

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

После второго прохождения на выходном полюсе 31 его модели 5 узле появляется уровень логического нуля. Аналогично тому, как это делается в известных моделях подобного типа, после того как на устройстве определена конфигурация различных деревьев, что фиксируется в данном устройстве трйггерами 10 моделей 1 ветвей, и на полюсах моделей присутствуют сигналы логической единицы.—

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

Нулевой логический уровень с выходного полюса 31 модели 5 узла передается на его входной полюс 40, который в свою очередь соединен с выходными полюсами 29 моделей 1 ветвей. Если в модели l ветви триггер 10 находится в единичном состоянии, то через элемент 19 индикации и диод 22. сигнал логического нуля передается на ее входной полюс 23, который дальше соединен

E с выходным полюсом 31 предыдуших моделей 5 узлов, и нулевой логический уровень передается íà его входной полюс 40, и т.д. пока не придет в зафиксированную точку. Таким образом, можно проследить путь или контур. При обнаружении признака контура с выхода 43 зафиксированной модели 5 узла снимается сигнал логической единицы, и на входе .

37 блока 3 управления появляется сигнал логического нуля. При этом блок 3 управления с выхода 35 выдает на блок 4

7 717787 8 на входном полюсе 40 так же, присутствует сигнал логической единицы, то при опросе эта модель 5 узла не выдает информационного сигнала на свой выход

43. И, наоборот, когда при опросе обнаруживается какая-либо модель 5 узла, у которой на выходном полюсе. 31 присутствует сигнал нуля, то с ее выхода 43 на один из входов многовходового элемента ИЛИ 8 поступает единичный логический сигнал, который с его выхода поступает на вход 37 блока 3 управления. По поступлению этого сигнала блок 3 управления прекращает выдачу импульсов на общий вход 40 распредели- теля 7 импульсов, в котором остается зафиксированным aдрес интересующей нас модели 5 узла. Одновременно блок3, управления с своего выходя 33 вй дает сигнал логической единицы на шину рикше-. 2О ния задачи о кратчайшем пути.

В отличие от задачи о длиннейшем. пути, решение задачи о- кратчайшем пути допускает наличие контуров или несформнрование ветви. Это дает возможность

Z5 проникнуть за границу несформированных Событий. Известнйе модели узлов, как и модели ветвей, однонаправлены от входного полюса к выходному полюсу. зо .При подаче сигнала логической едини. цы на шину решения задачи о кратчайшем пути автоматически происходит запуск в . реньше зафиксированной на распредели.теле 7 импульсов модели 5 узла. На вы-. ходе 31 этой модели 5 узла появляется 35 сигнал логической единицы, который запускает все модели 1 ветвей из него исходящйе. Аналогично вышеописанному, формирователи 9 временного интервала этих моделей 1 ветвей, сформировав их длительности, выдают с своего выхода

- ца вход элемента И 12 сигнал на установку в код 1 триггера 10, единичный логический уровень с единичного выхода

45 которого устанавливает в состояние "1 триггер 11. На. входном полюсе 40 любой модели 5 узла появляется сигнал логической единицы, если оканчивает свою работу хотя бы одна модеаь 1 ветвй, so подключенная своим выходным полюсом к нему. Переключением в состояние 1 триггера 11 снимается сигнал логической единицы на выходе элемента И-HE 17, и единичный логический уровень c его выхода через диод 20 поступает на выходной полюс 29 (дйоды 21 в режйме решения задачи о кратчайшем пути во всех моделях 1 ветвей заперты напра71778 индикации сигнал, по которому отмеча- ются все модели 1 ветвей, принадлежащих одному или нескольким контурам, в которые входит зафиксированный узел.

Модели 1 ветвей, принадлежащие этим контурам, с своих индикационных выходов 30 выдают сигналы логического нуля на свои индивидуальные входы 47. в блоке 4 индикации.

После отметки моделей ветвей, при-. 10 надлежащих обнаруженному замкнутому контуру, через некоторое время 2за-. держки блок 3 управления с выхода 32 снова выдает сигнал логической единицы на шину решения задачи о длиннейшем пути. Одновременно сигналом с выхода 36 блока 3 управления сбрасываюч ся в нулевое состояние триггеры 11 моделей 1 ветвей, которые участвовали в формировании кратчайших путей, эа исключением той модели ветви, которая принадлежала обнаруженному контуру и блокировала формирование узла, так как теперь она уже сформирована при поиске

25 кратчайших путей. Этим самым как бы разрывается контур и имеется возмож ность проникнуть дальше в граф. На входном полюсе 40 ранее опрашивавшегося узла появляется сигнал логической едизе ницы и идет дальше формирование длиннейших путей и проверка правильности избранного графа. При этом мы можем или достигнуть конца графа или прийти к новой границе. В первом случае проверка окончена,,и устройство останавли35 вается, во втором случае начинается аналогично проверка узлов этой новой границы.

При поиске ошибок и неисправностей 4 может быть случай, когда не все узлы границы несформированных узлов принадлежат контуру, или как это случается при наличии тупика или технической неисправности моделей 1 ветвей, вообще контура не будет. В первом случае опра. шиваемый узел блокируется позже встре. о чаемым контуром, и если после задержки t, в его входной полюс. модели 5 узла не приходит сигнал логической единицы, то на ее выходе 43 и на входе37 блока 3 управления не появляется сигнал логического нуля. Блок 3 управления с выхода 34 начинает подавать тактовые импульсы на вход 40 распределителя 7 импульсрв,. который переходит к опросу следующих моделей 5 узлов до тех пор пока не будет обнаружена следующая модель 5 узла, в которой обнаруживает7 10 ся признак контура. Работа устройства будет аналогична вышеописанному. Во втором случае распределителем 7 импульсов перебираются все модели 5 узлов границы . Одновременно с перебором моделей 5 узлов запускаются в режиме решения задачи о кратчайшем пути все модели 1 ветвей, лежащие после границы несформированных событий, и формируются соответствующие узлы. В тех моделях 1 ветвей, которые неисправны, в режиме решения задачи о длиннейшем пути на входных полюсах 23 моделей 1 ветвей присутствуют единичные логические уровни, а на выходных полюсах 29 их нет. Сигнал о сбое внутри модели 1 ветви образуется элементом И. 15. Сигнал логического нуля на выходном полюсе 29 ннвертируется и на обоих входах элемента И 15 в случае вышеуказанного сбоя присутствуют сигналы логической единицы. Элемент И 15 подключен к входу элемента 19 индикации, который через индикационный выход 30 модели 1 ветви выдает на свой индивидуальный вход 47 блока 4 индикации нулевой логический уровень. После проверки всех моделей 5 узлов с выхода 35 блока 3 управления подается сигнал, по которому фиксируются все неисправные модели 1 ветвей.

В исходном состоянии триггеры 4951 сброшены в срстояние 0 . По внешнему сигналу пуска триггер 49 устанавливается в состоянйе "1 . Уровень логической единицы с единичного выхода триггера 49 служит сигналом решения задачи о длиннейшем пути. Сброс в нулевое состояние триггера 49 происходит по сигналу лэгической единицы, поступающему с моделей 1 ветвей, образующих конец графа набранной задачи, через входной полюс 38 на вход элемента И 55," а также по сигналу с выхода элемента 63 задержКи, поступающему

1 C всякий раэ, когда мы опрашиваем модели 5 узлов, принадлежащих границе несформированных узлов. При этом, если

I модель 5 узла принадлежит контуру, запуск генератора 65 одиночного импульса происходит положительным фронтом пере» пара напряжений на выходе инвертора 52 через время прохождения этого сигнала через элемент 64 задержки. В противном случае, когда модель 5 узла не принадлежит контуру, запуск генератора 65 одиночного импульса производится по

11 7 177 сигналу с выхода элемента И 59. Время задержки прохождения сигнала через элемент 63 задержки может регулироваться для задач данного класса о длиннейшем пути. В качестве элемента 63

«регулируемой задержки можно использовать известные счетчико-регистровые структуры. Триггер 50 служит для различия режимов решения задач о длин нейшем и кратчайшем путях. Триггер 51 10 устанавливается в состояние 1 всякий раз, когда обнаруживается несформированная модель 5 узла границы. Сброс в нулевое состояние триггера 51 производится после конца анализа обнаруженной ошибки..Элемент И 58 служит для разрешения прохождения импульсов .тактового генератора с выхода 34 блока 3 управления на обший вход 40 распределителя 7 импульсов при соответствующих состояний триггеров 49-51 . Выход генератора 2. так: товых импульсов подключен к входу 39 блока 3 управления. Элемент И 58. фор мирует сигнал решения задачи о кратчайшем пути по состояниям триггеров 4925

51. Элемент И 60 предназначен для выдачи с выхода 35 блока 3 управления на вход блока 4 индикации сигнала разрешения индикации. Время индикации зо определяется элементом 64 задержки. . Устройство для анализа систем сетевой структуры выгодноотличается от ранее известных устройств, тем, чтвыаряду с решением задач об экстремальных путях в системах сетевой структуры, оно поз35 воляет ав томатизировать определение ошибок, допущенных при подготовке за- дачи к решению, наборе структуры, а также технических неисправностей одно40 типных моделей, составляюших основу таких структур.

Формула изобретения

1, Устройство для исследования сетей, содержашее генератор импульсов, выход которого подключен к первому входу бло-ка управления, первый выход которого соединен с входом распределителя, выходы которого подключены к первым входам моделей узлов, модели ветвей и блок индикации, о т л и ч а ю m е ес я тем, что, с целью повышения точности, в устройство введены элемент

ИЛИ и наборное поле, "первые группы входов и выходов которого соедийены соответственно с первыми выходами и вторыми входами моделей узлов, вторые

87 12 выходы которых подключены к входам элемента ИЛИ выход которого соединен с вторым входом блока управления, третий вход которого подключен к выходу наборного поля, вторые группы входов и выходов которого соединены соответственно с первыми выходами и входами моделей ветвей, вторые, третьи и чет вертые входы которых подключены соответственно к второму, третьему и четвертому выходам блока управления, пятый выход которого соединен с одним входом блока индикации, другие входы которого подключены к вторым выходам моделей-ветвей, пятые и шестые входы которых соединены с группой выходов генератора импульсов.

2. Устройство по и. 1, о т л и ч а юm е е с я тем, что блок управления содержит элементы И, элемент ИЛИ, триггеры, элемент НЕ, элементы задержки и генератор одиночного импульса, входы которого подключены соответственно к выходам первого элемента И и элемента задержки, вход которого соединен с первыми входами второго и третьего элементов И и подключен к выходу элемента НЕ, вход которого соединен с пэрвым входом первого триггера и является вторым входом блока управления, первый вход которого подключен к первым входам четвертого и пятого элементов И, второй вход которого соединен с первым входом шестого элемента И и подключен к первому выходу второго триггера, второй выход которого соединен с первыми входами седьмого элемента И и элемента ИЛИ и является вторым выходом блока управления, второй вход седьмого элемента И соединен с первым входом восьмого элемента И и является третьим входом блока управления, второй вход восьмого элемента И подключен к первому. выходу третьего триггера, первый вход которого соединен с выходом седьмого,элемента И, второй вход третьего трйтгера соединен с первыми входами второго триггера и первого элемента И и подключен к выходу второго элемента задержки, первый вход которого соединен с выходом четвертого элемента И, второй вход которого подключен к выходу элемента ИЛИ, второй вход которого соединен с вторыми входами первого и шестого элементов И и подключен к первому . выходу первого триггера, второй выход которого соединен с третьим входом пя13

7 17787

14 того элемента И, четвертый вход которого соединен с третьим входом шестого элемента И, с вторым входом второго элемента И и подключен к второму выходу третьего триггера, выходы второго, пя- 5 того и шестого элементов И являются соответственно пятым, первым и третьим выходами блока управления, выход генератора одиночного импульса соединен с вторым входом первого триггера, второго элемента задержки и третьего элемента И и является четвертым выходом блока управления, выходы третьего и восьмого элементов И подключены соо ветственно к второму и третьему вх дам второго триггера.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

% 305484, кл. Я 06 4 7/122, 1969.

2. Авторское свидетельство СССР

% 486339, кл. 6 06 Ь 7/48, 1971, (прототип).

7 17787

Составитель И. Загорбинина

Texpep H. а урка . Йаб Корректор Я. Веселовская

Редактор Герцен

Заказ 9850/88 Тираж 751

LIHNMIIH Государственного комитета СССР по делам изобретений и открытий

113036, Москва, Ж-35, Раушская наб., д. 4/

4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4