Устройство для выбора оптимального маршрута в централизованной сети передачи данных Советский патент 1988 года по МПК G06F15/173 

(21)4151836/24-24 .

(22)27.10.86

(46) 23.03.88. Бюл. № 11 (72) П. К. Павнитьев

(53)681.325(088.8)

(56) Авторское свидетельство СССР № 329538, кл. G 06 F 15/20, 1968. Авторское свидетельство СССР № 635490, кл. G 06 F 15/20, 1976.

(54)УСТРОЙСТВО ДЛЯ ВЫБОРА ОПТИМАЛЬНОГО МАРШРУТА В ЦЕНТРАЛИЗОВАННОЙ СЕТИ ПЕРЕДАЧИ ДАННЫХ

(57) Изобретение относится к вычислительной технике и может быть использовано при создании специализированных устройств управления. Цель изобретения - повышение быстродействия. Устройство содержит генератор 1 тактовых импульсов, коммутатор 2 тактовых импульсов, блоки 3 модели канала, элемент ИЛИ 4, наборное поле 5 коммутации приоритета, элемент ИЛИ 6, ключи 7, первый распределитель 8 импульсов, наборное поле 9 коммутации топологии, второй распределитель 10 импульсов, группу элементов И 11, элемент ИЛИ 12, первый счетчик 13, регистр 14, блок 15 сравнения, второй счетчик 16, элемент И 17, элемент НЕ 18, элемент И 19. I 3. п. ф., 5 ил.

