Волновая коммутационная ячейка Советский патент 1992 года по МПК G06F7/00 G06F15/16 

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

Известна волновая коммутационная

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

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

Цель изобретения - расширение области применения за счет использования в

ячейка для формирования системы комму- 10 го элемента И-НЕ ячейки соединен со всеми тационнбй сети связи, содержащая п блоков i-ми (, n) выходами группы поиска ячейки,

вторые входы элементов и группы каждого i-ro блока межъячеечной связи являются i- ми входами группы разрядов адреса ячейЭтап формирования канала связи в пло- 15 ки: выходы элементов И группы каждого i-ro

блока межъячеечной связи соединены с соответствующими входами элементов ИЛИ группы, выходы элементов ИЛИ группы соединены со всеми i-ми выходами группы 20 разрядов адреса ячейки и с первой группой входов первой схемы сравнения, вторая группа входов которой подключена к выходам первого регистра, введены два элемента И, иторой регистр и вторая схема сетевых структурах различных конфигура- 25 сравнения, причем первая группа входов ций.второй схемы сравнения подключена к вхоПоставленная цель достигается тем, что в дам элементов ИЛИ группы ячейки, вторая волновую коммутационную ячейку, содер- группа входов второй схемы сравнения под- жащую первый и второй элементы И-НЕ, элемент НЕ, группу элементов ИЛ И, первый 30 регистр, первую схему сравнения, (п+1) блоков межъячеечных связей (где п - количество линий связи, которые соединяют ячейку со смежными ячейками), каждый блок межъ- ячеечнои связи содержит три элемента И- 35 НЕ и группу элементов И, причем первый вход первого элемента И-НЕ каждого 1-го блока межъячеечной связи (1 1, п+1) является i-м входом группы контроля ячейки, второй вход первого элемента И-НЕ каждого i-ro блока межъячеечной связи является i-м входом группы поиска ячейки, третий вход первого элемента И-НЕ каждого i-ro блока межъячеечного связи соединен с выходом элемента НЕ ячейки, выход первого 45 схема волновой коммутационной ячейки; на элемента И-НЕ каждого i-ro блока межъ- фиг.2 - трехуровневая иерархическая коммутационная система,

Ячейка содержит (п+1) блоков 1 межъячеечных связей, регистры 2 и 3, первую и вторую 5 схемы сравнения, первый 6 и второй 7 элементы И, первый 8 и второй 9 элементы И-НЕ, элемент НЕ 10 и группу элементов ИЛИ 11.

Каждый из (п+1)блоков 1 межъячеечных

ключена к выходам второго регистра, выходы равенства и неравенства второй схемы сравнения подключены соответственно к первым входам первого и второго элементов И ячейки, выход второго элемента И ячейки соединен со всеми i-ми выходами группы поиска верхнего уровня ячейки, выход первого элемента И ячейки соединен с выходом поиска нижнего уровня ячейки, второй вход второго элемента И ячейки подключен к выходу первого элемента И-НЕ 40 ячейки и второму входу первого элемента и ячейки, третий вход которого подключен к выходу равенства первой схемы сравнения

На фиг.1 представлена функциональная

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

50

межъячеечной связи, первый вход третьего 55 связей состоит из первого 12, второго 13 и

входы третьих элементов И-НЕ всех блоков межъячеечной связи подключены к выходу второго элемента И-НЕ ячейки, i-e входы элемента И-НЕ являются i-ми входами группы потенциала выделения ячейки, причем выход первого элемента И-НЕ i-ro блока межъячеечной связи соединен с (|+3)-ми входами первых элементов И-НЕ всех блоков межъячеечной связи, кроме 1-го, вход перводам элементов ИЛИ группы ячейки, вторая группа входов второй схемы сравнения под- схема волновой коммутационной ячейки; на фиг.2 - трехуровневая иерархическая коммутационная система,

ключена к выходам второго регистра, выходы равенства и неравенства второй схемы сравнения подключены соответственно к первым входам первого и второго элементов И ячейки, выход второго элемента И ячейки соединен со всеми i-ми выходами группы поиска верхнего уровня ячейки, выход первого элемента И ячейки соединен с выходом поиска нижнего уровня ячейки, второй вход второго элемента И ячейки подключен к выходу первого элемента И-НЕ ячейки и второму входу первого элемента и ячейки, третий вход которого подключен к выходу равенства первой схемы сравнения

На фиг.1 представлена функциональная

50

