Устройство для формирования кратчай-шЕгО пуТи B цифРОВОй СЕТи СВязи Советский патент 1981 года по МПК G06F15/173 

I

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

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

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

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

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

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

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

Цель достигается тем, что в устройство для формирования кратчайп1его пути в цифровои сети связи, содержащее генератор тактовых импульсов, выход которого соединен со входом счетчика разрядные выходы которого соединены с первыми входами элементов И первой группы и группой входов узла опроса, выходы первого и второго регистров кода адреса подключены к входам элементов И второй группы соответственно, выходы которых соединены соответственно со входами элементов И третьей группы, выходы которых подключены к вторы.м входам элементов И первой группы, выходы которых соединены с группой входов элемента ИЛИ, вход которого подключен к выходу последнего разряда счетчика, выход элемента ИЛИ соединен с управляющим входом узла опроса и с первым входом генератора тактовых импульсов, выход которого подключен к управляющему входу второго регистра кода адреса, выход которого соединен с входом буферного регистра, информационные входы регистров кода адреса подключены к входам устройства, дополнительно введены регистр числа узлов сети, элементы И, счетчики, блок сравнения, регистр кода отказавшего узла, элемент НЕ, регистр порядка пересечения сети, группы элементов И и два циклических сдвиговых регистра, выходы которых подключены к первым входам элементов И соответственно четвертой и пятой групп, выходы которых соединены с входами первого и второго элементов И соответственно, выходы которых подключены соответственно к входам первого н второго счетчиков, выходы которых подключены к входам блока сравнения, выходы которого соединены соответственно с первыми входами третьего и четвертого элементов И, вторые входы которых подключены соответственно к выходам последнего разряда первого и второго циклических сдвиговых регистров, первые входы которых соединены с выходом буферного регистра, вы ход первого регистра кода адреса подключен к вторым входам циклических сдвиговых регистров, управляющие входы которых соединены с выходом узла опроса, выход генератора тактовых импульсов подключен к управляющему входу первого циклического сдвигового регистра, третий вход которого соединен с выходом пятого элемента И., первыи вход которого подключен к выходу счетчика, вы.ход регистра порядка пересечения сети соединен с вторы.м входом генератора тактовых импульсов и с вторы.м входо.м пятого элемента И. выход которого через элемент НЕ подключен к третьему входу второго циклического сдвигового регистра, информационные входы регистра порядка пересечения сети, регистра кода отказавшего узла и регистра числа узлов сети соединены с входом устройства, выход регистра числа узлов сети подключен к третьему входу .пятого элемента И, выходы регистра кода отказавшего узла соединены с вторыми входами элементов И четвертой и пятой гругш, выходы третьего и четвертого элементов И объедипены и являются выходом устройства. На чертеже показана блок схема предлагаемого устройства, включающего в себя генератор 1 тактовых импульсов, сметчик 2, первую группу 3 элементов И, третью и вторую группу 4 и 5 элементо; И, эле.мент 6 ИЛИ, узел 7 опроса, первый и второй регистры 8 и 9 кода адреса соответственно, буферный регистр 10, регистр 11 числа узлов сети, элеме1 т И 12, циклический сдвиговый регистр 13, регистр 14 кода отказаBnieго узла, элемепт НЕ 15, циклический сдвиговый регистр 16, четвертую, пятую группу элементов 7 и 18 соответственно, счетчик 19 блок сравнения 20, элемент И 21, регистр 22 порядка пересечения сети, элементы И 23 и 24, счетчик 25, элемепт И 26. Работа устройства происходит следуюпдим образом. Исходное состояние регистров ,10, 13, 16, счетчиков 2, 19 и 25, узла 7 опроса является пулевым, а по входу устройства в регистры 8 и 9 произведена запись кодов адресов узла-отправителя и узла-нолучателя соответственно, в регистр 11-числа узлов сети, в регистр 22 - ьорядка пересечения сети. Нри значении порядка пересечения сети равном «1 тактоБы.м импульсом с выхода генератора 1 осуществляется сдвиг содержимого регистра 9 на один разряд вправо, в результате, чего производится запись разряда кода уз.ла-получателя в регис1р 10. Одновременно ко.личество тактов фиксир ется счетчиком 2 и узло.м 7опроса. Элементы И группы 5 осуществляют поразрядное сравнение символов кодов регистров 8 и 9 ка равенство, а элементы И группы 4 фиксируют одновременно равенство символов всех сравниваемых разрядов. Если одновремс})ное равенство наступает после первого сдвига содержимого регистра 9, то наличие «еди-, ничного потенциала на выходе первого э,1е.мента И третьей группы 4 позволяет прохождение тактового импульса, появившегося на нервом выходе счетчика 2. через соответствующий элемент И первой группы 3 на вход элемента 6 ИЛИ. При несовпадении производится следующий сдвиг содержимого регистра 9, носле чего, если описанная ситуаПИЯ со1 ;1адеиил наблюдается, на вход лемента 6 ИЛИ поступает тактовый импульс с второго выхода счетчика 2, прошедший через соответствующий элемент И первой группы и т.д., вплоть до того момента, когда после (п - 1)-го сдвига (п-число разрядов кода адреса узла) одновременное совпадение всех сравнивае.мых разрядов не ироизо1лло, а в результате п-го сдвига тактовый импульс с последнего выхода счетчика 2 поступает непосредственно на вход эле.мента 6 И/1И. Каждый из тактовых импульсов, поступивших на вход элемента 6 ИЛИ и прошедших па его выход,. выполняет следующие функции: останавливает генератор 1 тактовых импульсов, запускает узел 7 опроса, ЧИС.ЛО тактов работы которого определяется числом тактовых и.мпульсов, записанных в него со счетчика 2, увеличенным па значение п. Узел 7 опроса осуществляет считывание содержи.мого регистров 8 и 10 в регистры 13 и 16 и выдачу их содержимого, в результате чего на выходе устройства появляется последовательность символов кода кратчай иего пути из узла-отправителя в узел-получатель.

