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

 

Устройство маршрутизации относится к вычислительной технике и технике связи и может найти применение при построении узлов коммутации на сетях передачи дискретной информации. Цель изобретения - повышение пропускной способности и надежности сети связи за счет равномерного перераспределения нагрузки. Цель достигается тем, что в устройство, содержащее мультиплексор, регистр ввода-вывода, демультиплексор, блок памяти рельефов, блок сравнения, блок памяти оптимальных маршрутов , блок анализа, блок памяти признаков , генератор тактовых импульсов и блок управления, введены соединенные соответствующим образом блок контроля нагрузки и блок перегрузки. Уменьшение блокировки сети заключается в том, что .нагрузка равномерно распределяется по всему множеству эквивалентных оптимальных маршрутов, а перегруженные маршруты из данного множества временно (до полного рассасывания) исключаются. 12 ил. Г (Л

союз советских

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

РЕСПУБЛИК (я)л G 06 F 15/419

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4464809/24 (22) 24.07.88 (46) 30,11.91. Бюл. ¹ 44 (72) Ю.Н. Максименко и В,С. Ракошиц (53) 681,325(088. 8) (56) Авторское свидетельство СССР

¹ 962967, кл, G 06 F 15/20, 1980.

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

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

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

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

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

„„SU „„1695329 А1 дежности сети связи за счет равномерного перераспределения нагрузки. Цель достигается тем, что в устройство, содержащее мультиплексор, регистр ввода-вывода, демультиплексор, блок памяти рельефов, блок сравнения, блок памяти оптимальных маршрутов, блок анализа, блок памяти признаков, генератор тактовых импульсов и блок управления, введены соединенные соответствующим образом блок контроля нагрузки и блок перегрузки. Уменьшение блокировки сети заключается в том, что нагрузка равномерно распределяется по всему множеству эквивалентных оптимальных маршрутов, а перегруженные маршруты из данного множества временно (до полного рассасывания) исключаются. 12 ил. фиг, 9 — функциональная схема блока памяти признаков; на фиг, 10 — функциональная схема блока анализа; на фиг. 11 — функцио- 0 нальная схема демультиплексорэ; на фиг, 12 (Л вЂ” функциональная схема блока дешифра- (д ции. )

Устройство (фиг. 1) содержит блок 1 вво- ) да-вывода, мультиплексор 2, демультиплексор 3, генератор 4 тактовых импульсов, блок

5 управления, блок 6 дешифрации, блок 7 перегрузки, блок 8 памяти рельефов, блок 9 сравнения рельефов, блок 10 памяти оптимальных маршрутов, блок 11 памяти признаков, блок 12 анализа и блок 13 контроля нагрузки, Устройство имеет (n + 1) информационных входов 14, подключенных к мультиплексору 2, (n + 1) информационных выходов 15, подключенных к демультиплексору 3, и входов 16 окончания обслуживания запросов, вход 17 уровня максимальной нагрузки, 1695329

20

50 вход 18 уровня минимальной нагрузки, подключенный к блоку 13 контроля нагрузки, выход 19 запроса освобождения ресурса (канала), подключенный к блоку 12 анализа, адресный выход 20, подключенный к блоку

1 ввода-вывода, и тактовых выходов 21, подключенных к генератору тактовых импульсов, и выходов 22 маршрутизации запроса, подключенных к блоку 13 контроля нагрузки.

Выходами 19, 20, 21) — 21n, 221 — 22n и входами 161-16, 17 и 18 устройство соединено с устройством управления ресурсами (не показано).

Блок 5 управления (фиг. 3) содержит триггер.23 сканирования, единичным входом подключенный к входу 24 разрешения сканирования, счетчик 25 адреса, элемент

ИЛИ 26, элемент И 27, шифратор28, первую группу элементов И 29, элемент 30 задержки, дешифратор 31, регистр 32, вторую группу элементов И 33 и выходы 34.

Блок 7 перегрузки (фиг. 4) включает иразрядный регистр 35, выходы 361-36 перегрузки, первую группу из и элементов И

37, вход 38 восстановления маршрутизации, первый элемент И)1И 39, выход 40 разрешения восстановления, вторую группу из и элементов И 41. входы 42>-42П рассасывания перегрузки, второй элемент ИЛИ 43 и входы 441 — 44П суммирования нагрузок.

Блок 1 ввода-вывода (фиг. 5) имеет входной регистр 45, информационный вход 46, выход 47, выходной регистр 48, информационный выход 49, элемент И 50, первый элемент НЕ 51, вход 52 занятости, второй элемент НЕ 53, вход 54 сканирования, третий элемент НЕ 55, вход 56 формирования перегрузки, шифратор 57 команд, вход 58 разрешения восстановления и элемент

