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

 

СО9Оз ОВЕт киьь (оциалистичеаиих

Республик

ОП ИКАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ („)838701 (61) Дополнительное к авт. свил-Ву (22) Заявлено 29.12.78 (21) 2723737:18-24 с присоединением заявки ¹ (23) Приоритет— (51) М. Кл.з

О 06 F 15, 20

)OCJABPI:Y8QHHblH КГььННтат (53) УДК 681.3 (088.8) Опубликовано 15.06.81. Бюллетень Х< 22

Дата опубликован33я описания 25.06.81 до делам нзабретеннй

Н QYKPbIYHH (В. И. Васильев, М. И. Ца33овь3лов и В.,М. Кош валок

1 ! ь 3 ь t

Московский институт инженеров гражданской авиа33ии (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ КРАТЧАЙШЕГО

ПУТИ В ЦИФРОВОЙ СЕТИ СВЯЗИ

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

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

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

Наиболее близким по сушности техническим решением задачи является устройсгво для формирования кода кратчайшего пути в цифровой сети связи (2), содержащее генератор, г3ервую группу элементов И, выходчой регистр, буферный регистр, две группы элементов И, элемент ИЛИ, узел опроса, два регистра кода адреса, в котором первая группа входов выходного регистра соединена с выходами буферного регистра, выход гснератора соединен с входом счетчика выходы которого соединены с первыми входами элементов И первой группы и группой входов узла опроса, управляющий вход которого через элемент ИЛИ соединен с в»3холами элементов И первой группы, вторые входы которых соединены с выходами элементов И второй группы, входы которых соединены с выходами элементов И третьей группы, входы которы.: соединены - выходами регистров кода адреса, информационные входы которых соединены со входом устройства управляющий вход второго реп3стра кола адреса соединен с .: ходом генератора. вход которого соединен с Зыходом элемента ИЛИ, 10 выход узла опрос;. -оединен с входом выходного регистра, вторая группа входов которого соединена с выходами первого регистра кола адреса, а выход соединен с выходом устройства.

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

20 устройства ограничены, так как оно может применяться только в цифровых сетях связи с порядком пересечения «1». Однако существуют сети переменной структуры (llo838701 рядок пересечения не равен «1»), и устройство формирования кодл кратчайшего пути в цифровой сети связи должно обеспечить возможность сдвига кода адреса узла-получателя более, чем на один разряд, и выбор кода кратчайшего пути среди нескольких 5 возможных.

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

«1» или «2».

Цель достигается тем, что в устройство для формирования кратчайшего пути в цифровой сети связи, содержащее генератор так-; товых импульсов, выход которого соединен со входом счетчика разрядные выходы которого соединены с первыми Входами элементов И первой группы и группой входов узла опроса, выходы первого и второго регйстров кода адреса подключены к входам элементов И второй группы соответственно, выходы которых соединены соответственно со входами элементов И третьей группы, выходы которых подключены к вторым входам элементов И первой группы, выходы которых соединены с группой входов элемента ИЛИ, вход которого подключен к выходу последнего разряда счетчика, выход элемента ИЛИ соединен с управляющим входом узл- опроса и с первым входом генератора тактовых импульсов, выход которого подключен к уп- зп равляющему входу второго регистра кода адреса, выход которого соединен с входом буферного регистра, информационные входы регистров кода адреса подключены к входам устройства, дополнительно введены регистр числа узлов сети, элементы И, счетчики, блок сравнения, регистр кода отказавшего узла, элемент НЕ, регистр порядка пересечения сети, группы элементов И и два циклических сдвиговых регистра, выходы которых подключены к первым входам элементов И соответственно четвертой и пятой групп, выходы к >Topblx соединены с входами первого и второго элементов И соответственно, выходы которых подключены соответственно к входам первого и второго счетчиков, выходы которых подключены к входам блока сравнения, выходы которого соединены соответс1венно с первыми входами третьего и четвертого элементов И, вторые входы которых подключены соответственно к выходам последнего разряда первого и второго циклических сдвиговых регистров, первые входы которых соединены с выходом буферного регистра, выход первого регистра кода адреса подключен к вторым входам циклических сдвиговых регистров. управляющие входы которых соединены с выходом узла опроса, выход генератора тактовых импульсов подключен к yrlравляющему входу первого циклического сдвигового регистра, третий вход которого соединен с выходом пятого элемента И, перВЫЙ ВХОД КОТОРОГО ПОДКЛЮЧСК К ВЫХОД>, СЧЕ1чика, выход регистра порядка пересечения сети соединен с вторым входом генератора

TdKT0BhiX HMll) 1bCOB H C Вторы."5! ВХОД(>:51 !!BTОго элемента И, выход которого через э.!емент НЕ подключен к третьему входу второго циклического сдвигового регистра. информационные входы регистра порядка псресечекия сети, регистра кода отказавшего узла и регистра числа узлов сети соедине! ы с Входом устройства, выход регистра числа узлов сети подключен к третьему входу;I5! Tl>I o элемента И, выходы регистра кода 0TKdзавшегс узла соединены с вторыми входами элеме)ггов И четвертой и пятой групп, Bhlxoды третьего и четвертогс 3.1eviei!TOB И Об ьединены и являются выходом устройства.

На чертеже показана блок схема кре I!Iàгаемог0 устройства, включаю>цего в себя генератор 1 тактовых импульсов, cчетчик 2, первую группу 3 элементов И, "ретьк> H !>т.>рую группу 4 и 5 элемеl то; И, 3.1е;!ект

6 ИЛИ, узел 7 опроса, первый и в1орой регистры 8 и 9 код- адреса соответствек:ю, буферный регистр 10, регистр 11 числа узлов сети, элемент И 12. v,Hêëè÷åñêHé сдВH!.овый регистр 13, регистр 14 кода отказавшего узла, элемент HE 15, циклический сдвиговый регистр 16, четвертую, пятую гpyi! !1у элементов 17 и 18 соответственно, счетчик 19 блок сравнения 20, элемент И 21, регистр 22 порядка пересечения сети, элементы И 23 и 24, счетчик 25, элемент И 26.

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

Исходное состояние рс »сТрОВ 10, l3, 16, счетчиков 2, 19 и 25, узла 7 опроса явл5;eTся пулевым, а по входу устройства в рог! стры 8 и 9 произведена запись кодов ВС!ресов узла-отправителя и узла->к>лучателя соответственно, в регистр 11 — числа узг ов сети, в регистр 22 — порядка пересечения сети. При значении порядка пересечения сети равном «1» тактовым импульсом с выхода генератора 1 осуществляется сдвиг содержимого регистра 9 ка один разряд впраи>, В pe3>, .!"!Ьтате, чего IlpoH330+HTc5! за!!ись разрегlic1 р 11!.

Одновременно количество тактов фикс;!руетCH CiIeT HK0Vi 2 H y3JIOM 70 IpOCB. 3 Ie_#_ieHTLi И группы 5 осуществляют поразрядное cpdiiнекие символов кодов регистров 8 и 9 hd равенство, а элементb! И группы 4 фик.ируют одновременно равенство символов всех сравниваемых разрядов. Если одноврсмс:!кое равенство наступает после nepBoi!; сдвига содержимого регистра 9, TG наличие «единичного» потенциала на выходе первого элемента И третьей группы 4 позволяет рсхсждение тактового импульса, появившегсся ьа первом выходе счетчика 2. через соO.I BåT —вующий элемент И первой группы 3 на кхсд элемента 6 ИЛИ. При кессвпадекии прoHBводится следующий сдвиг содержимого регистра 9, после чего, если OI>Hcакная ситуа838701

Зо

Форщ.(а пзоб ()егени. (50

55 ция сов;!адсния наблюдается. на вход элемента 6 ИЛИ li)ступает тактовый импульс с второго вь!Хода счетчика 2, прошедший через соответству!Ощий элемент И первой группы H I.J., в!(лить )0 тог0 момента, когда послс (и — 1)-го сдвига (п — число разрядов кода адреса узла) одновременное совпадение всех сравниваемых разрядов не произошло, а в результате и-го сдвига тактовый

H.

ИЛИ. Ка)кдый из тактовых импульсов. Iiocтупивших на вход элемента 6 ИЛИ и I!po ше, HIHx на его выход, . выполняет следуloп(ие функции: останавливает генератор 1 тактовых импульсов, запускает узел 7 )Iip0ca, число тактов работь! которого опредсляЕТСЯ ЧИ(.IОМ ТИК:ОНЫХ ИМГ(><.1ЬСОВ, зан!(С2Ннь(х В нс I O co счет<(и ка 2, увеличенным иа

3начспис и. Узел 7 OпpOc2 осуществляет считывание содержимого регистров 8 и 10 в рег:!стры 13 и 16 и выдачу их содержимого, в

p(. 3óëüòàòå чего на выходе устройства появляется последовательность символов кода кратчайшего пути из узла-отправителя в узел- пол уч атель.

Последним ич(1 ульсом с узла 7 опроса осу(цествляется возврат всего устройства в исходнос состояние (схемы уста(ковки в

«О» на !ертеже не показаны во избежание загромождения и вследствие отсутствия оригинальнссти в решении). Таким обр230м, если одновременное совпадение Всех сравниваемых разрядов кодов, записанных в регистраx 8 и 9 не наблюдается, то происходит серия последовательных сдвигов вправо содержимогO регистра 9 вплоть до того момента, когда совпадение наступает, пос.!е чего работы устройства по формированию крат(айшсго пути прекращается, а узе.i 7

0i!роса производит считывание содерж. IiloA) регистров 8 и 9 в регистры 13 и 16 и Выдачу их содержимого в виде последовательного кода кратчайшего пути на выход устройства.

Условие равенств сравниваемых разрядов кодов в регистрах 8 и 9 является неооходимым и достаточным для формирования кода кратчай!пего пути в цифровой сети связи. узлы которой имеют адреса, представимые в Видс кодовых последовательностей д. IHны и порядком пересечения равным «1».

11ри порядке пересечения сети 2 сдвиг кола в регистре 9 производится в ка)кдом такте на лва разряда вправо. С помощью элемента И 12 производится анализ на четность кода числа узлов сети, записанного в регистре 11. Если -!исло узлов четно, то процедуры формирования кратчайшего пути аналогич-!

Га вышеизложенной. Если число вершин нечетно и созпадения кодов в регистрах 8 и 9

IlpH сдвиге н2 (и — 1) разрядов не произошло, то производится сдвиг на два разряда вправо, содержимое регистров 8 и 10 передастся в регистры 13 и 16, а в (п + 1) ûé разряд оегистров !3 и 16 записываются

35 0

«1» ll «О» соотВстствснно, формирусмыс э,(ем сит<1 м и H 1 2 ll H Е ) О I а Kli и (Оp23()x<

В рсГист<ра х 1 3 H 1 6 Ок;13ы В а!От(я;(г><1 ко,(li

KP2тч2йLIIl1\ и>> T(и, Отл!i:iаюlпиP. Я 0;EIII(м Раз рядом. 131.!бор одного из ННх ос(и(ее гвля TCH (I0 ВТО )ИЧНОМ < IIPli3HHKX, KOTOPbl)I 5(BIH(ÒÑß ". l1(XтО ОТK

И 23 и 24 осуществляется сравнение код(!

ОТК232БI!:ЕГО ЗЛН (. КОДИМli IIPOXI(>ж < ТОЧHhlX

УЗлов на кРатчайш(l х и, THx 1,)Я ч(ГО HP003водится цикличсский сдви! кодов в регистраХ 1 3 !! 1 6 !I H 2 . 1,"i 2,1,(и и(. Вhl Xоды р(-. ГI1 СТрОВ

13 и 16 поступак) Иос.(слов((тес!ьно и -- разряд!(ые кодbl промс жуто IHblx узлов, в результате чего на первые входы групп эл >м Hтов И 7 и 18. сое.i!Iненных с младшими разря вами регистров 13 и !6 f: )ступакэт поС.l(. (ОВВTC, 1Ь 110 и — P23РЯД(I l>l(. КОДЫ I(PО. 1(ЖУ—

TO lHhlX X 3ЛОВ HLPBOI 0 ll E!TOPOI O KPHT !2I(IIIIIX путем соответственно, 2 на вторые входы— коды отказавших узлов с регистра 14. IIocле каждого сдвига. Грхппы элементов И 17 и 18 IlpOBQYT (IIIÍ I!(3 на совпадение кодов

IPBOI О И BTOPOI О к!)атчайших fl(TPÉ и кода QTKB 32BILI(10 x3(12.

При совпа (pHIIII кодов прох!ежмточн(.!х xç(ion с кодом отказавшего уз.!2 Н2 выходе элементов И 23 и 24 появляется «единичный» потенциал, который фиксируется счетчиками 9 и 25. После завер(пения циклов сдвига в регистрах 3 и 16, в регистр 14 321111chiВВЕТС51 (.,1PДXЮ(ЦИЙ KO l, OTh232 E3LUPГО Х 3 (2.

После того, как коды кратчайших путей проанализированы на всех кодах 0) h232Bших узлов, блок сравнения 20 проводит анализ содержи)IОГО счетчик2 19, ОткрыВает(. я элеме(т И 21 или 26, соответствующий счетчику с меиыпим 3HEI«pHIIP», и на выход устройства выдается последовательно код кратчайшегO пути с минимальnûxi числом OTêàзавших промежуточных узлов.

Использование в качестве исходной информации кодов число 3.)ов сети и порядка пересечения сети позв ICT значительно расширить функциона ii>!. .. с возможности устройства и использовать его в цифровой сети связи переменной структуры, а также повысить точность формирования.

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

2О подключены к первым входам элементов И соответственно четвертой !4 пятой групп выходы которых соединены с входами первого и второго элементов И соответственно, выходы которых подключены соответственно к входам первого и второго счетчиков, выходы которых подключены к входам блока сравнения, выходы которого соединены соответственно с первыми входами третьего и четВертого элементов И, вторые входы которых подключены соответственно к выходам пос! сдпеГО Раз13Ядсl iiPP В01 0 и BToPOI"> пик.! и ческих сдвиговых регистров, первыс входь! которых соединены «выходо)а буфер:гого регистра. Выход первого рсгH«1.1>d ко.i;1 адреса подключен к вторы: вхо,111 м цикл !. чески. сдвиговых регистров, уllpHI3 !II!OUI)с Bxоды которых соеди !ень;- .:.Ыx(),"оxl узла опроса, выход генератора тактовых импульсоз !10;i,— ключен к управляюпсему входу первого l HKличсского сдв! I QB01 . регистра, третий вх эд которого соединен с вь.xnzuxi ii".TOãî элемента И, HcpBi,!Й Вхо3, кс)торого Iio+K 3!Oчсн K вь— .ходу счет1ика, Выход регистра !IopH3,ка переССЧЕНИЯ СЕТИ СОСДИНС Н C ВТ(ЭРЫМ BXOQO."i Г.НСОатора та! кт01)ых и к! 5у. 1ьсов и с BTopbiх1 Входом пятого элемента И, выход котс рогс K pe3 элемент НЕ подклю lei! к третьему входу ВТоРОГО ЦИКЛИЧЕСКОГО СДВИГОВО;О РЕ!ИСтРВ, Hkiформа!пион!!ые ВхОды pBГиссpd liopilдка Iic .— ресечения сети, регистра кода отказавше:0 узла и реГис ра чис, i;» «ÇëÎ! се i 1! соединены с входом устройства, Bb!xo:: реги. ;рь числа узлОВ сети подключеll к I c Ãьему Входl iIH

ТОГО элемспта И, ВыхОды реГистра ко а:) Iказавшего узла соединены с вторыми вх«дами элементов И етвертой и пятой групп, выходы третьего и четвертого э.!ем l!тÎB И

Об ьс. динс Ibi и ЯВляlотся Выхо.сом уcTpойства.

Источники информации, принятые Во внимание при эксперт51зс !. Авторское свидетельство «С С..1э

¹ 288422, кл. G 06 F 15, 20, 1970.

2. Авторское свидсгельство (:(..С1)

Л 547770, кл. G Об 1э 15, 20, !975 (прототип!.

С,ocTB Bi!Tc;I» И. Jf, 5 QHHHHB

Редактор И.Шубина :" хргд А. Бойкас Корректор . T. Шаро ши

Заказ 444717 3 Тираж 745 Подписное

ВНИИПИ Государственно-о комитета СССР о делам изобретений и открытий

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

Филиал ППП «Патен-: », г. У "- город, ул. Проектная, 4