Последним имьульсом с узла 7 опроса осуществляется возврат всего устройства в исходное состояние (схемы установки в «О на чертеже не показаны во избежание загромождения и вследствие отсутствия оригинальности в решении). Таким образом, если одновременное совпадение всех ера впиваемых разрядов кодов, записанных в регистрах 8 и 9 не наблюдается, то происходит серия последовательных сдвигов вправо содержимого регистра 9 вплоть до того момепта, когда совпадение наступает, после чего работа устройства по формировапию кратчайше1о пути прекращается, а узел 7 Oiipoca производит считывание содержимого регистров 8 и 9 в регистры 13 и 16 и выдачу их содержимого в виде последовательного кода кратчайшего пути на выход устройства. Условие равенста сравниваемых разрядов кодов в регистрах 8 и 9 является необходи.1ым и достаточным для формирования кода кратчайп1его пути в цифровой сети связи, узлы которой имеют адреса, представпмые в виде кодовых последовательностей длины и порядко.м пересечения равны.м «1.

При пересечения сети 2 сдвиг кода в регистре 9 производится в каждом такте на два разряда вправо. С помощью элемента И 12 производитея анализ на четность кода числа узлов сети, записанного в регистре 11. Если число узлов четно, то процедура формирования кратчайшего пути аналогична вьяаеизложенной. Еели чиело вершин нечетно и совпадения кодов в регистрах 8 и 9 при сдвиге на (п - 1) разрядов не произош.то, то производится сдвиг на два разряда вправо, содержимое регистров 8 и 10 передается в регистры 13 и 16, а в (п + 1)-ый разряд регистров 13 и 16 записываются

«1 и «о соответственно, формируемые э.Кмептами И 12 и НЕ 15. Таким o6pa3o i, в регистрах 13 и 16 оказываются два кода кратчайших путей, отличающиеся одппм разрядом. Выбор одного из них осушеств, / ется по вторичном} пр113наку, которым является Ч11сло отказавпщх узлов на крат айшем пути. Коды отказг1впи1х узлов записываются по входу хстройства в регист|) отказавшего узла 14 последовательно один за другим. После загрузки кода отказав1пег() узла в регистр отказавшего узла 14, с помощью групп элеме1ггов 11 17, 18 п элемептов И 23 и 24 осхшествляется сравнение кода отказавп:сго узла с кодами промежуточных узлов на кратчайщих путях, д,тя че1ч) производится цшчлический c.iBnr кодов в регистрах 13 и 16 п на .младшие выходы регистров 13 и 16 поступают последовате,1ьно Г - разрядные коды про.межуточных уз,чов, в результате чего на первые входы групп элемептов П 17 и 18. соединепных с м.тадши.ми разрядами регистров 13 и 16 тступают последовательно п-разрядные коды промежуточных узлов первого п второго кратчайпп1х путем соответственно, а на вторые входы - коды отказавших узлов с регистра 14. После каждого сдвига, групны эле.ментов И 17 и 18 проводят aiia;iu3 па совпадение кодов промежуточных узлов первого и второго кратчайших путей и кода отказавше1Ч) уз.та. При совпадеппп кодов п|юмежуточных уз.тов с кодом отказавшего узла па выходе элементов И 23 и 24 появляется «единичный потенциал, которьп1 фикепруется счетчикаNni 19 li 25. После завершепия циклов сдвига в регистрах 13 и 16, в регистр 14 записывается следующий код отказавшего узла. После того, как коды кратчайших путей проап;1, изированы на всех кодах отказавших узлов, блок сравнения 20 ироводит анализ соде)жимого счетчика 19, открывается эле.мент П 21 или 26, соответствующий счетчику с меньшим. значением, и на выход устройства выдается после.ювательно код кратчайп1его пути с минимальным числом отказавши.ч промежуточных узлов.

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

Формула изобретения

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