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

8010372 СОЮЗ СОВЕТСОЦИАЛИСТИЧРЕСПУБЛИК 15/20нлр д цт,ИСАНИЕ ИЗОБРЕТЕНИ етельство ССС5/20, 1978.ельство СССР ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР О ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬТИ К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) 1. Авторское сеид РМ 838701, кл, С 06 Е 12. Авторское свидетпо заявке 8 ф 3241464/18-24,кл, С 06 Г 15/20, 1980 (прототип),(54)(57) 1, ВЬ 4 ЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ МАРШРУТА СООБ"ЩЕНИЯ, содержащее блок управления,генератор тактовых импульсов, счетчик, группу элементов И, группублоков сравнения, первый коммутатор,группу регистров адресов, выходыкоторых являются выходами устройства, информационный вход каждого.ре"гистра адресов подклюЧен к выходусоответствующего элемента И группы, информационные входы элементовИ группы подключены к группе входов блока управления и к группевыходов счетчика, тактовый вход которого соединен с выходом генераторатактовых импульсов, первый и второйвыходы блока управления подключенык управляющим входам генератора тактовых импульсов и счетчика соответственно, третий выход блока управления подключен к управляющему входупервого коммутатора, первая группаинформационных входов которого является первой группой входов устройства, вторая группа информационныхвходов первого коммутатора соединенас группой выходов счетчика, каждыйвыход группы выходов первого коммутатора подключен к первому входу соответствующего блока сравнения груп пы, второй и третий входы каждого блока сравнения группы подключены соответственно к четвертому и пятому выходам блока управления, первый и второй выходы каждого блока сравне" ния группы подключены к управляющим входам соответствующих элементов И и регистров адресов, о т л ич а ю щ е е с я тем, что, с целью повышения точности, в него введен . второй коммутатор, управляющий вход которого соединен с шестым выходом блока управления, выход второго ком" мутатора соединен с четвертыми входа" ми блоков сравнения группы, первая группа информационных входов второго коммутатора является второй группой входов устройства, вторая группа информационных входов соединена с группой выходов счетчика, управляющий вход блока управления является управляющим входом устройст" ва.2, Устройство по и. 1, ,о т л и ч а ю щ е е с я тем, что блок управления содержит элементы И, ИЛИ, НЕ, формирователь прямоугольных им" пульсов, триггер, элементы задержки и дешифратор, группа входов которого является группой входов блока управления, выходы дешифратора, начиная с первого, подключены соответст-, венно к входам первого элемента ИЛИ, первый выход дешифратора соединен с первым входам первого элемента И и с входом элемента НЕ, выход которого соединен с первым входом второго элемента И, выход которого подключен к первому входу второго элемента ИЛИ, второй вход которого является1037269 дактор О.Поло рек аказ 6012/ Патент", г, Ужгород, ул, Проектная,филиал оставитель А.Жерен ехред И,Метелева Тираж 706НИИПИ Государственногопо делам изобретений3035, Москва, Ж, Ра омитета открытий ская наб ПодписноСРд. 4/5управляющим входом блока, а выходподключен к первому входу триггера,выход триггера является первым выходом блока, выход первого элемента Иявляется вторым выходом блока, выходпервого элемента ИЛИ через формирователе прямоугольных импульсов подключен к входу первого из четырехпоследовательно соединенных элементов 1037269задержки, к второму входу триггераи к пятому выходу блока, выходы второго и третьего элементов задержкиявляются соответственно третьим ичетвертым выходами блока, выход первого элемента задержки является шестым выходом блока, выход четвертогоэлемента задержки соединен с вторымивходами первого и второго элементов И.ЛИзобретение относится к вычислительной технике и может использоваться для сбора и обработки данных, вчастности, в устройствах коммутациисообщений и пакетов в сетях электрон" 5ны вычислительных машин (ЭВИ).Известно устройство, содержащеегенератор тактовых импульсов, счетчики, два регистра кода адреса, эле"менты И и ИЛИ, регистр числа узлов 0сети, блок сравнения, регистр кодаотказавшегося узла, элемент НЕ, ре-.гистр порядка перечисления узла сети, два циклических регистра сдвига 11, 15Недостатком этого устройстваявляется низкая эффективность, которая обуславливается формированиеммаршрута с минимальным числом межузловых связей между узлом отправления 20и узлом назначения, что не исключает больших временных задержек в промежуточных узлах сети,Наиболее близким к изобретениюпо технической сущности является устройство, содержащее блок управления,генератор тактовых импульсов, счет"чик, группу элементов И, группу блоков сравнения, первый коммутатор,группу регистров адресов соседнихузлов, выходы которых являются выходом устройства, информационныйвход каждого регистра группы подклю"цен к выходу соответствующего элемента И группы, информационные входы всех элементов И группы объединены и подключены к группе входовблока управления, выходам счетчика,тактовый вход которого соединен свыходом генератора тактовых импульсовпервый и второй выходы блока управления подключены к управляющим входам 2генератора тактовых импульсов й счетчика соответственно, третий выходблока управления подключен к управ"ляющему входу первого коммутатора,. первая группа информационных входовкоторого являетая первой группойвходов устройства, вторая группаинформационных входов первого коммутатора соединена с выходами счетчика,каждый выход группы входов первогокоммутатора подключен к первому входу соответствующего блока сравнениягруппы, второй и третий входы каж"дого блокасравнения группы объединены и. подключены н четвертомуи пятому выходам блока управления, первый и второй выходы каж"дого блока сравнения группы подклюцены к управляющим входам соответствующих элементов И и регистровадресов соседних узлов 2 .Недостатком известного устройства является его низкая точность,которая обуславливается тем, что привыборе маршрута не учитывается вре".мя, необходимое на передачу сообщения из узла отправления на соседнийузел, а также время ожидания в очереди,Целью изобретения является повышение точности,Поставленная цель достигаетсятем, что в вычислительное устройстводля формирования маршрута сообщения,содержащее блок управления, генератор тактовых импульсов, счетчик, груп"пу элементов И, группу блоков сравнения, первый коммутатор, группурегистров адресов, выходы которыхявляются выходами устройства, информационный вход каждого регистра адресов подключен к выходу соответству69 4 15 3 10372 ющего элемента И группы, информационные входы элементов И группы подключены к группе входов блока управления и к группе выходов счетчика, так" товый вход которого соединен с выхо дом генератора тактовых импульсов, первый и второй выходы блока управления подключены к управляющим вхо" .дам генератора тактовых импульсов и счетчика соответственно, третий 10 выход бдока управления подключен к управляющему входу первого ком. мутатора, первая группа информационных входов которого является первой группой входов устройства, вторая группа информационных входов первого коммутатора соединена с группой выходов счетчика, каждый выход группы выходов первого коммутатора подключен к первому входу соответству-. ющего блока сравнения группы, второй и третий входы каждого флока сравнения группы. подключены соответ" ственно к четвертому и пятому выходам блока управления, первый и второй выходы каждого блока сравнения группы подключены -к управляющим входам соответствующих элементов И и регистров адресов, введен второй коммутатор, управляющий вход которого соединен с шестым выходом блокауправления, выход второго коммутатора соединен с четвертыми входа" ми блоков сравнения группы, первая группа информационных входов второго. коммутатора является второй группой входов устройства, вторая груп. па информационных входов соединенас группой выходов счетчика, управляющий вход блока управления является управляющим входом устройства.Кроме того, в вычислительном уст" ройстве блок управления содержит элемент И, ИЛИ, НЕ формирователь прямоугольных импульсов, триггер, элементы задержки и дешифратор, группа .входов которого является группойвходов блока управления, выходы дешифратора, начиная с первого, подключеиы соответственно к входам пер" вого элемента ИЛИ, первый выход дешифратора соединен с первым входом первого элемента И и с входом элемента НЕ, выход которого соединенс первымвходом второго элемента И.выход которого подключен к первомувходу второго элемента ИЛИ, второйвход которого является управляющимвходом блока, а выход подключен к первому вхоДу триггера, выхдд триггера является первым выходом блока,выход первого элемента И являетсявторым выходом блока, выход первого,элемента ИЛИ через формирователь прямоугольных импульсов подключен квходу первого из четырех последова"тельно. соединенных элементов задержки, к второму входу .триггера и кпятому выходу блока, выходы второ-.го и третьего элементов задержки являются соответственно третьим и четвертым выходами блока, выход первогоэлемента задержки является шестымвыходом блока, выход четвертогоэлемента задержки соединен с вторыми входами пеового и второго элементов И,На фиг. 1 представлена схема устройства;. на фиг. 2 - схема блока срав.нения; на фиг, 3 " схема блока управления; на фиг. 4 - схема первогокоммутатора; на фиг, 5 - схема второго коммутатора; на фигб - пример, поясняющий процедуру выборамаршрута передачи,Устройство содержит группу регистров 1 адресов, группу элементов И 2,группу блоков 3 сравнения, генератор 4 тактовых импульсов, счетчик 5,блок б управления, коммутаторы 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,группу элементов И 46, входные .регистры 47,Устройство работает следующимобразом.Исходное состояние регистров группы 1 и счетчика 5 - нулевое. Запускустройства осуществляется подаиейна (входную) шину 22 импульса послеприема по шинам 1 О информации о за"держках от соседних узлов в буферные регистры коммутатора 7. Нв выходной шине 13 блока 6 управления появляется высокий потенциал, при этомзапускается генератор 4 тактовых им-.пульсов, Тактовые импульсы с генера-.1037269 Ькоторый для данного узла назначения меньше.Таким образом, в регистрах 1 формируется таблица маршрутов, Циклформирования продолжается до техпор, пока на выходах счетчика не будет код адреса последнего соседнегоузла. После этого счетчик 5 обнуляо- ется.10 Блок 6 управления работает следующим образом, На вход дешифратора28 поступает двоичное число с выходов счетчика 5. Используются толькоте выходы дешифратора, которые соответствуют номерам соседних узлов дляданного узла сети, Остальные выходыдешифратора 28 с выходами элементаИЛИ 30 не соединяются.При наличии на входе дешифратора20 двоичного числа, соответствующего 25 тора поступают на счетчик 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 и переводит его в нулевоесостояние, запрещая прохождение зо тактовых импульсов на счетчик 5. Этот же импульс поступает на выходную шину 14 и через элементы 36-38задержки - на шины 15-17, С выходаэлемента 39 задержки импульс поступает на элемент И 32 и, если кодадреса соседнего узла не являетсяадресом последнего соседнего узла(низкий потенциал на последнемвыходе дешифратора 28), переводит40 триггер 34 в единичное состояние,на шине 13 вновь формируется высокий потенциал, разрешающий прохождение тактовых импульсов на счетчик 5,Если код адреса является адресомпоследнего соседнего узла, то высокий потенциал с последнего выходадешифратора разрешает прохождениеимпульса управления через элемент50И 29 на сброс счетчика 5 и запрещает установку триггера 34 в единичное состояние,Следующий циКл работы устройстваначинается после приема новой информации о задержках от соседних55 узлов по шинам 10 в буферные регистры коммутатора 7, При этом триггер34 переводится в единичное состояние импульсом, поступающим на его269 8с минимальными задержками, рассмотРим процедуру выбора маршрута дЛя ги потетической цифровой сети (Фиг.6),Дпя выбора маршрута с минимальной задержкой на узле отправителя необходимо иметь суммарную задержку, которая складывается из задержки ожидания в очереди и задержки от соседних узлов, которые определяют загруженность узла по данному направлению. На узле отправителя составля" ется таблица задержек узла после опроса всех соседних узлов и суммирования задержек,е еаЬеейе ее ее ее 1 2О 1 О 5 8ееевееется такомзадержкатся таблица е выбир второго составл этой. табли Ршрут, для нимальна,. Ршрутов уз ее М соседузла узла знач. Задержка . 3 3 4 ания таблицыемом устройствеаблица,Алгоритм формир маршрутов в предла поясняет следующая 7 1037единичный вход через элемент ИЛИ 33по шине 22.Блок сравнения работает следующимобразом.Исходное состояние регистра 25 5перед началом работЪ устройства " единичное. Импульсом, поступающим изблока управления по шине 14, устанавливаются в нулевое состояние реги-.стры накапливающего сумматора 27, Информация о задержках поступает наиакапливаоций сумматор 27 по шинам18 и 21. После сложения задержек поимпульсу, поступающему по шине 16,происходит сравнение числа А в выходном регистре накапливающего сумматора 27 с числом в регистре 25. Так какдля данного такта А 4 В (число Ввсе .единицы),то на выходе схемы 26,сравнения появляется импульс, который обнуляет регистр 25 и, пройдячерез элемент 24 задержки, разрешает перезапись содержимого выходного Регистра накапливающего сумматорав регистр 25. ,25В последующие такты работы устройства происходит сравнение числа В врегистре 25 с числом А - суммарнойзадержкой от следующего соседнего уз,ла. Перезапись содержимого выходного 30регистра накапливающегося сумматора27 в регистр минимальных задержек25 происходит только при выполнении условия А 4 В.Коммутатор 7 работает следующимобразом.При поступлении на входы дешифра. тора 40 кода адреса соседнего узла,на соответствующем выходе дешифрато-,ра появляется высокий потенциал, который поступает на группы элементовИ 42 данного соседнего узла, По сигналу .управления на шине 17 коды задержек из группы регистров 43 чер.з.группы элементов И 42 и элементовили 41 поступают на шины 21,Коммутатор 8 работает аналогич- .ным образом, При наличии на входедешифратора 45 кода адреса сосед. него узла и управляющего сигнала нашине 15 код задержки, равный времени передачи сообщения и времениожидания в очереди, из соответствующего регистра 47 через группу элементов И 46 и группу элементов ИЛИ 44поступает на выходную шину 18 ком"мутатора,В качестве примера, поясняющегопроцедуру выбора маршрута передачи,10 27 1000 0100 100 9100 0010 010 011 010 01 вторяется для всех соседних узлов. После опроса и анализа задержек от последнего соседнего узла в регистрах 1 будет сформирована таблица маршрутов.Допустим, нужно передать сообщение из узла У 1 в узел 1 6. Сообщение будет передано через узел Н 2, хотя кратчайший маршрут проходит через узел т 4.Устройство позволяет вычислять код маршрута движения сообщения .в цифровой сети связи с минимальной задержкой в пути с большей точностью эа счет учета времени ожидания в очереди в узле отправления и времени передачи на соседний узел. 0011 0010 011 0001 0001 100 При совпадении кода адреса соседнего узла с кодом на счетчике 5 задержки от данногофсоседнего узла для всех узлов назначения поступают из коммутаторов 7 и 8 в накапливающий сумматор 27 блока 3 сравнения, Суммарная задержка сравнивается с содержимым регистром 25, которые в исходном состоянии нахо" дятся в единичном состоянии, Так как числа на выходах сумматора 27 меньше или равны числам в регистрах 25 (максимальная задержка), то в регистры 1 заносится код адреса данного соседнего узла, а в регист" ры 25 переписывается суммарная задержка с выхода сумматора. Цикл по 1010 0011 0101 0100 0010 1100 ОО 010 011