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

О П И С А Н И Е р) 4863301ИЗОБРЕТЕНИЯК,АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Сова Советскнк Соаилнстнческик Республик(23) ПриоритетОпубликовано 30.09.75. Бюллетень36Дата опубликования описания 13.01.76 1 Ъсуларотеенный комитет Совета Министров СССР пе лолам изобретений(71) Заявител ики АН Украинской ССР нститут электро) УСТРОЙСТВО ДЛЯ ИССЛЕ ИЯ СЕТЕЙ 1Изобретение относится к области вычислительной техники и может быть использовано при построении специализированных вычислительных машин для решения задач о потоках в сетях, возникающих при проектировании сетей связи, транспортных сетей, информационных систем, электроннных цепей и т, д.Известны устройства для исследования сетей, содержащие блок моделей ветвей, соеди. ненный с блоком формирования циклов, генератор импульсов, подключенные к блоку управления. Неотъемлемой частью этих устройств является наборное поле, на котором вручную с помощью коммутационных проводников набирают топологию сети, Наличие наборного поля не позволяет полностью автоматизировать процесс решения задачи, снижает быстродействие и надежность устроиства.Цель изобретения - повышение быстродействия процессов подготовки и решения задач на сетях.Требуемый положительный эффект в предлагаемом устройстве достигается путем введения в устройство блока автоматического формирования топологии, состояп;его из распределителя импульсов, вход и первый выход которого подключены к блоку управления, а каждый из остальных выходов распределителя импульсов - к входу логического блока узловой функции, другие входы которого соедине ны с блоками управления, моделей ветвей, формирования циклов. Выходы логических блоков узловой функции подключены к входу блока управления, первые входы задатчиков 5 адресов начального и конечного узлов моделей ветвей - к первым шинам тактовых импульсов, вторые их входы соединены с шинами записи номера соответственно начального и конечного узлов, а выходы - с первыми 1 О входами соответственно первого, второго, третьего, четвертого элементов И. Выходы этих элементов И связаны с первым выходом модели ветви, с входами управления модели ветви, а их третьи входы - с нулевым 15 выходом первого триггера, вторым выходоммодели ветви и первым входом пятого элемента И, второй вход которого и второй вход четвертого элемента И соединены с входами формирования цикла модели ветви. Выход 20 четвертого элемента И связан с единичнымвходом второго триггера, нулевой вход которого подключен к входу сброса модели ветви, а его единичный вход и выход пятого элемента И через шестой элемент И и пер.25 вый элемент ИЛИ, соединенный другим входом с входом фиксации цикла модели ветви, подключены к единичному входу первого триггера, нулевой вход которого соединен с выходом счетчика. Вход счетчика через седьмой з 0 элемент И подсоединен к второй шине так486330 15 20 ИЛИ 43 подключен к выходам элементов И 39 и 42, первые входы которых соединены соответственно с единичными выходами триггеров 37, 38, а остальные их входы подключе 25 ны к входам 44 - 47 управления логическогоблока 6 узловой функции. Выход счетчика 36 подключен к нулевому входу триггера 37, выходы которого соединены с выходами 48, 49, и через элемент И 40, другой вход которого 30 соединен с отдельным входом 50 управлениялогического блока узловой функции, подключен к выходу 51 логического блока узловой функции. Два других входа 52, 26 логического блока узловой функции подключены через 35 элемент И 41 к нулевому входу триггера 38,единичный вход которого соединен с единичным входом триггера 37 и подключен к входу 53 сброса логического блока узловой функции,Устройство для исследования сетей работа ет следующим образом.Предварительно в счетчики 10 заносятся количества импульсов, пропорциональные пропускным способностям ветвей, а в задатчики адресов начального 8 и конечного 9 узлов, ко.45 торые могут быть выполнены на базе счетчиков импульсов, заносятся количества импульсов, пропорциональные номерам узлов, из которых данная ветвь выходит и в которые она входит.50 Триггеры 11, 37, 38 устанавливаются в единичное состояние. Синтез сети осуществляется в два этапа. На первом этапе проводится определение максимального потока через все узлы синтезируемой сети и формирование то пологии сети. Для этого из блока 2 управления на полюса (35, 47) подается сигнал, разрешающий прохождение импульсов ГИ в счетчики 10 и 36.Сигнал переполнения одного из счетчиков 60 10 устанавливает триггер 11 модели ветви внулевое состояние. Сигнал, появившийся на нулевом выходе триггера 11, поступает через выход 29 в устройство управления, запрещая поступление импульсов ГИ в счетчики 10, 36, 65 и разрешает поступление импульсов ГИ на товых импульсов и выходу второго элемента ИЛИ, входы которого соединены с входом управления модели ветви и выходом второго элемента И, второй вход которого подключен к единичному выходу первого триггера.Логический блок узловой функции содержит счетчик. Вход счетчика через первый элемент ИЛИ подключен к выходам первого и второго элементов И, первые входы которых соединены с единичными выходами соответственно первого и второго триггеров, а остальные нх входы - к входам управления логического блока узловой функции. Выход счетчика подсоединен к нулевому входу первого триггера, выходы которого соединены с выходами формирования цикла логического блока узловой функции, и через третий элемент И, другой вход которого соединен с отдельным входом управления логического блока узловой функции, подключен к выходу логического блока узловой функции. Два других входа последнего через четвертый элемент И подключены к нулевому входу второго триггера, единичный вход которого соединен с единичным входом первого триггера и входом сброса логического блока узловой функции.Такое изменение схемы устройства позволяет автоматически в процессе решения задачи формировать топологию исследуемой сети.На фиг, 1 изображена блок-схема предлагаемого устройства для исследования сетей; на фиг, 2 - блок-схема модели ветви, на фиг. 3 - блок-схема логического блока узловой функции.Предлагаемое устройство содержит генератор 1 импульсов, блок 2 управления, блок 3 моделей ветвей, блок 4 формирования циклов, блок 5 автоматического формирования топологии, состоящий из логических блоков 6 узловых функций и распределителя 7 импульсов.Блок 3 моделей ветвей содержит отдельные модели ветвей, выполненные по схеме фиг. 2, где изображены задатчики начального 8 и конечного 9 узлов, счетчик 10 импульсов, триггеры 11, 12, элементы И 13 - 19, элементы ИЛИ 20, 21. В модели ветви первые входы задатчиков адресов начального и конечного узлов подключены к первым шинам 22, 23 тактовых импульсов, вторые их входы - к шинам 24, 25 записи номера соответственно начального и конечного узла, а их выходы - к первым входам элементов И 14, 15 и 16, 17, Выходы элементов И 15, 16 соединены с первым выходом 26 модели ветви. Вторые входы этих элементов И, подключены к входам 27, 28 управления модели ветви, а их третьи входы - к нулевому выходу триггера 11, второму выходу 29 модели ветви и первому входу элемента И 18. Вторые входы элементов И 17 и 18 связаны с входами 30, 31 формирования цикла модели ветви. Выход элемента И 17 соединен с единичным входом триггера 12, нулевой вход которого подсоединен к входу 32 сброса модели ветви, а его единичный выход и выход элемента И 418 через элемент И 19 и элемент ИЛИ 20, другой вход которого соединен с входом 33 фиксации цикла модели ветви, подключены к единичному входу триггера 11. Нулевой вход триггера 11 соединен с выходом счетчика 10, вход которого через элемент И 13 подключен к второй шине 34 тактовых импульсов и выходу элемента ИЛИ 21. Входы элемента ИЛИ 21 соединены соответственно с входом 35 управления модели ветви и выходом элемента И 14, второй вход которого подключен к единичному выходу триггера 11.Логический блок 6 узловых функций, число которых соответствует числу узлов сети, содержит (фиг, 3) счетчик 36 импульсов, емкость которого равна емкости счетчика 10 импульсов модели ветви, триггеры 37, 38, элементы И 39 - 42, элемент ИЛИ 43.Вход счетчика 36 импульсов через элемент5вход распределителя 7 импульсов и входы задатчиков начальных (22) и конечных (23) узлов. Сигнал о переполнении одного из задатчиков адресов узлов подается через выход 26 в блок 5 автоматического формирования топологии и в блок 2 управления, запрещая поступление импульсов ГИ на полюса (22, 23) в распределитель импульсов, и разрешает поступление импульсов ГИ. Совпадение этого сигнала с сигналом на одном из элементов (41) логического блока узловой функции (вход 62) устанавливает соответствующий триггер 38 в нулевое состояние. Тем самым запрещается поступление импульсов ГИ в соответствующий счетчик 36 до окончания первого этапа.Процесс повторяется до тех пор, пока не появится сигнал на выходе распределителя импульсов, сигнализирующий блоку управления об окончании первого этапа.После окончания первого этапа в счетчиках 36 импульсов записаны количества импульсов, равные Умакс - ф.максгде Умакс - емкость счетчика;и - количество импульсов, пропорциональное максимальному потоку 1-го узла. На втором этапе проводится определение ветвей, принадлежащих гамильтонову циклу, и определение минимальных пропускных способностей ветвей, лежащих на этом цикле. Для этого по сигналу из блока 2 управления разрешается поступление импульсов ГИ в задатчики начальных 8 и конечных 9 узлов и формирователь гамильтоновых циклов, который, формируя цикл, устанавливает триггеры 11 в единичное состояние в тех моделях ветвей, у которых триггеры 37 находятся в единичном состоянии. При этом в счетчики 10 моделей ветвей, принадлежащих гамильтонову циклу, заносится количество импульсов, пропорциональное минимальным пропускным способностям этих ветвей. Далее на полученном множестве вновь формируется гамильтонов цикл и весь процесс повторяется.Второй этап закончится только тогда, когда все триггеры 37 окажутся установленными в нулевое состояние.При этом количество импульсов, записанных в счетчиках 10 моделей ветвей, характеризуют пропускную способность синтезируемой сети,Предмет изобретения 1. Устройство для исследования сетей, содержащее блок моделей ветвей, соединенный с блоком формирования циклов, генератор импульсов, подключенные к блоку управления, о т л и ч а ю щ е е с я тем, что, с целью увели. чения быстродействия процессов подготовки и решения задач на сетях, оно содержчт блок 5 о 15 20 25 зо 35 40 45 50 бо 05 6автоматического формирования топологии, состоящей из распределителя импульсов, вход и первый выход которого подключены к блоку управления, а каждый из остальных выходов распределителя импульсов соединен с входом логического блока узловой функции, другие входы которого соединены с блоками управления, моделей ветвей, формирования циклов; выходы логических блоков узловой функции подключены к входу блока управления; первые входы задатчиков адресов начального и конечного узлов моделей ветвей подключены к первым шинам тактовых импульсов, вторые их входы соединены с шинами записи номера соответственно начального и конечного узлов, а выходы - с первыми входами соответственно первого, второго, третьего и четвертого элементов И, выходы которых соединены с первым выходом модели ветви, подключены к входам управления модели ветви, а их третьи входы соединены с нулевым выходом первого триггера, вторым выходсм модели ветви и первым входом пятого элемента И, второй вход которого и второй вход четвертого элемента И соединены с входами формирования цикла модели ветви; выход четве,.того элемента И соединен с единичным входом второго триггера, нулевой вход которого подключен к входу сброса модели ветви, а его единичный вход и выход пятого элемента И через шестой элемент И и первый элемент ИЛИ, соединенный другим входом с входом фиксации цикла модели ветви, подключены и единичному входу первого триггера, нулевой вход которого соединен с выходом счетчика, вход которого через седьмой элемент И соединеч с второй шиной тактовых импульсов и выходом второго элемента ИЛИ. входы которого соединены с входом управления модели ветви и выходом второго элемента И, второй вход которого подключен к единичному выходу первого триггера.2, Устройство по п. 1, отличающееся тем, что логический блок узловой функции содержит счетчик, вход которого через первый элемент ИЛИ подключен к выходам первого и второго элементов И. первые входы которых соединены с единичными выходами соответственно первого и второго триггеров, а остальные их входы подключены к входам управления логического блока узловой функции; выход счетчика соединен с нулевым входом первого три"гсра, выходы которого соединены с выходами формирования цикла логического бока узловой функции, и через третий элемент И, другой вход ксторого соединен с отдельным входом управления логического блока узловой функции, подклю. чен к выходу логического блока узловой функции, два других входа которого через четвертый элемент И подключены к нулевому вхо. лу второго триггера, единичный вход которого соединен с единичным входом первого триггера и подключен к входу сброса логического блока узловой функции.486330 е 4 Ф 5 Составитель А. Киселедактор И, Грузова Техред М. Семенов Корректор А. Дзесо аказ 199/11ЦНИ одписное Типография, пр, Сапунова,Изд.858 И Государственнопо делам из Москва, Ж 3 комитета бретений Раугпска Тираж 679овета Министров Сткрытийаб., д. 45