(Л

СО 00

со

00 00

00

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

Цель изобретения - повышение быстродействия.

На фиг. 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. Аналогично в

10

15

шим приоритетом и .нулевое для всех осталь ных ребер положение. В блоке 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 оди- 2Q ночных импульсов при указанных условиях и появлению электрического контакта между выходами соответствующего ключа 7.

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

20

25

45

блоке 5 производится коммутация входов 40 элемента И 24. При этом прекращается выи выходов триггеров 36 в соответствии с их

приоритетом при одинаковом весе каналов

ребер соответствующего графа. Коммутации

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

полей 5 и 9.

Подготовка устройства к работе заключается в следующем. Обнуляются счетчики 13, 16 и 31, регистр 14, триггеры 25, 27, 37. В распределители 8 и 10 после их обнуления записываются единичные сигналы, которые 10Д воздействием тактовых импульсов, поступающих в процессе работы от генератора 1 через соответствующие выходы коммутатора 2, последовательно возбуждают один из выходов распределителей. В регистры 32 записывается информация о весе соответствующего ребра, триггер 36 для ребер с различным весом устанавливается в единичное положение, для ребер с одинаковым весом - в единичное для ребра с высдача тактовых импульсов к блоку 3 и происходит их перекоммутация на вход первого распределителя 8 через элемент И 26, на второй вход которого подается разрешающий сигнал с выхода триггера 27. С приходом тактового импульса на вход распределителя 8 на его первом выходе появляется единичный сигнал, который является опросным сигналом для ключа 7 и управляющим сигналом для переключения триггера 27 в единичное состояние. Последний снимает разрешающий сигнал с входа элемента И 26 и подается такой сигнал на вход элемента И 28. Происходит переключение тактовых импульсов генератора 1 на вход второго распределителя 10, который последователь- 55 но опрашивает состояние элемента И 11, зависящее от топологии графа и вида формируемого маршрута (циклического или ациклического). При этом счетчик 13 фиксирует текушую сумму импульсов. По оконча50

0

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 оди- Q ночных импульсов при указанных условиях и появлению электрического контакта между выходами соответствующего ключа 7.

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

0

5

0 элемента И 24. При этом прекращается вы5

дача тактовых импульсов к блоку 3 и происходит их перекоммутация на вход первого распределителя 8 через элемент И 26, на второй вход которого подается разрешающий сигнал с выхода триггера 27. С приходом тактового импульса на вход распределителя 8 на его первом выходе появляется единичный сигнал, который является опросным сигналом для ключа 7 и управляющим сигналом для переключения триггера 27 в единичное состояние. Последний снимает разрешающий сигнал с входа элемента И 26 и подается такой сигнал на вход элемента И 28. Происходит переключение тактовых импульсов генератора 1 на вход второго распределителя 10, который последователь- 5 но опрашивает состояние элемента И 11, зависящее от топологии графа и вида формируемого маршрута (циклического или ациклического). При этом счетчик 13 фиксирует текушую сумму импульсов. По оконча0

НИИ опроса с последнего выхода распределителя 10 происходит переключение коммутатора 2 (триггера 27, переводимого в нулевое состояние). Подается следующий тактовый импульс на вход первого распределителя 8, что приводит к появлению опросного единичного сигнала на его втором выходе и т. д. По окончании цикла опросов анализируется вид формируемого маршрута путем сравнения предыдущей текущей суммы импульсов, хранимой в регистре 14, с суммой, зафиксированной счетчиком 13. При совпадении последних (марщрут циклический) на выходе схемы 15 сравнения появится единичный сигнал, который готовит цикл исключения ребра из маршрута. Сигналом с предпоследнего выхода распределителя 8 через элементы И 17 и 38 переводится в нулевое состояние триггер 36. При этом снимается управляющий сигнал с входа ключа 7 что приводит к разрыву электрического контакта между выходами и к переключению триггера 36 ребра с равным весом и более низким приоритетом, если такой скоммути- рован в блоке 5- Анализ ацикличности мар- щрута при наличии такого ребра проводится аналогично описанному.

Если же формируемый марщрут ациклический, суммы в регистре 14 и счетчике 13 различны, на выходе схемы 15 присутствует нуЛевой сигнал, который запрещает цикл возврата (элемент И 17 заперт) и, инвертипричем вход запуска устройства соединен с входом запуска генератора тактовых импульсов, выход которого соединен с информационным входом коммутатора тактовых импульсов, отличающееся тем, что, с целью повышения быстродействия, в него введены п блоков модели канала, три элемента ИЛИ, наборное поле коммутации приоритета, наборное поле коммутации топологии, два распределителя импульсов, группа из я эле10 ментов И, два счетчика, схе.ма сравнения, элемент НЕ и два элемента И, причем первый выход коммутатора тактовых импульсов соедин ен с входом тактовых импульсов /-го (, п) блока модели канала, первый выход

г которого соединен с управляющим входом /-ГО ключа и г -м информационным выходом устройства, второй выход коммутатора тактовых импульсов соединен с входом тактовых импульсов первого распределителя импульсов, г -й выход которого соединен с г -м

20 входом (, п) первого элемента ИЛИ, входом /-ГО ключа и /-м входом первой группы входов наборного поля коммутации топологии, г -й вход второй группы входов которого соединен с выходом / -го ключа, (п-(-1) -и выход первого распределителя импульсов соединен с первым входом первого элемента И, выход которого соединен с входами сброса приоритета блоков .модели канала, ()-й выход первого распределителя импульсов соединен с входом синхронизации

руясь на элементе НЕ 18, подготавливает о регистра, первым управляющим входом ком- устройство к переходу для поиска нового ребра, включаемого в марщрут. Сигналом с последнего выхода распределителя 8 увеличивается на единицу содержимое счетчика 16, разрешается запись текущей суммы из счетчика 13 в регистр 14, обнуляются триггеры 37 и 25. В результате тактовые импульсы вновь поступают на входы блоков 3 до тех пор, пока не будет найдено следующее ребро с минимально возможным весом. Далее устройство работает подобно

35

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

чика 16, что должно наступить после записи в него п-2 единиц (где.« - число узлов в сети) с приходом последнего Сигнала на его вход. В этом случае оказывается сформированным оптимальный ациклический марщрут в виде дерева с минимальным суммарным весом ребер. Одновременно сигнал переполнения счетчика 16 обеспечивает выдачу управляющего сигнала (по шине 22) на считывание информации об оптимальном

45

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

входами регистра, выходы которого подклюмарщруте с шин 21 (позиционный двоичный чены к входам второй группы схемы сравнения, выход которой соединен с вторым входом первого элемента И и входом элемента НЕ, выход которого соединен с вторым входом второго элемента И, выход которого соединен со счетным входом второго счеткод) и отключение генератора 1 импульсов. Формула изобретения

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

данных, содержащее генератор тактовых импульсов, коммутатор тактовых импульсов и п ключей (где п - число узлов в сети).

синхронизации устройства и входом останова генератора тактовых импульсов, ( выход второго распределителя импульсов

причем вход запуска устройства соединен с входом запуска генератора тактовых импульсов, выход которого соединен с информационным входом коммутатора тактовых импульсов, отличающееся тем, что, с целью повышения быстродействия, в него введены п блоков модели канала, три элемента ИЛИ, наборное поле коммутации приоритета, наборное поле коммутации топологии, два распределителя импульсов, группа из я эле0 ментов И, два счетчика, схе.ма сравнения, элемент НЕ и два элемента И, причем первый выход коммутатора тактовых импульсов соедин ен с входом тактовых импульсов /-го (, п) блока модели канала, первый выход

г которого соединен с управляющим входом /-ГО ключа и г -м информационным выходом устройства, второй выход коммутатора тактовых импульсов соединен с входом тактовых импульсов первого распределителя импульсов, г -й выход которого соединен с г -м

0 входом (, п) первого элемента ИЛИ, входом /-ГО ключа и /-м входом первой группы входов наборного поля коммутации топологии, г -й вход второй группы входов которого соединен с выходом / -го ключа, (п-(-1) -и выход первого распределителя импульсов соединен с первым входом первого элемента И, выход которого соединен с входами сброса приоритета блоков .модели канала, ()-й выход первого распределителя импульсов соединен с входом синхронизации

о регистра, первым управляющим входом ком-

о регистра, первым управляющим входом ком-

35

мутатора тактовых импульсов, первым входом второго элемента И и с входом блокировки сброса приоритета блоков модели канала, вторые выходы которых соединены соответственно с входами второго элемента ИЛИ, выход которого соединен с вторым управляющим входом коммутатора тактовых импульсов, третий выход /-го блока модели канала соединен с /-м выходом наборного поля коммутации приоритета, /-и выход которого соединен с входом установки при40 оритета /-го блока модели канала, /-и выход

5

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

синхронизации устройства и входом останова генератора тактовых импульсов, ( выход второго распределителя импульсов

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

ночных импульсов, причем вход тактовых

импульсов блока соединен с первым входом10 с вторым входом третьего элемента И, выход

первого элемента И, выход которого соеди-которого соединен с вхбдом сброса триггера

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

пы схемы сравнения, входы второй группыа инверсный выход - с третьим выходом

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

а выход соединен через элемент НЕ с вторым соединен с входом установки в «1 триггера

входом первого элемента И и первым входомприоритета.

Отв Omj7 Фи.г.3

второго элемента И, выход которого соединен с входом установки в «1 триггера текущего состояния сети, первым выходом блока и входом генератора одиночных импульсов, выход которого подключен к второму выходу блока, вход блокировки сброса приоритета блока подключен к входу сброса триггера текущего состояния сети, выход которого соединен с первым входом третьего элемента И, вход сброса приоритета блока соединен

с вторым входом третьего элемента И, выход

Qtn 2

От 3(36)

О О О

1

К 3(361 ФигЛ

т 8

От 7

/ч

Л7 О И к ребра

U «-К / к о-о-о-о-о

о-о-о-о-о2/

0-0-0-0-0 п.вершины

иг.5