Изобретение относится к вычислительной и информационной технике и может быть использовано при построении коммутационных систем многопроцессорных вычислительных сетей и абонентских систем связи с децентрализованным управлением на основе волновых коммутационных ячеек Цель изобретения - расширение области применения за счет использования в сетевых структурах различных конфигураций Поставленная цель достигается тем, что устройство содержит п+1 блоков 1 межячееч- ных связей, регистры 2 и 3, первую и вторую схемы 4 и 5 сравнения, первый 5 и второй 6 элементы И, первый 8 и второй 9 элементы И-НЕ, элемент НЕ 10 и группу элементов ИЛИ 11 2 ил Я, hJ ел

элемента И-НЕ каждого i-ro блока межъячеечной связи соединен с выходом второго элемента И-НЕ i-ro блока межъячеечной связи и первыми входами элементов и группы i-ro блока межъячеечной связи, вторые

третьего элементов И-НЕ, а также группы элементов И 15.

Устройство имеет (п+1) адре ных входов 16, (п+1) группу входов 17 поиска, (п+1) группу входов 18 контроля, (п+1) группу входов

19 потенциалов выделения, п адресных выходов 20, (п+1) выходов 21 потенциалов выделения, п выходов 22 группы поиска верхнего уровня, п выходов 23 группы поиска и выход 24 группы поиска нижнего уровня.

Трехуровневая иерархическая волновая коммутационная сеть содержит k макроузлов 25 (где k 1, 2, 3 - номер уровня иерархии макроузла), а каждый макроузел 25 - множество ячеек 26, объединенных внешними входами-выходами 27 в связанные волновые коммутационные подсистемы, внутренние входы-выходы 28 ячеек 26 макроузлов первого (низшего) уровня подключены к абонентам 29, а внутренние входы-выходы ячеек 26 макроузлов других уровней иерархии подключены к внешним входам-выходам 27 граничных ячеек 26 предшествующих по уровню макроузлов.

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

В сформированной цепочке деревьев каналов связи из ячейки-приемника выделяется единственный ствол или канал, соединяющий источник с приемником.

Каждая ячейка системы имеет привязку к соответствующему макроузлу 25k и макроузлу 25k-i низшего уровня, подключенному к данному макроузлу через эту ячейку. Таким образом, ячейка имеет двухкоординат- ную нумерацию, по первой координате указывается номер макроузла, по второй координате - номер ячейки в данном макроузле. Данные номера хранятся в соответствующих регистрах 2 и 3. Если ячейка расположена в макроузле низшего уровня (25i), то номер ячейки совпадает с физическим номером ячейки или соответствующего абонента.

Если ячейка расположена в макроузле 25k более высокого уровня, то номер ячейки равен номеру макроузла, расположенного

0 ниже по уровню иерархии и подключенного к нему.

Полный адрес ячейки-приемника содержит физический номер ячейки-приемника в макроузле низшего уровня и последова5 тельность номеров всех макроузлов, охватывающих данную ячейку-приемник. Так, например, полный адрес ячейки-приемника в трехуровневой системе имеет вид: АО, Аг An, Am, где AQ- физический номер ячейки0 приемника; AI - номер макроузла первого (нисшего) уровня; Аи - номер макроузла второго уровня, охватывающего макроузел Ач; Am - номер макроузла третьего уровня, охватывающего макроузел Аи; А - абонент5 источник 29, подключенный по (п+1)-му входу к соответствующей ячейке 26, формирует на (п+1) входах 16 и 17 соответственно код полного адреса ячейки-приемника и исходный потенциал поиска).

0Потенциал поиска по (п-Н)-му входу 17

поступает на первый вход первого элемента И-НЕ 12 (п+1)-го блока 1 межъячеечных связей, и при отсутствии потенциалов поиска по другим входам 17 включается элемент

5 И-НЕ 12. Нулевой потенциал с выхода пер вого элемента И-НЕ 12 блока 1 инвертируется первым элементом И-НЕ 8 ячейки и в виде единичного потенциала транслируется с первого по n-й выходам 23 в смежные

0 ячейки. Полный адрес ячейки-приемника 26 с (п+1)-го входа адресной шины 16 через включенную (п+1)-ю группу элементов И 15 и группу элементов ИЛИ 11 в параллельном коде транслируется с первого по n-й выхо5 дам 20 в смежные ячейки.

Допустим с первого по n-й входы 16 ячейки одновременно поступает несколько потенциалов поиска. Пусть потенциал поиска поступает одновременно по входам 16ч