ИЛИ 59.

Блок 8 памяти рельефов (фиг. 6) содержит и групп по m (m — количество узлов сети) регистров 60, и групп по m элементов И 61 в каждой группе, вход 62 разрешения записи, дешифратор 63 адреса, элементы ИЛИ

64 и информационные входы 651 65л

Блок 13 контроля нагрузки (фиг. 7) вкл ючает и накапливающих регистров 66 -66п, группу схем 671 67П сравнения, первую группу элементов И 681-68п, входы 691 69п разрешения сравнения нагрузок, вход 70 разрешения запроса, схему 71 выбора минимальной нагрузки, вторую группу элементов И 72 -72,, элемент ИЛИ 73, схему 74 сравнения, первый элемент И 75, выход 76 трансляции, второй элемент И 77, выход 78 установки перегрузки, третью группу элементов И 791-79, и элементы 80 - 80 задержек, Блок 10 памяти оптимальных маршрутов (фиг, 8) имеет и групп по m триггеров 81, первые и групп по m элементов И 82, вход

83 ветвления, вторые и групп no m элементов И 84, и информационных входов 85, третьи и групп по m элементов И 86 в каждой группе, четвертые и групп по m элементов И

87 в каждой группе, вход 88 разрешения считывания, дешифратор 89 адреса. первую группу элементов ИЛИ 901 — 90п, выходы

911-91п инверсной маршрутизации, вторую группу элементов ИЛИ 921-92П и выходы

93 — 93П маршрутизации, Блок 11 памяти признаков (фиг, 9) содержит m триггеров 94 признака перегрузки, m триггеров 95 признака ветвления, первую группу из m элементов И 96, первую группу элементов 971-97П задержки, вторую группу из m элементов И 98, вторую группу элементов 99> — 99П задержки, третью группу из m элементов И 100, третью группу элементов 1011-101 задержки, четвертую группу из m элементов И 102, четвертую группу элементов 103> — 103m задержки, пятую группу из m элементов И

104, шестую группу из m элементов И 105, седьмую группу из m элементов И 106, восьмую группу из m элементов И 107, первый элемент ИЛИ 108. единичный выход 109 признака перегрузки, второй элемент ИЛИ

110, третий элемент ИЛИ 111, нулевой выход 112, четвертый элемент ИЛИ 113, дешифратор 114 адреса, пятый элемент ИЛИ

115, вход 116 разрешения переполнения, первый элемент И 117, шестой элемент ИЛИ

118, седьмой элемент ИЛИ 119, второй элемент И 120, восьмой элемент ИЛИ 121, третий элемент И 122, четвертый элемент И

123, пятый элемент И 124 и девятый элемент

ИЛИ 125.

Блок 12 анализа (фиг. 10) включает схему 12 приоритета, выходы 1271-127л кратчайших направлений, первую группу из и элементов И 128, вторую группу из и элементов И 129, группу из и элементов НЕ 130, третью группу из и элементов И 131> — 131n. первый элемент ИЛИ 132, второй элемент

ИЛИ 133, первый элемент И 134, элемент

НЕ 135, вход 136 коррекции, второй элемент

И 137, третий элемент И 138, вход 139 запроса, третий элемент ИЛИ 140. четвертый элемент И 141, четвертый элемент ИЛИ 142, пятый элемент И 143, элемент НЕ 144, шестой элемент И 145, пятый элемент ИЛИ 146, шестой элемент ИЛИ 147, вход 148 блокировки, седьмой элемент И 149, четвертую группу элементов И 1501 — 150n.

Демультиплексор 3 (фиг, 11) образуют группа из и элементов ИЛИ 151, группа из и элементов И 152, элемент И 153, элемент

1695329

25

154 задержки, элемент ИЛИ 155 и элемент

156 задержки, Блок дешифрации (фиг. 12) содержит дешифратор 157, выходом подключенный к кодовому входу 47, первым выходом подключенный к входу 54 сканирования, вторым выходом подключенный к выходу

38 восстановления маршрутизации, третьим выходом подключенный к выходу 136 коррекции, четвертым выходом подключенный к выходу 139 запроса, и элемент ИЛИ

158, входом подключенный к первым трем выходам дешифратора 157, а выходом — к выходу 148 блокировки, Устройство реализует процесс блокировки и перераспределения нагрузки, связанный с кратковременной перегрузкой ветви, Предполагается, что рельефы и соответствующие им деревья кратчайших k3правлений маршрутов сформированы, а информационный обмен осуществляется по кратчайшим маршрутам, Устройство маршрутизации работает следующим образом.

