Устройство маршрутизации

Устройство маршрутизации

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и технике связи и может использоваться при проектировании устройств обработки данных и построении узлов коммутации на сетях передачи дискретной информации. Цель изобретения - повышение пропускной способности сети связи за счет сокращения объема передаваемой служебной информации и повышение скорости реконфигурации. Сущность изобретения заключается в том, что в устройство, содержащее мультиплексор 2, блок ввода-вывода 1, демультиплексор 3, блок памяти рельефов 4, блок сравнения рельефов 5, блок анализа 6, генератор тактовых импульсов 8, сумматор 7 и блок управления 9, дополнительно введены блок отказа 10, блок памяти оптимальных маршрутов 11, блок памяти признаков 12 и блок дешифрации 13. Эффективность устройства пропорциональна числу узлов сети связи, построенной на его основе. 12 ил.

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

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

РЕСПжЛИН

Щ) С 06 Р 15 16

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР и АВТОРСКОМУ СВИДЕТЕЛЬСВ ВУ

1 (2Я 4353397/24-24 (22) 30.12.87 (46) 23.08.90. Бюл. Р 31 (72) Ю.Н.Максименко и В.С.Ракошиц (53) 681. 325(088.8) (56) Авторское свидетельство СССР

У 1432546, кл. С 06 F 1.5/16, 1986.

Авторское свидетельство СССР

Ф 1499370, кл, С 06 F 15/20, 1987. (54) УСТРОЙСТВО МАРШРУТИЗАЦИИ (57) Изобретение относится к вычислительной технике и технике связи и может использов аться при проектировании устройств обработки данных и построении узлов коммутации на сетях передачи дискретной информации.

Цель изобретения — повышение проSU«1587530 А1

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

9, дополнительно введены блок отказа 10, блок памяти оптимальных маршрутов 11, блок памяти признаков 12 и блок дешифрации 13. Эффективность устройства пропорциональна числу узлов сети связи, построенной на его основе. 12 ил.

1587530

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

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

На фиг.1 представлена блок-схема предлагаемого устройства;на фиг.2 процедура маршрутизации; на фиг.3— функциональная схема блока управлег ния; на фиг.4 — функциональная схема блока отказа; на фиг.5 — функциональная схема блока памяти рельефов; на фиг.б — функциональная схема блока 20 памяти оптимальных маршрутов; на фиг.7 — функциональная схема блока памяти признаков; на фиг. 8 — функциональная схема блока анализа;на фиг.9функциональная схема демультиплексо- 25 ра; на фиг. 10 — функциональная схема блока ввода-вывода; на фиг.11 функциональная схема блока сравнения рельефов; на фиг.12 — функциональная схема блока дешифрации. 30

Устройство (фиг.1) содержит блок

1 ввода-вывода, мультиплексор 2, демультиплексор 3, блок 4 памяти ре льефов, блок 5 сравнения рельефов, блок 6 анализа, сумматор 7, генератор 8 тактовых импульсов, блок 9 уп35 равления, блок 10 отказа, блок 11 памяти оптимальных маршрутов, блок 12 памяти признаков и блок 13 дешифрации.

Устройство имеет (n+1) информационных входов 14, (п+1) информационных выходов 15, адресный вход 16, rpynny (и+1) входов 17 восстановления ветвей, вход 18 начальной уста- 45 новки, Блок 9 управления (фиг.3) содержит триггер 19 сканирования, вход 20 текущего отказа транзитного направления, счетчик 21 адреса, элемент 22

50 задержки, второй 23, третий 23 первый 23" тактовые входы, дешифЬ+2 ратор 24, триггер 25 гашения, вход

26 запроса гашения, шифратор 27 команд вход 28 отказа собственного наЭ

55 правления, регистр 29, группу элементов И 30, информационный выход 31, первый элемент И 32, первый адресный вход 33, первый элемент ИЛИ 34, второй элемент И 35, третий элемент

И 36, выход 37 признака сканирования, четвертый элемент И 38, второй элемент ИЛИ 39, третий элемент ИЛИ 40.

Блок 10 отказа (фиг.4) содержит схему 41 контроля, информационный вход 42, n+1 разрядный регистр 43, выходы 441 — 44 " отказа транзитных направлений и инверсные выходы 451— Ъ

45 отказов транзитных направлений, первый элемент ИЛИ 46, второй элемент ИЛИ 47, выход 48 схемы 41 конт-: роля, вход 49 командного отказа, и+1 элементов И 50, n+! элементов

ИЛИ 51.

Блок 4 памяти рельефов (фиг,5) содержит и групп по ш регистров 52,. в каждой группе (i = 1, 2-,...,n), (j = 1, 2,...,m), n групп по m элеб ментов И 53. в каждой группе, информационный вход 54, и групп по ш элементов И 55; в каждой группе, входы

56 — 56 адресных сигналов считывания, h элементов ИЛИ 57, информационные выходы 58 — 58 ", и групп по

m элементов И 59, в каждой группе, входы 60 — 60 " адресных сигналов записи, по m элементов И 61 в каж-! дой группе, входы 62 — 62 адресных сигналов сканиров ания, п групп по m элементов ИЛИ 63 в каждой

1 группе °

Блок 11 памяти оптимальных маршрутов (фиг.6) содержит и групп no rn триггеров 64 в каждой группе, и групп по m элементов И 65, 1 информационные входы 66 — 66 входы 67 — 67 адресных сигналов записи маршрутов, m элементов И 68., входы 69 — 69 адI ресных сигналов гашения, элемент

НЕ 70, вход 71 запроса квитирован ия, элемент 72 з аде ржки, вход 7 3 гашения, m элементов ИЛИ 74, входы

75 — 75 адресных сигналов обнуления, и групп по ш элементов .И 76;, l и элементов ИЛИ 77, выходы 78 — 78" инверсной маршрутизации, и групп по

m элементов И 791, входы 80 — 80" адресных сигналов считывания маршрутов, и элементов ИЛИ 81, выходы

82 — 82 " маршрутиз ации.

Блок 12 памяти признаков (фиг.7) содержит m триггеров 83 признака запроса, m триггеров 84 признака переформирования.ю элементов И 85> вход 86

J признака трансляции, m элементов

И 87, входы 88" — 88 адресных сиг1587530 налов квитирования, вход 89 формирования,m элементов И 90,m элементов

ИЛИ 91, ч элементов И 92,m элементов И 93, m элементов ИЛИ 94, m элементов И 95, m элементов И 96,,входы 97 — 97 адресных сигналов считьвания признака переформирования, элемент ИЛИ 98, выход 99 признака переформирования, элемент IUIH 100, выход 101 запроса формирования, m элементов 102 задержки, m элементов 103 задержки.

Блок 6 анализа (фиг .8) содержит первые и элементов И 104, вторые п элементов И 105, элементы НЕ 106, третьи п элементов И 107, первый элемент ИЛИ 108, первый элемент ИЛИ-НЕ

109, первый элемент И 110, элемент 111 задержки, второй элемент ИЛИ 112 третий элемент ИЛИ 113, второй элемент И 114, элемент НЕ 115, вход

116 формирования рельефа, четвертый элемент ИЛИ 117, выход 118 разрешения, третий элемент И 119, четвертый элемент И 120, вход. 121 нулевого рельефа, элемент НЕ 122, элемент НЕ

123, пятый элемент И 124, вход 125 запроса, элемент НЕ 126, выход 127 исходного квитирования, шестой элемент И 128, вход 129 квитирования, второй элемент ИЛИ-НЕ 130, вход 131 сканирования, элемент И-НЕ 132, элемент НЕ 133, восьмой элемент И 134, выход 135 блокировки.

Демультиплексор 3 (фиг.9) содержит и элементов И 136, первые n+f элементов И-НЕ 137, вторые и+1 элементов И-НЕ 138, и элементов ИЛИ 139, элементы НЕ 140 — 140 и+ 1 третьих элементов И-НЕ 141, элемент HE

142, и+1 элементов И 143, информационный вход 144.

Блок 1 ввода-вьвода (фиг.10) содержит входной регистр 145, выходной регистр 146, шифратор 147 команд, регистр адреса 148, первый элемент

И 149, второй элемент И 150, второй адресный выход 15t элемент ИЛИ-НЕ

152, первый элемент ИЛИ 153, второй элемент ИЛИ 154, третий элемент

И 155, элемент НЕ 156, четвертый элемент И 157, рельефный вход 158, третий элемент ИЛИ 159, первый элемент ИЛИ-НЕ 160, второй элемент И-НЕ 161, элемент 162 задержки, пятый элемент И 163, командный выход 164, четвертый элемент ИЛИ 165, третий адресный выход 166.

6

Блок 5 сравнения рельефов (фиг,11) содержит п-1 групп по и-k схем 167 попарного сравнения (k = 1,2,. ..n-1),п элементов И 168,п,групп элементов Й 169, группу элементов ИЛИ

170, информационные вь:оды 1 71, элемент ИЛИ-НЕ 172.

Блок 13 дешифрации (фиг.12) содержит дешифратор 173 кода, первый дешифратор174 адреса, второй дешифратор 175 адреса, матрицу элементов

И 176 (j = 1,2,...,m, k = 1,2,. ° .,7), m групп по пять элементов ИЛИ 177-181.

В исходчом состоянии физический адрес устройства по адресному входу

16 заносится в регистр 148, а по входу 18 поступает единичый потенциал, который обнуляет регистр .52 блока 4 памяти рельефов, устанавливает в ноль триггеры 64 блока 11 памяти оптимальных маршрутов, обнуляет элемент И 95 признака запроса и элемент И 96 признака переформирования блока 12 памяти признаков, обнуляет регистр 43 блока 10 отказа, устанавливает в ноль триггер 19 сканирования и триггер 25 гашения бло— ка 9 управления и запускает генератор 8 тактовых импульсов.

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

По информационным входам 14 1-14 "" поступают сообщения, которые поочередно .в соответствии с последовательностью тактовых импульсов, вырабатываемых генератором 8 и поступающих по входам 23 — 23 "" на мультиплексор 2, коммутируются на информационный вход 42 мультиплексора 2 и по входу 42 поступают на блок 1 ввода-вывода и блок 10 отказа. С входа

42 блока 10 отказа принятые сообщения поступают на схему 41 контроля, где осуществляется проверка его, например, по четности. Если произошел отказ i-й (i = 1, 2,...,п+1) ветви, то на выхбде 48 схемы контроля (фиг.4) формируется единичньш .потенциал, который через элемент ИЛИ 47 поступает на первые входы элементов

И 501 —. 50 ", На вторые входы этих элементов по входам 23 — 23 "" поступают тактовые импульсы с выхода

1)87530 генератора 8, которые определяют подключенное входное направление. В данном случае по входу 23. поступаг ет тактовый импульс, который открывает элемент И 50. и разрешает за1 пись единицы в i-й разряд регистра 43. Если произошел отказ i-ro транзитного направления (i = 1, 2,...,п), то на входе 20 элемента

