Вычислительное устройство для формирования маршрута сообщения

 

ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ МАРШРУТА СООБЩЕНИЯ , содержащее генератор тактовых импульсов, группы элементов И, блок буферных регистров и коммутатор, группа информационных входов которого является группой информационных входов устройства, отличающееся тем, что, с целью повышения быстродействия и сокращения оборудования , оно содержит-регистр вводд и блок сравнения п двоичных чисел, ин формационные входы которого соединены соответственно с выходами ком.мутатора , тактовый и управляющий входы подключены соответственно к выходу генератора тактовых импульсов и к входу установки исходного состояния устройства., выходы блока сравнения п двоичных чисел соединены соответственно с первыми входами элементрв И группу вторые входы которых подключены к информационному выходу регистра ввода, адресный выход которого соединен с адресным входом ком- i мутатора, выходы групп элементов И соединенц соответственно с входами блока буферных регистров, выходы .которого являются выходами устройства , вход регистра ввода является информационным входом устройства.

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

РОЗ сс

РЕСПУБЛИК (19l (И) А

3c59G 06F 1 2 с,. 1 с

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ":: -:::::-. -- :,. -, Н А870РСНОМУ СВИДЕТЕЛЬСТВУ е. (54) (57) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО

ДЛЯ ФОРМИРОВАНИЯ МАРШРУТА СООБЩЕНИЯ, содержащее генератор тактовых импульсов, группы элементов И, блок буферных регистров и коммутатор, rpynna информационных входов которо- . го является группой информационных . входов устройства, о т л и ч à ющ е е с я тем, что, с целью повыше" (21) 3470757/18-24 (22) 15,07.82 (46) 23. 10.83. Бюл. 1 39 (72) В. С. Любинский и В. П. Синявин

I (53) 681 325.22(088.8) (56) 1. Клейнрок Л. Вычислительные системы с очередями. М., "Мир !,1979 с. 470-473.

2. Авторское свидетельство СССР по заявке М 3241464/18-24 кл. G 06 F 15/20, 1980 (прототип). ния быстродействия и сокращения оборудования, оно содержит регистр ввода и блок сравнения и двоичных чисвп, информационные входы которого соединены соответственно с выходами ком« мутатора, тактовый и управляющий входы подключены соответственно к выходу генератора тактовых импульсов и к входу установки исходного состояния устройства., выходы блока сравнения и двоичных чисел соединены соответственно с первыми входами элементрв И rpynn вторые входы которых подключены к информационному выходу регистра ввода, адресный выход которого соединен с адресным входом ком- д мутатора, выходы групп элементов И ® соединены соответственно с входами блока буферных регистров, выходы ,которого являются выходами устройства, вход регистра ввода является информационным входом устройства. 2

1 1049

Изобретение относится к вычислительной технике и предназначено для применения в устройствах коммутации сообщений и пакетов в сетях электронных вычислительных машин (ЗВИ).

Известно устройство для формиро вания кода маршрута в цифровой сети связи, включающее мини-ЗВИ (1) .

Недостатками устройства являются высокая стоимост,ь, сложность и 10 сравнительно низкая надежность.

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

Недостатками известного устройства являются сравнительно высокие аппаратурные затраты на его реализацию и низкое быстродействие, обусловленное необходимостью формирования таблицы .З0 маршрутов.

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

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

Поставленная цель достигается тем, 45 что вычислительное устройство, содержащее генератор тактовых импульсов, группы элементов И, блок буферных регистров и коммутатор, группа информационных входов которого является груп50 пой информационных входов устройства, содержит регистр ввода и блок сравнения и двоичных чисел, информационные входы которого соединены соответственно с выходами коммутатора, такто- 5 вый и управляющий входы подключены соответственно к. выходу генератора тактовых. импульсов и к входу установки ис917 2 ходного состояния устройства., выходы блока сравнения и двоичных чисел соединены соответственно с первыми входами элементов И групп, вторые входы которых подключены к информационному выходу регистра ввода, адресный выход которого соединен с адресным входом коммутатора, выходы групп элементов И соединены соответственно с входами блока буферных регистров, выходй которого являются выходами устройства, вход регистра ввода является информационным входом устройства.

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

Устройство содержит регистр 1 вво да, блок 2 буферных регистров, группы элементов И 3, блок 4 сравнения и двоичных чисел, коммутатор 5, генератор 6 тактовых импульсов, информационный вход 7 устройства, вход 8 установки исходного состояния устройства, выходы 9 устройства, группу информационных входов 10 устройства, входы-выходы 11-14 блоков устройства, регистры 154, 15,...,15ь, сдвигающий регистр 16, регистр 17 результата, элементы И 18,182,...,18п,weменты ИЛИ 194, 19,..., 19п, элемент 20 задержки, накапливающий сумматор 21, триггер 22 знака, элементы И 23, 244,242,..., 24п, группы элементов И 254, 25,.. .25п, 26,1, 26, ..., 26 ), элементы И 27у, 272, : ° ° 27л- 28<, 282, ., 28и-» менты 29 и 30 задержки, элемент ИЛИ 31, элемент 32 задержки, счетчик 33, триггер 34 управления, элемент И 35,дешифратор 36, группы регистров 37,37, .;.,37щ задержек, группы элементов

