Устройство для выбора оптимального маршрута в централизованной сети передачи данных

"АБИО,ОП- НТРА- ДАНГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ ВТОРСКОМУ СВИДЕТЕЛЬСТ(54) УСТРОЙСТВО ДЛЯ ВЫБОРАТИМАЛЬНОГО МАРШРУТА В ЦЕЛИЗОВАННОЙ СЕТИ ПЕРЕДАЧИНЫХ(57) Изобретение относится к вычислительной технике и может быть использовано при создании специализированных устройств управления. Цель изобретения - повышение быстродействия. Устройство содержит генератор 1 тактовых импульсов, коммутатор 2 тактовых импульсов, блоки 3 модели канала, элемент ИЛИ 4, наборное поле 5 коммутации приоритета, элемент ИЛИ 6, ключи 7, первый распределитель 8 импульсов, наборное поле 9 коммутации топологии, второй распределитель 10 импульсов, группу элементов И 11, элемент ИЛИ 12, первый счетчик 13, регистр 14, блок 15 сравнения, второй счетчик 16, элемент И 17, элемент НЕ 18, элемент И 19.з. п. ф., 5 ил.шим приоритетом и нулевое для всех остальных ребер положение. В блоке 5 выходы триггеров 36 с большим приоритетом ребра соединяются с входами триггеров 36 ребер более низкого приоритета. В блоке 9 осуществляется коммутация выходов ключей 7 согласно топологии графа централизованной сети передачи данных. Устройство. работает следующим образом.После включения генератора 1 импульсов (по шине 20) на вход коммутатора 2 поступают тактовые импульсы, которые через элемент И 24 подаются на входы блоков 3, в силу того, что в исходном состоянии на него подается единичный сигнал с выхода триггера 25 коммутатора 2. В блоках 3 элементы И 29 открыты сигналами с выходов узлов 37, инвертируемыми схемами НЕ 30. При этом осуществляется подсчет тактовых импульсов в счетчиках 31. После совпадения чисел, записанных в счетчике 31 и регистре 32, на выходе сравнивающего устройства 33 появляется единичный сигнал, что приводит к: закрытию входа блока 3 (снимается единичный сигнал с второго входа схемы И 29), переводу триггера 37 текущего состояния сети в единичное состояние при условии первоначальной установки в единичное состояние триггера 36 приоритета; выдаче одиночного импульса на переключение коммутатора 2 с выхода генератора 34 одиночных импульсов при указанных условиях и появлению электрического контакта между выходами соответствующего ключа 7.После появления сигнала на выходе одного из блоков 3 начинается анализ ацикличности формируемого маршрута в централизованной сети передачи данных. Импульсом с выхода генератора 34 одиночных импульсов переводится в единичное состояние триггер 25, что приводит к появлению единичного сигнала на втором входе элемента И 23 и нулевого сигнала на втором входе элемента И 24. При этом прекращается выдача тактовых импульсов к блоку 3 и происходит их перекоммутация на вход первого распределителя 8 через элемент И 26, на второй вход которого подается разрешающий сигнал с выхода триггера 27. С приходом тактового импульса на вход распределителя 8 на его первом выходе появляется единичный сигнал, который является опросным сигналом для ключа 7 и управляющим сигналом для переключения триггера 27 в единичное состояние, Последний снимает разрешающий сигнал с входа элемента И 26 и подается такой сигнал на вход элемента И 28. Происходит переключение тактовых импульсов генератора 1 на вход второго распределителя 10, который последовательно опрашивает состояние элемента И 11, зависящее от топологии графа и вида формируемого маршрута (циклического или ациклического), При этом счетчик 13 фиксирует текущую сумму импульсов, По оконча 1383388Изобретение относится к вычислительнойтехнике и может быть использовано при создании специализированных устройств управления, специализированных устройствдля решения ряда оптимизационных задач,формулируемых в терминах теории графов. 5Цель изобретения - повышение быстродействия.На фиг. 1 представлена структурная схема устройства; на фиг. 2 - структурнаясхема коммутатора тактовых импульсов; Она фиг. 3 - структурная схема блока моделиканала; на фиг. 4 - наборное поле коммутации приоритета; на фиг, 5 - наборноеполе коммутации топологии.Устройство содержит генератор 1 тактовых импульсов, коммутатор 2 тактовых импульсов, блоки 3 модели канала, первыйэлемент ИЛИ 4, наборное поле 5 коммутацииприоритета, второй элемент ИЛИ 6, ключи 7,первый распределитель 8 импульсов, наборное поле 9 коммутации топологии, второйраспределитель 10 импульсов, группу элементов И 11, третий элемент ИЛИ 12, первыйсчетчик 13, регистр 14, схему 15 сравнения,второй счетчик 16, первый элемент И 17,элемент И 18, второй элемент И 19 и имеетвход 20 запуска, информационные выходы 21выход 22 синхронизации.Коммутатор 2 тактовых импульсов(фиг. 2) содержит первый 23 и второй 24элементы И, первый триггер 25, третий элемент И 26, второй триггер 27, четвертый элемент И 28,Блок 3 модели канала (фиг. 3) содержитпервый элемент И 29, элемент НЕ 30, счетчик 31, регистр 32, схему 33 сравнения, генератор 34, одиночных импульсов, второйэлемент И 35, триггер 36 приоритета,триггер 37 текущего состояния сети, третий элемент И 38.Выходы ключей 7 коммутируются согласно топологии графа централизованной сетипередачи данных в блоке 9. Аналогично вблоке 5 производится коммутация входов 40и выходов триггеров 36 в соответствии с ихприоритетом при одинаковом весе каналовребер соответствующего графа, Коммутациипроизводятся с помощью установки перемычек в соответствующие гнезда наборныхполей 5 и 9. 45Подготовка устройства к работе заключается в следующем. Обнуляются счетчики 13, 16 и 31, регистр 14, триггеры 25, 27,37. В распределители 8 и 1 О после их обнуления записываются единичные сигналы,которые чод воздействием тактовых импульсов, поступающих в процессе работы от генератора 1 через соответствующие выходыкоммутатора 2, последовательно возбуждают один из выходов распределителей. Врегистры 32 записывается информация о весе соответствующего ребра, триггер 36 дляребер с различным весом устанавливаетсяв единичное положение, для ребер с одинаковым весом - в единичное для ребра с выс 1383388нии опроса с последнего выхода распределителя 10 происходит переключение коммутатора 2 (триггера 27, переводимого в нулевое состояние) . Подается следующий тактовый импульс на вход первого распределителя 8, что приводит к появлению опросного единичного сигнала на его втором выходе и т. д. По окончании цикла опросов анализируется вид формируемого маршрута путем сравнения предыдущей текущей суммы импульсов, хранимой в регистре 14, с суммой, зафиксированной счетчиком 13. При совпадении последних (маршрут циклический) на выходе схемы 15 сравнения появится единичный сигнал, который готовит цикл исключения ребра из маршрута. Сигналом с предпоследнего выхода распределителя 8 через элементы И 17 и 38 переводится в нулевое состояние триггер 36. При этом снимается управляющий сигнал с входа ключа 7, что приводит к разрыву электрического контакта между выходами и к переключению триггера 36 ребра с равным весом и более низким приоритетом, если такой скоммутирован в блоке 5. Анализ ацикличности маршрута при наличии такого ребра проводится аналогично описанному.Если же формируемый маршрут ациклический, суммы в регистре 14 и счетчике 13 различны, на выходе схемы 15 присутствует нуЛевой сигнал, который запрещает цикл возврата (элемент И 17 заперт) и, инвертируясь на элементе НЕ 18, подготавливает устройство к переходу для поиска нового ребра, включаемого в маршрут. Сигналом с последнего выхода распределителя 8 увеличивается на единицу содержимое счетчика 16, разрешается запись текущей суммы из счетчика 13 в регистр 14, обнуляются триггеры 37 и 25. В результате тактовые импульсы вновь поступают на входы блоков 3 до тех пор, пока не будет найдено следующее ребро с минимально возможным весом. Далее устройство работает подобно описанному до момента переполнения счетчика 16, что должно наступить после записи в него и - 2 единиц (где и - число узлов в сети) с приходом последнего сигнала на его вход. В этом случае оказывается сформированным оптимальный ациклический маршрут в виде дерева с минимальным суммарным весом ребер. Одновременно сигнал переполнения счетчика 16 обеспечивает выдачу управляющего сигнала (по шине 22) на считывание информации об оптимальном маршруте с шин 21 (позиционный двоичный код) и отключение генератора 1 импульсов.Формула изобретения1, Устройство для выбора оптимального маршрута в централизованной сети передачи данных, содержащее генератор тактовых импульсов, коммутатор тактовых импульсов и и ключей (где и - число узлов в сети),4причем вход запуска устройства соединен с входом запуска генератора тактовых импульсов, выход которого соединен с информационным входом коммутатора тактовых импульсов, отличающееся тем, что, с целью повышения быстродействия, в него введены и блоков модели канала, три элемента ИЛИ, наборное поле коммутации приоритета, наборное поле коммутации топологии, два распределителя импульсов, группа из и эле ментов И, два счетчика, схема сравнения,элемент НЕ и два элемента И, причем первый выход коммутатора тактовых импульсов соединен с входом тактовых импульсов -го (=1, и) блока модели канала, первый выход 15 которого соединен с управляющим входом-го ключа и -м информационнымвыходом устройства, второй выход коммутатора тактовых импульсов соединен с входом тактовых импульсов первого распределителя импульсов, -й выход которого соединен с -м 20 входом (=1, и) первого элемента ИЛИ,входом -го ключа и -м входом первой группы входов наборного поля коммутации топологии, -й вход второй группы входов которого соединен с выходом -го ключа, (и+1) -й выход первого распределителя импульсов соединен с первым входом первого элемента И, выход которого соединен с входами сброса приоритета блоков модели канала, (и+2)-й выход первого распределителя импульсов соединен с входом синхронизации З 0 регистра, первым управляющим входом коммутатора тактовых импульсов, первым входом второго элемента И и с входом блокировки сброса приоритета блоков модели канала, вторые выходы которых соединены соответственно с входами второго элемента З 5 ИЛИ, выход которого соединен с вторымуправляющим входом коммутатора тактовых импульсов, третий выход 1-го блока модели канала соединен с -м выходом наборного поля коммутации приоритета, -й выход которого соединен с входом установки при оритета 1-го блока модели канала, -й выходвторого распределителя импульсов соединен с первым входом -го элемента И группы, второй вход которого подключен к -му выходу наборного поля коммутации топологий, а выход соединен с -м входом третьего эле мента ИЛИ, выход которого соединен сосчетным входом первого счетчика, выходы которого соединены с входами первой группы схемы сравнения и информационными входами регистра, выходы которого подключены к входам второй группы схемы сравнения, выход которой соединен с вторым входом первого элемента И и входом элемента НЕ, выход которого соединен с вторым входом второго элемента И, выход которогосоединен со счетным входом второго счет чика, выход которого соединен с выходомсинхронизации устройства и входом останова генератора тактовых импульсов, (и+ 1)-й выход второго распределителя импульсов1383388 От 8 От 70 соединен с четвертым управляющим входом коммутатора тактовых импульсов, третий выход которого соединен с тактовым входом второго распределителя импульсов.2. Устройство по п. 1, отличающееся тем, что блок модели канала содержит три элемента И, счетчик, регистр, схему сравнения, элемент НЕ, триггер текущего состояния сети, триггер приоритета и генератор одиночных импульсов, причем вход тактовых импульсов блока соединен с первым входом 10 первого элемента И, выход которого соединен со счетным входом счетчика, выходы которого подключены к входам первой группы схемы сравнения, входы второй группы которой соединены с выходами регистра, а выход соединен через элемент НЕ с вторым входом первого элемента И и первым входом второго элемента И, выход которого соединен с входом установки в 1 триггера текущего состояния сети, первым выходом блока и входом генератора одиночных импульсов, выход которого подключен к второму выходу блока, вход блокировки сброса приоритета блока подключен к входу сброса триггера текущего состояния сети, выход которого соединен с первым входом третьего элемента И, вход сброса приоритета блока соединен с вторым входом третьего элемента И, выход которого соединен с входом сброса триггера приоритета, прямой выход которого соединен с вторым входом второго элемента И, а инверсный выход - с третьим выходом блока, вход установки приоритета блока соединен с входом установки в 1 триггера приоритета.1383388 Оя 7 ф СосТехр ира РедаЗакВНИ енк. Мус д. 4/ород, ул Прои ектная От У Г 36) 3 язвФиг. Ф тор Н. Лаза915/49ИПИ Госуда113зводственно витель Л. ЧеканИ. Верес704СССР по деламРаушская наедприятие, г. Уж ственного комитета35, Москва, Ж - 3полиграфическое пр вКорректор Подписное зобретении и открыти