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

(Л

Фш.1

31А9

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

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

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

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

Устройство имеет п информационных

0

67

5

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

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

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

Изобретение относится к вычислительной технике и технике связи ,в частности, к технике построения узлов коммутации на сетях передачи дискретной информации. Цель изобретения - повышение быстродействия в режиме обмена и уменьшение аппаратурных затрат. Цель достигается за счет исключения необходимости сравнения адресов, принятых в составе сообщения, при этом соответственно исключается необходимость использования в составе устройства схемы опознавания адреса. Это обеспечивается за счет использования адресного блока 17, выполненного на элементе ИЛИ-НЕ 19, входы которого соединены с выходами блока 4 памяти оптимальных маршрутов, элемента 18 задержки и элемента И 20, соединенных с выходом дешифратора 9 кода режима. 3 ил.

входов 21„, подключенных-к муль- ЗО о максимальной высоте рельефа, в типлексору 2 и п информационных вы-сети образуется А-рельеф, представходов , подключенных к первому демультиплексору 3. Вход 23 установки исходного состояния подключен к управляющему входу блока 4 памяти

35

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

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

Блок 1 ввода-вывода (фиг.З) состоит из регистра 24 ввода и регистра 25 вывода. Первые входы 26 регистра 24 подключены к выходам мультиплек- сЬра 2, а второй информационный выход 27 регистра 25 подключен к информационным входам первого демуль- типлексора 3. Первый информационный выход 28 информационной части регистра 24 подключен к первому информационному входу второго демультиштек- сора 10. Вход 29 информационной части регистра 25 подключен к выходу блока 11 элементов ИЖ. Кодовый 30 и адресный 31 выходы регистра 24 подключены соответственно к кодовым и адресным входам регистра 25. При этом кодовый выход 30 подключен к входу дешифратора 9 кода режима, а адресньй выход 31 - к входу дешифратора 7 адреса.

5

0

5

0

5

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

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

Сообщение поступает по j-му (j 1,2,...,п) входу 21 в устройство. Служебная кодовая часть этого сообщения из регистра,24 ввода поступает на выход 30, на дешифратор 9 кода режима, на втором выходе которого формируется единичный потенциал Обмен, разрешаюш;ий обращение в блок 4 памяти оптимальных маршрутов. Де- мультиплексор 3 коммутирует блок 1 ввода-вывода на то выходящее направление, которое находится на кратчайшем пути в конечный i-й узел, в соответствии с управляющей информацией, хранящейся в блоке 4 памяти оптимальных маршрутов.

Выходное направление комкута1Д1и определяется единичным состоянием i-й строки блока 4, где i - адрес узла назначешта, передаваемый в составе сообщения. Этот адрес, как и в режиме формирования рельефа, поступает на дешифратор 7 и разрешает доступ в соответствующие строки блоков 4 и 6 памяти. В данном случае блок б не работает, т.е. на втором управляющем выходе.дешифратора 9 кода режима установлен нулевой потенциал. Сообщение коммутируется по выбpaннo ry направлению и транслируется в смежный узел по направлению кратчайшего пути.

Если сообщение поступает в узел, в котором по п-му направлении подключен абонент-адресат (приемник сообщения), то направление, коммутации в абонент определяется адресным блоком 17. В строке памяти маршрутов соответствующей данному конечному узлу, хранятся нули, записанные на этапе формирования рельефа. На выходе элемента ИЛИ-НЕ 19 формируется единичньш потенциал, который поступает на второй вход элемента И 20. На первый вход этого элемента подается управочнющий единичный потенциал с выхода дешифратора 9 кода. Этот потенциал соответствует режиму обмена. На третий вход элемента И 20 поступает тот же потенциал обмена, задержанный на время сГд элементом 18 задержки. Время с э задержки должно отвечать условию:

-- пом ;

где т f,(5A время обращения в памя Еь 4 оптимальных маршрутов. Таким образом, если сообщение достигло узла приемника, то на выходе элемента И 20 адресного блока 17 5)ормируется потенциал, направляющий поступившее сообщение по п-му направлению в абонент - приемник сообщения.

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

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

0

5

0

5

0

5

0

5

0

5

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

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

K&I.WOfn&t.n

Г

а

ts

fffftSК&1.7

Фиг.з

Редактор В. Петраш

Составитель В. Сычев Техред Л.Сердюкова

Заказ А696/49

Тираж 668

ВШПШИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

0

5

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

28 19

г5

f(Sjt.3

г7

30 ЗГ

Корректор Т.Малец

Подписное