И 384, 382, °, 38, группы элементов ИЛИ 39. !

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

Сообщение по входу 7 поступает в регистр 1, Одновременно с этим на вход 8 подается управляющий импульс, готовящий блок 4 к работе. Адрес узла назначения принятого сообщения поступает в коммутатор 5. Во входных регистрах коммутатора 5 хранятся вепичины задержек по всем возможнь1м маршрутам для сообщения с произвольным адресом. Эти задержки пе917. 4

Если второе двоичное число окажется -больше или равно первому числу, то единица из сдвигающего регистра 16 в регистр 17 результата не перезапишется.

Тактовый импульс после окончания сравнения поступает также через элемент 30 задержки на шину сдвига сдвигающего регистра 16, обеспечивая сдвиг единицы на один разряд, и через элемент HJlH 31 на вход сброса накапливающего сумматора 21, который устанавливается в нулевое состояние.

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

21 записывается наименьшее число в прямом коде, выбранное в предыдущих тактах. Номер этого числа определяется положением единицы в регистре 17.

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

17 результата устанавливаются в нулевое состояние сигналом, поступающим . через элементы ИЛИ 19 на нулевые входы этих триггеров.

3 1049 риодически обновляются вутем опроса соседних узлов (входы 10). На .выходах коммутатора 5 появляются величины задержек flo всем, возможным маршрутам следования для сообщения с за.двнным адресом. Эти задержки поступают на блок 4. После сравнения задержек на одном иэ выходов блока 4 появляется импульс, который, поступая на одну из групп элементов И 3, раз- 10 решает прохождение сообщения из регистра i в буферный регистр, откуда .оно передается на соседний узел.Следуя через выбранный соседний узел к узлу назначения; сообщение име- . 1 ет минимальную задержку в пути.

Блок сравнения работает следующим образом.

Исходное состояние устанавливает- . ся путем подачи на вход 8 установоч- 20 ного. импульса, по которому в единичное состояние устанавливаются триггеры младших разрядов сдвигающего регистра 16, регистра 17 результата и триггер 34 управления. Счетчик 33 25 и накапливающий сумматор 21 с триггером 22 знака устанавливаются в нуле- вое состояние.

Первый тактовый импульс через элемент И 35, открытый единичным потен- зп циалом с триггера управления, и эле-. мент И 24», который открыт единичным потенциалом с триггера младшего разряда регистра 17 результата, подается на входы группы элементов И 25 . Пер- 3 вое число s прямом коде из регистра

l5 записывается в накапливающий сум4 матор 2!.,Этот же импульс, задержан- ный элементом 20 задержки, подается на элементы И 271 27 ° ° 27я » Еди- 40 ничным потенциалом с триггера младшего разряда сдвигающего регистра 16 элемент И 27» открывается, сигнал с его выхода поступает на входы группы элементов И 26», и второе число из 4> регистра 15 записывается в накапливающий сумматор 21 в обратном коде

