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

 

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

„SU„„1037269

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

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

РЕСПУВЛИН цц G 06 F 15/20

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3443828/18-24 (22) 28.05 ° 82 (46) 23,08.83. Бюл. 1г 31 (72) А.B,Ãoðíîñòàé, В .С .Любинский и B.11.ÑèHÿ8èH (53) 68 1.325.22(088 .8) (56) 1. Авторское свидетельство СССР

N 838701, кл. G 06 F 15/20, 1978.

2. Авторское свидетельство СССР по заявке N 3241464/18-24 кл. С 06 F 15/20, 1980 (прототип), (54)(57) 1. ВЦЧИСЛИТЕЛ6НОЕ УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ МАРШРУТА СООБ"

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

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

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

° ми блоков сравнения группы, первая группа информационных входов второго коммутатора является второй группой входов устройства, вторая группа информационных входов соединена с группой выходов счетчика, управляющий вход блока управления является управляющим входом устройст" ва.

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

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

10 37269 задержки, к второму входу триггера и к пятому выходу блока, выходы второго и третьего элементов задержки являются соответственно третьим и четвертым выходами блока, выход первого элемента задержки является шестым выходом блока, выход четвертого элемента задержки соединен с вторыми входами первого и второго элементов И.

30!

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

Известно устройство, содержащее генератор тактовых импульсов, счетчики, два регистра кода адреса, эле" менты И и ИЛИ, регистр числа узлов сети, блок сравнения, регистр кода отказавшегося узла, элемент НЕ, регистр порядка перечисления узла сети, два циклических регистра сдвига 1), 15

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

Наиболее близким к изобретению по технической сущности является уст- ройство, содержащее блок управления, генератор тактовых импульсов, счет" чик, группу элементов И, группу блоков сравнения, первый коммутатор, группу регистров адресов соседних узлов, выходы которых являются выходом устройства, информационный вход каждого регистра группы подклю" чен к выходу соответствующего элемента И группы, информационные входы всех элементов И группы объединены и подключены к группе входов блока управления, выходам счетчика, тактовый вход которого соединен с выходом генератора тактовых импульсов „ первый и второй выходы блока управления подключены к управляющим входам

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

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

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

3 10372 ющего элемента И группы, информационные входы элементов И группы подключены к группе входов блока управления и к группе выходов счетчика, так" товый вход которого соединен с выходом генератора тактовых импульсов, первый и второй выходы блока управления подключены к управляющим вхо.дам генератора тактовых импульсов и счетчика соответственно, третий 10 выход бдока управления подключен к управляющему входу первого ком. мутатора, первая группа информационных входов которого является первой группой входов устройства, вторая

rpynna »»нформационных входов первого коммутатора соединена с группой выходов счетчика, каждый выход группы выходов первого коммутатора подключен к первому входу соответству= ющего блока сравнения группы, второй и третий входы каждого »»лока сравнения группы. подключены соответственно к четвертому и пятому выходам блока управления, первый и второй выходы каждого блока сравнения группы подключены -к управляющим входам соответствующих элементов И и регистров адресов, введен второй коммутатор, управляющий вход которого соединен с шестым выходом блока управления, выход второго коммутатора соединен с четвертыми входа" ми блоков сравнения группы, первая группа информационных входов второго. коммутатора является второй группой входов устройства, вторая груп. па информационных входов соединена с группой выходов счетчика, управляющий вход блока управления является управляющим входом устройства.

Кроме того, в вычислительном устройстве блок управления содержит элемент И, ИЛИ, НЕ формирователь прямоугольных импульсов, триггер, элементы задержки и дешифратор, rpynna входов которого является группой входов блока управления, выходы дешифратора, начиная с первого, подключеиы соответственно к входам пер" вого элемента ИЛИ, первый выход дешифратора соединен с первым входом первого элемента И и с входом элемента НЕ, выход которого соединен с первым входом второго элемента И. выход которого подключен к первому входу второго элемента ИЛИ, второй вход которого является управляющим входом блока, а выход подключен к первому входу .триггера, выхдд триггера является первым выходом блока, выход первого элемента И является вторым выходом блока, выход первого .элемента ИЛИ через формирователь прямоугольных импульсов подключен к входу первого из четырех последовательно соединенных элементов задержки, к второму входу .триггера и к пятому выходу блока, выходы второ-. го и третьего элементов задержки являются соответственно третьим и четвертым выходами блока, выход первого элемента задержки является шестым выходом блока, выход четвертого элемента задержки соединен с вторыми входами пеового и второго элементов И, На фиг. 1 представлена схема устройства;. на фиг. 2 - схема блока сравнения; на фиг. 3 - схема блока управления; на фиг. 4 - схема первого коммутатора; на фиг, 5 - схема второго коммутатора; на фиг..6 - пример, поясняющий процедуру выбора маршрута передачи, Устройство содержит группу регистров 1 адресов, группу элементов И 2, группу блоков 3 сравнения, генератор 4 тактовых импульсов, счетчик 5, блок 6 управления, коммутаторы 7 и .

