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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (19) (11) (51) 4 G 06 F 15/20

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

2» и

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

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

ПРИ П.(НТ СССР

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4 294 170/24-24 (22) 05.08,87 (46) 07.08.89. Бюл. N 29 (72) Ю.Н. Максименко и В.С. Ракошиц (53) 681.3 25 (088. 8) (56) Авторское свидетельство СССР

N 1396818, кл. G 06 Г 15/20, 1986.

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

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

17, выполненного на элементе ИЛИ-НЕ

19, входы которого соединены с выходами блока 4 памяти оптимальных маршрутов, элемента 18 задержки и элемента И 20, соединенных с вьмодом дешифратора 9 кода режима. 3 ил °

367 4

Совокупность устройств, соединенных дуплексными линиями связи по входам 21 -21 д и выходам 22 -22„, обра15

Блок 1 ввода-вывода (фиг.3) состоит из регистра 24 ввода и регистра

25 вывода. Первые входы 26 регистра

24 подключены к выходам мультиплексора 2, а второй информационный выход 27 регистра 25 подключен к информационным входам первого демультиплексора 3. Первый информационный выход 28 информационной части регист. ра 24 подключен к первому информационному входу второго демультиплексора 10. Вход 29 информационной части регистра 25 подключен к выходу блока 11 элементов ИЛИ. Кодовый 30 и адресный 31 выходы регистра 24 подключены соответственно к кодовым и адресным входам регистра 25. При этом кодовый выход 30 подключен к входу дешифратора 9 кода режима, а адресный выход 31 — к входу дешифратора 7 адреса.

3 1499

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

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

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

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

1 ввода-вывода, мультиплексор 2, демультиплексор 3, блок 4 памяти оптимальных маршрутов, блок 5 сравнения, блок 6 памяти рельефов, дешифратор

7 адреса, генератор 8 сканирования, дешифратор 9 кода режима, демультиплексор 10 данных, блок 11 элементов

ИЛИ, сумматор 12 единицы, первый элемент И 13, элемент НЕ 14, второй элемент И 15, элемент ИЛИ 16, и адресный блок 17, который содержит элемент 18 задержки, элемент ИЛИ-НЕ 19 и элемент И 20.

Устройство имеет п информационных входов 21 — 21„, подключенных-к муль типлексору 2 и и инфсфмационных вьходов 22<-22„, подключенных к первому демультиплексору 3. Вход, 23 установки исходного состояния подключен к управляющему входу блока 4 памяти оптимальных маршрутов и блока 6 памяти рельефов.

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

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

А-рельеф по следующему алгоритму.

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

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

Сообщение поступает по j ìó (j=

=1,2,...,п) входу 21 в устройство.

Служебная кодовая часть этого сообщения из регистра,24 ввода поступает на выход 30, на дешифратор 9 кода режима, на втором выходе которого формируется единичный потенциал "Обмен", разрешающий обращение в блок

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

5 14993

Выходное направление коммутации определяется единичным состоянием

i-й строки блока 4, где i — адрес узла назначения, передаваемый в составе сообщения. Этот адрес, как и в

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

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

На первый вход этого элемента подается управляющий единичный потенциал

30 с выхода дешифратора 9 кода. Этот потенциал соответствует режиму обмена. На третий вход элемента И 20 поступает тот же потенциал обмена, задержанный на время à> элементом 18 за- 35 держки, Бремя задержки должно отвечать условию: сзз) пом у где Т „- время обращения в память

4 оптимальных маршрутов.

Таким образом, если сообщение достигло узла приемника, то на выходе элемента И 20 адресного блока

17 формируется потенциал, направляющий поступившее сообщение по и-му направлению в абонент — приемник сообщения.

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

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

ИЛИ, элемент НЕ, причем информационные входы мультиплексора являются одноименными входами устройства, выход мультиплексора соединен с входом сообщения блока ввода-вывода, выход сообщения которого соединен с информационным входом демультиплексора, выходы которого являются выходаж устройства, с первого по (n1)-й выходы генератора сканирования (n — количество направлений связи) соединены с первого по (n-1)-й входами адреса мультиплексора и входами адреса направления связи блока памяти рельефов, п-й выход генератора сканирования сосдинен с и-м входом адреса мультиплексора, с первым входом первого элемента И и через элемент НЕ с первым входом второго элемента И, выходы блока памяти рельефов соединены с информационными входами блока сравнения, выходы которого соединены с входами адреса направления связи блока памяти оптимальных маршрутов, выходы которого соединены с вхоцами с первого по (n-1)-й разрядов адреса демультиплексора, вход и-го разряда адреса которого подключен к выходу третьего элемента И, входы установки в "0" блоков памяти рельефов и оптимальных маршрутов соединены с r:.. öîì начальной установки устройства, вь:)ц поля адреса блока ввода-вывода соединен с входом дешифратора адреса, с первого по m-й выходы которого (m— количество устройств в реализуемой сети передачи данных) соединены с первого по m-й входами адреса рельефа блоков памяти рельефов и сптим ".ьных маршрутов, выход поля команды

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

ЦЩ7

sam

Составитель В. Сычев

Техред Л. Сердюкова

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

Подпис ное

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

Заказ 4696/49

Тираж 668

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

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

Производственно-издательский комбинат "Патент", r.Óæãîðîä, ул. Гагарина,101 торого соединен с информационным входом блока памяти рельефов, выход первого элемента И соединен с вторым входом элемента ИЛИ, выход которого подключен к первому управляющему входу демультиплексора данных, второй управляющий вход которого соединен с выходом второго элемента И, выход минимального рельефа блока сравнения соединен с информационным входом сумматора единицы, выход которого и первый выход демультиплексора данных соединен с первым и вторым входами блока элементов ИЛИ соответственно, выход которого соединен с. входом информационного поля блока ввода-вывода, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия в режиме обмена и уменьшения аппаратурных затрат, в него введены элемент задержки и элемент

ИЛИ-НЕ, причем с первого по (и-1)-й входы элемента ИЛИ-НЕ подключены к

10 выходам с первого по (n-1)-й блока памяти оптимальных маршрутов, выход элемента ИПИ-HE соединен с вторым входом третьего элемента И, третий вход которого через элемент задержки соединен с вторым выходом дешифратора кода режима.