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

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

Иллюстрации

Показать все

Реферат

 

О П И С А Н И Е (и) 486330

ИЗОБРЕТЕНИЯ

К .АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Сове Советскнк

Сеннллнстнческнк

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 28.12.71 (21) 1730328/18-24 с присоединением заявки № (23) Приоритет

Опубликовано 30.09.75. Бюллетень № 36

Дата опубликования описания 13.01.76 (51) М. Кл. 6 06g 7/48

1 сулеротееннмй комитет

Сената Министров СССР пе лелем изобретений н открмтнй (53) УДК 681.333(088.8) (72) Авторы изобретения В. В. Васильев, А. Г. Додонов, В. В. Федотов н Н. В. Федотов (71) Заявитель

Институт электродинамики АН Украинской ССР (54) УСТРОИСТВО ДЛЯ ИССЛЕДОВАНИЯ СЕТЕЙ

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

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

Цель изобретения — повышение быстродействия процессов подготовки и решения задач на сетях.

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

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

t0 входами соответственно первого, второго, третьего, четвертого элементов «И». Выходы этих элементов «И» связаны с первым выходом модели ветви, с входами управления модели ветви, а их третьи входы — с нулевым

15 выходом первого триггера, вторым выходом модели ветви и первым входом пятого элемента «И», второй вход которого и второй вход четвертого элемента «И» соединены с входами формирования цикла модели ветви. Выход

20 четвертого элемента «И» связан с единичным входом второго триггера, нулевой вход которого подключен к входу сброса модели ветви, а его единичный вход и выход пятого элемента «И» через шестой элемент «И» и пер25 вый элемент «ИЛИ», соединенный другим входом с входом фиксации цикла модели ветви, подключены к единичному входу первого триггера, нулевой вход которого соединен с выходом счетчика. Вход счетчика через седьмой зо элемент «И» подсоединен к второй шине так486330 товых импульсов и выходу второго элемента

«ИЛИ», входы которого соединены с входом управления модели ветви и выходом второго элемента «И», второй вход которого подключен к единичному выходу первого триггера.

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

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

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

Предлагаемое устройство содержит генератор 1 импульсов, блок 2 управления, блок 3 моделей ветвей, блок 4 формирования циклов, блок 5 автоматического формирования топологии, состоящий из логических блоков 6 узловых функций и распределителя 7 импульсов. 4

Блок 3 моделей ветвей содержит отдельные модели ветвей, выполненные по схеме фиг. 2, где изображены задатчики начального 8 и конечного 9 узлов, счетчик 10 импульсов, триггеры 11, 12, элементы «И» 13 — 19, элементы 4

«ИЛИ» 20, 21. В модели ветви первые входы задатчиков адресов начального и конечного узлов подключены к первым шинам 22, 23 тактовых импульсов, вторые их входы — к шинам

24, 25 записи номера соответственно началь- 5 ного и конечного узла, а их выходы — к первым входам элементов «И» 14, 15 и 16, 17.

Выходы элементов «И» 16, 16 соединены с первым выходом 26 модели ветви. Вторые входы этих элементов «И», подключены к вхо- 5 дам 27, 28 управления модели ветви, а их третьи входы — к нулевому выходу триггера 11, второму выходу 29 модели ветви и первому входу элемента «И» 18. Вторые входы элементов «И» 17 и 18 связаны с входами 30, 6

31 формирования цикла модели ветви. Выход элемента «И» 17 соединен с единичным входом триггера 12, нулевой вход которого подсоединен к входу 32 сброса модели ветви, а его единичный выход и выход элемента «И» 65

18 через элемент «И» 19 и элемент «ИЛИ» 20, другой вход которого соединен с входом 33 фиксации цикла модели ветви, подключены к единичному входу триггера 11. Нулевой

5 вход триггера 11 соединен с выходом счетчика 10, вход которого через элемент «И» 13 подключен к второй шине 34 тактовых импульсов и выходу элемента «ИЛИ» 21. Входы элемента «ИЛИ» 21 соединены соответст1О венно с входом 35 управления модели ветви и выходом элемента «И» 14, второй вход которого подключен к единичному выходу триггера 11.

Логический блок 6 узловых функций, число

15 которых соответствует числу узлов сети, содержит (фиг. 3) счетчик 36 импульсов, емкость которого равна емкости счетчика 10 импульсов модели ветви, триггеры 37, 38, элементы

«И» 39 — 42, элемент «ИЛИ» 43.

20 Вход счетчика 36 импульсов через элемент

«ИЛИ» 43 подключен к выходам элементов

«И» 39 и 42, первые входы которых соединены соответственно с единичными выходами триггеров 37, 38, а остальные их входы подключе25 ны к входам 44 — 47 управления логического блока 6 узловой функции. Выход счетчика 36 подключен к нулевому входу триггера 37, выходы которого соединены с выходами 48, 49, и через элемент «И» 40, другой вход которого

30 соединен с отдельным входом 50 управления логического блока узловой функции, подключен к выходу 51 логического блока узловой функции. Два других входа 52, 26 логического блока узловой функции подключены через з5 элемент «И» 41 к нулевому входу триггера 38, единичный вход которого соединен с единичным входом триггера 37 и подключен к входу

53 сброса логического блока узловой функции, Устройство для исследования сетей работаО ет следующим образом.

