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

 

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

СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИН

„„SU,, 143254 (51) 4 G 06 Р 15/20

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

ПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ВС .Ожсн4я

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ц „,,,:, ц(Н АВТОРСНОМУ СВИДЕТЕЛЬСТВУ МЕЛА»»;.;у„ (54) УСТРОЙСТВО МАРШРУТИЗАЦИИ (21) 4190384/24-24 (22) 29.12 ° 86 (46) 23,10,88. Бкл. Р 39 (72) И.Н.Максименко и В.С.Ракошиц (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Р 962967, кл. G 06 F 15/20, 1980.

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

11» 1396818, кл. С 06 F 15/20, 1986. (57) Изобретение относится к вычислительной технике и позволяет реализовать сети передачи дискретной инФормации, при этом достигается сокращение анпаратурных затрат. Цель достигается введением схемы 10 сравнения адреса с соотнетствукицими связями, что позволяет сократить объемы блока 7 памяти рельефов и блока 5 памяти оптимальных маршрутов. Устройство работает в режимах формирования рельефа и обмена, которые задаются полем команды в формате сообщения поступающего на информационные входы

241-24„ устройства. Поле команды анализируется дешифратором 16 кода режима в блоке 8 управления, и в зависи. мости от его содержания происходит работа устройства в одном иэ режимов.

2 з.п.ф-лы, 3 ил .

1432546

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

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

На Фиг.1 представлена Функциональ- 10 ная схема устройства на Фиг.2 - схема блока ввода-вывода на Фиг.3,процедура маршрутизации, Устройство (фиг.1) содержит блок

,1 ввода»вывода, мультиплексор 2, блок 15

l3 буферных регистров, демультиплек сор 4, блок 5 памяти оптимальныхмаршрутов, блок 6 сравнения, блок 7 памя-! ти рельефов, блок 8 управления, деши Фратор 9 адреса и схему 10 сравнения адреса.

Схема 10 сравнения адреса содержит схему 11 сравнения, первый элемент

И 12, элемент НЕ 13 и второй элемент, И 14. 25

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

ИЛИ 18 и элементы И 19 и 20.

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

Устройство имеет и информационных входов 241-24„ и и выходов 251-25„, вход 26 установки исходного состояния и адресный вход 22.

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

29 вывода и имеет вход 30 сообщения, .выход 31 сообщения, выход 32 информационного поля, вход 33 информационного ноля, выход 34 поля команды и выход 35 поля адреса.

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

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

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

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

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

Очередность обслуживания поступающих на устройство по входам 24„-24„ сообщений определяется генератором

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

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

По входу.24 „ устройства иэ абонента i поступает сообщение "Формирование рельефа", в информационной час-. ти которого хранится единичный рельеф.

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

3 f4325

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

Элементы г; этой матрицы принимают < значение 0 или 1, при этом значение

r,, =1 указывает íà j-тое направление, совпадающее с направлением кратчайшего пути из данного устройства в

j òîå устройство. Если 1-й рельеф не сформирован, то в соответствующих

j-x строках блоков 5 и 6 записаны нули. Задача этапа формирования рельефа заключается в том, чтобы записать в блок 7 информацию, соответствующую высотам формируемого рельефа, а в блок

5 памяти — информацию о кратчайших путях.

Единичный рельеф иэ регистра 28 по выходу 32 поступает на информационный вход демультиплексора 21. На первый управляющий вход демультиплексора 2f поступает единичный потенциал через элемент ИЛИ 18 с выхода элемента И

20. Лемультиплексор 21 по первому управляющему входу подключает единичный рельеф через блок 22 на вход 33 регистра 29 вывода. Единичный рельеф поступает из регистра 29 по выходам

31 на информационный вход демультиплексора 4. Выходные направления ком- 45 мутации демультиплексора 4 определяются нулевыми выходами триггеров i-й строки блока 5 памяти оптимальных маршрутов. В данном случае в i-й строке записаны нули и единичный рельеф с выхода блока 1 ввода-вывода транслируется по всем п-1 направлениям.

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

Сообщение "Формирование рельефа" 55 поступает в транзитный узел по входу

24, обрабатывается, как и в узле— источнике сообщения. Отличие заключи46 4 ется в том, что информационная часть сообщения переключается демультиплексором 21 на erî второй выход, поступает на информационный вход блока

7 памяти рельефов и записывается в

j-й столбец i-й строки. В этом случае демультиплексор 21 управляется единичным потенциалом, поступающим по второму его входу с выхода элемента

И 19, при этом единичный признак транзитного узла формируется на выходе элемента HE 17. После того, как в j-й столбец записался поступивший по j-му направлению рельеф целиком, считывается i-я строка блока ? и поступает на блок 6 сравнения.

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

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

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

Сообщение поступает но входу 24 (К=1, ..., II) в устройство. Служебная кодовая часть этого сообщения из регистра 28 ввода поступает по выходу

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

На второй вход элемента И 14 поступает единичный потенциал с второго выхода дешифратора 16 кода режима, и на выходе элемента И 14 формируется

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

Ствии с управляющей информацией, хра.— нящейся в блоке 5 памяти оптимальных маршрутов.

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

Определяется единичным состоянием i-й строки блока 5, здесь i — адрес узла

Назначения, передаваемый в составе

Сообщения. Этот адрес, как и в режиме ормирования рельефа, поступает на дешифратор 9 и разрешает доступ в соответствующие сроки блоков 5 и 7. В данном случае блок 7 не работает, так

Как на втором управляющем выходе блоКа 8 управления установлен нулевой

Ф

1 отенциал, Сообщение коммутируется цо выбранному направлению и через соОтветствующий блок буферных регистров транслируется в смежный узел по направлению кратчайшего пути.

3254á го по (n-1)-й разрядов адреса демультиплексора, входы установки в "О" блоков памяти рельефов и оптимальных маршрутов соединены с входом начальной установки устройства, выход поля адреса блока ввода-вывода соединен с входом дешифратора адреса, с первого по ш-й выходы которого (m — количество устройств в реализуемой сети передачи данных) соединены с первого по

m-й входами адреса рельефа блоков па15

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

1. Устройство маршрутизации, содержащее мультиплексор, демультинлексор, демультиплексор данных, блок элементов ИЛИ, сумматор единицы, блок ввода-вывода, блок управления, блок памяти рельефов„ блок сравнения, блок памяти оптимальных маршрутов и дешифратор адреса, информационные входы мультиплексора являются одноименными входами устройства, выход мультиплексора соединен с входом сообщения блока ввода-вывода, выход сообщения которого соединен с информационным входом демультиплексора, выходы которого являются выходами устройства, с пер-. вого по (n-1)-й выходы опроса блока управления (и — количество направлений связи) соединены с первого по (и-1)-й входами адреса мультиплексора и входами адреса направления связи блока памяти рельефов, и-й выход опроса блока управления соединен с и-м входом адреса мультиплексора„ выходы блока памяти рельефов соединены с информационными входами блока сравнения, выходы которого соединены с входами адреса направления связи блока памяти оптимальных маршрутов, выходы которого соединены с входами с первоонным входом демультиплексора данных соответственно, второй выход которого соединен с информационным входом блока памяти рельефов, второй и третий выходы режима блдка управления соединены с первым и вторым управляющими входами демультиплексора данных соответственно, о т л и ч а ю щ е— е с я тем, что, с целью сокращения аппаратурных затрат, в него введены схема сравнения адреса, первый и второй информационные входы которой соединены с выходом поля адреса блока ввода-вывода и с адресным входом устройства соответственно, вход строба выдачи схемы сравнения адреса соединен с четвертым выходом режима блока управления, прямой и инверсный выходы признака равенства схемы сравнения адреса соединены с входом и-го разряда адреса демультиплексора и входом разрешения выдачи блока памяти оптимальных маршрутов, 2 ° YCTPOHCTBO IIO II 1, O T JI H ч а ю щ е е с я тем, что блок управ-. ления содержит генератор сканирования, дешифратор кода режима, два элемента И, элемент НК и элемент ИЛИ, с первого по и-й выходы генератора сканирования являются с первого по и-й выходами опроса блока, вход ко7 14325 манды которого соединен с входом дешифратора кода режима, первый выход которого соединен с первыми входами первого и второго элементов И и является первым выходом режима блока, 5 второй выход дешифратора кода режима соединен с первым входом элемента

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

НЕ с вторым входом второго элемента

И, выход первого элемента И соединен с вторым входом элемента ИЛИ, выход которого и выход второго элемента И являются вторым и третъим выходами режима блока.

46 8

3. Устройство по п.1, о т л и " ч а ю щ е е с я тем, что схема сравнения адреса содержит схему сравнения, два элемента И и элемент НЕ, первый и второй информационные входы схемы сравнения являются одноименными входами схемы сравнения адреса, прямой и инверсный выходы признака равенства которой соединены с выхоI дами первого и второго элементов И соответственно, первые входы которых соединены с входом строба выдачи схемы сравнения адреса, выход схемы сравнения соединен с вторым входом первого элемента И и через элемент

НЕ с вторым входом второго эле-, мента И.

Фиг.2

1432546

Составитель А.Ушаков

Техред А.Кравчук Корректор С.Черни

Редактор О.Юрковецкая

Заказ 5443/43

Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4