По информационным входам 141-14,+1 в устройство поступают сообщения, кото-. рые поочередно в соответствии r. последовательностью тактовых импульсов, вырабатываемой генератором 4 и поступающей по входам 211 — 21n+1 на мультиплексор 2, коммутируются на информационный выход мультиплексора 2 и по входу 46 поступают в блок 1 ввода-вывода, Кодовая и адресная части принятого сообщения по iму (i = 1, 2..., и+1) входу заносятся в регистр

45 приема блока 1 ввода-вывода, откуда они по входам 47 и 20 поступают соответственно на блок 6 дешифрации и адресные входы блока 8 памяти рельефов, блока 10 памяти оптимальных маршрутов и блока 11 памяти признаков. 8 блоках 10 и 11 адрес поступает соответственйо на дешифраторы 89 и 114 адреса и считывает содержимое соответствующих триггерных ячеек 81 и 94. Считанный элементами И 86 код оптимального маршрута через элементы ИЛИ 921 — 92П поступает по входам 931 — 93п на блок 12 анализа, по входам 361 — 36л на который из блока

7 перегрузки поступает инверсный код перегрузки. С помощью элементов И 128>—

128л блока 12,анализа осуществляется поразрядное маскирование считанной триггерной ячейки блока 10 памяти оптимальных маршрутов регистром 35 перегрузки блока 7 перегрузки. Если все единичные разряды считанной триггерной ячейки бло. ка 10 замаскированы регистром 35 (все выходные направления перегружены), то на выходе элемента HE 144 формируется единичный потенциал, который поступает на первый вход элемента И 143. Если в кодовой части принятого сообщения содержится код запроса, то на выходе 139 дешифратора 157 кода блока 6 устанавливается единичный потенциал, который поступает на второй вход элемента И 143. 8 блоке 11 памяти признаков хранится признак переполнения. Единичное состояние признака переполнения указывает на то, чтосоответствующий ему оптимальный маршрут был перегружен, нулевое состояние признака переполнения указывает на то, что соответствующий ему оптимальный маршрут имел запас по нагрузке. Предположим, что выбранный по принятому адресу оптимальный маршрут имел запас по нагрузке, Нулевое состояние выбранного дешифратором 114 адреса триггера 94 перегрузки Q = 1, 2, ..., m) считывается элементом И 106i и через элемент ИЛИ 111 транслируется на выход 112. На нулевом выходе 112 признака перегрузки блока 11 памяти признаков формируется единичный потенциал. который поступает на третий вход элемента И 143, включает его и на выходе 56 элемента ИЛИ 146 формируется единичный потенциал формирования перегрузки, который поступает на шифратор 57 команд и элемент HE 55 блока 1 ввода-вывода. На выходе шифратора 57 команд формируется код перегрузки, который через элемент ИЛИ 59 поступает на кодовую часть выходного регистра 48. Элемент 55 нулевым выходным потенциалом отключает элемент

И 50, блокируя трансляцию принятого кода запроса на выходной регистр 48. Сформированное в регистре 48 сообщение, содержащее код перегрузки и адрес узла-адресата, по информационному выходу 49 поступает. на демультиплексор 3, Единичный потенциал формирования перегрузки с выхода элемента ИЛИ 146 блока 12 анализа через элемент ИЛИ 147 блокирует схему 126 приоритета, по выходу 56 поступает на элемент

ИЛИ 115 блока 11 памяти признаков и включает элемент ИЛИ 121. На выходе элемента

ИЛИ 121 формируется единичный потенциал разрешения считывания, который по входч 88 поступает на элементы И 871 — 87n блока 10 памяти оптимальных маршрутов и разрешает считывание нулевых разрядов выбранной триггерной ячейки 92. Считанные разряды инверсной маршрутизации через элементы ИЛИ 90 — 90л по входам

911 — 91n инверсной маршрутизации поступает на элементы ИЛИ 151 — 151П демультиплексора 3 и включает соответствующИе элементы И 152) — 152n, Элементы И 1521—

152п стробируются тактовыми импульсами, собираемыми элементом ИЛИ 155. Эле1695329

10 аритета, 15 мент 154 задержки служит для блокировки просечек в переходной период. Сформированное служебное сообщение, содержащее код переполнения и адрес узла адресата, транслируется по выходным направлениям

15 -15л, инверсным оптимальной маршрутизации, или по направлениям распространения волны формирования рельефа.

Каждое выходное направление (ветвь) содержит ц каналов связи (ресурсов), из которых Л (Л < 0) каналов используются для информационного обмена, а 0 — Л каналов эарезервированы для передачи служебных сообщений. Одновременно единичный потенциал формирования перегрузки через элемент ИЛИ 115 блока 11 памяти признаков включает выбранный дешифратором