8, шины 9-22 связи, группу элементов И 23, элемент 24 задержки, регистр 25 минимальных задержек, схему 26 сравнения, накапливающий сумматор 27, дешифратор 28, элемент

И 29, элемент ИЛИ 30, элемент НЕ 31, элемент И 32, элемент ИЛИ 33, триггер 34, формирователь 35 прямоуголь" ных импульсов; элементы 36-39 задержки, дешифратор 40, группу элементов ИЛИ 41, группу элементов.И 42, группу буферных регистров 43, груп-. па элементов ИЛИ 44, дешифратор 45, rpynny элементов И 46, входные .регистры 47.

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

Исходное состояние регистров группы 1 и счетчика 5 - нулевое. Запуск устройства осуществляется пода@ей на (входную) шину 22 импульса после приема по шикам 10 информации о задержках от соседних узлов в буферные регистры коммутатора 7. Нв выходной шине 13 блока 6 управления появляется высокий потенциал, при этом запускается генератор 4 тактовых им-. пульсов. Тактовые импульсы с генера-. тора поступают на счетчик 5. При совпадении кода на счетчике с кодом адреса соседнего узла генератор 4 тактовых импульсов отключается и в блоке 6 управления вырабатывается . послсдовательность управляющих импульсон. Первый импульс появляется на шине 14 и устанавливает выходные регистры накапливающих сумматоров бл ков 3 сравнения в нулевое состояние.

По второму импульсу (шина 15) в данные накапливающие сумматоры через коммутатор 8 поступает код задержки, равный времени передачи сообщения на данный соседний узел и времени ожидания в .очереди. Длительность ожидания в очереди определяется временем передачи сообщений, стоящих н выходной очереди узла к данному соседнему узлу. Эта задержка периодически обновляется и хра" нится во входных регистрах коммутатора 8.

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

По четвертому импульсу (шина 16) происходит сравнение принятых суммарных задержек с задержками, находящимися в регистрах минимальных задержек блоков сравнения. 8 тех блоках сравнения, где задержка меньше, осуществляется ее перезапись в регистр минимальных задержек и вырабатываются импульсы сброса (шины 20) устанавливающие соответствующие регистры группы 1 в нулевое состояние, и импульсы записи (шины 19) поступающие на элементы И группы 2 и разрешающие запись кода адреса соседнего узла со счетчика 5 в соответствующие регистры группы 1.

После этого на шине 13 в блоке

6 управления появляется высокий потенциал и запускается генератор 4 тактовых импульсов.

При совпадении кода адреса следующего соседнего узла с кодом на счет чике 5 вновь отключается генератор

4, в блоке 6 управления вырабатываются импульсы управления, в блоках 3 сравнения происходит сравнение задержек и в соответствующие регистры 1 записывается код адреса очередного соседнего узла, суммарная задержка прохождения сообщения через адресу соседнего узла, на одном из выходов появляется разрешающий .потенциал, который через элемент ИЛИ 30 поступает на формирователь 35 прямоугольных импульсов. На выходе фор" мирователя 35 появляется импульс, который поступает на вход триггера 34 и переводит его в нулевое

-состояние, запрещая прохождение

30 тактовых импульсов на счетчик 5.

Этот же импульс поступает на выходную шину 14 и через элементы 36-38 задержки - на шины 15- 17. С выхода элемента 39 задержки импульс поступает на элемент И 32 и, если код адреса соседнего узла не является адресом последнего соседнего узла (низкий потенциал на последнем выходе дешифратора 28), переводит

40 триггер 34 в единичное состояние, на шине 13 вновь формируется высокий потенциал, разрешающий npoxowдение тактовых импульсов на счетчик 5, Если код адреса является адресом последнего соседнего узла, то высокий потенциал с последнего выхода дешифратора разрешает прохождение импульса управления через элемент

И 29 на сброс счетчика 5 и запрещает установку триггера 34 в единичное состояние.

Следующий циКл работы устройства начинается после приема новой ин формации о задержках от соседних

55 узлов по шинам 10 в буферные регистры коммутатора 7. При этом триггер

