Устройство для формирования кратчай-шего пути b цифровой сети связи

СОюз % ОветкАнСоциалытичеамнхРеспублик ОП ИКАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУОпубликовано 15.06.81. Бюллетень хз 22Дата опубликования описания 25.06.81 йо денны нзс 5 энтгннй н ОтнрытнйВ. И. Васильев, М. И. 1 цаповалов и В.,М. Кони валовМосковский институт инженеров гражданской авиации(54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ КРАТЧАЙШЕГО ПУТИ В ЦИФРОВОЙ СЕТИ СВЯЗИИзобретение относится к области проектирования устройств обработки данных в вычислительной технике.Известно устройство для определения кратчайших путей между узлами сети, содержащее элементы НЕ, ИЛИ, схему упорядоченной выборки номеров ветвей кратчайшего пути, диоды, цепи задержки (11.Ввиду сравнительно высокой аппаратурной избыточности быстродействие устройства является низким, что делает затруднительным его использование в цифровых сетях связи, требующих высоких темпов обмена информацией (данными).Наиболее близким по сушности техническим решением задачи является устройсгво для формирования кода кратчайшего пути в цифровой сети связи 12, содержащее генератор, г 1 ервую группу элементов И, выходчой регистр, буферный регистр, две группы элементов И, элемент ИЛИ, узел опроса, лва регистра кода адреса, в котором первая группа входов выходного регистра соединена с выходами буферного регистра, выход гснератора соединен с входом счетчика выходы которого соединены с первыми входами элементов И первой группы и группой входов узла опроса, управляющий вход которого через элемент ИЛИ соединен с выходами элементов И первой группы, вторые входы которых соединены с выходами элементов И второй группы, входы которых соединены с выходами элементов И третьей груп пы, входы которых соединены с выходами регистров кода адреса, информационные входы которых соединены со входом устройства управляющий вход второго регистра кола адреса соелинен схолом генератора, вход которого соединен с 1 ыходом элемента ИЛИ, 10выход узла опрос;. соединен с входом выходного регистра, вторая группа вколов которого соединена с выходами первого регистра кола адреса, а выход соединен с выходомустройства.В этом устройстве не предусмотрена возможность сдвига кода адреса узла-получателя более, чем на один разряд за олин такт работы устройства, а также возможность появления нескольких колов кратчайших путей. Таким образом, возможности 20 устройства ограничены, так как оно можетприменяться только в цифровых сетях связи с порядком пересечения 1. Однако существуют сети переменной структуры (по 838701рядок пересечения не равен 1), и устройство формирования кода кратчайшего пути в цифровой сети связи должно обеспечить возможность сдвига кода адреса узла-получателя более, чем ка один разряд, и выбор кода кратчайшего пути среди нескольких 5 возможных.Целью изобрете 1 я является повышение точности и расширение функциональных возможностей устройства формирования крагчайшего пути в сети связи переменной структуры, т.е. в случае, когда порядок переО сечения сети может принимать значения 1 или 2.Цель достигается тем, что в устройство для формирования кратчайшего пути в цифровой сети связи, содержащее генератор так-; товых импульсов, выход которого соединен со входом счетчика разрядные выходы которого соединены с первыми Входами элементов И первой группы и группой входов узла опроса, выходы первого и второго регйстров кода адреса подключены к входам эле ментов И второй группы соответственно, выходы которых соединены соответственно со входами элементов И третьей группы, вьходы которых подключены к вторым входам элементов И первой группы, выходы которых соединены с группой входов элемента ИЛИ, вход которого подключен к выходу последнего разряда счетчика, выход элемента ИЛИ соединен с управляющим входом узла опроса и с первым входом генератора тактовых импульсов, выход которого подключен к уп- Зо равляющему входу второго регистра кода адреса, выход которого соединен с входом буферного регистра, информационные еходы регистров кода адреса подключены к входам устройства, дополнительно введены регистр числа узлов сети, элементы И, счетчики, блок сравнения, регистр кода отказавшего узла, элемент НЕ, регистр порядка пересечения сети, группы элементов И и два циклических сдвиговых регистра, выходы которых подключены к первым входам элементов И соответственно четвертой и пятой групп, выходы которых соединены с входами первого и второго элементов И соответственно, выходы которых подключены соответственно к входам первого и второго счетчиков, выходыкоторых подключены к входам блока сравнения, выходы которого соединены соответс- венно с первыми входами третьего и четвертого элементов И, вторые входы которых подключены соответственно к выходам последнего разряда первого и второго циклических сдвиговых регистров, первые входы которыхсоединены с выходом буферного регистра, выход первого регистра кода адреса подключенк вторым входам циклических сдвиговых регистров. управляющие входы которых соединены с выходом узла опроса, выход генератора тактовых импульсов подключен к управляющему входу первого циклического сдвигового регистра, третий вход которого соединен с выходом пятого элемента И, перВый Вход которого подключен к Выход счет- цика, выход регистра порядка пересечения сети соединен с вторым Входом генератора тактсВых импульсов и с Вторым Входом пятого элемента И, выход которого через э.емент НЕ подключен к третьему входу Второго циклического сдвиговогс регистра. Информационные входы регистра порядка псресечекия сети, регистра кода отказавшего узла и регистра числа узлов сети соедикеы с Входом устройства, выход регистра чи ла узлов сети подключен к третьему входу пя.ого элемента И, выходы регистра кода отказавшегс узла соединены с вторыми входами элемеВгов И четвертой и пятой групп, выходь третьего и четвертогс элементов И Ооьединены и являются выходом устройства.На чертеже показана блок схема предлагаемого устройства, включаюцего в себя генератор 1 тактовых импульсов, счетчик 2, первую группу 3 элементов И, "1 эетьО Вторую группу 4 и 5 элеме то; И, элемент 6 ИЛИ, узелопроса, первый и ворой регистры 8 и 9 кода адреса соответствек:ю, суферный регистр 10, регистр 11 числа узлов сети, элемент И 12, циклический сдвигсвый регистр 13, регистр 14 кода отказавшего узла, элемент НЕ 15, циклический сдвигоВый регистр 16, четвертую, пятую группу элементов 17 и 18 соответственно, счетчик 19 блок сравнения 20, элемент И 21, регистр 22 порядка пересечения сети, элементы И 23 и 24, счетчик 25, элемент И 26.Работа устройства роисходит следующим образом.Исходное состояние регистров .10, 3, 16, счетчиков 2, 9 и 25, узлаопроса является пулевым, а по входу устройства в регистры 8 и 9 произведена запись кодов а ресов узла-отправителя и узла-получателя соответственно, в регистр 11 - числа узг ов сети, в регистр 22 - порядка пересечения сети. При значении порядка пересечения сети равном 1 тактовым импульсом с выхода генератора 1 осуществляется сдвиг содержимого регистра 9 ка один разряд вправо, В резъ.Гьтате. чего п 1)оизвсдится запись разряда кодазла-полх ча геля В регистр 11. Одновременно количество тактов фикс;руется сечико 2 и узлом опроса. Злеме 5 Ты И группы 5 осуществляют поразрядное сравнение символов кодов регистров 8 и 9 ка равенство, а элементы И группы 4 фик.ируют одновременно равенство символов всех сравни 5 аемых разрядов, Если одноврсмс:- ное равенство наступает после первого сдвига содержимого регистра 9, то наличие единичного потенциала на выходе первого элемента И третьей группы 4 позволяетОсхсждение тактового импульса, появившегсся ьа первом выходе счетчика 2, через сссВегствующий элемент И первой группы 3 на кхсд элемента 6 ИЛИ. При кессвпадекии производится следующий сдвиг содержимого регистра 9, после чего, если описанная ситуа 838)О30 Фор,у.а 1(ЗГ)орегенич 50 55 ция сов;аления наблюдается, на вход элемента 6 ИЛИ ц эступаст тактовый импульс с второго вьхода счетчика 2, прошедший через сооте)стствуОеци Й элемент И первой группы и т.д., вплоть до того момента, когда посл (и - 1) -го сдвига (п - число разрядов кола адреса узла) олноврсменное совпадение всех сравниваемых разрядов не произошло, а Б результате и-го сдвига тактовый импульс с последнеГО ВыхОдя счетчика 2 поступает непосредственно ча вход элемента 6 ИЛИ. Ка)кдьй из тактовых импульсов. вступивших на вход элемента 6 ИЛИ и прошедших ца его выход,.выполняет слсдуюцие функции: останавливает генератор 1 тактовых импульсов, запускает узел 7 опроса, число тактов работы которого определяется чи(.Ом тдк:Оныхнь(х В нсГО со счет(ика 2, уВеличенным цз значение и. Узел 7 опроса осуществляет считывание солержимого регистров 8 и 1 О в регистры 13 и 16 и выдачу их содержимого, в рсзулетдтс чего нд выходе устройства появляется последовательность символов кода КРДтсЕйцЕ ГО ПУТИ ИЗ УЗЛа-ОтЦРавнтЕЛЯ В узел- пол уч атель.Последним ихПульсом с узла 7 опроса осущсств:ястс 51 возврат всего устройства в исходнос состояние (схемы устаовки в О на ертсже нс показаны во избежание загромождения и вследствие отсутствия ориГиндльнг)сти В рсшеци(и. Таким Обр 23051, если одновременное совпадение Всех сравниваемых разрядов кодов, записанных в регистрах 8 и 9 це наблюдается, то происходит серия последовательных сдвигов вправо содержимого регистра 9 вплоть до того момента, когда совпадение наступает, цос.е чего работы устройства по формированию крдтчайш(.го пути прекращается, а узс. 7 опроса производит считыванче солерж.)Ого регистров 8 и 9 Б регистры 13 и 16 и Былдчу их содержимого в виде последовательного кода кратчайшего пути на выход устройства. Условие равенств сравниваемых разрядов кодов в регистрах 8 и 9 является необходимым и достаточным для формирования кода кратчайПего пути в цифровой сети связи. узлы которой имеют адреса, представимые в Видс кодовых последовательностей д. ины и порядком пересечения равным 1. 11 ри цорялкс пересечения сети 2 слвигкода Б регистре 9 производится в ка)клом такте нд лва разряда вправо. С помощью элемента И 12 производится анализ нз четность кода чцслд узлов сети, записанного в регистре 11. Если исло узлов четно, то процедура формировация кратчайшего пути андлогичц; Г)ыпе(3.0 кснцой. Если Число Верпин нечстцо и созпадения кодов в регистрах 8 и 9 цри сдвиге на (и - 1) разрядов не произошло, то производятся сдвиг на два разряда впраею, солсржимое регистров 8 и 10 передается в регистры 13 и 16, а в (п + 1)-ый разряд регистров 3 и 16 записываются 10 15 20 25 35 40 1 и О соотВ.тствсцно, фое)хИрме.(11 сИ 12 и ЯГ О зких Рордзом В рсГистсрс 1 х 13 и 16 Окдзывс 3 от(.51;ев(1 кО,ЕЗ КРДТЧДЙЕЦИХ ПУТС 1, ОТЛИ 2101 ЦИЕС 51 ОДНИМ Р(3 рялом. 1 Зьбор олного из них ол цесс БляСТСЯ ПО ВТО)ИЧНОМХ ЦРИЗН(КМ, КОТРЫ) 5 БЛ 5 СТС 51 Чи(Х 10 ОТКзс 1 БЦИХ (ЗЛОЕ) 3(1 КР(ТДИШСМ П) тц КОЛЫ ОТКДЗ 1)иИХ УЗГОЕ 3 ЗДГСЬ- ВаОтс 51 по 1)холм мстрйисте)д В рсГпс Гр ОткдззВНс 0 с 3312 14 посл(.ловзтс,ьцо Однц 3;1 лрмГ и х 1. Поссе 32 Грмзки колс 1 Отказа)п(.ГО узг 2 В 1 э(Гистр Отксес)ВНс 0 узгс 1 14, с пОмО- щыо групп элемснОВ17, 18 и элем(цтов И 23 и 24 осуществляется сравнение колд ОТ К Д 3 Д Б П: С ГО (ЗЛ с 1 (. КОД Д М П П Р 0 5 Еж ХТО Ч Н Ь Х )злов на кратчзЙших ихт 51 х еля ч(ГО произволится Еикли(сски 1 слвц колов в регистрах 13 и 16 и Нд .11 лс 1 пи(. 13 ЫХОЛЫ р( Ги(ТРОВ 13 и 16 поступакго цос,сдовдтсльцо и - . рдзрядпыс коды промежуточных узлов, в рвзхльтдтс чего на цсрвыс вХоды грмпп элсхснтов И 7 и 18. Соецицсцньх с младшими разрядами регистров 13 и 6 : )ступдкэт нос г 1 ( (е13 д т с г ь ц О и - 1 э д 3 Г) 53 л 11 ь е и 0 д ы 11 р О м ( ж у - тОчных узлов перВОГО и е ОрОГО кратЗЙпц 1 х путем соответственно, д цд вторые вхолы - коды отказавших мзгОв с рсИстра 14. 1 ослс каждого сдвига.: рхцпы элементов И 17 и 18 проводят ацдлцз цд совпадение кодов 5 РОЗежтОчцых мзгОБ пе)эвого и ВтОРО 0 КРЗТДЙ ШИК ПМТЕЙ И КО;Ес 3 ОТКДЗДВ 1 П(.ГО МЗЛД. При совп(1;ееции ко)ОБ промсжхточцых хз,10 Б с колом отказавшего уз,(а цд выоде элементов И 23 и 24 появляется единичный потенциал, который фиксирх ется счетчиками 9 и 25. После завершения циклов сдвига Б регистраХ3 и 16, в регистр 14 зацисыБЗЕТС 51 СЛЕЛХ 10 ЦИ 1 КОД ОТКс 132 Е)Ш(.ГО Х ЗЛЗ. После того, как колы кратчайших мтей проанализированы нд всех кодах отказавших узлов, блок сравнения 20 проводит дцасолержимого счстчикд 19, Открывс)сгс 1 элеме т И 2 или 26, соответствующий счетчику с мецыцим значением, и ца выХод устройства выдается последовательно код кратчайшего пути с хИццмальным числом отказавших промежуточных узлов.Использование в качестве исходной информации кодов число з,ов сети и порялкд пересечения сети позв цст значительно расширить функциональ. с возможности уст. РОЙСТБД И ИСПОЛЬ.3013(3 Г (.Г В ЦцфРЕ)БО (.(.Тп связи переменной структуры, а также повысить точность формирования. Устройство для формирования кратчайшего и) ти в цифровой сети связи, солержащее генератор тактовых импульсов, выход которого соединен с вХодом счетчика, рдз. рядные выходы которого соединены с первыми вХодами элементов И ГерБОЙ группы и группой входов узла опроса, выходы первого и второго регистров кода адресаподключены к входам элементов И второй группы соответственно, выходы которых соединены соответственно с входами элементов И третьей группы, выходы которых подключены к вторым входам элементов И первой группы, выходы которых соединены с группой входов элемента ИЛИ, вход которого подключен к .ходу последнего разряда счетчика, выход элемента И,1 И соединен с управляюцим входом узла опроса и с первым входом генерагора тактовых импмльсов, Выход которого подключен к управляющему входу второго регистра кода адреса, выход которого соединен с входом буферного регистра, информационные входы регистров кода адреса подключены к входам устройства, отличающееся тем, что, с целью по вышения точности, В него введены регистр числа узлов сети, элементы И, счетчики, блок сравнения, регистр кода отказавшего узла, элемент НЕ, регистр порядка пересечения сети, группы элементов И и два циклических сдвиговых регистра, выходы которых2 О подключены к первым входам элементов Р 1 соответственно четвертой 14 пятой групп выходы которых соединены с входами первого и второго элементов И соответственно, выходы которь)х подключены соответственно к входам первого и второго счетчиков, выходы которых подключены к входам блока сравнения, выходы которого соединены соответственно с первыми входами третьего и четвертого элементов И, вторые входы которых подключены соответственно к выходам пос,сдпеГО разряд 1 псре 3010 и ВторОГ 1) цикг 11- ческих сдвиговых регистров, первые входь которых соединены с выходом буферного регистра, выход первого рсге)стра коля адреса ПОДК,ЮЧЕЕ К ВТЕ)13 ЫМ Е)ХО)ЕЕ)М цнкпь-)ЕСКИХ сдвиговых регистров, уира)ляюш 130 входы которых соедине 13 ы . 13 ыхе)дом )зла опрос 1, веХод генератора тяклговых их 11 ульс)в подключен к управляюц 1 сму входу первого цикличсско)о сдвигового регистра, третий вход которого соединен с ВьЕходом пятого элемента И, первый вход кеггорого подкл)очсн к Вь) - .Ходу счет икя, выход регистра порядка иереССЧСНИ 51 СОТИ СОСДИНЕ Е С ВТОРЫМ ВХОД 13 КЕ ГСНС. Батора тектое 3 ых иму.1 ъсов и с Вторых входом пятоГО элемента И, выход кбторОГО к пез элемент НЕ подключен к третьему входу второго циклического сдвигово;о рс;истра, информационные ВхОды регис)1)я пор 51 дка 1 сресечения сети, регистра кода огкязявше:о узла и рсГисра чис,)а узл 013 сс)п соединены с входом устройства, выход регистра числа УЗЛОВ СЕТИ ПОДКЛЮЧЕН К Г;)СГЬЕМХ ВХО;О НЯ ТОГО элемсптд И, ВыхОды рсГистра ко я:)1- казавшсго узла соединены с вторыми вхо. дами элементов И Гетвертой и пятой групп, в).ходы третьего и чете)СОТОГО э,)емсптов И Обьсдинсны и ЯВл 5110 тся Выхо,10 м устройства.Источники информации,принятые во внимание при экспе 1 зтизс . Авторское свидетельство С(Х 1 д Ж 288422, кл. С) Об Г 1=,20, 1070.2. Авторское свидсгельство (:Е.Е:.1 Л 547770, кл. С) Об 1. 1 б,20, 975 (прототип).Составитель И. дубинина Редактор И.Шубина Техред А. Бойкас Корректор М. Шароши Заказ 444773 Тираж 745 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж 35, Раун)скан наб., д. 4/5 Филиал ППП Патен)3 ч г, У ъород, ул. Проектная, 4