114 адреса элемент И 981 и через элемент

99I задержки устанавливает в "1" триггер

941 признака перегрузки. Если замаскированы не все единичные разряды считанной триггерной ячейки блока 10, то на выходах

691 — 69n формируются потенциалы разрешения сравнения рельефов, на выходе элемента ИЛИ 142 формируется единичный потенциал, который включает элемент И . 145, В результате на выходе 70 блока 12 анализа формирования единичный потенциал разрешения запроса, который поступает на первые входы элементов И 68>-68л блока 13 контроля нагрузки, На вторые входы указанных элементов по входам 69> — 69, поступают потенциалы разрешения сравнения нагрузок, подключающие выходы соответствующих накапливающих регистров

66> — 66л блока 13 контроля нагрузки к входам схемы 71 выбора минимальной нагрузки. На выходах элементов И 70 формируется код текущей минимальной нагрузки, который через элемент ИЛИ 73 поступает на вход схемы 74 сравнения, на второй вход которой по входу 17 поступает код уровня максимальной нагрузки Л, Если код текущей минимальной нагрузки меньше кода уровня максимальной нагрузки, то на выходе "Меньше" схемы 74 сравнения формируется единичный потенциал, который включает выбранной схемой 71 сравнения элемент И 79ь На выходе элемента И 79 формируется единичный потенциал маршрутизации запроса, который с задержкой на такт элементом 80 задержки поступает на вход прибавления единицы накапливающего регистра 66ь одновременно единичный потенциал маршрутизации запроса с выхода элемента И 79 по входу 22 поступает на демультиплексор 3. Принятое блоком

1 ввода-вывода сообщение запроса транслируется демультиплексором 3 по i-му ми20

55 нимально загруженному направлению. Единичный потенциал "Меньше" с выхода схемы 74 сравнения блока 13 контроля нагрузки поступает на управляющий вход элемента И 77, на выходе элемента И 77 формируется единичный потенциал трансляции, который по входу76 поступает на вход элемента ИЛИ 147 блока 12 анализа и блокирует выдачу единичных потенциалов кратчайших направлений схемы 126 приКроме того, устройство маршрутизации по входам 22 и 20 направляет в устройство управления ресурсами (не показано) запрос на резервирование одного иэ Л каналов связи I-го выходного направления. Код запроса и требуемое выходное направление однозначно определяются единичным потенциалом на соответствующем выходе 22ь по адресным выходам 20 транслируется адрес абонента, запрашивающего канал связи

i-й ветви. Если код текущей минимальной нагрузки больше или равен коду уровня максимальной нагрузки jL то на выходе "Больше или равно" схемы 74 сравнения формируется единичный потенциал, который включает элемент И 77. На выходе элемента И 77 формируется единичный потенциал установки перегрузки, который по входу 78 поступает на управляющие входы элементов И 150>-150, блока 12 анализа, На информационные входы этих элементов с выходов элементов И 1281-128л поступает единичный потенциал разрешения сравнения нагрузок. На выходах элементов И

150> — 150п формируются потенциалы суммирования нагрузок. которые по входам 44>44л поступают на единичные входы регистра 35 перегрузки блока 7 перегрузки.

Одновременно единичный потенциал установки перегрузки по входу 78 поступает на элемент ИЛИ 146 блока 12 анализа. На входе элемента ИЛИ 146 формируется единичный потенциал формирования перегрузки, который по входу 56 поступает на шифратор

57 команд и элемент НЕ 55 блока 1 вводавывода. Происходит блокировка принятого кода запроса и формирование служебного сообщения перегрузки, которое по информационным выходам 49 направляется в демультиплексор 3 и транслируется из него по зарезервированным служебным каналам инверсных направлений маршрутизации, формируемых на выходах 91> — 91л блока 10 памяти оптимальных маршрутов.

Кроме того, единичный потенциал формирования перегрузки по входу 56 поступает на элемент ИЛИ 115 блока 11 памяти признаков и устанавливает в "1" выбранный

1695329

5

15

50 дешифратором 114 адреса триггер 94> при знака перегрузки через элемент И 98 и элемент 99 задержки. Предположим, что требуемый оптимальный маршрут перегружен, тогда единичное состояние триггера

94> признака перегрузки блока 11 памяти памяти признаков считывается элементом

И 104) и на выходе элемента ИЛИ 108 формируется единичный потенциал признака перегрузки, который поступает по входу 109 на первые входы элементов И 141 и 138 блока 12 анализа, Если сообщение запроса поступило в устройство по информациîííому входу 14л+ от собственного абонента, то на выходе элемента И 138 формируется единичный потенциал занятости, который по входу 52 поступает на шифратор 57 команд и элемент НЕ 51 блока 1 ввода-вывода. На выходе шифратора 57 команд формируется код занятости, который через элемент ИЛИ