ИЛИ 46 формируется сигнал отказа транзитного направления, если произошел отказ ветви, связывающей узел со своим абонентом, то на входе 28. формируется сигнал отказа собственного направления. Сигнал аппаратного отказа с выхода 48 схемы 41 контроля поступает на шифратор 147 команд регистра 1 ввода-вывода. На выходе шифратора 147 формируется код командйого отказа, который через элемент ИЛИ 165 поступает на кодовую часть регистра 146, откуда по входу 144 поступает на информационные входы элементов И 143 —

143 " демультиплексора 3. Направление коммутации командного отказа определяется элементами И-НЕ 137 и

138. При отказе i-го направления на выходе элемента И-НЕ 138. форми1 руется единичный потенциал, который разрешает выдачу командного отказа на информационный выход 15, ° Все остальные выходные направления будут заблокированы нулевыми потенциалами с .выходов своих элементов И-НЕ

138. Кодовая часть принятого с ошибкой сообщения блокируется сигналом аппаратного отказа с выхода 48 с помощью элемента ИЛИ-НЕ 161 блока

1 ввода-вывода. На выходе элемента

ИЛИ-НЕ 161 формируется нулевой потенциал, который блокируется элементом И 163. Таким образом, если произошел отказ входящей ветви, то устройство .маршрутизации фиксирует отказавшее входное направление в регистре 43 и формирует ответное сообщение об отказе ветви, которое по исправной обратной ветви транслируется в устройство маршрутизации смеж.ного узла. Командный отказ в составе сообщения поступает в смежный узел, дешифрируется дешифратором 173 кода блока 13 дешифрации, в виде единичного потенциала с входа 49 поступает на вход элемента KIN 47 блока 10 отказа и записывается в соответствующий разряд регистра 43. Таким обра10

