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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 22.12.80 (21) 3241464/18-24 }j1} М. Кд.з

G 06 F 15/20 с присоединением заявки №(23) Приоритет—

Государственный комитет

СССР яо делам изобретений и открытий

53} УДК 681. 325 (088. 8) Опубликовано 30.0982. Бюллетень ¹ 36

Дата опубликования описания 300Я82

A.В,Горностай, В.С.Любинский и В.П.Синяви (72) Авторы изобретения (71) Заявитель (54) В ЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ЛЯ ФОРМИРОВАНИЯ

МАРШРУТА СООБЩЕНИЯ

Изобретение относится к сбору и обработке данных, в частности к устройствам коммутации сообщений и пакетов в сетях ЭВМ. 5

Известны устройства для Формирования кода маршрута в цифровой сети связи с использованием мини-ЭВМ $1).

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

И, группу регистров адресов соседних узлов, счетчик, вход которого соединен с выходом генератора тактовых импульсов, а его выходы — с первыми входами элементов И группы, выходы которых соединены с пряьыми входами регистров группы (2 j.

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

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

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

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

Блок управления содержит дешиф= ратор, элемент ИЛИ, формирователь импульсов, три элемента задержки, 15 два элемента И, элемент НЕ и триггер, выход которого соединен c первым выходом блока, вход сброса триг. гера соединен с выходом формирователя импульсов, пятым выходом блока и входом первого элемента задержки, выход которого соединен с третьим выходом блока и входом второго элемента задержки, выход которого соединен с четвертым выходом блока и вхьдом третьего элемента задержки, выход которого подключен к первым входам первого и второго элементов И, выход второго элемента И подключен к входу установки триггера, а второй вход — .к выходу элемента НЕ, вход которого соединен с вторым входом первого элемента И и выходом младшего разряда дешифратора, выходы которого подключены к входам элемента ИЛИ,.выход которого соеди- 35 нен с входом формирователя импульсов, вход дешифратора соединен с входом блока, выход перного элемента И соединен с вторым выходом блока.

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

Устройство содержит группу регистров 1 адресов соседних узлов (группа регистров таблицы маршрутов), группу элементов И 2, группу блоков

3 сравнения, генератор 4,тактовых импульсов, счетчик 5, блок 6 управления, коммутатор 7, входные и выходные шины 8-17.

Количество регистров группы регистров 1, элементов И группы 2 и блоков 3 сравнения группы равно количеству узлов назначения в сети для данного узла. В состан блока сравнения входят группа элементов И 18, элемент 19 задержки, регистры 20 минималных задержек, схемы 21 сравне- 60 ния и приемный регистр 22. Блок управления содержит дешифратор 23, элемент И 24, элемент ИЛИ 25, триггер

26, элемент Й 27, элемент HE 28, формирователь импульсов 29, элементы

30-32 задержки . Коммутатор 7 содержит дешифратор 33, группу элементов ИЛИ

34, группу элементов И 35, группу буферных регистров 36 приема.

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

Исходное состояние группы регистров 1 и счетчика 5 — нулевое. При запуске генератора 4 импульсы поступают на счетчик 5. Если код на счетчике совпадает с кодом адреса соседнего узла, то генератор отключается и в блоке 6 управления вырабатывается последовательность управляющих импульсов. Импульсы выполняют следующие функции: первый импульс появляется на выходе 10 и устанавливдет приемные регистры блоков сравнения в нулевое состояние; второй импульс (выход 12) поступает в ком.мутатор 7 и разрешает запись информации о задержках для каждого из узлов назначения. Эта информация поступает путем периодического опроса от соседнего узла и хранится н коммутаторе 7. Код адреса очередного соседнего узла находится в счетчике

5. По третьему импульсу (выход 11) происходит сравнение принятых задержек с задержками, находящимися в регистрах минимальных задержек блоков сравнения. В тех блоках сравнения, где задержка меньше, осуществляется ее перезапись в регистр минимальных задержек и вырабатываются импульсы сброса (выход 17), устанавливающие соответствующие регистры

1 группы в нулевое состояние, и импульсы записи (выход 16), по которым происходит запись кода адреса соседнего узла со,начетчика 5 — в регистры

1 блока.

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

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

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

96296 7 формирователь импульса 29, на выходе которого появляется импульс, поступающий. на вход триггера 26 и переводящий его в нулевое состояние. Этот же импульс, пройдя через элементы

30-32 задержки, поступает на элемент

И 27 и,если код на входе дешифратора не является кодом адреса последнего соседнего узла, приводит тоиггер 26

s единичное состояние. В противном случае импульс с элемента 32 задержки через элемент И 24 поступает на выход 8.

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

Исходное состояние регистра 22 единичное. Импульсом сброса (вход 13) регистр 22 устанавливается в нулевое состояние. Запись информации о задержках осуществляется параллельным кодом (входы 15) . По импульсу управления (вход 14) из блока управления происходит сравнение числа A в регистре 22 с числом В в регистре 20. ,Если A c В, то на выходе схемы сравнения 21 появляется импульс, который обнуляет регистр 20„и, пройдя через элемент 19 задержки, разреша- . ет перезапись содержимоro регистра .-22 в регистр 20.

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

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

По сигналу управления на шине 12 осуществляется перезапись кодов задержек из группы регистров 36 приема в регистры блоков 3 сравнения через группы элементов И 35 и элементов ИЛИ 34.

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

Формула изобретения

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

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

;щ группы, второй и третий входы каждого блока сравнения группы объединены и подключены к четвертому и пятому выходам блока управления, первый и второй выходы каждого блока срав2 нения группы подключены к управляющим входам соответствующих элементов

И и регистров адресов соседних узлов.

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

45 элемента H подключен к входу установки триггера, а второй вход — к выходу элемента НЕ, вход которого соединен с вторым входом первого элемента И и выходом младшего раз5О ряда дешифратора, выходы которого подключены к входам элемента ИЛИ, выход которого соединен с входом формирователя импульсов, вход дешифратора соединен с входом блока, у выход первого элемента И соединен с вторым выходом блока.

Источники информации, принятые во внимание при экспертизе

1 ° Клейнрок Л. Вычислительные системы с очередями. M. "Мир", 1979, с.470-473.

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

Р 547770, кл.G 06 F 15/20, 1977 (прототип).

962967

Составитель П. Чистобородов

Редактор Т.Лопатина Техред М.Тепер Корректор E.Poøêo

Заказ 7515/70 Тираж 731 Подписное

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

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

Филиал ППП "Патент", r.Óæãîðîä, ул.Проектная,4