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

.РЕСПУБЛИН ш 14 09 51) 4 Р 15 СР;Ож ПИСАН ВТОРСНОМУ Ц а- тис- али- ин- окраов. ОСУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) Авторское свидетельство ССР 962967, кл. С 06 Р 15/20, 198Авторское свидетельство СССРВ 1396818, кл. С 06 Р 15/20, 19 4) УСТРОЙСТВО МАРШРУТИЗ(57) Изобретение относится к вычлительной технике и позволяет рэовать сети передачи дискретнойФормации, при этом достигается щение анпаратурных затрат. Цель достигается введением схемы 10 сравнения адреса с соотнетствукщими связями, что позволяет сократить объемыблока 7 памяти рельефов и блока 5 имяти оптимальных маршрутов, Устройсво работает в режимах формированиярельефа и обмена, которые задаютсяполем команды в формате сообщения поступающего на информационные входы241-24 устройства. Поле команды анализируется дешифратором 16 кода режима в блоке 8 управления, и в зависимости от его содержания происходитработа устройства в одном иэ режим2 з.п.ф-лы, 3 ил .Изобретение относится к вычислительной технике и технике связи и может использоваться при проектированииустройств обработки данных и построении узлов коммутации на сетях пере 5дачи дискретной информации.Цель изобретения - сокращение аппаратурных затрат.На Фиг.1 представлена Функциональная схема устройства на Фиг.2 - схема блока ввода-вывода на Фиг.3,процедура маршрутизации,Устройство (фиг,1) содержит блок,1 вводавывода, мультиплексор 2, блок 153 буферных регистров, демультиплексор 4, блок 5 памяти оптимальныхмаршрутов, блок 6 сравнения, блок 7 памяти рельефов, блок 8 управления, дешифратор 9 адреса и схему 10 сравненияадреса.Схема 10 сравнения адреса содержитсхему 11 сравнения, первый элементИ 12, элемент НЕ 13 и второй элемент,И 14. 2Блок 8 управления содержит генератор 15 сканирования, дешифратор 16кода режима, элемент НЕ 17, элементИЛИ 18 и элементы И 19 и 20.Кроме того, устройство содержит 30демультиплексор 21 данных, блок 22элементов ИЛИ и сумматор 23 единицы.Устройство имеет и информационныхвходов 24-24 и и выходов 25-25,вход 26 установки исходного состояния и адресный вход 27.Блок 1 ввода-вывода (фиг.2) состоит из регистра 28 ввода и регистра29 вывода и имеет вход 30 сообщения,выход 31 сообщения, выход 32 информационного поля, вход 33 информационного ноля, выход 34 поля команды и выход 35 поля адреса.Совокупность устройств, соединенных дуплексными линиями связи по входам 24,-24 и выходам 25;25, образует сеть связи. При этом устройствомаршрутизации является узлом сети,авходы 24-24 п и выходы 25-25связывают его с соседними узлами.Предположим, что на сети решается 50задача нахождения множества критических путей в узел А (фиг.3). В этомслучае из узла А формируется А-рельефпо следующему алгоритму,Узлу А пу.сваивается единичное 55значение к рельефа, которое транслируется и; всем исправным направлениямв смежи с ним узлы. Соседние узлы,получив рельеф, выбирают минимальный (который в данном случае равен 1), увеличивают на единицу значение минимального рельефа и транслируют измененное значение рельефа по тех выходным направлениям, которые не содержат минимальные рельефы. Этим самым обеспечивается направленное распространение рельефа в сети, что исключает перегрузку сети за счет отражений и образования циклов.Через конечное количество трансляций, равное максимальной высоте рельефа, в сети формируется А-рельеф, представляющий собой по числу направлений связи набор чисел, хранящихся в каждом узле сети. Значение высоты рельефа, соответствующее данному направлению, равно числу транзитных узлов на пути обмена в узел А по данному направлению. Совокупность направленЯ, помеченных минимальными высотами А-рельефа, образует кратчайший маршрут в узел АУстройство маршрутизации работает следующим образом.Очередность обслуживания поступающих на устройство по входам 24-24 сообщений определяется генератором 15 сканирования. Генератор 15 формирует на своих выходах временную по. следовательность единичных потенциалов, в соответствии с которой мультиплексор 2 поочередно заполняет ре. гистр 28 ввода поступающими сообщениями. При этом частота опроса (сканирования) мультиплексора 2 выбирается с учетом скорости поступления сообщений но входам 24-24 таким образом, чтобы избежать очередей. п-ое направление соответствует связи уст" ройства с собственным абонентом.При подключении устройства в сеть происходит обнуление блоков 5 и 7 памяти по входу 25. Затем начинается этап формирования рельефа -го узла ( 1, , ш, где ш - количество узлов в сети).По входу.24устройства иэ абонентапоступает сообщение "Формирование рельефа", в информационной час-. ти которого хранится единичный рельеф. Это сообщение по входам 30 заносится в блок 1 ввода-вывода, с выходов 35, 34 и 32 которого его составные части- адрес, команды и информация поступают параллельно в дешифратор 9 адреса, дешифратор 16 кода режима ы на вход3 14325демультиплексора 21. На первом выходе дешифратора 16 кода режима формируется единичный потенциал формирования рельефа который разрешает обраФ5щение в блоки 5 и 7 памяти. Последниеимеют матричную структуру: -я строка(=1.ш) каждого блока соотвествует -му рельефу, а 3-й (1=1,п) столбец соответствует направлению связи данного устройства со смежными устройствами. Элемент матрицыг; блока 7 памяти рельефов, стоящийна пересечении г-й строки и 1-гостолбца, равен высоте рельефа, поступившей в данное устройство по 1-мунаправлению. В блоке 5 памяти оптимальных маршрутов записана сжатаяблоком 6 сравнения матрица рельефов.Элементы г, этой матрицы принимаютзначение О или 1, при этом значениег =1 указывает на 1-тое направление,совпадающее с направлением кратчайшего пути из данного устройства в1-тое устройство. Если 1-й рельеф несформирован, то в соответствующих1-х строках блоков 5 и 6 записаны нули. Задача этапа формирования рельефа заключается в том, чтобы записатьв блок 7 информацию, соответствующуювысотам формируемого рельефа, а в блок5 памяти - информацию о кратчайшихпутях.Единичный рельеф иэ регистра 28 повыходу 32 поступает на информационныйвход демультиплексора 21, На первыйуправляющий вход демультиплексора 21поступает единичный потенциал черезэлемент ИЛИ 18 с выхода элемента И20, Демультиплексор 21 по первому управляющему входу подключает единичныйрельеф через блок 22 на вход 33 регистра 29 вывода. Единичный рельефпоступает из регистра 29 по выходам31 на информационный вход демультиплексора 4. Выходные направления коммутации демультиплексора 4 определяются нулевыми выходами триггеров 1.-йстроки блока 5 памяти оптимальныхмаршрутов. В данном случае в -й строке записаны нули и единичный рельеф 50с выхода блока 1 ввода-вывода транслируется по всем пнаправлениям.Процесс обработки рельефа в транзитном узле.Сообщение "Формирование рельефа" 55поступает в транзитный узел по входу24, обрабатывается, как и в узле -источнике сообщения. Отличие заключа 46 4ется в том, что информационная частьсообщения переключается демультиплексором 21 на его второй выход, поступает на информационный вход блока7 памяти рельефов и записывается в3-й столбец х-й строки. В этом случаедемультиплексор 21 управляется единичным потенциалом, поступающим повторому его входу с выхода элементаИ 19, при этом единичный признактранзитного узла формируется на выходе элемента НЕ 17, После того, какв 1-й столбец записался поступившийпо 1-му направлению рельеф целиком,считывается х-я строка блокаи поступает на блок б сравнения,Блок 6 сравнения выбирает в д-йстроке рельеф с минимальной высотой,.подключает его на свой информационный выход, а на своих сигнальных выходах Формирует единичные потенциалы,соответствующие направлениям поступления минимальных высот рельефа. Выделенный блоком 6 сравнения минимальный рельеф поступает на сумматор 23,где, увеличенный на единицу, черезблок 22 поступает на блок 1 вводавывода и транслируется демультиплексором 4 по выбранным выходным направ-,лениям. Выходные направления коммутации демультиплексора 4 определяютсянулевыми разрядами -й ячейки блока5 памяти оптимальных маршрутов. Увеличенный на единицу рельеф транслируется по всем выходным направлениям,не совпадающим с направлениями кратчайшего пути в -й узел. Волна формирования рельефа, распространяясь изузла 3., охватывает все узлы сети игасится на ее границах.Работа устройства в режиме обмена.Сообщение поступает о входу 24(К=1, , и) в устройство. Служебнаякодовая часть этого сообщения из регистра 28 ввода поступает по выходу34 в дешифратор 16 кода режима, навтором выходе которого Формируетсяединичный потенциал "Обман", Если адрес, принятый в составе сообщения,не равен физическому адресу устройства, то на выходе схемы 11 присутствует нулевой потенциал, который инвертируется элементов НЕ 13 и поступает на первый вход элемента И 14.На второй вход элемента И 14 поступает единичный потенциал с второго выхода дешифратора 16 кода режима, ина выходе элемента И 14 формируется5 14единичный потенциал, разрешающий обращение в блок 5 памяти оптимальныхмаршрутов, Демультиплексор 4 коммутирует сообщение с блока 1 ввода-выВода на то выходящее направление, которое находится на кратчайшем пути в конечный -й узел, в соответСтвии с управляющей информацией, хра. -нящейся в блоке 5 памяти оптимальныхмаршрутов,Выходное направление коммутацииОпределяется единичным состоянием "йСтроки блока 5, здесь х - адрес узлаНазначения, передаваемый в составеСообщения. Этот адрес, как и в режимеормирования рельефа, поступает надешифратор 9 и разрешает доступ в соОтветствующие сроки блоков 5 и 7. Вданном случае блок 7 не работает, такКак на втором управляющем выходе блоКа 8 управления установлен нулевой1 отенциал, Сообщение коммутируетсяцо выбранному направлению и через соответствующий блок буферных регистровтранслируется в смежный узел по направлению кратчайшего пути, 3254 бго по (и)-й разрядов адреса демультиплексора, входы установки в "О" блоков памяти рельефов и оптимальных маршрутов соединены с входом начальной установки устройства, выход поля адреса блока ввода-вывода соединен с входом дешифратора адреса, с первого по ш-й выходы которого (ш - количество устройств в реализуемой сети передачи данных) соединены с первого по ш-й входами адреса рельефа блоков па 15 20 2 б мяти рельефа и оптимальных маршрутов,первый выход режима блока управлениясоединен с входами разрешения обращения блоков памяти рельефов и оптимальных маршрутов и блока сравнения, выход минимального рельефа которого соединен с информационным входом сумматора единицы, выход которого и первыйвыход демультиплексора данных соединены с первым и вторым входами блокаэлементов ИЛИ соответственно выходкоторого соединен с входом информационного поля блока ввода-вывода, выходы поля команды и информационногополя которого соединены с входом ко- .манды блока управления и информаци Формула из обретения 1. Устройство маршрутизации, содержащее мультиплексор, демульти лексор, демультиплексор данных, блок элементов ИЛИ, сумматор единицы, блок ввода-вывода, блок управления, блок памяти рельефов блок сравнения, блок памяти оптимальных маршрутов и дешифратор адреса, информационные входы мультиплексора являются одноименными входами устройства, выход мультиплексора соединен с входом сообщения блока ввода-вывода, выход сообщения которого соединен с информационным входом демультиплексора, выходы которого являются выходами устройства, с пер-, вого по (и)-й выходы опроса блока управления (и - количество направлений связи) соединены с первого по (и)-й входами адреса мультиплексора и входами адреса направления связи блока памяти рельефов, а-й выход опроса блока управления соединен с и"м входом адреса мультиплексора выходы блока памяти рельефов соединены с информационными входами блока сравнения, выходы которого соединены с входами адреса направления связи блока памяти оптимальных маршрутов, выходы которого соединены с входамис первоонным входом демультиплексора данных соответствепно, второй выход которого соединен с информационным входом блока памяти рельефов, второй и третий выходы режима блдка управления соединены с первым и вторым управляющими входами демультиплексора данных соответственно, о т л и ч а ю щ е - е с я тем, что, с целью сокращения аппаратурных затрат, в него введены. схема сравнения адреса, первый и вто"рой информационные входы которой соединены с выходом поля адреса блока ввода-вывода и с адресным входом устройства соответственно, вход строба выдачи схемы сравнения адреса соединен с четвертым выходом режима блока управления, прямой и инверсный выходы признака равенства схемы сравнения адреса соединены с входом и-го разря" да адреса демультиплексора и входомразрешения выдачи блока памяти оптимальных маршрутов,2 Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок управления содержит генератор сканирования, дешифратор кода режима, два эле"мента И, элемент НК и элемент ИЛИ,с первого по и-й выходы генераторасканирования являются с первого пои-й выходами опроса блока, вход ко 7 14325 манды которого соединен с входом дешифратора кода режима, первый выход которого соединен с первыми входами первого и второго элементов И и является первым выходом режима блока,5 второй выход дешифратора кода режима соединен с первым входом элемента ИЛИ и является четвертым выходом режима блока, п-й выход генератора сканирования соедине с вторым входом первого элемента И и через элемент НЕ с вторым входом второго элемента И, выход первого элемента И соединен с вторым входом элемента ИЛИ, выход которого и выход второго элемента И являются вторым и третъим выходами режимаблока. 46 83. Устройство по п.1, о т л и " ч а ю щ е е с я тем, что схема сравнения адреса содержит схему сравнения, два элемента И и элемент НЕ, первый и второй информационные входы схемы сравнения являются одноименными входами схемы сравнения адреса, прямой и инверсный выходы признака равенства которой соединены с выхо-дами первого и второго элементов И соответственно, первые входы которых соединены с входом строба выдачисхемы сравнения адреса, выход схемы сравнения соединен с вторым входом первого элемента И и через элемент НЕ с вторым входом второго эле-, мента И.1432546 едактор О.Юрковецкая С.Черн орр аказ 5443/4 О Подписное 4/ зводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,оставител ехред А.К ВНИИПИ Государственного ко по делам изобретений и13035, Москва, Ж, Раушска