59 занятости поступает в кодовую часть выходного регистра 48. Одновременно нулевым потенциалом с выхода элемента НЕ 51 блокируется принятый входным регистром

45 код запроса. Сформированное в регистре

48 служебное сообщение, содержащее код занятости и адрес запрашиваемого узла, по информационному выходу 49 поступает на информационные входы элемента И,53 демультиплексора 4, на управляющий вход которого через элемент 154 задержки по входу 52 поступает единичный потенциал занятости, Длительность задержки элемента 154 выбирается такой, чтобы согласовать по времени информационные и управляющий сигналы и таким образом исключить просечки на выходе элемента И 153. Таким образом, сформированное служебное сообщение занятости направляется по (и+1)-му выходному направлению в собственный абонент и информирует его о кратковременной занятости требуемого оптимального маршрута. Абонент в ответ на сообщение занятости должен снять свой запрос и повторить его через некоторое время.

Если сообщение запроса поступило в устройство по транзитному информационному входу 14, то на выходе элемента ИЛИ

140 блока 12 анализа формируется единичный потенциал, который включает элемент

И 141, на выходе элемента 146 формируется единичный потенциал формирования перегрузки. Этот потенциал по входу 56 поступает на блок 1 ввода-вывода, где блокирует код запроса и формирует служебное сообщение перегрузки, которое транслируется демультиплексором 3 по служебным каналам инверсных направлений маршрутизации.

Служебное сообщение, содер.кащее код перегрузки и адрес узла признака, поступает в текущее устройство маршрутизации по i-му входу 14 и через мультиплексор

2 заносится в регистр 45 блока 1 ввода-вывода. Кодовая часть принятого сообщения по входу 47 поступает на блок 6 дешифрации, На выходе 136 дешифратора 157 команд формируется единичный потенциал коррекции, который поступает на вход элемента И 158 и формирует на его выходе единичный потенциал блокировки. Потенциал блокировки по входу 148 поступает на элемент ИЛИ 147 блока 12 анализа и с era выхода блокирует работу схемы 1?6 приоритета. Адресная часть принятого блоком 1 ввода-вывода сообщения по адресному Вхо ду 20 транслируется в блок 11 памяти признаков и поступает на дешифратор 114 адреса. На J-м выходе дешифратора 114 адреса формируется единичный потенциал, который открывает соответствующие элементы Vl 104, 106 и считывает состояние триггера 94 признака перегрузки.

Если триггер 94 находился в нулевом состоянии, то на нулевом выходе 112 признака перегрузки формируется единичный потенциал, который поступает на вход элемента И 149 блока 12 анализа и формирует на его выходе единичный потенциал запроса освобождения ресурса. Этот потенциал по выходу 19 в сопровождении соответствующего тактового импульса 21 и адреса j-го узла абонента, транслируемого по входу 20, поступает на устройство управления ресурсами, которое освобождает занятый на этапе запроса ресурс (канал связи), соответствующий I-му направлению и /-му узлу абонента. Освобождение предвари-. тельно занятого на этапе запроса ресурса сопровождается формированием устройством управления ресурсами соответствующего потенциала окончания обслуживания запроса, который по входу 16 поступает на вычитающий вход накапливающего регистра 66 блока 73 контроля нагрузки.

По принятому адресу узла-приемника j дешифратор адреса блока 10 памяти оптимальных маршрутов формирует единичный потенциал на своем j-м выходе и с помощью элементов И 86; (i = 1, 2, ..., n) считывает j-ю триггерную ячейку 81 памяти оптимальных маршрутов, Потенциалы маршрутизации, соответствующие выходным оптимальным направлениям из данного узла в j-й узел, с выходов элементов ИЛИ 921 — 92„по входам

931 — 93п поступают на первые входы элементов И 1281 — 128,, 1291 — 129,, 131> — 131, и входы схемы 126 приоритета блока 12 анализа.

Если в )-й ячейке 81 памяти оптимальных

1695329

10

15 маршрутов записано более чем одна единиц, то данный узел j-го дерева оптимальных путей помечается единичным признаком ветвления. Условие ветвления выявляется с помощью элементов И 1291129, 1311 — 132л, НЕ 130>-130 и ИЛИ 132 и

133, Если имеется ветвление, то на выходах элементов ИЛИ 132 и 133 устанавливаются единичные потенциалы, которые включают элемент И 137, и на его выходе формируется единичный потенциал ветвления. Потенциал ветвления по входу 83 поступает на управляющие входы элементов И 102 -102 блока 11 памяти признаков и через элемент

