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

 

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

15И 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АBTOPCKOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (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) УСТРОЙСТВО ДЛЯ ВЫБОРА ОПТИМАЛЬНОГО МАРШРУТА В ЦЕНТРАЛИЗОВАННОЙ СЕТИ ПЕРЕДАЧИ ДАННЫХ

„„SU„„1383388 А1 (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

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

На фиг. 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 и !0 после их обнуления записываются единичные сигналы, которые чод воздействием тактовых импульсов, поступающих в процессе работы от генератора 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, что должно наступить после записи в него n — 2 единиц (где и — число узлов в сети) с приходом последнего сигнала на его вход. В этом случае оказывается сформированным оптимальный ациклический маршрут в виде дерева с минимальным суммарным весом ребер. Одновременно сигнал переполнения счетчика 16 обеспечивает выдачу управляющего сигнала (по шине 22) на считывание информации об оптимальном маршруте с шин 21 (позиционный двоичный код) и отключение генератора 1 импульсов.

Формула изобретения

1. Устройство для выбора оптимального маршрута в централизованной сети передачи данных, содержащее генератор тактовых импульсов, коммутатор тактовых импульсов и п ключей (где п — число узлов в сети), 4 причем вход запуска устройства соединен с входом запуска генератора тактовых импульсов, выход которого соединен с информационным входом коммутатора тактовых импульсов, отличающееся тем, что, с целью повышения быстродействия, в него введены п блоков модели канала, три элемента ИЛИ, наборное поле коммутации приоритета, наборное поле коммутации топологии, два распределителя импульсов, группа из и эле10 ментов И, два счетчика, схема сравнения, элемент НЕ и два элемента И, причем первый выход коммутатора тактовых импульсов соединен с входом тактовых импульсов -го (i=l, и) блока модели канала, первый выход

15 которого соединен с управляющим входом

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

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

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

З5 ИЛИ, выход которого соединен с вторым управляющим входом коммутатора тактовых импульсов, третий выход -го блока модели канала соединен с i-м выходом наборного поля коммутации приоритета, -й выход которого соединен с входом установки при40 оритета i-го блока модели канала, i-й выход второго распределителя импульсов соединен с первым входом r-го элемента И группы, второй вход которого подключен к i-му выходу наборного поля коммутации топологий, а выход соединен с i-м входом третьего эле45 мента ИЛИ, выход которого соединен со счетным входом первого счетчика, выходы которого соединены с входами первой группы схемы сравнения и информационными входами регистра, выходы которого подключены к входам второй группы схемы сравнения, выход которой соединен с вторым входом первого элемента И и входом элемента НЕ, выход которого соединен с вторым входом второго элемента И, выход которого соединен со счетным входом второго счет55 чика, выход которого соединен с выходом синхронизации устройства и входом останова генератора тактовых импульсов, (и+1) -й выход второго распределителя импульсов

1383388

0m 8

От 4 От10

Фиг. 2

Dm 2 к 7 Dm8 От77

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

2. Устройство по п. 1, отличающееся тем, что блок модели канала содержит три элемента И, счетчик, регистр, схему сравнения, элемент НЕ, триггер текущего состояния сети, триггер приоритета и генератор одиночных импульсов, причем вход тактовых импульсов блока соединен с первым входом 10 первого элемента И, выход которого соединен со счетным входом счетчика, выходы которого подключены к входам первой группы схемы сравнения, входы второй группы которой соединены с выходами регистра, а выход соединен через элемент НЕ с вторым входом первого элемента И и первым входом второго элемента И, выход которого соединен с входом установки в «1» триггера текущего состояния сети, первым выходом блока и входом генератора одиночных импульсов, выход которого подключен к второму выходу блока, вход блокировки сброса приоритета блока подключен к входу сброса триггера текущего состояния сети, выход которого соединен с первым входом третьего элемента

И, вход сброса приоритета блока соединен с вторым входом третьего элемента И, выход которого соединен с входом сброса триггера приоритета, прямой выход которого соединен с вторым входом второго элемента И, а инверсный выход — с третьим выходом блока, вход установки приоритета блока соединен с входом установки в «I » триггера приоритета.

1383388

От Я(36) Ore 7 к 3 (36)

Фиг. Ф фиг.5

Составитель A. Чеканов

Редактор Н. Лазаренко Техред И. Верес Корректор И. Муска

Заказ 915/49 Тираж 704 Подписное

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

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4