0 и 16П. Так как по этого момента на блоки межъячеечной связи не поступали потенциалы поиска, то каждый из элементов И-НЕ 12 имеет разрешение на прием потенциала поиска со стороны остальных блоков межъ5 ячеечной связи. Предположим, что по входам 17i и 17П с блоков аппаратного контроля поступают единичные сигналы, разрешающие прием потенциала поиска. Во время действия потенциала поиска на входы элементов И-НЕ 12i и 12П последние вместе

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

Допустим, что потенциал поиска принимается элементом 12. При этом его инвертируемое значение с выхода элемента 12 прикладывается к входам со второго по (п+1)-й элементов И-НЕ 12, изолируя ячейку по-остальным входам и входу элемента И-НЕ 8. Инвертируясь элементом 8, потенциал поиска распространяется с первого по n-й выходам 23 на смежные ячейки в виде единичного потенциала. Так, в макроузле последовательно формируется концентрически расходящаяся волна потенциала поиска с центром в ячейке-источнике. Эта волна охватывает все исправные и незанятые в данный момент ячейки макроузла. Если ячейка макроузла неисправна по i-му направлению, то по входу 19j с блока аппаратного контроля (не показан) поступает нулевой потенциал, который блокирует поступление потенциала поиска в i-м блоке межъячеечный связей. В этом случае неисправное i-e направление ячейки автоматически обходится на этапе поиска и не включается в канал связи.

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

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

Составляющие полного адреса AI и АО с выходов групп элементов ИЛИ 11 поступа- ют соответственно на первые входы схем 4 и 5 сравнения. На вторые входы данных схем с выходов регистров 2 и 3 поступают компоненты полного номера ячейки: физический номер макроузла и физический номер ячейки данного макроузла. При достижении волной поиска искомой ячейки срабатывают схемы 4 и 5 сравнения и на выходе элемента И 6 формируется единичный потенциал поиска нижнего уровня, который по выходу 24 транслируется в соответствующий абонент, запрашивая его об обмене. Абонент в ответ на запрос формирует нулевой потенциал выделения, который по (п+1)-му входу 19 поступает на элемент И-НЕ 9 соответствующей ячейки- приемника, инвертируется этим элементом и в форме единичного потенциала поступает на первые входы с первого по (п+1)-й элементов И-НЕ 14 блоков 1 межъячеечных связей. Элементы И-НЕ 13 и 14 с обратными связями образуют схему защелки, с помощью которой потенциал выделения фиксирует состояние блоков 1 межъячеечных связей.

