Устройство для формирования маршрута сообщения Советский патент 1993 года по МПК G06F15/419 

Изобретение относится к вычислительой технике и может быть использовано в ифро§ы х сетях связи, в том числе в сетях ЭВМ для вычисления оптимальных маршруов передачи сообщений.

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

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

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

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

соединен с информационными входами регистра состояния, выходы сдвигового регистра соединены с вторыми входами

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

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

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

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

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

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

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

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

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

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

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

На фиг. 1 представлена структурная схема устройства для формирования и маршрута сообщения; на фиг, 2 - структурная схема блока анализа; на фиг. 3 -структурная схема устройства определения минимального ко- 5 да; на фиг. 4 - структурная схема ячейки попарного упорядочения кодов, входящей в состав устройства определения минимального кода; на фиг. 5 - структурная схема преобразователя кодов.

0 Устройство для формирования и маршрута сообщений (фиг. 1) содержит входной регистр. 1, блок 2 буферных регистров, блок 3 элементов И, дешифратор 4, мультиплексор 5, блок.6 элементов ИЛИ, блоки 7 и 8

5 элементов И, первый 9 и второй 10 элементы НЕ, элемент 11 задержки, элемент И 12, формирователь 13 импульсов, блок 14 определения минимального кода, преобразователь 15 кодов, элемент 16 ИЛИ, блок 17

0 анализа маршрутов, блок 18 памяти кодов маршрутов регистров загрузки 19, регистр 2С состояния. Вход сообщения 21 соединен с информационным входом регистра 1, вход запуска 22 соединен с синхровходом блока

5- 1 и с входом блока 11. Установочный 23 вход устройства соединен с входом элемента НЕ 9, и с первыми входами элементов группы 8. Группы входов 24-|-242 соединены с информационными входами регистров группы 19.

0 Входы 25i-25x соединены с информационными входами регистра 20. Выход отказа 26 устройства соединен с выходом формирователя 13 импульсов. Выходы 27i-27« соединены с выходами регистров группы 2 и

5. являются выходами сообщения устройства. Группы выходов 281-28к соединены с входами всех блоков 17 анализа,-группа выходов 29 блока 20 соединена с другими входами всех блоков анализа, Выходы блоков анали0 за 301-ЗОм (соответственно блоков 1 1-17м) соединены с входами элемента 16 и блока 15, Группы выходов 311-31м и 321-32м соединены с входами устройства 14, группа выходов которого и группа выходов блока 15

5 соединены соответственно с первыми входами элементов И групп 8 и 7. Вторые входы элементов группы 7 соединены с выходом элемента НЕ 9. Выходы групп 331-ЗЗм блока памяти 18 соединены с третьми группами

0 входов соответствующих блоков 17. Вход выдачи 34 сообщения устройства соединен с синхровходами всех регистров группы 2. Выход 35 окончания работы устройства соединен с выходом элемента задержки 11 и

5 с входом второго элемента И 12. Первая

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

Каждый блок анализа (фиг. 2) содержит первую 36 и вторую 37 группы элементов И, .группу 38 элементов И, (группы элементов И 381-38к), схему сравнения 39, элемент 40 НЕ, группу К-1 сумматоров 411-41к-1, регистр номера маршрута 42, группу элементов ИЛИ 43. Входы 44 номера маршрута соединены с информационными входами регистра номера маршрута 42 (эти входы устройства не показаны на фиг. 1, они могут быть реализованы постоянным подключением информационных входов регистра 42 к шинам питания и нулевой устройства, также и без регистра 32 постоянным подключением входов 44 - в данном случае непосредственно соединенных с выходами 32 блока анализа 17 - к шинам питания и нулевой можно обеспечить формирование постоянных сигналов номера канала - маршрута). Входы 29 блока 17 соединены с первыми входами элементов И групп 36, вторые входы элеменов И группы 36 соединены с входами 33 данного блока 17 и с второй группой входов схемы сравнения 39, а также с объединеными вторыми входами элементов И соответствующей группы блока элементов И 38. Соответствующие группы входов 28 соединены с первыми группами входов групп соответствующих элементов и группы 38. Выходы элементов 1-й группы 38 соединены с первой группой входов i-1-го сумматора 41, к второй группе входов сумматора 411 соединены выходы элементов И группы 38i, сумматорч 41 соединены последовательно от первого до K-1-ro со вторыми группами входов. Выходы сумматора 41к-1