30 зом, осуществляется обнаружение отказавшей ветви в ее приемной части с помощью аппаратного контроля и локализация передающей части отказавшей ветви с помощью командного отказа. В качестве командного отказа

i может быть использован результат тестового программного контроля. Дальнейшая обработка командного и àïïàратного отказов происходит аналогичным образом. Если произошел отказ собственного n+1-го направления, связывающего узел со своим абонен- том, то на входе 28 блока 10 отказа формируется единичный потенциал, который поступает на шифратор 27 команд блока 9 управления. На выходе шифратора 27 формируется код команды обнуления, который записывается в кодовую часть регистра 29, Одновременно физический адрес устройства, хранящийся в регистре 148 адреса, по входу 33 через элемент И 32 и элемент ИЛИ 34 заносится в адресную часть регистра 29. Сформированное блоком 9 управления сообщение, содержащее код Обнуление" и физический адрес устройства„ по (п+2)-му. тактовому импульсу поступает íà (n+2)-й

55 информационный вход мультиплексора

2 и записывается в регистр 145 блока,1 ввода-вывода. Рельефная часть регистра 145 по (и+2)-му тактовому импульсу обнуляется, а содержимое

35 кодовой и адресной частей по выходам

164 и 166 поступает на дешифратор

1?3 кода и второй дешифратор 175 адреса. блока 13 дешифрации. На входе

40 75 () — адрес обрабатываемого сообщейия) формируется единичный потенциал, который через элемент ИЛИ 178.

3 по входу 97 поступает на элемент

