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

(я) 4 С 06 Р 15 ИОАН РЕТЕН Б. БЛИС.К 29и В.С. Ракошиц ССР986.Р троенияередачиель изобр ГОСУДАРСТ 8 ЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ П.(НТ СССР ОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СУ 1396818, кл . С 06 Г 15/20, 1Авторское свидетельство СССУ 1432546, кл. С 06 Р 15/20, 1986,(57) Йзобретение относится к вычислительной технике и технике связи,в частности к технике пос Улов коммутации на сетях идискретной инФормации. Ц е тения - повышение быстродействия врежиме обмена и уменьшение аппаратурньм затрат. Цель достигается за счетисключения необходимости сравненияадресов, принятьм в составе сообщения, при этом соответственно исключается необходимость использованияв составе устройства схемы опознавания адреса. Это обеспечивается засчет использования адресного блока17, выполненного на элементе ИЛИ-НЕ19, входы которого соединены с выходами блока 4 памяти оптимальныхмаршрутов, элемента 18 задержки иэлемента И 20, соединенных с вьмодомдешифратора 9 кода режима. 3 ил367 4Совокупность устройств, соединенных дуплексными линиями связи по вхо.дам 21 -21 д и выходам 22 -22, обра 15 20 25 30 35 40 45 50 55 Блок 1 ввода-вывода (фиг.З) состоит из регистра 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 и и инфс 9 мационных вьходов 22-22, подключенных к перво"му демультиплексору 3 . Вход, 23 установки исходного состояния подключенк управляющему входу блока 4 памятиоптимальных маршрутов и блока 6 памяти рельефов. зует сеть связи, При этом устройство маршрутизации является узлом сети,.а входы 21 и выходы 22 связыва"ют его с соседними узлами,Предположим, что на сети решается задача нахождения множества кратчайших путей в узел А (фиг.2), В этом случае из узла А формируется А-рельеф по следующему алгоритму. Узлу А присваивается единичное значение А-рельефа, которое транслируется по всем исправным направлени-. ям в смежные с ним узлы. Соседние узлы, получив рельеф, выбирают минимальный (который в данном случае равен 1), увеличивают на единицу значение минимального рельефа и транслируют измененное значение рельефа по тем выходным направлениям, которые не содержат минимальные рельефы, Этим обеспечивается направленное распространение рельефа в сети, что исключает перегрузку сети за счет отражений и образования циклов. Через конечное количество трансляций, равное максимальной высоте рельефа, в сети образуется А-рельеф, прецставляющий собой по числу направлений связи набор чисел, хранящихся в каждом узле сети, Значение высоты рельефа, соответствующее данному направлению, равно числу транзитных узлов на пути обменав узел А по данному направлению. Совокупность направлений, помеченных минимальньпи высотами А-рельефа, образует кратчайший путь в узел А.Работа устройства в режиме обмена,Сообщение поступает по 1-му (1= =1,2 п) входу 21 в устройство. Служебная кодовая часть этого сообщения из регистра,24 ввода поступает на выход 30, на дешифратор 9 кода режима, на втором выходе которого формируется единичный потенциал "Обмен", разрешающий обращение в блок 4 памяти оптимальных маршрутов. Демультиплексор 3 кьммутирует блок 1 ввода-вывода на то выходящее направление, которое находится на кратчайшем пути в конечный 1-й узел, в соответствии с управляющей информацией, хранящейся в блоке 4 памяти оптимальных маршрутов.5 14993Выходное направление коммутацииопределяется единичным состоянием-й строки блока 4, где- адресузла назначения, передаваемый в составе сообщения. Этот адрес, как и в5режиме формирования рельефа, поступает на дешифратор 7 и разрешаетдоступ в соответствующие строки блоков 4 и 6 памяти, В данном случаеблок 6 не работает, т.е. на второмуправляющем выходе дешифратора 9 кода режима установлен нулевой потенциал. Сообщение коммутируется повыбранному направлению и транслиру 15ется в смежный узел по направлениюкратчайшего пути,Если сообщение поступает в узел,в котором по и-му направлению подключен абонент-адресат (приемниксообщения), то направление коммутации в абонент определяется адреснымблоком 17. Б строке памяти маршрутов,соответствующей данному конечномуузлу, хранятся нули, записанные наэтапе Формирования рельефа, На выходе элемента ИЛИ-НЕ 19 формируетсяединичный потенциал, который поступает на второй вход элемента И 20.На первый вход этого элемента подается упраьля 1 ющий единичный потенциал30с выхода дешифратора 9 кода. Этотпотенциал соответствует режиму обмена. На третий вход элемента И 20 поступает тот же потенциал обмена, задержанный на время ю элементом 18 задержки, Бремязадержки должно отвечать условию:лОЗ) пюм угде Т - время обращения в память4 оптимальных маршрутов.Таким образом, если сообщениедостигло узла приемника, то на выходе элемента И 20 адресного блока17 формируется потенциал, направляющий поступившее сообщение по и-му 45направлению в абонент - приемниксообщения,Формула из обретения 50Устройство маршрутизации, содержащее мультиплексор, демультиплексор, демультиплексор данных, сумматор единицы, блок ввода-вывода,.блок памяти 55 рельефов, блок сравнения, блок памяти оптимальных маршрутов, дешифратор адреса, генератор сканирования,67 6дешифратор кода режима, блок элементов ИЛИ, три элемента И, элемент ИЛИ, элемент НЕ, причем информационные входы мультиплексора являются одноименными входами устройства, выход мультиплексора соединен с входом сообщения блока ввода-вывода, выход сообщения которого соединен с информационным входом демультиплексора, выходы которого являются выходаж устройства, с первого по (и)-й выходы генератора сканирования (и - количество направлений связи) соединены с первого по (и)-й входами адреса мультиплексора и входами адреса направления связи блока памяти рельефов, и-й выход генератора сканирования соединен с п-м входом адреса мультиплексора, с первым входом первого элемента И и через элемент НЕ с первым входом второго элемента И, выходы блока. памяти рельефов соединены с информационными входами блока сравнения, выходы которого соединены с входами адреса направления связи блока памяти оптимальных маршрутов, выходы которого соединены с вхоцами с первого по (и)-й разрядов адреса демультиплексора, вход и-го разряда адреса которого подключен к выходу третьего элемента И, входы установки в "0" блоков памяти рельефов и оптимальных маршрутов соединены с вкладом начальной установки устройства, вьац поля адреса блока ввода-вывода соединен с входом дешифратора адреса, с первого по ш-й выходы которого (ш - количество устройств в реализуемой сети передачи данных) соединены с первого по ш-й входами адреса рельефа блоков памяти рельефов и сптим-".ьных маршрутов, выход поля команды 1блока ввода-вывода соединен с входом дешифратора кода режима, первый выход которого соединен с вторымн входами первого и второго элементов И, с входами р,зрешения обращения блоков памяти рельефа, оптимальных маршрутов и сравнения, второй выход дешифратора кода режима соединен с входом разрешения выдачи блока памяти оптимальных маршрутов, с первыми входами элемента ИЛИ и третьего элемента И, выход информационного поля блока ввода-вывода соединен с информационным входом демультиплексора данных. первый выход ко1499367 Составитель В, СычевТехред Л. Сердюкова Корректор Т,Мале етра Редакто Заказ 4696/49 Тираж 668 Подпис ное ВНИИПИ Государственного комитета по изобретениям и открытиям пр113035, Москва, Ж, Раушская наб., д. 4/5 ГКНТ СССР роизводственно-издательский комбинат "Патент", г.ужгород Гагарина,101 торого соединен с информационнымвходом блока памяти рельефов, выходпервого элемента И соединен с вторымвходом элемента ИЛИ, выход которогоподключен к первому управляющему входу демультиплексора данных, второйуправляющий вход которого соединенс выходом второго элемента И, выходминимального рельефа блока сравнениясоединен с информационным входомсумматора единицы, выход которогои первый выход демультиплексора данных соединен с первым и вторым входами блока элементов ИЛИ соответственно, выход которого соединен с входом информационного поля блокаввода-вывода, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия в режиме обмена и уменьшения аппаратурных затрат, в неговведены элемент задержки и элементИЛИ-НЕ, причем с первого по (и)-йвходы элемента ИЛИ-НЕ подключены к 10 выходам с первого по (и)-й блокапамяти оптимальных маршрутов, выходэлемента ИЛИ-НЕ соединен с вторымвходом третьего элемента И, третийвход которого через элемент задержки соединен с вторым выходом дешифратора кода режима.