Предварительно в счетчики 10 заносятся количества импульсов, пропорциональные пропускным способностям ветвей, а в задатчики адресов начального 8 и конечного 9 узлов, ко5 торые могут быть выполнены на базе счетчиков импульсов, заносятся количества импульсов, пропорциональные номерам узлов, из которых данная ветвь выходит и в которые она входит. о Триггеры 11, 37, 38 устанавливаются в единичное состояние. Синтез сети осуществляется в два этапа. На первом этапе проводится определение максимального потока через все узлы синтезируемой сети и формирование то5 пологии сети. Для этого из блока 2 управления на полюса (35, 47) подается сигнал, разрешающий прохождение импульсов ГИ в счетчики 10 и 36.

Сигнал переполнения одного из счетчиков

О 10 устанавливает триггер 11 модели ветви в нулевое состояние. Сигнал, появившийся на нулевом выходе триггера 11, поступает через выход 29 в устройство управления, запрещая поступление импульсов ГИ в счетчики 10, 36, и разрешает поступление импульсов ГИ на

486330

5 вход распределителя 7 импульсов и входы задатчиков начальных (22) и конечных (23) узлов. Сигнал о переполнении одного из задатчиков адресов узлов подается через выход 26 в блок 5 автоматического формирования топологии и в блок 2 управления, запрещая поступление импульсов ГИ на полюса (22, 23) в распределитель импульсов, и разрешает поступление импульсов ГИ. Совпадение этого сигнала с сигналом на одном из элементов (41) логического блока узловой функции (вход 62) устанавливает соответствующий триггер 38 в нулевое состояние. Тем самым запрещается поступление импульсов ГИ в соответствующий счетчик 36 до окончания первого этапа.

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

После окончания первого этапа в счетчиках

36 импульсов записаны количества импульсов, равные 1 макс где макс — емкость счетчика; п1„,„, — количество импульсов, пропорциональное максимальному потоку 1 -го узла.

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

Для этого по сигналу из блока 2 управления разрешается поступление импульсов ГИ в задатчики начальных 8 и конечных 9 узлов и формирователь гамильтоновых циклов, который, формируя цикл, устанавливает триггеры 11 в единичное состояние в тех моделях ветвей, у которых триггеры 37 находятся в единичном состоянии. При этом в счетчики 10 моделей ветвей, принадлежащих гамильтонову циклу, заносится количество импульсов, пропорциональное минимальным пропускным способностям этих ветвей. Далее на полученном множестве вновь формируется гамильтонов цикл и весь процесс повторяется.

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

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

Предмет изобретения

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

6 автоматического формирования топологии, состоящей из распределителя импульсов, вход и первый выход которого подключены к блоку управления, а каждый из остальных выходов распределителя импульсов соединен с входом логического блока узловой функции, другие входы которого соединены с блоками управления, моделей ветвей, формирования циклов; выходы логических блоков узловой функции подключены к входу блока управления; первые входы задатчиков адресов начального и конечного узлов моделей ветвей подключены к первым шинам тактовых импульсов, вторые их входы соединены с шинами записи номера соответственно начального и конечного узлов, а выходы — с первыми входами соответственно первого, второго, третьего и четвертого элементов «И», выходы которых соединены с первым выходом модели ветви, подключены к входам управления модели ветви, а их третьи входы соединены с нулевым выходом первого триггера, вторым выходсм модели ветви и первым входом пятого элемента «И», второй вход которого и второй вход четвертого элемента «И» соединены с входами формирования цикла модели ветви; выход четве,. того элемента «И» соединен с единичным входом второго триггера, нулевой вход которого подключен к входу сброса модели ветви, а его единичный вход и выход пятого элемента «И» через шестой элемент «И» и первый элемент «ИЛИ», соединенный другим входам с входîM фиксации цикла модели ветви, подключены и единичному входу первого триггера, нулевой вход которого соединен с ыходом счетчика, вход которого через седьмой элемент «И» соединеч с второй шиной тактовых импульсов и выходом второго элемента «ИЛИ». входы которого соединены с входом управления модели ветви и выходом второго элемента «И», второй вход которого подключен к единичному выходу первого триггера.

2. Устройство по п. I, отличающееся тем, что логический блок узловой функции содержит счетчик, вход которого через первый элемент «ИЛИ» подключен к выходам первого и второго элементов «И». первые входы которых соединены с единичными выходами соответственно первого и второго триггеров, а остальные их входы подключены к входам управления логического блока узловой функции; выход счетчика соединен с нулевым входом первого три"гсра, выходы которого соединены с выходами формирования цикла логического б..ока узловой функции, и через третий элемент «И», другой вход ксторого соединен с отдельным входом управления логического блока узловой функции, подключен к выходу логического блока узловой функции, два других входа которого через четвертый элемент «И» подключены к нулевому входу второго триггера, единичный вход которого соединен с единичным входом первого триггера и подключен к входу сброса логического блока узловой функции.

486330.9 t5

53 52 2о 51

Фиг.3

Редактор И. Грузова

Корректор А. Дзесова

Заказ 199111 Изд. № !858 Тираж 679 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, 5К-35. Раушская наб., д. 4 5

Типография, пр. Сапунова, 2

Составитель А. Киселев

Техред М. Семенов

О