И 96 блока 12 памяти признаков и

4S считывает 1-й триггер 84 признака . переформирования. Если триггер 84>. находится в единичном состоянии, то на выходе элемента ИЛИ 98 формируется единичный потенциал, который поступает на первые входы элементов

И 91 — 91™. Ha второй вход элемента

И 91 по входу 75 . поступает адресJ 3 ный сигнал обнуления с выхода блока

13 дешифрации. Совместное появление укаэанных сигналов открывает элемент

И 91. и через элемент ИЛИ 93. и эле1 J мент 102 задержки происходит обну5 ление триггера 84„., Величина задержки элемента 102 равна длительности

5 !

О

9 158 тактового импульса. Сигнал признака переформирования с выхода элемента

И 98 по выходу 99 поступает на элемент ИЛИ 117 блока 6 анализа и по выходу 127 поступает на входы разрешения элементов И 143 — 143 " " демультиплексора 3. Сообщение, содержащее код обнуления и адрес обнуленного рельефа, по входу 144 поступает на демультиплексор 3 и коммутируется по исправным выходным направлениям. Направленная коммутация определяется по нулевым состояниям триггеров 64 блока 11 памяти оптимальных маршрутов, которые считываются адресными сигналами обнуления по входам 75 — 75 через элементы ИЛИ 74 — 74 Считанные нулевые состояния триггеров 64, соответствующих 1-му адресу обнуля-емого рельефа, через элементы И 76, ИЛИ 77 по. выходам 78 " — 78" поступают на демультиплексор 3, где через элемент ИЛИ 139 поступают на управ1 ю ляющие входы элементов И 143 — 143

Если признак переформирования на выходе 99 был в нулевом состоянии, то на выходе 118 разрешения устанавливается нулевой потенциал, который блокирует элементь1 И 143 — 143 " демультиплексора 3. Признак переформирования указывает на состояние соответствующего рельефа. Если рельеф не сформирован или находится в состоянии переформирования, то признак переформирования устанавливается в нулевое состояние, если рельеф находится в работоспособном состоянии, то его признак переформирования установлен в единичное состояние. Обработка сообщения обнуления в других устройствах аналогична описанному, Единственное отличие заключается в том,. что сообщение обнуления поступает в устройство по одному из транзитных направлений 14" — 14 " и по адресным сигналам записи, формируемым на выходах 60 -60 элементами ИЛИ 177 —

177 блока 13 дешифрации, осуществляется запись по входу 54 через элементы И 53 нулевого рельефа по направлению поступления сообщения обнуления, определяемому элементами И 59.

Если произошел отказ транзитного направления, то на входе 20 элемента ИЛИ 46 блока 10 отказа формируется единичный потенциал, который поступает на блок 9 управления,где

7530 10 устананливает в ноль счетчик 21 адреса и устанавливает в единицу триг- гер 19 сканиронания. Триггер 19 единичным выходом открывает элемент

И 36 и тактовые импульсы по входу

23 "" поступают на вход счетчика 21 адреса. Код адреса с выхода счетчика

21 поступает на элемент И 35, который управляется тактовыми импульсами, поступающими по входу 23 "" и задержанными элементом задержки 22 на время . Величина равна времени изменения состояния счетчика 21. Сформированный адрес через элемент ИЛИ 34 поступает в адресную часть регистра

29. Одновременно сигнал с выхода элемента И 36 поступает на шифратор 27 команд, на выходе которого формируется код сканирования. Этот код с выхода шифратора 27 поступает на кодовую часть регистра 29. Сформированное в регистре 29 сообщение, содержащее код сканирования и адрес

25 рельефа, по (n+2)-му тактовому импульсу через группу элементов И 30 но выходу 31 поступает на (и+2)-й информационный вход мультиплексора

2 и по его входу 42 по тому же (n +

+ 2)-му тактовому импульсу транслируется на входной регистр 145 блока 1 ввода-вывода. Кодовая и адресная части принятого в регистре 145 сообщения передаются в блок 13 дешифрации соответственно по выходам 164 и 166. На входах 131 сканирования блока 13 дешифрации формируется единичный потенциал, который поступает на блок 6 анализа и через элемент

ИЛИ-HE 130 закрывает элемент И 134, тем самым блокируя трансляцию сообщения сканирования на выход устройства. На входах 62 — 62 блока 13 дешифрации формируется адресный сигнал сканирования, который поступает на элементы И 61. блока 4 памяти рельефов. Адресные сигналы на входах

62" — 62" выбирают строку памяти рельефов. Выбор направления в этой строке осуществляется сигналами отказа транзитных направлений, поступающими по выходам 44 — 44 ". Совпадение указанных сигналов на входах одного из элементов И 61 формирует единичный потенциал на его выходе, который через элемент ИЛИ 63 поступает на управляющий вход соответству. ющего элемента И 53. На информационный вход 54 поступает нулевой ре7530 12