34 переводится в единичное состояние импульсом, поступающим на его (037269 Ь который для данного узла назначения меньше.

Таким образом, в регистрах 1 формируется таблица маршрутов. Цикл формирования продолжается до тех пор, пока на выходах счетчика не будет код адреса последнего соседнего узла. После этого счетчик 5 обнуляется.

10 Блок 6 управления работает следующим образом. На вход дешифратора

28 поступает двоичное число с выходов счетчика 5, Используются только те выходы дешифратора, которые соответствуют номерам соседних узлов для данного узла сети, Остальные выходы дешифратора 28 с выходами элемента

ИЛИ 30 не соединяются.

При наличии на входе дешифратора а двоичного числа, соответствующего

69 8 с минимальными задержками, рассмотрим процедуру выбора маршрута для гипотетической цифровой сети (фиг.6).

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

«еееее еЕееее

3 е

10 8 .6

4 1О 8

7 12 5 8 е ее Ве е е

35 Ао этой. таблице выбирается таком маршрут, для которого задержка

; минимальна,.и составляется таблица маршрутов узла е е

М сосед. узла

И узла назнач.

Задержка

Алгоритм формирования таблицы маршрутов в предлагаемом устройстве поясняет следующая таблица.

7 10372 единичный вход через элемент ИЛИ 33 по шине 22.

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

Исходное состояние регистра 25 5 перед началом работЪ устройства - еди- . ничное. Импульсом, поступающим из блока управления по шине 14, устанавливаются в нулевое состояние реги-. стры накапливающего сумматора 27. Ин- 10 формация о задержках поступает на иакапливааций сумматор 27 по шинам

18 и 21. После сложения задержек по импульсу, поступающему по шине 16, происходит сравнение числа А в выход- 15 ном регистре накапливающего сумматора 27 с числом в регистре 25. Так как для данного такта А 4 В (число Bвсе единицы),то на выходе схемы 26, сравнения появляется импульс, кото- 20 рый обнуляет регистр 25 и, пройдя через элемент 24 задержки, разрешает перезапись содержимого выходного регистра накапливающего сумматора в регистр 25.,25

В последующие такты работы устройства происходит сравнение числа В в регистре 25 с числом А - суммарной задержкой от следующего соседнего уз- . ,ла. Перезапись содержимого выходного ЗО регистра накапливающегося сумматора

27 в регистр минимальных эадерже)с

25 происходит только при выполнении условия А 4 В.

Коммутатор 7 работает следующим образом.

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

И 42 данного соседнего узла. По сигналу .управления на шине 17 коды за- 1 держек из группы регистров 43 чер-.-.з группы элементов И 42 и элементов 2 или 41 поступают на шины 2).

Коммутатор 8 работает аналогич- . 3 ным образом. При наличии на входе дешифратора 45 кода адреса сосед- 4 . него узла и управляющего сигнала на шине 15 код задержки, равный вре- 5 мени передачи сообщения и времени ожидания в очереди, из соответству- 6 ющего регистра 47 через группу элементов И 46 и группу элементов ИЛИ 44 7 поступает на выходную шину 18 ком" .

55 мутатора.

В качестве примера, поясняющего процедуру выбора маршрута передачи

6 2 .3 4

1037269

Регистры

27

0001 0010 1010

1111 1111 1111

010 010 010

0101 0001 1000

010

27

0001 0010,1010

010 011 011

011

1000 0100 1000

9100 0010 0101

010 010 011

27

0011 0010 0110

0001 0001 1000

010 011 100

100 вторяется для всех соседних уэлрв.

После опроса и анализа задержек от последнего соседнего узла в регистрах 1 будет сформирована таблица маршрутов.

Допустим, нужно передать сообщение из узла И 1 в узел У 6. Сообщение будет передано через узел Н 2, хотя кратчайший маршрут проходит через узел N 4.

Устройство позволяет вычислять код маршрута движения сообщения -в цифровой сети связи с минимальной

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

При совпадении кода адреса соседнего узла с кодом на счетчике 5 задержки от данного соседнего узла для всех узлов назначения поступают из коммутаторов 7 и 8 в накапливающий сумматор 27 блока 3 сравнения, Суммарная задержка сравнивается с содержимым регистром 25, которые в исходном состоянии находятся в единичном состоянии. Так как числа на выходах сумматора 27 меньше или равны числам в регистрах 25 (максимальная задержка), то в регистры 1 заносится код адреса данного соседнего узла, а в регистры 25 переписывается суммарная задержка с выхода сумматора. Цикл по0100 0010 1!00

1111 1111 1111

010 010 010

1010 0011 0101

0100 0010 1100

010 010 011

)037269

3037269

1037269

3037269

1037269

Составитель А.Жеренов

Редактор О.Половка Техред И.Метелева

Корректор, Д. Бокаан филиал Allll "Патент", г. Ужгород, ул, Проектная, 4

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

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

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