Если второе двоичное число ока-. жется меньше первого числа, то триггер 22 знака - в нулевом состоянии, ° поэтому тактовый импульс, задержанный элементами 20 и 29 на время выполне ния суммирования, поступает через элементы И 23 и 28 на триггер регистра 17 результата, и единичное значение из сдвигающего регистра 16 перезаписывается в соответствующий триггер регистра 17 результата.

После подачи всех тактовых импульсов цикл сравнения чисел заканчивается. В результате один из триггеров регистра 17 результата находится в единичном состоянии, ° номер этого триггера соответствует номеру регистра, в котором записано минимальное число. После поступления последнего тактового импульса на выходе счетчика 33 появляется импульс, который переводит триггер управления в нулевое состояние,- запрещая прохождение тактовых импульсов через элемент

И 35, и через один из открытых элементов И 18 поступает на выход блока 4.

Коммутатор работает следующим оораэом. Двоичные числа задержек от соседних узлов для всех узлов назначения поступают на группы регистров 37»,37д,...,37 я по входам 10 путем периодического опроса этих узлов (tA - число узлов назначения).

10499

5

При наличии на входе 14 адреса узла назначения на одном иэ выходов дешифратора 36 появляется высокий потенциал, и информация о задержках для. данного узла назначения через группы элементов И 38 и группы эле ментов ИЛИ 39 передается на выход 9

В.качестве примера, поясняющего. процедуру выбора маршрута передачи с минимальными задержками, рас- 10 смотрим процедуру выбора маршрута для гипотетической цифровой сети, представленной на фиг.4.

Для выбора маршрута с минимальной задержкой на узле-отправителе 15 необходимо иметь информацию о задержках от соседних узлов. Для этого формируется таблица задержек узла °

После опроса всех соседних узлов таблица хранится в регистрах 37 комму- 20 татора 5.

Допустим, что нужно передать сообщение иэ узла l в узел Ч1. Для этого на дешифратор 36 подается код адреса узла Vl и двоичные числа задержек 0010, 0011, 0100 поступают на блок 4 ° После сравнения чисел появляется импульс на выходе, соответствующем соседнему узлу fl,è сообщение передается в указанный узел,з0 где вновь определяется маршрут с минимальной задержкой, и т.д.

В данном примере для передачи сообщения иэ узла 1 в узел Vl маршрут с минимальной задержкой прохо- 35 дит через узел Il, хотя кратчайший маршрут - через узел 1V.

Предлагаемое устройство позволяет

l снизить аппаратурные затраты и повысить быстродействие при решении за17 дачи вычисления маршрута с минимальб ной задержкой в пути.

В известном устройстве формировение маршрута кратчайшего пути в цифровой сети связи осуществляется на основе данных, хранимых в регистрах в виде таблицы маршрутов. Таблица маршрутов имеет (й-1) строк, где Nобщее число узлов в цифровой сети связи. Число групп элементов И и блоков сравнения также равно числу узлов назначения в сети.

В.предлагаемом устройстве вместо группы блоков сравнения, содержащей (N- 1) блоков, используется один блок сравнения и двоичных чисел, где

n - число соседних узлов.

Число буферных регистров и групп элементов И равно не (N-l), как в известном устройстве, а и. Так как в любой цифровой сети связи (N-1) > n, то изобретение обеспечивает сокращение объема оборудования при решении такого же объема задач, как и в известном устройстве.

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

-1049917

10499 17 i

1049917

1049917

Составитель В. Вертлиб

Редактор О.Бугир Техред А.Бабинец Корректор А.Повх

»««»«»»»»»»«»»»«««»»»»« » »«

Заказ 8427/46 Тираж 706 Подписное

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

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

««»«««»»»»»»«»«»»«»»«»»»«««»«»»««»»»«»«»«»««»«»»««»«««»»»

» ««»»«»»

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4