11 158 льеф с выхода рельефной части регистра 145. Таким образом, в выбранном

Ч регистре 52 через соответствующий элеменд И 53 записывается нулевой рельеф

Адресный сигнал сканирования на входах 62j (j 1., 2,...,m) через элемент ИЛИ 180J поступает по входу 80 на элементы И 79 блока 11, соответствующие )-му адресу. Считывается

j-я строка блока 11 памяти оптимальных маршрутов, которая через элементы ИЛИ 81 поступает по выходам 82

82 на блок 6 анализа. В блоке 6 на

Щ выходе 26 формируется запрос гашения j-го рельефа в случае, если отказ маскирует единственный оптимальный маршрут (кратчайшее направление) и если j-й рельеф находится в работоспособном состоянии и его признак переформирования равен единице. Укаэанные условия реализуются элементами И 107, ИЛИ 108, ИЛИ-НЕ 109, элементом И 110 и элементом 111 задержки. Задержка элемента 111 равна длительности тактового импульса и необходима для синхронизации работы триггера 25 блока 9 управления. Инверсный сигнал отказа i-го транзитного направления (i = 1, 2,...,n) поступает с нулевого выхода i-го разряда регистра 43 блока 10 по выходу 45, на вход элемента И 107.,тем самым

Ф

1 маскируя. х-е кратчайшие направления оптимального маршрута. Если это направление было единственным, то на выходе элемента ИЛИ"НЕ 109 формируется единичный потенциал, который поступает на элемент 110. Если i-я строка оптимальных маршрутов не нулевая, то на выходе элемента ИЛИ 108 сформирован единичный потенциал, коTîðüM поступает на элемент И 110, по входам 99 и 37 которого поступают соответственно единичные потенциалы признака переформирования и признака сканирования. На выходе элемента .И 110 формируется единичный потенциал, который через элемент 111 задержки по входу 26 поступает на единичный вход триггера 25 гашения. Потенциал с единичного выхода триггера

25 гашения поступает на шифратор 27 команд, на выходе которого формируется код гашения. Код гашения поступает на кодовую часть регистра 29. Адрес считывания на счетчике 21 адреса зафиксирован нулевым потенциалом с.выхода нулевого плеча триггера 25. Этот 5

1О

2О

?5

5О

55 же потенциал блокирует поступающие потенциалы сканирования на вход шй ратора 27 команд. Сообщение, включаю щее код гашения и адрес рельефа, с выхода регистра 29 блока управления по выходу 31 поступает через мультиплексор 2 на информационный вход 42. блока 1 ввода-вывода. Кодовые и адресные части принятого сообщения по выходам 164 и 166 поступают на блок 13 дешифрации. На одном из входов 69

69 формируется j é адресный сигнал гашения, который включает j-й элемент

И 90 блока 2 и через элемент ИЛИ 93 °

J и элемент 102 задержки устанавливает в ноль j-й триггер 84 признака переформирования. Одновременно j -й адресный сигнал гашения поступает на

j-й элемент И 68 блока 11 и через элемент ИЛИ 74 поступает на адресные входы j-х элементов И 76. Происходит считывание нулевых состояний триггеров 64 j-й строки блока 11 памяти оптимальных маршрутов. Инверсный код j-й строки памяти оптимальных маршрутов через элементы ИЛИ 77 поступает по выходам 78 на элементы

ИЛИ 139 демультиплексора 3. Сообщение, содержащее нулевой рельеф, код гашения и адрес (номер) обрабатываемого рельефа,коммутируется элементами И 143 демультиплексора 3 по вы- ходным направлениям, соответствующим нулевым состояниям триггеров j-й строки памяти оптимальных маршрутов.

Триггер 25 гашения (n+2) -м тактовым импульсом включает элемент И 38 и через элемент ИЛИ 39 устанавливает в ноль триггер 25. Прерванный процесс сканирования рельефов продолжается, а сформированное сообщение гашения транслируется по направлениям, инвераным оптимальным,или по направлениям движения волны формирования рельефа.

Устройство маршрутизации текущего узла сети принимает сообщение гашения по информационному входу 14 (i

1, 2,...,n), в i-м такте принятое мультиплексором 2 сообщение поступает по информационному входу 42 на регистр 145 блока 1 ввода-вывода, откуда кодовая и адресная части по выходам 164 и 166 поступают на блок 13 дешифрации. На входе 73 гашения дешифратора 173 кода формируется единичный потенциал и íà i-м выходе дешифратора 175 адреса формируется еди13

1587530

14 ничный потенциал. совместное включение указанных сигналов включает соответствующий элемент И 176 и на входах 69, 60,. 97, 80 появляются адресные сигналы: гашения, записи, считывания признака переформирования и считывания маршрутов. В блоке 4 памяти рельефов по адресным сигналам записи с выхода 60 и тактовому импульсу с входа 23:, соответствующему