Так, если на выходе элемента 12| был нулевой потенциал (что соответствует прохождению потенциала поиска через i-й блок 1 межъячеечных связей), то на втором входе элемента 14| удерживается единичный потенциал. Следовательно, с поступлением нулевого потенциала выделения по одному из (п+1 , входов 19 на выходе элемента 14i формируется нулевой потенциал выделения, который запоминается элементами 13i и 14j с обратными связями и по шине 21; поступает на смежную ячейку. Если обнулить потенциал поиска на входе данной ячейки, то ее состояние не изменится, поскольку оно зафиксировано потенциалом выделения.

Входной потенциал выделения с выхода элемента И-НЕ 9 через элемент НЕ 10 блокирует все блоки 1 межъячеечных связей, изолируя ячейку на время работы канала, и обнуляете первого по n-й выходы 23 выдачи потенциала поиска, освобождая все те же ячейки макроузла, которые подвергались действию волны поиска, но не вошли.в формируемый канал связи, Процесс выделения канала связи начинается с ячейки-приемника и, последовательно охватывая все ячейки канала связи, завершается в ячейке-источнике. Нулевой потенциал выделения поступает в ячейку-источник по одному из входов 19 и транслируется по (п+1)-му выходу 21 в абонент, квитируя его запрос на установление канала связи. Данный сигнал информирует абонент-источник об установлении канала связи и возможности начала обмена.

По окончании обмена абонент-приемник отключает нулевой потенциал выделения по(п+1)-му входу 19. На входе элемента И-НЕ 9 формируется нулевой потенциал, который отключает с первого по (п+1)-й элементы И-НЕ 14, формирующие выходные потенциалы выделения, Происходит последовательное снятие нулевого потенциала выделения в ячейках канал-: от ячейки-приемника до ячейки-источника. С

момента исчезновения потенциала выделения на выходе элемента НЕ 10 ячейка освобождается и может быть использована для образования нового канала связи.

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

Потенциалы поиска верхнего уровня транслируются по шине 22 по всем внешним направлениям, но воспринимаются эти потенциалы лишь по внутренним направлениям ячеек вышерасположенного макроузла.

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

Волна поиска распространяется по ячейкам вышерасположенного макроузла 25i. Этот процесс устанавливается адресными регистрами 2 и 3, в макроузле 25i (первого) уровня. Но в регистре 2 ячеек макроузла 252 (второго) уровня записаны физические номера нижерасположенных макроузлов, а в регистре 3 - физический номер данного макроузла второго уровня. Соответственно на адресные входы схем 4 и 5 сравнения заводятся адреса AI и Аи. Если искомый макроузел подключен к данному макроузлу, то срабатывают обе схемы 4 и 5 сравнения, сигналы равенства с выходов этих схем включают элемент И 6, на выходе которого формируется единичный потенциал поиска нижнего уровня. Потенциал поиска нижнего уровня по внутреннему выходу транслируется в нижерасположенный макроузел, где он воспринимается граничными ячейками по одному или нескольким внешним направлениям. Волна поиска достигает искомой ячейки данного макроузла, которая в ответ на поступление потенциала по шине 24 формирует на (п+1)- м входе 19 нулевой потенциал выделения. Потенциал выделения в макроузле-приемнике формирует единственный канал связи, который продолжается через граничную ячейку в вышерасположенном макроузле и завершается в макроузле-источнике.

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

Если искомый макроузел не подключен к данному макроузлу (не охватывает данный

макроузел), то на выходе несравнения схемы 5 всех ячеек формируются единичные потенциалы, которые включают элементы И 7 и на всех выходах 22 формируются потенциалы поиска верхнего уровня. Волна поиска направляется в вышерасположенный макроузел третьего уровня. В регистрах 2 и 3 ячеек этого макроузла записаны соответственно физические номера нижерасположенных макроузлов и физический номер

данного макроузла. Соответственно на адресные входы схем 4 и 5 сравнения заводятся адреса Аи и Am,

В остальном работа ячеек макроузла третьего уровня аналогична работе нижерасположенных ячеек.

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

30

5

0

5

0

5

Формула изобретения Волновая коммутационная ячейка, содержащая первый и второй элементы И-НЕ, элемент НЕ, группу элементов ИЛИ, первый регистр, первую схему сравнения, п+1 блоков межъячеечных связей, где п - количество линий связи, которые соединяют ячейку со смежными ячейками), каждый блок межьячеечной связи содержит три элемента И-НЕ и группу элементов И, причем первый вход первого элемента И-НЕ каждогр -го блока межъячеечной связи (i 1, п+1) является i-м входом группы контроля ячейки, второй вход первого элемента И-НЕ каждого i-ro блока межъячеечной связи является i-м входом группы поиска ячейки, третий вход первого элемента И-НЕ каждого i-ro блока межъячеечной связи соединен с выходом элемента НЕ ячейки, выход первого элемента И-НЕ каждого i-ro блока межъячеечной связи подключен к i-му входу первого элемента И-НЕ ячейки и первому входу второго элемента И-НЕ i-ro блока межъячеечной связи, второй вход второго элемента И-НЕ каждого i-ro блока межъячеечной связи является i-м выходом группы потенциала выделения ячейки и соединен с выходом третьего элемента И-НЕ i-ro блока межъячеечной связи, первый вход третьего элемента И-НЕ каждого i-ro блока межъячеечной связи соединен с выходом второго элемента И-НЕ i-ro блока межъячеечной связи и первыми входами элементов И группы 1-го блока связи, вторые входы третьих элементов И-НЕ всех блоков межъячеечных связей подключены к выходу второго элемента И-НЕ ячейки, i-e входы элемента И-НЕ являются i-ми входами группы потенциала выделения ячейки, причем выход первого элемента И-НЕ 1-го блока соединен с (1+3)-ми входами первых элементов И-НЕ всех блоков межъячеечных связей, кроме i-ro, выход первого элемента И-НЕ ячейки соединен со всеми j-ми (j 1, п) выходами группы поиска ячейки, вторые входы элементов И группы каждого i-ro блока связи являются i-ми входами группы разрядов адреса ячейки, выходы элементов И группы каждого i-ro блока связи соединены с соответствующими входами элементов ИЛИ группы, выходы элементов ИЛИ группы соединены со всеми j-ми выходами группы разрядов адреса ячейки и с первой группой входов первой схемы сравнения, вторая

0

5

0

5

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