соединены с первыми входами элементов И группы 37, вторые входы которых объединены и соединены с выходом схемы сравнения 39, с входом элемента НЕ 40 и выходом 30

данного блока анализа 17. Выходы элементов И первой группы 36 соединены с первой группой входов схемы 39 сравнения. Выходы элементов группы 37 И соединены с первыми входами элементов ИЛИ группы 43,

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

5 анализа 17.

Блок определения минимального кода 14 содержит ряд ступеней сравнения, в каждую из которых входят ячейки попарногб упорядочения кодов 45 (фиг. 3). Число ячеек

0 первой ступени в два раза меньше числа блоков анализа, к каждой ячейке первой ступени подключены выходы 31 и 42 двух блоков анализа (произвольных, различных по всем ячейкам 45). К ячейкам 45 второй сту5 пени подключены выходы (аналогично выходам 31 и 32) ячеек первой,ступени, и т.д. (если на какой либо ступени число ячеек 45

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

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

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

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

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

5 выходами (типа соответственно 31 и 32) ячейки 45,

Блок преобразования кодов (преобразователь кодов) 15 фиг. 5 содержит группу элементов И , и шифратор 50. Вход 30т блока 15 соединен с первым входом

шифратора 50, входы ЗОз-ЗОм блока 15 соединены соответственно с прямыми входами соответствующих элементов и 49 группы. Также каждый 1-й вход 301, i fTM-i. соединен с инверсными входами всех элементов И 49 группы от И-1-го до M-го, выходы элементов соединены с соответствую- щими входами шифратора 50, выход которого (группа выходов) является выходом блока 15 преобразователя кодов.

В чертежах и описании заявляемого устройства использованы следующие обозна- чения: М - количество маршрутов, достигаемых из данного узла (в котором располагается заявляемое устройство) коммутации - всех остальных (для каждого - М, в отдельности) узлов коммутации сети; К - количество узлов коммутации в сети.

Принцип работы устройства заключается в следующем.

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

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

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

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

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

Рассмотрим работу устройства в пер5 вом режиме (анализ состояний узлов маршрутов).

Сообщение по входу 21 поступает на информационные входы регистра 1. Одновременно с сообщением появляется сигнал

0- пуска (короткий положительный импульс) на входе 22 Запуск устройства, Информация записывается в регистр 1. Эта информация состоит из двух частей: адреса узла назначения и самого сообщений (его информаци5 онной части). Код адреса узла назначения поступает на адресные входы блока 18 памяти. На выходах блока 18 памяти 331-ЗЗм появляются одновременно коды маршрутов. Количество маршрутов для к аждого уз0.ла назначения фиксировано и равно М. Предполагается, что в сети - К узлов.

Таким образом, с выходов блока памяти формируются М К-разрядных кодов, при . этом, если данный узел входит в данный

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

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

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

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

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

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

определение суммарного количества сообщений во всех буферных регистрах узлов коммутации данного маршрута, Суммарный код поступает на первые входы элементов И группы 37, на выходах которых он появляется в случае, когда схема сравнения 39 выдает положительный сигнал (сигнализируя о разрешении данного маршрута. Далее этот код проходит через эле0 мент ИЛИ группы 43.

Сумматор 41к-1 имеет следующую специфику: его разрядность (как и количество элементов групп 37 и 43) больше, чем достаточная разрядность для представления мак5 симально возможной суммы чисел на входах 28 таким образом, значение сигнала на старшем разряде сумматора всегда равно нулю, в случае формирования на выходе схе-1 мы сравнения 39 нулевого сигнала (исклю0 чение данного маршрута из анализа вследствие переполнения каких-либо буферных регистров узлов данного маршрута) на выходе элемента Н Е 40 формируется единичный сигнал, который независимо от зна5 чения кода на выходах элементов И 37 формирует на выходе группы элементов ИЛИ 43 код (с единицей в старшем разряде), значение которого заведомо больше любого максимального возможного суммарного ко0 да с выходов группы 37 - это важно для дальнейшей работы устройства 14.

На выходах регистра 42 формируется . постоянный (для каждого маршрута) индивидуальный номер маршрута - соответст5 венно для маршрутов записанных в кодах 331-ЗЗм - числа от 1 до М. Таким образом, на выходах 30, 32 и 31 блока анализа 18 формируются следующие сигналы: (соответственно) сигнал разрешения анализаданно0 го маршрута, номер маршрута и суммарное число сообщений буферных регистрах узлов данного маршрута.

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

5 канал использования выходов 31 и 32 (блоки 14) закрыт нулевым сигналом на входах элементов И группы 8.

Совокупность сигналов с выходов 30i-. 30м поступает на входы преобразователя

0 кодов 15 (фиг. 5), который работает следующим обраом: сигнал, поступающий на вход 30, закрывает элементы И 49 от 1-го до М-го, таким образом, на совокупности сигналов 301 и с выходов элементов форми5 руется единичный позиционный код, где место единственной единицы определяется минимальным номером разрешенного маршрута (напомним, что чем меньше номер маршрута, тем он оптимальнее, это опреде- пяется расположением кодов маршрутов и в

блоке памяти). В шифраторе 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 формрует импульс требуемой длительно- сти, свидетельствующий об отказе в передаче сообщения (невозможности выбора какого-либо маршрута).

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

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

Устройство 45 работает следующим образом, (фиг. 4): коды сумм (входы 31| и 31|-н) сравниваются на устройстве сравнения 46. Выходной сигнал с его выхода управляет коммутаторами 47 и 48. В том случае, когда . код на входе 31| больше кода на входе 31i+i с выхода устройства формируется положительный сигнал, осуществляющий коммутацию на выход коммутатора 47 кода с входов 31ц-1, а на выход коммутатора 48 - кода с входов 32|-н в противном случае.коммутируются альтернативные коды. Такой принцип формирования выходных сигналов соответствует во-первых, выбору меньшего из кодов суммы (и соответствующего ему номера канала), и, во-вторых, при равенстве кодов - выбор кода меньшего по номеру канала (который по принципу формирования содержимого блока, памяти является более предпочтительным).

Выбранный среди всех каналов номер канала (маршрута) пост пает с БМ.Х-ОД.Э устройства 14 на выходы блока элементов И 8, далее - на входы элементов ИЛИ 6 и т.д., в остальном устройство во втором режиме функционирует аналогично описанию первого режима.

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

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

Таким образом, заявляемое устройство во-первых, позволяет существенно повысить быстродействие по определению маршрута сообщения, требуя для окончания этого процесса интервала времени, определяемого лишь срабатыванием последовательности узлов устройства, а прототип для этого же результата требует до М тактов работы, что в среднем повышает быстродействие заявляемого устройства в сравнении с прототипом в М/2 раз, во-вторых, заявляемое устройство позволяет расширить область применения прототипа путем

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

Отметим, что выбором соответствующе-.

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

Дополнительным достоинством устройства является формирование им специального сигнала отказа при невозможности

посылки сообщения по какому-либо маршруту, в то время как в прототипе такой сигнал не вырабатывается.

Таким образом, заявляемое устройство соответствует поставленной цели изобретения.

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

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

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

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

«Рил 2

3

30,

-ii,

30,

ЗсШ

.

3LU

U

tt

Фиг. 4

hi

1te

ч

9ltr.S