l, подключенному входному направлению, включается элемент И 591., единичный потенциал с выхода которого через элемент ИЛИ 63". открывает элемент И

53 .. Нулевой рельеф, поступающий на

1 информационный вход 54, записывается в выбранныи регистр 52 1. Адресный

1 сигнал считывания признака переформирования по входу 97„поступает на элеме н т 96 блока 1 2 памя ти приз н аJ ков и считывает состояние соответствующего триггера 84 . Если триггер 84 признака переформирования

j;ro рельефа находился в единичном состоянии, то на выходе 99 формируется единичный потенциал, а соответствующий триггер 84. обнуляется с задержкой на такт с йсмощью элементов И 90, ИЛИ 93 ., элемента !02 . задержки. Элемент 102 задержки осу— ществляет необходимую задержку обнуления на один такт. По адресному сигналу считывания маршрутов с выхода 80, поступающему на управляющие входы элементов И 79, блока

11 памяти оптимальных маршрутов,считывается j-я строка, которая через элементы ИЛИ 81 — 81" .пс выходам

82" — 82" поступает на блок 6 анализа и демультиплексор 3. В блоке 6 анализа выявляется точка ветвления в дереве кратчайших маршрутов, которая содержит более чем одно направление кратчайшего пути и, если признак переформирования равен единице и признак нулевого рельефа равен нулю (т.е. сообщение гашения поступило впервые в узел, соответствующий данной точке ветвления), формируется сообщение запроса квитирования.

Точка ветвления с нулевым рельефом и единичным признаком переформирования выявляется с помощью элемента

И 120, на первый вход которого по выходу 99 поступает единичный потенциал признака переформирования, на второй вход через элемент НЕ 122 по входу 121 поступает нулевой потекциал признака нулевого рельефа, на третий вход подается единичный потенциал гашений. Оставшиеся два

5 входа элемента И 120 включаются, если j-я строка памяти оптимальных маршрутов содержит более чем одну единицу. Анализ содержимого j-й строки памяти оптимальных маршрутов осуществляется элементами ИЛИ 112, 113, И 104, 105 и НЕ 106. При этом на выходе элемента ИЛИ 113 формируется единичный потенциал, если

E выбранной j é строке памяти маршрутов записана единица по подключенному -му направленюо. На выходе элемента ИЛИ 112 формируется .единичный потенциал в том случае, если по другим неподключенным направлениям

2Î в выбранной j.-й строке памяти маршрутов записача хотя бы одна единица.

Таким образом, если в результате анализа выявлена точка ветвления, то на входе 7 1 блока 6 анализа форми25 руется единичнЫй потенциал запроса квитирования, который поступает на блок 11 памяти оптимальных маршрутов, блок 12 памяти признаков и блок

i ввода-вывода. Единичный потенциал

3п запроса квитирования поступает на шифратор 147 команд, элемент И 149 и элемент ИЛИ-НЕ 161 блока 1 вводавывода. На выходе шифратора команд

147 формируется код запроса квити35 рования, который через элемент ИЛИ

165 поступает на кодовую часть регистра 146, физический адрес устройства 43 регистра 148 подключается элементом И 149 через элемент

4О ИЛИ 153 на вторую адресную часть регистра 146. Одновременно единичный потенциал запроса квитирования через элемент ИЛИ-НЕ 161 закрывает эле.мент И 163, тем самым блокируя даль5 нейшую трансляцию кода гашения.

Сформированное сообщение, содержащее в кодовой части регистра 146 код запроса квитирсвания, адрес обрабатываемого рельефа в первой адресной

5О части регистра 146 и адрес точки ветвления во второй адресной части регистра 146, по входу 144 поступает на информационный вход демультиплексора 3. Выходное направление коммуS5 тации определяется единичным состоянием триггеров 64 блока 11 соответствующих j-й строке и выбранных соответствующим адресным сигналом считывания маршрутов. Считанные еди- . с

16 по инверсным направлениям маршрутизации. При этом прямые направления маршрутизации, соответствующие единичным состояниям j-й строки триггеров 64 памяти маршрутов, блокируются элементами И 136 с помощью нулевого потенциала блокировки, который формируется элементом И 134. Элемент И 134 отключается элементом И-НЕ 132, на вход которого поступает единичный потенциал гашения и инвертированный элементом НЕ 133 нулевой потенциал запроса гашения. Если прием сообщения гашения сопровождается появлением единичного потенциала признака нулевого рельефа на выходе блока 5 сравнения рельефов, то на выходе элемента И 119 блока 6 анализа форми20

1 руется единичный потенциал признака трансляции, который через элемент

