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

(Л

4

со

ь

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

Цель изобретения - сокращение аппаратурных затрат.

На фиг.1 представлена функциональ- ная схема устройства на фиг.2 - схема блока ввода-выводаj на фиг.З - процедура маршрутизации.

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

Схема 10 сравнения адреса содержит схему 11 сравнения, первый элемент И 12, элемент НЕ 13 и второй элемент И 14.

Блок 8 управления содержит генератор 15 сканирования, дешифратор 16 кода режима, элемент НЕ 17, элемент ИЛИ 18 и элементы И 19 и 20.

Кроме того, устройство содержит демультиплексор 21 данных, блок 22 элементов ИЛИ и сумматор 23 единицы. Устройство имеет п информационных входов , и п выходов , вход 26 установки исходного состояния и адресный вход 27,

Блок 1 ввода-вьшода (фиг.2) состоит из регистра 28 ввода и регистра 29 вывода и имеет вход 30 сообщения, выход 31 сообщения, выход 32 информа- |ционного поля, вход 33 информационного поля, выход 34 поля команды и выход 35 поля адреса.

Совокупность устройств, соединенных дуплексными линиями связи по входам и выходам 25 ,-25,,, образует сеть связи. При этом устройство маршрутизации является узлом сети,;а входы 24,-2А„ и выходы связывают его с соседними узлами.

Предположим, что на сети решается задача нахождения множества критических Йутей в узел А (фиг.З). В этом случае из узла А формируется А-рельеф по следующему Алгоритму,

Узлу А 1т: «лваивается единичное значение л рельефа, которое транслируется по всем исправньм направлениям в смежиJi с ним узлы. Соседние узлы.

Q

5 0

5

о

0

5

5

0

5

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

Через конечное количество трансляций, равное максимальной высоте рельефа, в сети формируется А-рельеф, представляющий собой по числу направлений связи набор чисел, хранящихся в каждом узле сети. Значение высоты рельефа, соответствующее данному направлению, равно числу транзитных узлов на пути обмена в узел А по данному направлению. Совокупность направлений, помеченных минимальными высотами А-рельефа, образует кратчайший маршрут в узел А.

Устройство маршрутизации работает следующим образом.

Очередность обслуживания поступающих на устройство по входам сообщений определяется генератором 15 сканирования. Генератор 15 формирует на своих выходах временнзто nof следовательность единичных потенциалов, в соответствии с которой мультиплексор 2 поочередно заполняет ре-г гистр 28 ввода поступающими сообщениями. При этом частота опроса (сканирования) мультиплексора 2 выбирается с згчетом скорости поступления сообщений по входам 24,-24j, таким образом, чтобы избежать очередей, п-ое направление соответствует связи устройства с собственным абонентом.

При подключении устройства в сеть происходит обнуление блоков 5 и 7 памяти по входу 25, Затем начинается этап формирования рельефа i-ro узла (, ..,, т, где m - количество узлов в сети).

По входу.24„ устройства из абонента i поступает сообщение Формирование рельефа, в информационной часг ти которого хранится единичный рельеф. Это сообщение по входам 30 заносится в блок 1 ввода-вывода, с выходов 35, 34 и 32 которого его составные части- адрес, команды и ин формация поступают параллельно в дешифратор 9 адреса, дешифратор 16 кода режима и на вход

314

демультиплексора 21, На первом выхо- де дешифратора 16 кода режима формируется единичный потенциал формирования рельефа, который разрешает обращение в блоки 5 и 7 памяти. Последние имеют матричную структуру: i-я строка (, .,., га) каждого блока соотвест- вует i-му рельефу, а j-й (, ..., п-1) столбец соответствует направле- нию связи данного устройства со смежными устройствами. Элемент матрицы

блока 7 памяти рельефов, стоящий

на пересечении i-й строки и j-ro

столбца, равен высоте рельефа, посту-jr по j-му направлению рельеф целиком.

20

25

35

пившей в данное устройство по j-му направлению, В блоке 5 памяти оптимальных маршрутов записана сжатая блоком 6 сравнения матрица рельефов. Элементы г- этой матрицы принимают значение О или 1,. при этом значение г.. 1 указывает на j-тое направление, совпадающее с направлением кратчайшего пути из данного устройства в j-Toe устройство. Если j-й рельеф не сформирован, то в соответствующих J-X строках блоков 5 и 6 записаны нули. Задача этапа формирования рельефа Заключается в том, чтобы записать в блок 7 информацию, соответствующую ,- высотам формируемого рельефа, а в блок 5 памяти - информацию о кратчайших путях.

Единичный рельеф из регистра 28 по выходу 32 поступает на информационный вход демультиплексора 21. На первый управляющий вход демультиплексора 21 поступает единичный потенциал через элемент ИЛИ 18 с выхода элемента И 20. Демультиплексор 21 по первому управляющему входу подключает единичный рельеф через блок 22 на вход 33 регистра 29 вьшода. Единичный рельеф поступает из регистра 29 по выходам 31 на информационный вход демультиплексора 4. Выходные направления ком- мутации демультиплексора 4 определяются нулевыми выходами триггеров i-й строки блока 5 памяти оптимальных маршрутов. В данном случае в -й строке записаны нули и единичный рельеф 50 с выхода блока 1 ввода-вывода транслируется по всем п-1 направлениям.

Процесс обработки рельефа в транзитном узле.

Сообщение Формирование рельефа 55 поступает в транзитный узел по входу 24, обрабатывается5 как и в узле - источнике сообщения. Отличие заключасчитывается 1-я строка блока 7 и поступает на блок 6 сравнения.

Блок 6 сравнения выбирает в i-й строке рельеф с минимальной высотой, подключает его на свой информацион- ньш выход, а на своих сигнальных выходах формирует единичные потенциалы соответствукяцие направлениям поступления минимапьньк высот рельефа. Выделенный блоком 6 сравнения минималь ньш рельеф поступает на сумматор 23, где, увеличенньй на единицу, через блок 22 поступает на блок 1 ввода- вывода и транслируется демультиплек- сором 4 по выбранным выходным направ лениям. Выходные направления коммута ции демультиплексора 4 определяются нулевыми разрядами i-й ячейки блока 5 памяти оптимальных марпфутов. Увеличенный на единицу рельеф транслируется по всем выходным направлениям не совпадающим с направлениями кратчайшего пути в i-и узел. Волна форми рования рельефа, распространяясь из узла i, охватывает все узлы сети и гасится на ее границах.

Работа устройства в режиме обмена

Сообщение поступает по входу 24 (, ..., п) в устройство. Служебна кодовая часть этого сообщения из регистра 28 ввода поступает по выходу 34 в дешифратор 16 кода режима, на втором выходе которого формируется единичный потенциал Обман. Если ад рес, принятый в составе сообщения, не равен физическому адресу устройства, то на выходе схемы 11 присутствует нулевой потенциал, который инвертируется элементов НЕ 13 и поступает на первьй вход элемента И 14. На второй вход элемента И 14 поступает единичный потенциал с второго выхода дешифратора 16 кода реж1- ма, и на выходе элемента И 14 формируется

ется

в том, что информационная часть сообщения переключается демульти- плексором 21 на его второй выход по ступает на информационный вход блока 7 памяти рельефов и записывается в j-й столбец 1-й строки. В этом случае демультиплексор 21 управляется единичным потенциалом, поступающим по второму его входу с выхода элемента И 19, при этом единичный признак транзитного узла формируется на выходе элемента НЕ 17. После того, как в j-й столбец записался поступивший

r по j-му направлению рельеф целиком.

0

5

5

-

0

5

считывается 1-я строка блока 7 и поступает на блок 6 сравнения.

Блок 6 сравнения выбирает в i-й строке рельеф с минимальной высотой,. подключает его на свой информацион- ньш выход, а на своих сигнальных выходах формирует единичные потенциалы, соответствукяцие направлениям поступления минимапьньк высот рельефа. Выделенный блоком 6 сравнения минималь- ньш рельеф поступает на сумматор 23, где, увеличенньй на единицу, через блок 22 поступает на блок 1 ввода- вывода и транслируется демультиплек- сором 4 по выбранным выходным направ-. лениям. Выходные направления коммутации демультиплексора 4 определяются нулевыми разрядами i-й ячейки блока 5 памяти оптимальных марпфутов. Увеличенный на единицу рельеф транслируется по всем выходным направлениям, не совпадающим с направлениями кратчайшего пути в i-и узел. Волна формирования рельефа, распространяясь из узла i, охватывает все узлы сети и гасится на ее границах.

Работа устройства в режиме обмена.

Сообщение поступает по входу 24 (, ..., п) в устройство. Служебная кодовая часть этого сообщения из регистра 28 ввода поступает по выходу 34 в дешифратор 16 кода режима, на втором выходе которого формируется единичный потенциал Обман. Если адрес, принятый в составе сообщения, не равен физическому адресу устройства, то на выходе схемы 11 присутствует нулевой потенциал, который инвертируется элементов НЕ 13 и поступает на первьй вход элемента И 14. На второй вход элемента И 14 поступает единичный потенциал с второго выхода дешифратора 16 кода реж1- ма, и на выходе элемента И 14 формируется

единичный потенциал, разрешающий обращение в блок 5 памяти оптимальных 1йаршрутов, Демультиплексор 4 комму- tиpyeт сообщение с блока 1 ввода-вывода на то выходящее направление, которое находится на кратчайшем пути в конечный i-й узел, в соответ- (JTBHH с управляющей информацией, хра. йящейся в блоке 5 памяти оптимальных Маршрутов.

Выходное направление коммутации Определяется единичным состоянием i-й строки блока 5, здесь i - адрес узла азначения5 передаваемый в составе Ьообщения, Этот адрес, как и в режиме формирования рельефа, поступает на | eшифpaтop 9 и разрешает доступ в со |этветствующие сроки блоков 5 и 7. В данном случае блок 7 не работает, так на втором управляющем выходе блока 8 управления установлен нулевой 1отенциал. Сообщение коммутируется ho выбранному направлению и через со

0

5

0

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

Изобретение относится к вычислительной технике и позволяет реализовать сети передачи дискретной информации, при этом достигается сокращение аппаратурных затрат. Цель достигается введением схемы 10 сравнения адреса с соответствунхцими связями, что позволяет сократить объемы блока 7 памяти рельефов и блока 5 памяти оптимальных маршрутов. Устройство работает в режимах формирования рельефа и обмена, которые задаются полем команды в формате сообщения поступающего на информационные входы устройства. Поле команды анализируется дешифратором 16 кода режима в блоке 8 управления, и в зависимости от его содержания происходит работа устройства в одном из режимов. 2 з.п.ф-лы, 3 ил. S

ртветствующий блок буферных регистров 25 Дионного поля блока ввода-вывода, вы- |транслщ)уется в смежный узел по на Правлению кратчайшего пути,

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

ходы ПОЛЯ команды и информационного поля которого соединены с входом ко- манды блока управления и информационным входом демультиплексора дан1а1х соответственно, второй выход которого соединен с информационным входом блока памяти рельефов, второй и тре тий выходы режима блбка управления соединены с первым и вторым управляющими входами дег-гультиплексора данных соответственно, отличающееся тем, что, с целью сокращения аппаратурных затрат, в него введены, схема сравнения адреса, первый и второй информационные входы которой соединены с выходом поля адреса блока ввода-вывода и с адресным входом устройства соответственно, вход строба выдачи схемы сравнения адреса соединен с четвертым выходом режима блока управления, прямой и инверсный выходы признака равенства схемы сравнения адреса соединены с входом п-го разря да адреса демультиплексора и входом разрешения выдачи блока памяти оптимальных маршрутов,

0

5

0

ходы ПОЛЯ команды и информационного поля которого соединены с входом ко- манды блока управления и информационным входом демультиплексора дан1а1х соответственно, второй выход которого соединен с информационным входом блока памяти рельефов, второй и тре тий выходы режима блбка управления соединены с первым и вторым управляющими входами дег-гультиплексора данных соответственно, отличающееся тем, что, с целью сокращения аппаратурных затрат, в него введены, схема сравнения адреса, первый и второй информационные входы которой соединены с выходом поля адреса блока ввода-вывода и с адресным входом устройства соответственно, вход строба выдачи схемы сравнения адреса соединен с четвертым выходом режима блока управления, прямой и инверсный выходы признака равенства схемы сравнения адреса соединены с входом п-го разря да адреса демультиплексора и входом разрешения выдачи блока памяти оптимальных маршрутов,

0

7 1432546

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

8 3. Устройство по П.1, отличающееся тем, что схема сравнения адреса содержит схему сравне- , ния, два э;}емента И и элемент НЕ, первый и второй информационные входы схемы сравнения являются одноименными входами схемы сравнения адреса, прямой и инверсный выходы признака

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

сравнения соединен с вторым входом первого элемента И и через элемент НЕ с вторым входом второго эле- . мента И.

32

33

JV

35