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

 

Изобретение относится к вычислительной технике и может быть использовано в цифровых сетях связи, в частности в сетях ЭВМ для вычисления оптимальных маршрутов передачи сообщений. Целью изобретения является повышение быстродействия и расширение функциональных возможностей за счет обеспечения числа сообщений в каждом буферном регистре узлов маршрута . Цель достигается за счет того, что в состав устройства введены блок регистров загрузки 19, мультиплексор 5, блок анализа маршрутов 17, блок определения минимального кода 14, преобразователь кодов 15, формирователь импульсов 13, первый 9 и второй 10 элементы НЕ. 5 ил.

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

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

РЕСПУБЛИК (l9) ((1) (я)я G 06 F 15/419

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ Ба

К АВТОРСКОМУ .СВИДЕТЕЛЬСТВУ (21) 4893168/24 (22) 19.12.90 (46) 07.02.93. Бюл. N 5 (71) Московский институт инженеров гражданской авиации (72) С.Ж.Кишенский, Н.С.Вдовиченко, В,Б.Панова и О.Ю.Христенко (56) Авторское свидетельство СССР

N 1383385,кл. G 06 F 15/20, 1986.

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

¹ 1527641, кл, G 06 F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

МАРШРУТА СООБЩЕНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано в цифровых сетях связи, в частности в сетях

ЭВМ для вычисления оптимальных маршрутов передачи сообщений, Целью изобретения является повышение быстродействия и расширение функциональных возможностей за счет обеспечения числа сообщений в каждом буферном регистре узлов маршрута, Цель достигается за счет того, что в состав устройства введены блок регистров загрузки 19, мультиплексор 5, блок анализа маршрутов 17, блок определения минимального кода 14, преобразователь кодов 15, формирователь импульсов 13, первый 9 и второй 10 элементы НЕ. 5 ил.

1793447

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

ЭВМ для вычисления оптимальных маршрутов передачи сообщений.

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

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

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

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

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

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

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

45 сообщений по данному маршруту, то есть— на оптимальность по времени задержки сообщения в узлах данного маршрута.

Целью изобретения является повышение быстродействия и расширение области

50 применения устройства.

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

Л

И И, причем адресный выход входимого сообщения; на фиг. 2 — структурная схема " регистра подключен к адресному входу бло- блока анализа; на фиг.3-структурная схема ка памяти кодов маршрутов, информацион- устройства определения минимального коный выход к второй группе входов первого 5 да: на фиг. 4 — структурная схема ячейки блока элементов И, информационный вход попарного упорядочения кодов, входящей в является информационным входом устрой- состав устройства определения минимальства, группа выходов второго блока элемен- ного кода; на фиг. 5 — структурная схема тов И подключена к первой группе входов преобразователя кодов. блока элементов ИЛИ, отличающееся тем, 10 Устройство для формирования и маршчто, с целью повышения быстродействия и рута сообщений (фиг. 1) содержит входной расширение функциональных возможно- регистр.1, блок 2 буферных регистров, блок стей за счет обеспечения учета числа сооб- 3 элементов И, дешифратор 4, мультиплекщений в каждом буферном регистре узлов сор 5, блок 6 элементов ИЛИ, блоки 7 и 8 маршрута, дополнительно введены блок ре- 15 элементов И, первый 9 и второй 10 элеменгистров загрузки, группы входов которого ты НЕ, элемент 11 задержки, элемент И 12, являются второй группой информационных формирователь 13 импульсов, блок 14 опревходов устройства, мультиплексор, блок деления минимального кода, преобразоваанализа маршрутов, блок определения ми- тель 15 кодов, элемент 16 ИЛИ, блок 17 нимального кода, преобразователь кодов 20 анализа маршрутов, блок 18 памяти кодов формирователь импульсов, выход которого маршрутов регистров загрузки 19, регистр является выходом отказа устройства, пер- 2С состояния. Вход сообщения 21 соединен вый элемент НЕ, вход которого является с информационным входом регистра 1, вход установочным входом устройства. второй запуска 22 соединен с синхровходом блока элемент НЕ, вход которого подключен к 25. 1исвходомблока11. Установочный23вход третьей группе входов первого блока эле- устройства соединен с входом элемента НЕ ментов И и к выходу элемента ИЛИ, а вы- 9, и с первыми входами элементов группы 8. ход — к первому входу элемента И, выход Группы входов 241 — 242 соединены с инфоркоторого подключен к входу формирования мационными входами регистров группы 19. импульсов, а второй вход-к выходуэлемен- 30 Входы 25>-25к соединены с информационта задержки, вход которого подключен к ными входами регистра20. Выходотказа26 синхровходу вхОдного регистра и является устройства соединен с выходом формировавходом запуска устройства, выход мульти- теля 13 импульсов. Выходы 27> 27к соедиплексора подключен к входу дешифратора, нены с выходами регистров группы 2 и

ИЛИ г пп и адресный вход — к выходу блока элементов 35 являются выходами сообщения устр и, группа информационных входов к Группы выходов 281-28к соединены с входагруппе выходов блока памяти кодов марш- ми всех блоков 17 анализа, группа выходов рутов и к первой группе информационных 29 блока 20 соединена с другими входами . входов блока анализа маршрутов, вторая и всех блоков анализа, Выходы блоков аналитретья группы информационных входов ко- 40 за 30 — 30м(соответственно блоков 171 — 17M) торого подключены соответственно к груп- соединены с входами элемента 16 и блока и е инфо рмацион ных выхдов блока 15, Группы выходов 311-31м и 32>-32м соерегистров загрузки и к выходу регистра со- динены с входами устройства 14, группа выстояния, группавыходовразрешениямарш- ходов которого и группа выходов блока 15 рута — к группе входов элемента ИЛИ и к 45 соединены соответственно с первыми вхогруппе входов преобразователя кодов. дами элементов И групп 8 и 7. Вторые входы группе выходов номера маршрута и группе элементов группы 7 соединены с выходом выходов числа сообщений в буферных реги- элемента HE 9. Выходы групп 331-33м блострах узлов маршрута — соответственно к ка памяти 18 соединены с третьми группами первой и второй группе входов блока опре- 50 входов соответствующих блоков 17, Вход деления минимального кода, выход которо- выдачи 34 сообщения устройства соединен го подключен к первому входу третьего с синхровходами всех регистров группы 2. блока элементов И, выход которого подклю- Выход 35 окончания работы устройства сочен ко второи группе входов блока элемен- единен с выходом элемента задержки 11 и тов ИЛИ. второй вход к входу первого 55 с входом второго элемента И 12. Первая

1793447

30

50 группа выходов (адреса конечного узла) входного регистра 1 соединена с адресными входами блока памяти 18. Вторая группа выходов сообщения регистра входного 1 соединена с первыми входами элементов И соответствующих групп блока 3. Выходы групп элементов И блока 3 соединены с информационными входами соответствующих буферных регистров группы 2. Выходы дешифратора 4 соединены с вторыми входами

- всех элементов И всех групп блока 3. Выходы мультиплексора 5 соединены с входами дешифратора 4. Выходы группы элементов

ИЛИ 6 соединены с адресными входами мультиплексора 5. Выходы групп элементов

И 7 и 8 соединены cooTBGTcTBGHHQ с одноименными первыми и вторыми входами соответствующих элементов ИЛИ группы 6.

Выход элемента НЕ 10 соединен с первым входом элемента И 12, выход которого соединен с входом формирования импульсов

13, Выход элемента ИЛИ 16 подключен к третьим входам всех элементов И всех групп блока 3 и входу элемента НЕ 10.

Каждый блок анализа (фиг. 2) содержит первую 36 и вторую 37 группы элементов И, группу 38 элементов И, (группы элементов

И 38 — 38к), схему сравнения 39, элемент 40

НЕ, группу К-1 сумматоров 41> — 41к-1, регистр номера ма рш рута 42, груп r.y элементов ИЛИ 43. Входы 44 номера маршрута соединены с информационными входами регистра номера маршрута 42 (эти входы устройства не показаны на фиг. 1, они могут быть реализованы постоянным подключением информационных входов регистра 42 к шинам питания и нулевой устройства, также и без регистра 32 постоянным подключением входов 44 — в данном случае непосредственно соединенных с выходами

32 блока анализа 17 — к шинам питания и нулевой можно обеспечить формирование постоянных сигналов номера канала — маршрута). Входы 29 блока 17 соединены с первыми входами элементов И групп 36, вторые входы элеменов И группы 36.соединены с входами ЗЗ данного блока 17 и с второй группой входов схемы сравнения 39, а также с объединеными вторыми входами элементов И соответствующей группы блока элементов И 38. Соответствующие группы входов 28 соединены с первыми группами входов групп соответствующих элементов и группы 38, Выходы элементов i-й группы 38 соединены с первой группой входов i-1-го сумматора 41, к второй группе входов сумматора 41 соединены выходы элементов И группы 38ъ сумматорч 41 соединены последовательно оТ первого до К-1-го со вторыми

i руппами входов. Выходы сумматора 41к-> соединены с первыми входами элементов И группы 37, вторые входы которых объединены и соединены с выходом схемы сравнения

39, с входом элемента НЕ 40 и выходом 30 данного блока анализа 17. Выходы элементов И первой группы 36 соединены с первой группой входов схемы 39 сравнения. Выходы элементов группы 37 И соединены с первыми входами элементов ИЛИ группы 43, вторые входы которых объединены и соединены с выходом элемента НЕ 40. Выходы элементов ИЛИ 43 и информационные входы регистра 42 являются соответственно группами выходов 31 и 32 данного блока анализа 17.

Блок определения минимального кода

14 содержит ряд ступеней сравнения. в каждую из которых входят ячейки попарногб упорядочения кодов 45 (фиг, 3), Число ячеек первой ступени в два раза меньше числа блоков анализа, к каждой ячейке первой ступени подключены выходы 31 и 42 двух блоков анализа (произвольных, различных по всем ячейкам 45). К ячейкам 45 второй ступени подключены выходы (аналогично выходам 31 и 32) ячеек первой, ступени, и т.д. (если на какой либо ступени число ячеек 45 — нечетно, то к соответствующей ячейке следующей ступени} это касается и первой ступени при нечетном числе блоков анализа (к одной из групп входов 31 подключается шина питания устройства), На последней ступени устройства 14 имеется единственная ячейка 45, у которой используется выход типа 32 блока анализа, то есть на ее выходе формируется номер маршрута, код которого минимален среди всех кодов маршрутов для данного оконечного узла, к которому направляется сообщение.

Ячейка 45 попарного упорядочения чисел (фиг. 4) содержит схему 46 сравнения, первый 47 и второй 48 коммутаторы (мультиплексоры), Входы 31 ячейки 45 соединены соответственно с первой и второй группой входов схемы 46 сравнения, выход которой соедийен с управляющими входами мультиплексоров (коммутаторов) 47 и 48. Входы 31 ячейки 45 соединены соответственно с первой и второй группами информационных входов мультиплексора 47. Входы 32 (две группы, также как и входы 31) ячейки 45 соединены соответственно с первой и второй группами входов мультиплексора 48.

Выходы мультиплексоров 47 и 48 являются выходами (типа соответственно 31 и 32) ячейки 45, Блок преобразования кодов (преобразователь кодов) 15 фиг. 5 содержит группу элементов И 49 — 49м, и шифратор 50, Вход

30> блока 15 соединен с первым входом

1793447

10 шифратора 50, входы 30з — 30м блока 15 сое-, шрута осуществляется параллельным анадинены соответственно с прямыми входами лизом сравнением характеристик мар к маршрусоответствующих элементов и 49 группы. тов, а не последовательно, как в прототипе, Также каждый i-й вход 30i, i = 1, У-1, соеди- таким образом, выбор маршрута осуществнен с инверсными входами всех элементов 5 ляется за время, соответствующее задержИ 49 группы от )+1-го до М-го, выходы эле- ке срабатывания совокупности узлов ментов 49z — 49м соединены с соответствую- устройства. щими входами шифратора 50, выход Устройство работает следующим обракоторого (группа выходов) является выхо- зом. дом блока 15 преобразователя кодов. 10 Режим работы устройства задается поВ чертежах и описании заявляемого ус- стоянным потенциалом на вхбде 23: единичтройства использованы следующие обозна- ный уровень сигнала на этом входе чения; М вЂ” количество маршрутов, определяется второй режим(режим выбора достигаемых из данного узла (в котором рас- маршрута по минимуму суммарного количеполагается заявляемое устройство) комму- 15 ства сообщений в буферных регистрах узлов тации — всех остальных (для каждого — M. в данного маршрута), нулевой уровень соототдельности) узлов коммутации сети; К вЂ” ветствует первому режиму(выбора маршруколичество узлов коммутации в сети. та по отсутствию переполненных буферных

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

Устройство работает в двух режимах. В данном входе поддерживается в течение первом режиме работы устойства мало от- всего интервала работы устройства в соличается от работы прототипа: анализирует- тветствующем режиме. ся состояние буферных накопителей узлов, Рассмотрим работу устройства в перчерез которые проходит сответствующий 25 вом режиме (анализ состояний узлов маршмаршрут сообщения. Если хотя бы один бу- рутов). фер переполнен(об этом сообщает соответ- Сообщение по входу 21 поступает на ствующий разряд слова состояния узлов информационные входы регистра 1. Одно(данный маршрут отвергается. Из разре- временно с сообщением появляет шенных ма ш тов ( ршрутов (все узлы в составе ко- 30 пуска (короткий положительный импульс) на торых работоспособны,тоестьихбуферные входе 22 Запуск устройства, Информация регистры не переполнены), выбирается on- записывается в регистр 1. Эта информация тимальный (этот выбор осуществляется состоит из двух частей: адреса узла назнапредварительным размещением кодов мар- чения и самого сообщений (его информацишрутов в ячейках блока памяти), в соответ- 35 онной части). Код адреса узла назначения ствии с выбранным маршрутом сообщений поступает на адресные входы блока 18 папередается в первый узел данного маршру- мяти. На выходах блока 18 памяти 33)-33М та. появляются одновременно коды маршруВо втором режиме (отличительном от тов, Количество маршрутов для каждого уззаявляемого устройства в сравнении с про- 40 ла назначения фиксировано и равно М. тотипом) устройство анализирует не только Предполагается, что в сети — К узлов. факт переполнения буферных регистров со- Таким образом, с выходов блока памяти ответствующего маршрута, но и степень формируются M К-разрядных кодов, при . (уровень)заполнения,тоестьчислосообще- этом, если данный узел входит в данный ний, наодящихся в текущем моменте време- 45 маршрут, в соответствующем разряде соотни в каждом буферном регистре узлов ветствующего кода — единица, в противном маршрута, Далее определяются суммарные случае данный разряд имеет нулевое значеколичества сообщений в буферах узлов со- ние сигнала. Для каждого устройства (заявответствующих маршрутов, Выбор маршру- ляемое устройство располагается в каждом та. по которому направляется сообщение, 50 узле сети) внешние для данного узла узлы осуществляется в данном режиме по следу- нумеруются таким образом, что смежный ющему критерию: чем меньще суммарное узел каждого маршрута соответствует перчисло сообщений в некотором маршруте, вому (из К) разряду соответствующего кода. тем этот маршрут предпочтительнее. В дан- Иначе говоря, в первых разрядах кода саном режиме также осуществляется исклю- 55 держатся состояния смежных с данным узчение маршрутов из числа анализируемых ломустройства, каждомуузлусоответствует при переполнении буферов. узлов, составля- свой индивидуальный разряд, возможно, ющих данные маршруты. для каждого устройства — своя нумерация

Следует отметить, что в заявляемом ус- для соблюдения условия смежности, Бозтройстве в отличие от прототипа выбор мар- можное и несоблюдение условия смежно1793447

20

30

40

50 сти — соответствующей нумерации узлов кодов — это в конечном счете влияет на структуру дешифратора 4.

Выходные сигналы по выходам 33 блока памяти поступают в блок анализа 17>. В блоках . анализа 17 поступают также выходные коды с регистров 19 группы и регистра 20.

Заметим, что аналогично прототипу, маршрут, записанный в коде на выходах 331 является оптимальным, и далее маршруты

Следуют в порядке уменьшения предпочтительности, маршрут, определяемый кодом

33м самым худшим.

В блоке анализа 17 осуществляется аналогичная процедура для соответствующих маршрутов. Блок анализа работает следующим образом, Код маршрута (выходы 33) поступает на первые входы элементов И группы 36, на вторые входы которых поступает слоЬо состояния узлов из регистра 20. (Каждый разряд слова состояния сети соответствует определенному узлу коммутации сети, если количество сообщений в соответствующем узле коммутации сети меньше установленного порога, то в данном разряде .записывается единица, если больше. порога (буфер узла коммутации переполнен) — нуль, Слово состояния сети формируется и периодически обновляется в соответствии с состояниями узлов путем посылки в сеть специальных сообщений сетеметрии (тракты и средства и для пртотипа, не показаны), В регистр 20 слово состояния поступает по информационным входам 25. Аналогично в регистры уровня загрузки 191 — 19к (для К узлов коммутации сети) записываются коды, соответствующих узлов коммутации по входам 24). Цепи управления записью в регистры 19 и 20 не показаны на фиг. 1.

Если все буферные регистры узлов данного маршрута непереполнены, то код на выходе элементов И группы 36 совпадает с кодом на входах 33. И с выхода устройства сравнения 39 (выход типа Равно) формированию положительный сигнал. Одновременно коды с выходов 28 28к поступают на элементы И группы элементов И 38. Вторые входы элементов И каждой руппы 38 объе.динены и соединены с соответствующим разрядом кода 33, таким образом, если некоторый узел входит в маршрут на выходах соответствующей группы элементов И 38 формируется код числа сообщений в очереди буферного регистра соответствующего узла коммутации — проходит код 28, если узел не входит-в маршрут — код на выходе .-элементов И соответствующей группы блока 38 — нулевой. На сумматорах 41 происходит сложение всех кодов, то есть., определение суммарного количества сообщений во всех буферных регистрах узлов коммутации данного маршрута, Суммарный код поступает на первые входы элементов И группы 37, на выходах которых он появляется в случае, когда схема сравнения 39 выдает положительный сигнал (сигнализируя о разрешении да н ного маршрута. Далее этот код проходит через элемент ИЛИ группы 43.

Сумматор 41к-1 имеет следующую специфику: его разрядность (как и количество элементов групп 37 и 43) больше, чем достаточная разрядность для представления максимально возможной суммы чисел на входах

28 таким образом, значение сигнала на старшем разряде сумматора всегда равно нулю, в случае формирования на выходе схе мы сравнения 39 нулевого сигнала (исключение данного маршрута из анализа вследствие переполнения каких-либо буферных регистров узлов данного маршрута) на выходе элемента Н Е 40 формируется единичный сигнал, который независимо от значения кода на выходах элементов И 37 формирует на выходе группы элементов

ИЛИ 43 код(с единицей в старшем разряде), значение которого заведомо больше любого максимального возможного суммарного кода с выходов группы 37 — это важно для дальнейшей работы устройства 14.

На выходах регистра 42 формируется постоянный (для каждого маршрута) индивидуальный номер маршрута — соответственно для маршрутов записанных в кодах

331 — 33M — числа от 1 до M. Таким образом, на выходах 30, 32 и 31 блока анализа 18 формируются следующие сигналы: (соответственно) сигнал разрешения анализа данного маршрута, номер маршрута и суммарное число сообщений буферных регистрах узлов данного маршрута.

В данном. режиме устройством используются лишь сигналы с выходов 30, так как канал использования выходов 31 и 32 (блоки

14) закрыт нулевым сигналом на входах элементов И группы 8.

Совокупность сигналов с выходов 301 —.

30м поступает на входы преобразователя кодов 15 (фиг. 5), который работает следующим обраом: сигнал, поступающий на вход

30l, закрывает элементы И 49 от 1-го до М-ro, таким образом, на совокупности сигналов

30 и с выходов элементов 492-49м формируется единичный позиционный код, где место единственной единицы определяется минимальным номером разрешенного маршрута (напомним, что чем меньше номер маршрута, тем он оптимальнее, это определяется расположением кодов маршрутов и в

1793447

20

30

50

55 блоке памяти). В шифраторе 50 этот код преобразуется в двоичный код, который через открытые элементы И.блока 7 и элементы ИЛИ блока 6 поступает на адресные входы мультиплексора 5, на информационные входы мультиплексора 5 поступают коды маршрутов по выходам 33, таким образом, на выходах мультиплексора 5 формируется код выбранного. маршрута. Этот код поступает на входы дешифратора 3, в котором выбирается номер узла, в который в соотвествии с данным маршрутом передается непосредственно сообщение, содержащееся в входном регистре 1, номер смежного узла.

При размещении кодов(вернее — разрядов) узлов в соответствии с принципом, описанным выше, дешифратор 4 может быть реализован по принципу блока 15 (фиг. 5), но без блока 50.

При наличии хотя бы одного разрешенного маршрута на выходе элемента ИЛИ 16 формируется положительный сигнал, открывающий все элементы И блока 3, на вторые входы элементов И соответствующего блока 3 подается разрешающий сигнал с соответствующего выхода дешифратора 4, таким образом, на выходах элементов И соответствующей группы блока 4 появляется информационное сообщение из входного регистра 1, С поступлением сигнала выдачи это сообщение записывается в соответствующий регистр 2, из котоого по выходам 27 поступает на выход устройства, Вход выдачи 34 формируется вне данного устройства, он может также формироваться внутри данного устройства, будучи соединенным с выходом элемента задержки 11).

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

Если же среди возможных маршрутов не найден ни один разрешенный, то на выходе элемента ИЛИ 16 — нулевой потенциал, на выходе элемента НЕ 12 — единичный потенциал, и поступление импульса, задержанного элементом 11 на второй вход элемента И

12, формирует на выходе элемента И 12 положительный импульс, по положительному фронту которого формирователь импульсов

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

В данном режиме на входе 23 — единичный сигнал, отключающий канал элементов

И 7 и подключенный канал с элементами И

8. В этом режиме существенна работа устройства определения минимального кода 14 (фиг. 3 и фиг. 4). Устройство 14 фиг. 3 содержит совокупность соединенных по пирамидальной структуре устройств попарно упорядочения 45. Каждое устройство 45 получает по входам 31 и 32 соответствующие суммарные коды загруженности маршрутов и номера маршрутов от соответствующих блоков анализа 17. На первой ступени устройства 14 каналы объединяются на устройствах 45 последовательно попарно, выходы устройства 45 первой ступени также последовательно попарно объединяются в анализе по входам устройств 45 второй ступени, и т.д. С выходов каждого устройства попарного упорядочения кодов 45 снимаются соответственно код суммы (меньшей среди двух входных) и соответствующий ему номер маршрута. В устройстве 45 последней ступени (единственном) используется только номер маршрута.

Устройство 45 работает следующим образом, (фиг. 4): коды сумм (входы 31 и 31I+1) сравниваются на устройстве сравнения 46.

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

31н-1, а на выход коммутатора 48 — кода с входов 32н-1 в противном случае коммутируются альтернативные коды. Такой принцип формирования выходных сигналов сооТВеТствует во-первых, выбору меньшего из кодов суммы (и соответствующего ему номера канала), и, во-вторых, при равенстве кодов— выбор кода меньшего по номеру канала (который по принципу формирования ",.îдержимого блока. памяти является более и редпочтител ьн ым).

Выбранный среди всех каналов номер канала (маршрута) поступает с ем од,з уст15

1793447

16 ройства 14 на выходы блока элементов И 8, далее — на входы элементов ИЛИ 6 и т.д„в остальном устройство во втором режиме функционирует аналогично описанию первого режима.

Заметим, что при переполнении буферного регистра одного из узлов некоторого маршрута, код его суммы на выходах 31 заведомо больше любого допустимого максимального кода суммы любого разрешенного . маршрута, таким образом для запрещенных маршрутов коды сумм (и номеров) их будут отсеяны устройством 14.

Отметим также, что на чертежах устройства (фиг, 1) неприведены цепи записи информации в блок памяти 18.

Таким образом. заявляемое устройство во-первых, позволяет существенно повысить быстродействие по определению маршрута сообщения, требуя для окончания этого процесса интервала времени, определяемого лишь срабатыванием последовательности узлов устройства, а прототип для этого же результата требует до М тактов работы, что в среднем повышает быстродейФормула изобретения устройство для формирования маршрута сообщения, содержащее последовательно соединенные дешифратор, первый блок элементов И, блок буферных регистров, группа выходов которого является выходами сообщения устройства, а группа синхровходов — входом выдачи сообщения устройства, а также входной регистр, блок памяти кодов маршрутов, регистр состояния, группа входов которого является первой группой информационных входов устройства, элемент задержки, выход которого является выходом окончания работы устройства, элемент И, элемент ИЛИ, второй и третий блоки элементов И, блок элементов ИЛИ, причем адресный выход входного регистра подключен к адресному входу блока памяти кодов маршрутов, информационный выход — к второй группе входов первого блока элементов И, информационный вход является информационным входом устройства, группа выходов второго блока элементов И и подключена к первой группе входов блока элементов ИЛИ, а т л и ч а ю щ е е с я тем, 5

25 ствие заявляемого устройства в сравнении с прототипом в М/2 раз, во-вторых. заявляемое устройство позволяет расширить область применения прототипа путем обеспечения возможности гибкого выбора, основанного на оценке загруженности регистров (буферных) узлов, входящих в маршруты соответствующих сообщений, Отметим, что выбором соответствующего установочного потенциала можно легко переводить устройство с режима на режим, а характеристики заявляемого устройства в режиме с оценкой состояния узлов (без учета их загруженности) не хуже, а быстродействию — значительно лучше — чем у и рототи па, Дополнительным достоинством устройства является формирование им специального сигнала отказа при невозможности посылки сообщения по какому-либо маршруту, в то время как в прототипе такой сигнал не вырабатывается.

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

ИЛИ, группа информационных входов — к

1793447

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

ИЛИ, второй вход — к входу первого элемен. та НЕ, выход которого подключен к первому входу второго блока элементов И, второй вход которого подключен к выходу преобразователя кодов.

1793447

Составитель С. Кишенский

Редактор С, Кулакова Техред М.Моргентал Корректор М, Ткач

Заказ 505 Тираж Подписное

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

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

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