ИЛИ 117 поступает на демультиплексор 3, разрешая дальнейшую трансляцию сообщения гашения. Одновременно единичный потенциал признака трансляций поступает на блок 12 памяти признаков, где по адре сному сигналу гашения через элементы И 85 -, ИЛИ 94 и элемент 103 задержки на такт осуществляется обнуление триггера

83 запроса.: Таким образом, точка

Ф ветвления с обнуленным рельефом транслирует сообщение гашения смежным узлам до тех пор, пока не встретится точка ветвления или сообщение не достигнет граничного узла. Направление коммутации сообщения запроса квитирования в текущих узлах определяется единичным состоянием триггеров 64 блока 11, соответствующих j-й строке памяти маршрутов, выбранной адресным сигналом считывания маршрутов. Если сообщение запроса квитирования достигло основания j то все триггеры .64 j -й строки памяти маршрутов будут в нулевом состоянии соответственно на выходах 82 маршрутизации установятся нулевые потенциалы, которые через элемент ИЛИ 108 и элемент НЕ 126. включают элемент

И 124, формируют единичный потенциал исходного квитирования, который по выходу 127 поступает на блок 1 ввода-вывода и демультиплексор 3.

С выхода 127 потенциал исходного квитирования поступает на шифратор 147 команд блока 1, на выходе которого формируется код квитирования. Код квитирования через элемент ИЛИ 165

15 1587530 ничные состояния триггеров 64 по выходам 82 поступают на элементы И 136 демультиплексора 3. На вторые входы этих элементов поступает единичный потенциал с выхода элемента И 134

5 блока 6 анализа, который в свою очередь открыт единичным потенциалом запроса квитирования через элементы НЕ 133 и И-НЕ 132, Единичные потенциалы направлений коммутации через элементы ИЛИ 139 поступают на управляющие входы элементов И 143, которые транслируют. сообщение запроса квитирования в смежные узлы. Блокировка направлений коммутации, соответствующих нулевым состояниям триггеров 64 блока 11, осуществляется элементами И 69 — 69 ", на общие

1 входы которых поступает нулевой по-. тенциал с выхода элемента НЕ 70, включенного единичным потенциалом запроса квитирования. Единичный потенциал запроса квитирования поступает на блок 12 памяти признаков, где он записывается в соответствующий j-й триггер 83 по адресному сигналу гашения через элемент И 92

Если сообщение гашения не породило сообщения — запрос квитирования, то 30 оно коммутируется по выходным направлениям, соответствующим нулевым состояниям j-й строки триггеров 64 блока 1. Считывание нулевых состояний j-й строки памяти оптимальных маршрутов осуществляется по адресному сигналу гашения, поступающему на соответствующий элемент И 68 блоЭ ка 11 памяти оптимальных маршрутов.

На общие входы элементов И 65 через 40 элемент 72 задержки поступает единичный потенциал гашения с входа 73 блока 13 дешифрации. Задержка элемента 72 должна быть не менее 8С, где с- задержка одного логического элемента. Элемент 72 задержки исключает просечки при переключении с сообщения гашения на сообщение — запрос квитирования, а величина задержки равна времени переходного процес- 50 са.

Считанные нулевые состояния j-й строки триггеров 64 памяти маршрутов через элементы И 76 и ИЛИ 77 поступают на входы 78 демультиплексора, откуда они через элементы ИЛИ 139 поступают на управляющие входы элементов И 143, Принятое сообщение гашения транслируется смежным узлом

1587530 18 поступает на кодовую часть регистоа

146. Одновременно единичный потенциал исходного квитирования поступает на элемент ИЛИ-НЕ 161 и запирает элемент И 163, блокируя тем самым принятый в регистр 145 код запроса квитирования. Сформированное в регистре 146 сообщение, содержащее код квитирования, адрес корректируемого рельефа и адрес точки ветвления по входу 144 поступает на информационный вход 144 демультиплексора З,и выдается по всем и выходным направлениям. Направления коммутации в этом случае задаются потенциалом исходного квитирования, который по выходу

127 поступает на п элементов ИЛИ 139 и открывает п исправных выходных направлений. Элементы И-HE 141 служат для блокировки отказавших направлений при отсутствии потенциала àïïàратного отказа. Появление потенциала аппаратного отказа на выходе 48 через элемент НЕ 142 снимает блокировку отказавших направлений для целей трансляции сообщения командного отказа.

Сообщение квитирования поступает в смежное устройство маршрутизации по

i-му (i = 1, 2,...,п) информационному входу 14 и i-му тактовому импульсу заносится в регистр 145, откуда кодовая и адресная части поступают соответственно по выходам 164 и 151 на дешифратор кода 173 и дешифратор 174 адреса блока 13. На входе 129 формируется единичный потенциал квитирования, а на входе 88 ь (р — адрес точки ветвления) формируется адресный сигнал квитирования, который через элемент ИЛИ 180 по входу 80 поступает на блок 11 памяP ти оптимальных маршрутов. По этому адресному сигналу считывается ф— строка памяти маршрутов, которая по выходам. 82 поступает на элементы ИЛИ

