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

О ПИЗОБРЕТЕН ИЯ Союз СоветскихСоциалистическихРеспублик и 717787 К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(51)М. Кл,606 Ь 7/122 й 1 еудеретвеииьй кенитет СССР ав делам изееретеиий я фткрытвя(Институт электродинамики АН Украинской ССР(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ СЕТЕЙ Настоящее изобретение относится к области электронного моделирования и может быть применено при построении специализированных вычислительных устройств для решения задач в сетевой постановке, в частности для решения5 задач сетевого планирования и управления, исследования систем сложной структуры,Известно устройство для моделирова-10ния экстремальных путей на графе, которое выполнено на логических элемен-,тах, соединенных между собой в соответствии с структурой системы, и вычисли 15тельный процесс в них имеет аналоговыйхарактер. Такое устройство обладает высоким быстродействием, простотой инаглядностью процесса решения, алгоритмфункционирования полностью или частич 20, но заложен в их структуре, они прост 1 ав обслуживании, имеют большие возможности резервирования и замены элементов 1,1,1,Однако применение в вышеуказанных устройствах элементов аналоговой вычислительной техники или электромеханических устройств приводит к снижению точности, надежности и затруднению диалога между человеком и машиной, Попытки представить информацию в удобной для человека форме, автоматизировать ввод и вывод информации, процесс поиска неисправностей или просмотра различных вариантов решения задач приводят к значительным затратам оборудования, что усложняет устройство и повышает его стоимость. Из известных устройств наиболее близким к изобретению по технической сущности является устройство, содержащее генератор импульсов, выход которого подключен к первому входу блока управления, первый выход которого соединен с входом распределителя, выходы которого подключены к первым входам моделей узлов, модели ветвей 1 блок ин7787 5 10 3 . 71дикации и дополнительные логическиеэлементы 2,1Известное устройство не обеспечиваетдостаточную точность анализа систем сетевой структуры.Пелью изобретения является повьппениеточности устройства,Поставленная цель достигается тем,что в устройство введены элемент ИЛИи наборное поле, первые группы входови выходов которого" соединены соответственно с первыми выходами и вторымивходами моделей узлов, вторые выходыкоторых подключены к входам" элементаИЛИ, выход которого соединен с вторымвходом блока управления, третий входкоторого подключен к выходу наборногополя, вторые группы входов и выходовкоторого соединены соответствэнно с первыми выходами и входами моделей ветвей, вторые, третьи и четвертые входыкоторых подключейы" соответственно квторому, третьему и четвертому выходам блока управления, пятый выходко-торогосоединен с одним "входом блокаиндикации, другие входы которого подключены к вторым выходам моделей ветвей, пятые и шестые входы которых соединены с группой выходов генератора импульсов, кроме того блок управления содержит элементы И, элемент ИЛИ, триггеры, элемент НЕ, элементы задержки игенератор одиночного импульса, входыкоторого подключены соответственно квыходам первого элемента И и элементазадержки, вход которого соединен с первыми входами второго и третьего элементов И и подключен к выходу элемента НЕ, вход которого соединен с пер-.вым входом первого триггера и являетсявторым входом блока управления, первыйвход которого подключен к первым входам четвертого и пятого элементов И,второй вход которого соединен с первымвходом шестого элемента И и подключенк первому выходу второго триггера, второй выход которого соединен с первымивходами седьмого элемейта И и элемен-та ИЛИ и является вторым выходом блока управления, второй вход седьмогоэлемента И соединен с первым входомвосьмого элемента И и является третьимвходом блока управления, второй входвосьмого элемента И подключен к первому выходу третьего триггера, первыйвход которого соединен с выходом седьмого элемента И, второй вход третьеготриггера соединен с первыми входамивторого триггера и первого элемента, И и подключен к выходу второго элементазадержки, первый вход которого соединен с выходом четвертого элемента И,второй вход которого подключен к выходу элемента ИЛИ, второй вход которого соединен с вторыми входами первого и шестого элементов И и подключенк первому выходу первого триггера, второй выход которого соединен с третьимвходом пятого элемента И четвертый вход которого соединен с третьим входомшестого элемента И, с вторым входомвторого элемента И и подключен к второму выходу третьего триггера, выходы15второго "пятого и шестого элементов Иявляются соответственно пятым, первыми третьим выходами блока управления,выход генератора одиночного импульсасоединен с вторым входом первого триггера, второго элемента задержки и третьего элемента И и является четвертымвыходом блока управления, выходы третьего и восьмого элементов И подключены соответственно к второму и третьему входам второго триггера,На фиг. 1 приведена блок-схема устройства; на фиг, 2 - функциональнаясхема блока управления.30Устройство содержит модели 1 ветвей, генератор 2 импульсов, блок 3 управления, блок 4 индикации, модели 5,узлов, наборное поле 6, распределитель7 импульсов, многовходовый элементИЛИ 8, Каждая модель 1 ветвей содержит формирователь 9 временного интервала, триггеры 10 и 11, элементы И12-15, инвертор 16, элементы И-НЕ17 и 18, элемент 19 индикации, диоды4020 - 22, полюса 23-30, моделей выходы 31 моделей узлов выходы и входы. 1.32-39 блока управления вход 40 и выходы 41 распределителя, входы 42 ивыходы 43 моделей 5 узлов, выходы 44-45 46 генератора импульсов, входы 47 и 48блока индикации.Блок Управления содержит триггеры49-51, инвертор 52, элементы И 5360, элемент ИЛИ 61, элементы 63 ир 64 задержки, генератор 65 одиночногоимпульса.Устройство работает следующим обФразом.В исходном состоянии, перед решением55 задачи на устройстве, модели 1 ветвейи модели 5 узлов скоммутированы междусобой на наборном поле 6 в соответствйис топологией графа. В формирователи 9временных интервалов моделей 1 ветвей10 15 20 25 30 35 ошибки, такие как замкнутые контуры тупики, или произошел сбой в одной или нескольких моделях ветвей, сигнал в конце графа не появляется, Как указано 40на фиг. 2 в графе будет граница , сосостоящая из несформированных узлов, блокируюших достижение конца графа.Эта граница будет иметь всегда место, если не сформируется хотя бы одна ветвь 45или узел из-за вышеуказанных ошибок. 50 55 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 ветви, формирующейся последнейв данном узле, останется в единичномсостоянии, и будет сигнализировать отом, что эта ветвь принадлежит экстремальному дереву моделируемого графа, Вычислительщй процесс протекаетвыше описанным образом дальше без вмешательства блока управления, подобно тому как это происходит в реальных процессах, путем формирования ветвей исрабатывания узлов. Если граф составлен и набран правильно, и не произошло отказа ни в одной из моделей 1 ветвей, то через некоторое время на выходных полюсах 29 моделей 1 ветвей, образуюших конец графа появляется сигнал логической единицы,который свидетельствует об отсутствииошибок. Этот сигнал через вход 38 блока 3 управления поступает для остановавсего устройства, В противоном случае,если в решаемой сети есть логические Если через наперед заданное времязадержки на входе 38 блока 3 управления не появляется. сигнал логической единицы с выходов моделей 1 ветвей, образующих конец графа, то блок 3 управления снимает сигнал с шины решения задачи о длиннейшем пути и импульсы с его выхода 34 поступают на общий вход 40 распределителя 7 импульсов, который последовательно через входы 42 опрашивает модели 5 узлов. Если в модели 5 узла на выходном полюсе 31, и значитжением логической единицы с выходов элементов И-НЕ 18), Появление сигнала логической единицы на входе 40 модели 5 узла после окончания работы одной или одновременно нескольких моделей 1 ветвей, подключенных своими выходными полюсами 29 к нему, блокирует срабатывание элементов И 12 и 13 остальных, еще не отработавших моделей 1 ветвей, входящих в данный узел, так как на выходе инвертора 16 будет сигнал логического нуля. Триггеры 10 этих моделей 1 ветвей не установлены в единичное состояние потому, что эти ветви уже не несут никакой информации о кратчайших путях, проходящих через данный узел.Если зафиксированный узел принадлежит замкнутому контуру, то в режиме решения задачи о кратчайшем пути этотузел проходится больше чем один раз. После второго прохождения на выходном полюсе 31 его модели 5 узле появляется уровень логического нуля. Аналогично тому, как это делается в известных моделях подобного типа, после того какна устройстве определена конфигурацияразличных деревьев, что фиксируется вданном устройстве трйггерами 10 моделей 1 ветвей, и на полюсах моделей присутствуют сигналы логической единицы. -Сигналы, индицирующие различные пути и контуры, имеют характер противоположный сигналам измерения, т,е, индикация путей или контуров производится сигналами нулевого логического уровня. Нулевой логический уровень с выходного пощоса 3 1 модели 5 узла передаетсяна его входной полюс 40, который всвою очередь соединен с выходными полюсами 29 моделей 1 ветвей, Если в модели 1 ветви триггер 10 находится в единичном состоянии, то через элемент 19 индикации и диод 22 сигналлогического нуля передается на ее входной пощос 23, который дальше соединенс выходнымпощосом 31 предыдущих моделей 5 узлов, и нулевой логический уровень передается на его входной полюс 40, и т.д. пока не придет в зафиксированную точку. Таким образом, можно проследить путь или контур. При обнаружении признака контура с выхода 43зафиксированной модели 5 узла снимаетсяс сигнал логической единицы, и на входе .37 блока 3 управления появляется сигналлогического нуля, При этом блок 3 управления с выхода 35 выдает на блок 4 7 717787 8на входном полюсе 40 так же, присутствует сигнал логической единицы, топриопросе эта модель 5 узла невыдаетинформационного сигнала на свой выход43, И, наоборот, когда при опросе обнаруживается какая-либо модель 5 узла,у которой на выходном пощосе. 31 присутствует сигнал нуля, то с ее выхода 43на один из входов многовходового элемента ИЛИ 8 поступает единичный логический сигнал, который с его выходапоступает на вход 37 блокаЭ управления. По поступлению этого сигналаблок 3 управления прекращает выдачуимпульсов на общий вход 40 распредели. теля 7 импульсов, в котором остаетсязафиксированным адрес интересующейнас модели 5 узла. Одновременно блок 3,управления с своего выходя 33 вйдает. сигнал логической единицы на шину реше-. 20ния задачи о кратчайшем пути,/В отличие от задачи о длиннейшем,пути, решение задачи о кратчайшем путидопускает наличие контуров или несформнрование ветви, Это дает возможность25проникнуть за границу несформированныхСобытий. Известнйе модели узлов, каки модели ветвей, однонаправлены от входного полюса к выходному полюсу.30При подаче сигнала логической едини. цы на шину решения задачи о кратчайшемпути автоматически происходит запуск в. реньше зафиксированной на распределителе 7 импульсов модели 5 узла, На выходе 31 этой модели 5 узла появляется35сигнал логической единицы, который запускает все модели 1 ветвей из него исходящйе, Аналогично вышеописанному,формирователи 9 временного интервалаэтих моделей 1 ветвей, сформировав ихдлительности, выдают с своего выхода.на вход элемента И 12 сигнал на установку в код 1 триггера 10, единичныйлогический уровень с единичного выхода45которого устанавливает в состояние "1триггер 11. На входном полюсе 40 любой модели 5 узла появляется сигнал логической единицы, если оканчивает сво 1 оработу хотя бы одна модеаь 1 ветвй;50подключенная своим выходным полюсомк нему. Переключением в состояние "1триггера 11 снимается сигнал логическойединицы на выходе элемента И-НЕ 17,и единичный логический уровень с еговыхода через диод 20 поступает на выходной полюс 29 (дйоды 21 врежймерешения задачи о кратчайшем пути вовсех моделях 1 ветвей заперты напра71778 индикации сигнал, по которому отмеча-ются все модели 1 ветвей, принадлежащих одному или нескольким контурам, вкоторые входит зафиксированный узел,Модели 1 ветвей, принадлежащие этимконтурам, с своих индикационных выходов 30 выдают сигналы логического нуля на свои индивидуальные входы 47.в блоке 4 индикации,1После отметки моделей ветвей, при янадлежащих обнаруженному замкнутомуконтуру, через некоторое время 2 за-.держки блок 3 управления с выхода 32снова выдает сигнал логической единицы на шину решения задачи о длиннейшем пути. Одновременно сигналом с выхода 36 блока 3 управления сбрасываюгся в нулевое состояние триггеры 11 моделей 1 ветвей, которые участвовали вформировании кратчайших путей, эа исключением той модели ветви, котораяпринадлежала обнаруженному контуру иблокировала формирование узла,так кактеперь она уже сформирована при поиске25кратчайших путей. Этим самым как быразрывается контур и имеется возможность проникнуть дальше в граф. На входном полюсе 40 ранее опрашивавшегосяузла появляется сигнал логической еди 30нины и идет дальше формирование длиннейших путей и проверка правильностиизбранного графа, При этом мы можемили достигнуть конца графа или прийтик новой границе. В первом случае нроверка оконченаи устройство останавли 35вается, во втором случае начинается аналогично проверка узлов этой новой границы.При поиске ошиббк и неисправностейможет быть случай, когда не все уздыграницы несформированных узлов принадлежат контуру, или как это случаетсяпри наличии тупика или технической неисправности моделей 1 ветвей, вообщеконтура не будет, В первом случае опрашиваемый узел блокируется позже встреочаемым контуром, и если после задержки 11 в его входной полюс. модели 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ветвей." В исходном состоянии триггеры 49- 51 сброшены в состояние"0. По внешнему сигналу пуска триггер 49 устанавливается в состоянйе "1, Уровень логической единицы с единичного выхода триггера 49 служит сигналом решения задачи о длиннейшем пути. Сброс в нулевое состояние триггера 49 происходит по сигналу лэгической единицы,поступающему с моделей 1 ветвей, образующих конец графа набранной задачи, через входной полюс 38 на вход элемента И 55," а также по сигналу с выхода элемента 63 задержКи, поступающему1всякий раэ, когда мы опрашиваем модели 5 узлов, принадлежащих границе несформированных узлов. При этом, если модель 5 узла принадлежит контуру, запуск генератора 65 одиночного импульса происходит положительным фронтом пере нада напряжений на выходе инвертора 52 через время прохождения этого сигнала через элемент 64 задержки. В противномслучае, когда модель 5 узла не принадлежит контуру, запуск генератора 65 одиночного импульса производится по50 11 7177 сигналу с выхода элемента И 59. Время задержки 1 прохождения сигнала через элемент 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 типных моделей, составляющих основу таких структур. формула изобретения 451, Устройство для исследования сетей, содержащее генератор импульсов, выход которого подключен к первому входу бло- ка управления, первый выход которого соединен с входом распределителя, выходы которого подключены к первым входам моделей узлов, модели ветвей и блок индикации, о т л и ч а ю щ е ес я тем, что, с целью повышения точности, в устройство введены элемент ИЛИ и наборное поле, "первые группы входов и выходов которого соедийены соответственно с первыми выходами и вторыми входами моделей узлов, вторые 87 12 выходы которых подключены к входамэлемента ИЛИвыход которого соединенс вторым входом блока управления, третий вход которого подключен к выходунаборного поля, вторые группы входови выходов которого соединены соответственно с первыми выходами и входамимоделей ветвей, вторые, третьи и четвертые входы которых подключены соответственно к второму, третьему и четвертому выходам блока управления, пятый выход которого соединен с однимвходом блока индикации, другие входы которого подключены к вторым выходаммоделей-ветвей, пятые и шестые входыкоторых соединены с группой выходовгенератора импульсов. 2. Устройство по и. 1, о т л и ч а ющ е е с я тем,что блок управления содержит элементы И, элемент ИЛИ, триггеры, элемент НЕ, элементы задержки и генератор одиночного импульса, входыкоторого подключены соответственно к выходам первого элемента И и элемента задержки, вход которого соединен с первыми входами второго и третьего элементов И и подключен к выходу элемента НЕ, вход которого соединен спэрвым входом первого триггера и является вторым входом блока управления,первый вход которого подключен к первым входам четвертого и пятого элементов И, второй вход которого соединен с первым входом шестого элемента И иподключен к первому выходу второготриггера, второй выход которого соединен с первыми входами седьмого элемента И и элемента ИЛИ и являетсявторым выходом блока управления, второй вход седьмого элемента И соединен с первым входом восьмого элемента И и является третьим входом блокауправления, второй вход восьмого элемента И подключен к первому, выходу третьего триггера, первый вход которогосоединен с выходом седьмого,элемента И, второй вход третьего трйтгера соединен с первыми входами второго триггера и первого элемента Ии подключенк выходу второго элемента задержки,первый вход которого соединен с выходом четвертого элемента И, второйвход которого подключен к выходу элемента ИЛИ, второй вход которого соединен с вторыми входами первого и шестого элементов И и подключен к первомувыходу первого триггера, второй выходкоторого соединен с третьим входом пятого элемента И, четвертый вход которогосоединен с третьим входом шестого элемента И, с вторым входом второго элемента И и подключен к второму выходутретьего триггера, выходы второго, пятого и шестого элементов И являютсясоответственно пятым, первым и третьимвыходами блока управления, выход генератора одиночного импульса соединенс вторым входом первого триггера, второго элемента задержки и третьего эле-мента И и является четвертым выходом блока управления, выходы третьего и восьмого элементов И подключены соо- ветственно к второму и третьему вх- дам второго триггера.Ф Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССРКорректор я Веселовская актор рце 8" "Тираж 751 Подпис БНИИПИ Государственного комитета СССР по делам изобретений и открытий 13036, Москва, Ж, Раушская набд, 4