1031 задержки на такт записывает единицу в выбранный дешифратором 114 адреса J-й триггер 95 признака ветвления, Одновременно единичный потенциал ветвления по входу 83 поступает на управляющие входы элемента И 82 блока 10 памяти оптимальных маршрутов и выбранный дешифратором 89 адреса триггер 81 ь находящийся на

1-м входном направлении, определяемом тактовым импульсом 21ь Если в J-й триггерной ячейке 81 памяти оптимальных маршрутов записана одна единица и она расположена по i-му направлению поступления служебного сообщения перегрузки, определяемому тактовым импульсом 21ь то на выходе элемента ИЛИ 133 формируется единичный потенциал, а на выходе элемента ИЛИ 132 присутствует нулевой потенциал, который, инвертируясь элементом НЕ

135, включает элемент И 134. На выходе элемента И 134 формируется единичный потенциал разрешения переполнения, который по входу 116 поступает на вход элемента ИЛИ 115 блока 11 памяти признаков и через элемент И 981 и элемент 99 задержки на такт устанавливает в "1" триггер 941 признака перегрузки. Одновременно единичный потенциал разрешения переполнения через элемент ИЛИ 115 поступает на вход элемента ИЛИ 121, на выходе которого формируется единичный потенциал разрешения считывания. Этот потенциал по входу 88 поступает на элементы И 87 блока

10 памяти оптимальных маршрутов и разрешает считывание инверсных состояний выбранной дешифратором 89 J-й триггерной ячейки 82, Состояния инверсной маршрутизации, формируемые на выходах элементов

ИЛИ 90>-90п, по входам 91>-91, поступают на элементы ИЛИ 151 — 151> демультиплексора 3 и определяют выходные н,"правления трансляции принятого служебного сообщения перегрузки. Если J-й признак ветвления находится в единичном состоянии, то данное состояние триггера 95> через элемент И

1051 и элемент ИЛИ 110 блока 11 памяти

55 признаков включит элемент И 124 и на выходе элемента ИЛИ 125 формирует единичный потенциал разрешения записи. который по входу 62 поступает на управляющие входы элементов И 61 блока 8 памяти рельефов. Выбранное дешифратором 63 адреса содержимое регистровых ячеек 60 через элементы ИЛИ 64 — 64 по входам

651-65п поступает на блок 9 сравнения рельефов; формируются потенциалы маршрутизации. Происходит восстановление исходного состояния J-й триггерной ячейки памяти оптимальных маршрутов по соответствующему ее рельефу, хранящемуся в блоке

8 памяти рельефов. Кроме того, единичный потенциал с выхода элемента И 124 через элемент И 119 поступает на выбранный элемент И 1001 и через элемент 101 задержки на такт устанавливает в "0" триггер 95 признака ветвления. Таким образом, процесс распространения служебного сообщения перегрузки, вызванный перегрузкой произвольной ветви сети, направленно движется вверх по инверсному дереву оптимальных маршрутов и заканчивается в точках (узлах) ветвления или на граничных узлах. При этом в узлах ветвления осуществляется кратковременное отключение перегруженных выходных направлений, а остальные узлы, расположенные в зоне действия перегрузки, помечаются признаком перегрузки. Если узел ветвления целиком попал в зону действия перегрузки, то он помечается признаком перегрузки, и возобновляется процесс трансляции служебного сообщения перегрузки вверх по инверсному дереву маршрутизации. Если занятый ресурс (канал) -го направления освободился, то на соответствующем входе 16 появляется единичный потенциал окончания обслуживания запроса, который поступает на вычитающий вход накапливающего регистра 66 блока 13 нагрузки и уменьшает его содержимое на единицу. Схема 67 сравнения сравнивает код, хранящийся в регистре 66ь с кодом о уровня минимальной нагрузки д(д <Л) . поступающим по входам 18 от устройства управления ресурсами (не показана).

При достижении счетчиком 66 нижнего порога i нагрузки на выходе 42 схеМы 67 сравнения формируется единичный потенциал рассасывания нагрузки, который по входу 42; поступает на элемент И 41 блока

7 перегрузки. Если i-й разряд регистра 35 находится в состоянии "1", то на выходе элемента И 41 формируется единичный потенциал, который устанавливает в "0" i-й разряд регистра 35 и формирует на выходе элемента ИЛИ 43 единичный потенциал разрешения сканирования, который по вхо13

1695329

10

20

35

50

55 ду 24 поступает на единичный вход триггера