139 — 139 демультиплексора 3 и управляет его коммутацией. Сообщение квитирования транслируется в смежные устройства по направлениям, соответствующим единичным состояниям р-й строки триггеров 64 блока 11 памяти.

Если сообщение квитирования достигло точки ветвления, то на выходах

82 — 82 " блока 11 памяти будут нулевые потенциалы, на выходе элемента

НЕ 126 блока 6 анализа сформируется единичный потенциал, который откро5

t0

Р

55 ет элемент И 124. Вторым определяющим потенциалом является запрос формирования, который по выходу 101 поступает из блока 12 памяти признаков. Этот потенциал формируется на выходе элемента ИЛИ t00 при считывании адресным сигналом квитирования триггера 83 запроса. Единичное состояние триггера 83р через элемент

И 95 поступает на вход элемента

ИЛИ t00, по выходу 101. включает элемент И 128, На выходе элемента И 128 формируется единичный потенциал формирования, который по входу 89 поступает на блок 1 ввода-вывода, блок 12 памяти признаков и блок 13 дешифрации. В блоке 1 потенциал формирования по входу 89 поступает на шифратор 147 команд, на выходе которого формируется код формирования рельефа.

Этот код через элемент ИЛИ t65 поступает на кодовую часть регистра

146, Одновременно потенциал формирования поступает на вход элемента

ИЛИ-НЕ 161 и блокирует код квитирования нулевым потенциалом на управляющем входе элемента И 163. Кроме того, потенциал формирования через ,элемент ИЛИ-НЕ 152 блокирует трансляцию адреса р точки ветвления и обнуляет вторую адресную часть регистра 146. Рельефная часть принятого сообщения квитирования блокируется потенциалом формирования. Потенциал формирования через элементы ИЛИ

154 .и НЕ 156 закрывает элемент И 155 блока 1, запрещая тем самым перепись рельефа из регистра 145 в регистр

146. Одновременно потенциал формирования через элементы ИЛИ 154, И 157 и ИЛИ 159 открывает запись рельефа в рельефную часть регистра 146 из накапливающего сумматора 7 по входу е

158. Потенциал формирования, поступая на вход 89 блока 12, формирует на выходе соответствующего ему элемента И 176 единичный потенциал, который через элементы ИЛИ 1791, ИЛИ 181 транслируется на вход 56 . в виде адресного сигнала считывания. По адресным сигналам считывается j-я строка регистров 52 блока

4, которая через элементы И 55 и элементы ИПИ 57 по выходам 58 поступает на блок 5 сравнения рельефов. Выбранный блоком 5 минимальный рельеф по выходу 171 поступает на сумматор 7, где происходит уве19

1587530 20 личение на единицу минимального рельефа. Увеличенный на единицу рельеф по входу 158 поступает на рельефную часть регистра 146. В регистре 146 сформировалось сообщение формирования рельефа, содержащее соответствующий код, адрес корректируемого рельефа и ре тьеф. Это сообщение по входу 144 поступает на демультиплексор 3. Направление коммутации определяется. нулевыми состояниями j-й строки триггеров 64 блока 11. Потенциал формирования по входу 89 поступает на блок 13 и формирует на выходе элемента ИЛИ 179 адресный сигнал записи маршрута, который по входу 67 поступает на блок 11. По адресному сигналу записи маршрутов осуществляется запись направлений кратчайших путей,:соответствующих максимальным рельефам, в j.-ю строку памяти маршрутов. Сформированные блоком 5 направления кратчайших IIyтей по информационному входу бб поступают на блок 11 где через подключенные элементы И 65 записывают3 ся в соответствующие триггеры 64>, Затем адресный сигнал записи маршрута 67 осуществляет считывание нуJ левых состояний j-й строки триггеров 64> через элемент ИЛИ 74., и элементы И 76 .Считанные нулевые состо:J яния триггеров 64 - по выходам 78 инверсной маршрутйзации поступают на демультиплексор 3 и через элементы ИЛИ 139 управляют его коммутацией. Единичное состояние триггеров 64 блокируется потенциалом формирования. Потенциал формирования поступает на вход элемента ИЛИ-HF.

130 блока 6 и нулевым потенциалом на его выходе запирает элемент И 134, нулевой потенциал на выходе которого закрывает элементы И 136 по выходу 135 блокировки демультиплексора 3. Сообщение "Формирование

Рельефа" транслируется в смежные узлы по. указанным направлениям. Смежный узел принимает сообщение "Формцрование рельефа", по )-му входу и по х-му такту заносит его в регистр 145 блока 1, кодовая и адресная части поступают в соответствующие части регистра 146, а по выходам 164 и 16