Устройство для формирования маршрута сообщения

 

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

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

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

РЕСПУБЛИН (1) 4 G 06 F 15/20

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

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

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

IlO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ П1НТ СССР (21) 4377928/24-24 (22) 17.11.88 (46) 07.12.89. Бюл. ¹ 45 (72) В,С, Любинский и В.П. Синявин (53) 681.325(088.8) (56) Авторское свидетельство СССР № 1049917, кл, С 06 F 15/20) 1982.

Авторское свидетельство СССР № 1383385, 10,04.87 (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

МАРШРУТА СООБПЖНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано в цифровых сетях связи, в том числе п сетях ЭВМ> для вычисления оптимальных маршрутов передачи сообщений. Целью изобретения является повышение точности формирования маршрута. Для обеспечения работы устройства требуются минимальный расход

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

Целью изобретения является повышение точности формирования маршрута.

На чертеже представлена блок-схема устройства.

Устройство содержит входной регистр

1, буферный регистр 2, блок 3 групп элементов И> дешифратор 4, схему 5 сравнения, группу 6 элементов И, регистр 7 состояния, группы 8 и 9 элементов И, группу 10 элементов ИЛИ, блок 11 групп элементов И> элемент

ИПИ 12, элемент И 13, сдвиговый ре„„SU„„152 41 А 1

2 пропускной способности каналов связи и незначительные затраты производительности вычислительного устройства на прием служебной информации о текущем состоянии загрузки сети, Существеннь1ми отличительными признаками изобретения в сравнении с известными устройствами является наличие сдвигающего регистра, группы элементов И, ИПИ, элементов задержки, шифратора, триггера управления, новых функциональных связей, которые в совокупности с известными блоками и функциональными связями обеспечивают достижение положительного эффекта, Характерными особенностями предлагаемого устройства являются его высокая экономичность по потреблению сетевых ресурсов и учет полной информации по загрузке всех узлов сети. 1 ил. гистр 14, элементы 15-17 задержки, элемент ИЛИ 18, триггер 19, элемент

И 20, генератор 21 импульсов, блок 22 памяти, выход 23 сообщения устройства, входы 24 состояния узлов устройства информационный вход 25 устройства, выход 26 окончания, вход

27 установки, вход 28 пуска, вход 29 выдачи устройства.

Количество буферных регистров блока 2 и групп элементов И блока 3 соответствует количеству соседних узлов коммутации для данного узла, ЧисЛо разрядов в регистре 7 состояния узлов равно п-1, где n — общее число узлов коммутации в сети передачи данных.

1527641

Число групп элементов И блока 11 равно М, а число разрядов сдвигового регистра 14 составляет M+ 1, где М— число фиксированных маршрутов для

5 каждого адреса узла назначения, Устройство работает следующим образом, Сообщение по входу 25 поступает в регистр 1. Одновременно с ним на вход подается управляющий импульс, переводящий триггер 19 в единичное состояние. Адрес узла назначения принятого сообщения поступает на адресный вход блока 22 памяти. Количество строк равно (n-1) M, a количество столбцов и-1. Для каждого узла назначения определяется М фиксированных маршрутов (M строк), первый из которых является оптимальным, а остальные — субоптимальными.

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

По адресу узла назначения из блока 22 памяти выбираются соответствующие М строк с кодами маршрутов и подаются на блок 11 групп элементов И.

Тактовый импульс через элемент

И 20, поступая на вход регистра 14, перемещает единицу из нулевого разряда в первый разряд, и код первого маршрута через первую группу элементов И блока 11, группу 10 элементов

ИЛИ подается на группу 6 элементов И.

Одновременно с этим с регистра 7

40 состояния на группу 6 элементов И поступает двоичный код (слово состояния сети), характеризующий состояние буферных накопителей узлов сети. Каждый разряд слова состояния сети соответствует узлу коммутации б сети. Если количество сообщений в буферном накопителе узла коммутации меньше установленного порога, то в данном разряде записывается единица, 50 в противном случае — нуль. Слово состояния сети формируется и периодически обновляется с помощью посылки в сеть спе циальных корректирующих сообщений. В регистр

7 слово состояния сети поступает по информационным входам

24.

С выходов элементов И группы 6 двоичный код подается на схему 5 сравнения, где осуществляется проверка на совпадение с кодом маршрута, поступающего через группу 9 элементов И по первому тактовому импульсу, задержанному элементом 17 задержки на время выполнения логических операций.

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

12 и элемент 15 задержки поступает на выход 26, информируя о завершении выбора маршрута, и через элемент ИЛИ

18 устанавливает регистр 1, сдвиговый регистр 14 и триггер 19 в исходное состояние.

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

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

И 13, элемент ИЛИ 12, элемент 15 задержки и элемент ИЛИ 18 устанавливает устройство в исходное состояние.

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

Устройство для формирования маршрута сообщения, co;,åðæàùåå входной регистр, блок памяти, первый и второй блоки групп элементов И, регистр состояния, схему сравнения, генератор импульсов и буферный регистр, причем вход сообщения устройства соединен с информационным входом входного регистра, выход которого соединен с адресным входом блока памяти, 1527641 выходы разрядов К-й группы которого (К=1, 2.. ., М,где M — число фиксиронаннык маршрутов для каждого адреса узла назначения) соединены

5 с первыми входами соответствующих элементов И К-й группы первого блока, выходы разрядон входного регистра соединены с первыми входами соответствующих элементов И каждой группы второго блока, выходы которых подключены к информационным входам соответствующих разрядов одноименной группы буферного регистра, ныход и вход синхронизации которого соединены соответственно с выходом сообщения и тактовым входом выдачи устройства, вход состояния узлов которого соединен с информационным входом регистра состояния, о т л и ч а ю щ е е с я 20 тем, что, с целью повышения точности формирования маршрута, в него введены три группы элементов И, группа элементов ИЛИ, дешифратор, сднигоный регистр, триггер, два элемента И, два 25 элемента ИЛИ и три элемента задержки, причем выходы разрядон сдвигового регистра соединены с вторыми входами элементов И соответствующих групп первого блока, выходы которых соеди- 30 иены с соответствующими входами одноименных элементов ИЛИ группы, выходы которых соединены с первыми входами соответствующих элементов И с первой по третью групп ° выходы Разрядов ре- 35 гистра состояния соединены с нторыми входами соответствующих элементов

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

Составитель А, Зорин

ТехРед Л.Сердюкова КоРРектоР А. ОбРУчаР

Редактор В. Петраш

Заказ 7511/53 Тираж 66В Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101