23 и через элемент ИЛИ 26 на вход начальной установки счетчика 25 адреса блока 5 управления. В блоке 5 управления запускается цикл сканирования рельефов. Триггер

23 открывает элемент И 27, по второму входу которого поступают (и+1)-е тактовые импульсы 21. С выхода элемента И 27 тактовые импульсы поступают на суммирующий вход счетчика 25 адреса. Адрес, сформированный счетчиком 25, через элемент И 29 поступает на адресный вход регистра 32 и дешифратор 31. На управляющий вход элемента И 29 поступают (и+1)-е тактовые импульсы, задержанные элементом 30 задержки. Длительность задержки элемента 30 должна быть не меньше длительности задержки счетчика 25 адреса. Единичное состояние триггера 23 включает шифратор

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

42 поступают параллельно на группу элементов И 33, которая стробируется (и+2)-ми тактовыми импульсами 21. С выходов элементов И 32 код сканирования и текущий адрес рельефа по входу 34 поступают на мультиплексор 2, откуда (и+2)-м тактовым импульсом транслируются по входу 46 на блок 1 ввода-вывода. Кодовая часть принятого сообщения сканирования по входу 47 поступает на дешифратор 157 команд, на выходе 54 которого формируется единичный потенциал сканирования, адресная часть принятого сообщения поступает по входу 20 на соответствующие дешифраторы адреса блоков 10 и 11 памяти. Если соответствующий данному адресу j-й рельеф помечен признаком перегрузки, то на выходе элемента ИЛИ 108 блока 11 памяти признаков формируется единичный потенциал. который включает элемент И 117, через элемент ИЛИ 118 обнуляет j-й триггер 94 признака перегрузки и на выходе элемента

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

58 поступает на шифратор 57 команд блока

1 ввода-вывода. На выходе шифратора 57 команд формируется код восстановления, который в сопровождении адреса по входу

49 поступает на демультиплексор 3. Служебное сообщение восстановления j-го рельефа направляется по направлениям 91 инверсной маршрутизации, определяемым нулевыми разрядами j-й триггерной ячейки

81 блока памяти оптимальных маршрутов.

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

И 122, на первый вход которого по входу 54 поступает единичный потенциал сканирования.

Если j-й рельеф помечен признаком ветвления, то на выходе элемента ИЛИ 110 формируется единичный потенциал, который включает элемент И 122 и устанавливает на выходе элемента ИЛИ 125 единичный потенциал разрешения записи. По этому сигналу происходит восстановление исходного состояния J-й триггерной ячейки 81 блока 10 памяти оптимальных маршрутов.

Кроме того, единичный потенциал с выхода элемента И 122 через элемент ИЛИ 119 включает элемент И 100 и через элемент

101 задержки на такт устанавливает в "0" триггер 951 признака ветвления.

Служебное сообщение восстановления поступает в устройство по i-му входу 14ly по

1-му такту 211 с выхода 46 мультиплексора 2 заносится в блок 1 ввода-вывода.

Кодовая часть принятого сообщения по входу 47 поступает на дешифратор 157 блока 6 дешифрации, и на выходе 38 формируется единичный потенциал восстановления маршрутизации, который поступает на управляющие входы группы элементов И 37>—

37л блока 7 перегрузки. Если 1-е направление не перегружено, то I-й разряд регистра 35 находится в нулевом состоянии, элемент И 37 включен, а на.выходе элемента ИЛИ 39 формируется единичный потенциал разрешения восстановления, который по входу 40 поступает на управляющие входы элементов И 120 и 123 блока 11 памяти признаков. Если j-й рельеф, соответствующий адресу принятого служебного сообще-. ния восстановления, не помечен признаком ветвления и помечен признаком перегрузки, то на выходе элемента И 120 формируется единичный потенциал, который поступает на элемент ИЛИ 121. На выходе элемента ИЛИ 121 формируется единичный потенциал считывания, который по входу 88 поступает на блок 10 памяти оптимальных маршрутов и разрешает выдачу принятого служебного сообщения восстановления по инверсным направлениям маршрутизации.

Единичный потенциал с выхода элемента

ИЛИ 118 устанавливает в "0" триггер 94> признака перегрузки. Если при тех же условиях j-й рельеф помечен признаком ветвления, то на выходе элемента И 122 формируется единичный потенциал, кото-. рый поступает на входы элементов ИЛИ 119 и 125, На выходе элемента И 125 формируется единичный потенциал разрешения записи, по которому осуществляется

1б95329

10

25

55 восстановление исходного состояния j-й триггерной ячейки памяти оптимальных маршрутов. На выходе элемента ИЛИ 119 формируется единичный потенциал, по которому осуществляется установка в "0" триггера 95 признака ветвления, На выходе элемента ИЛИ 118 формируется единичный потенциал, по которому осуществляется установка в "0" триггера 94 признака перегрузки. По достижении счетчиком 25 конечного адреса на выходе дешифратора

31 формируется единичный потенциал начальной установки, по которому устанавливаются в "0" триггер 23 и регистр 32. Цикл сканирования рельефов заканчивается.

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

Устройство маршрутизации, содержащее блок ввода-вывода, мультиплексор, демультиплексор, генератор тактовых импульсов, блок управления, блок дешифрации, блок памяти рельефов, блок сравнения рельефов, блок памяти оптимальных маршрутов, блок памяти признаков, при этом (n+1) информационных входов устройства (n— количество направлений связи) являются соответствующими, информационными входами мультиплексора, выход которого соединен с информационным входом блока ввода-вывода, информационный выход которого подключен к информационному входу демультиплексора, (и+1) информационных выходов которого являются соответствующими информационными выходами устройства, и выходов генератора тактовых импульсов подключены к соответстующим входам сканирования мультиплексора, демультиплексора и блока анализа, (л+1)-й выход генератора тактовых импульсов соединен с (и+1)-м входом сканирования мультиплексора и первым тактовым входом блока управления, (n+2)-й выход генератора тактовых импульсов подключен к второму тактовому входу блока управления, выход которого соединен с (n+2)-м информационным входом мультиплексора, командный выход блока ввода-вывода подключен к входу дешифрации, выход признака сканирования которого подключен к одноименным входам блока ввода-вывода и блока памяти признаков, а выходы признаков запроса, коррекции и блокировки соединены с содноименными входами блока анализа, адресный выход блока ввода-вывода подключен к одноименному входу блока памяти рельефов, п информационных выходов которого через блок сравнения рельефов подключены к соответствующим информационным входам блока памяти оптимальных маршрутов, и выходов маршрутизации которого соединены с одноимеными входами блока анализа, и выходов кратчайших направлений которого подключены к входам демультиплексора, а выход занятости соединен с одноименными входами демультиплексора и блока ввода-вывода, и выходов u,ísåðñèè маршрутизации блока памяти оптимальных маршрутов подключены к одноименным входам демультиплексора, выход разрешения переполнения блока анализа соединен с одноименным входом блока памяти признаков, единичный и нулевой выходы признака перегрузки которого подключены к соответствующим одноименным входам блока анализа, выход формирования перегрузки которого подключен к соответствующим одноименным входам блока памяти признаков и блока ввода-вывода, отличающееся тем,что,с целью повышения пропускной способности и надежности сети за счет равномерного перераспределения нагрузки, в него введены блок перегрузки и блок контроля нагрузки, причем и выходов генератора тактовых импульсов являются соответствующими тактовыми выходами устройства и соединены с соответствующими одноименными входами блока перегрузки и блока памяти оптимальных маршрутов, (n + 1)-й выход генератора тактовых импульсов соединен с соответствующим входом сканирования блока анализа, адресный выход блока ввода-вывода, являющийся адресным выходом устройства, соединен с адресными входами блока памяти оптиMçëьнblх маршрутов и блока памяти признаков, и входов окончания обслуживания запросов и входы уровня максимальной и минимальной нагрузок блока контроля нагрузки являются соответствующими одноименными входами устройства, и выходов маршрутизации запроса блока контроля нагрузки соединены с соответствующими одноиMeêíûми входами демультиплексора и являются соответствующими одноименными выходами устройства, выхрд запроса освобождения блока анализа является одноименным выходом устройства, вход признака восстановления маршрутизации, и входов рассасывания перегрузки, п входов суммирования нагрузок блока перегрузки подключены к соответствующим одноименным выходам блока дешифрации, блока контроля нагрузки и блока анализа соответственно, выход разрешения сканирования. выход разрешения восстановления и и выходов перегрузки блока перегрузки соединены с соответствующими одноименными входами блока управления, блока памяти признаков и блока анализа соответственно, п выходов разрешения сравнения нагрузок и выход разре17

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

5 ввода-вывода соответственно, выход разрешения записи блока памяти признаков соединен с соответствующими одноименными входами блока памяти оптимальных маршрутов и блока памяти рельефов.

1695329

1695329

H M

Р

21

27

Ы 54 56 58

9Ъг 5

1695329

1695329

1695329

1695329

27(-, 02

39

РО

f03

24л+4

56

76

448

Нб

rZ7r

1695329

Корректор С.Черни

Редактор А.Огар

Заказ 4164 Тираж 398 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина. 101

s4

38

И6

Составитель B,Ñû÷eB

Техред M.Ìîðãåèòàë