СЕТЬ ДЛЯ МАРШРУТИЗАЦИИ СООБЩЕНИЙ Российский патент 1998 года по МПК G06F15/16 G06F15/163 H04L12/56 

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

Известна вычислительная система для параллельной обработки информации (см. патент Великобритании 2227341, кл. G 06 F 13/38, НКИ G 4 A, публ. 25.07.90, N 30), содержащая по меньшей мере три узла, каждый из которых используется для обработки потока данных и содержит средства для маршрутизации информации между узлами, что дает возможность резервирования определенного тракта передачи данных по сети узлов. Сообщения могут быть переданы из одного исходного узла в узел назначения по зарезервированному тракту. Использование устройства резервирования тракта позволяет сократить требования к буферизации информации в промежуточных узлах, уменьшить время ожидания при пропускании информации по сети и повысить общую скорость передачи информации между узлами. При этом обеспечивается синхронная передача сообщений между узлами.

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

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

Известна также параллельная вычислительная система для обмена информацией между узлами (патент Великобритании 2249243, кл. H 04 L 12/56, 12/42, НКИ H 4 P, публ. 29.04.92, N 18), имеющая усовершенствованную архитектуру по сравнению с системой, заявленной в патенте Великобритании N 2227341. Эта вычислительная система объединяет по крайней мере три узла. Каждый узел в такой системе служит для обработки информации и для маршрутизации и передачи информации между узлами. Средства маршрутизации узла позволяют резервировать маршрут в сети. Таким образом, сообщения могут передаваться от исходного узла к узлу назначения по зарезервированному маршруту. Использование системы резервирования маршрута снижает требования к буферизации информации в промежуточных узлах маршрута, уменьшает время ожидания прохождения сообщений и увеличивает межузловую пропускную способность. Обмен сообщениями между узлами в синхронном режиме осуществляется с помощью стробирующего сигнала, модифицируемого в узлах путем восстановления фронтов сигнала для того, чтобы сократить сжатие импульса сигнала строба.

Изобретение по патенту Великобритании N 2249243 охватывает вычислительную систему, имеющую множество обрабатывающих узлов, соединенных между собой в двоичный n-куб. Каждый узел имеет средства для обработки информации и маршрутизации ее между узлами n-куба. Маршрутизатор осуществляет прием адресной информации от средств обработки и посылает ее от узла к узлу для построения маршрута связи информации от исходного узла к узлу назначения. После того, как маршрут связи установлен, узел назначения посылает ответ по тому же маршруту, в обратном порядке с подтверждением готовности к приему информации. Затем начинается передача информации по зарезервированному маршруту. По завершении передачи информации маршрут освобождается и каналы, используемые маршрутом, становятся открытыми для связи между другими узлами. Каждое средство маршрутизации объединяет два канала для передачи информации. Первый канал используется для передачи информации от узла к смежному узлу, а второй - для получения от соседнего узла. Передача информации между узлами осуществляется с помощью синхронизирующих сигналов, передаваемых вместе с информацией. Каждый канал включает средства передачи информации (собственно данных сообщения и информации управления состоянием), а также средства передачи синхронизирующих сигналов, для управления отправкой и получением информации.

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

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

Наиболее близким техническим решением к заявляемому является сеть для маршрутизации сообщений (см. патент Великобритании 2251356, кл. H 04 L 12/56, НКИ H 4 K, публ. 30.08.91), включающая первую сеть, имеющую множество узлов, каждый из которых имеет устройство маршрутизации, связанных между собой каналами первой сети для маршрутизации сообщений между узлами, и вторую сеть с множеством узлов, каждый из которых имеет устройство маршрутизации, а узлы связаны с помощью каналов второй сети для маршрутизации сообщений между узлами. Каждый маршрутизатор во второй сети соединен по крайней мере с одним из маршрутизаторов первой сети с помощью Z-каналов для маршрутизации сообщений между узлами каждой сети; первая и вторая сети имеют одинаковые размеры. Средства маршрутизации сообщений размещены внутри каждого маршрутизатора этих двух сетей, при этом маршрутизация сообщений происходит от узла-источника к узлу назначения через каналы первой сети и каналы второй сети. В случае недоступности необходимого канала первой сети или второй сети маршрутизация происходит с помощью средств маршрутизации сообщений между первой и второй сетью по Z каналам.

В предпочтительном примере осуществления этого решения в описании к патенту 2251356 описывается первая многомерная сеть маршрутизации, обозначенная A, включающая множество узлов обработки. Каждый узел включает средства обработки информации и блок прокладки маршрута для маршрутизации информации (т.е. сообщений) между узлами сети. Чтобы улучшить эффективность маршрутизации сообщений, проходящих через схему в сети A, вторая многомерная сеть маршрутизации из блоков прокладки маршрута, обозначенная B, соединяется с сетью A. Сети A и B имеют одинаковую топологию и измерение. Блок прокладки маршрута имеет X-координату и Y-координату в соответствующей сети. Блок прокладки маршрута в конкретных координатах в сети A соединяется с блоком прокладки маршрута в соответствующих координатах в сети B через каналы, обозначенные Z.

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

Первый канал применяется для передачи информации между блоком прокладки маршрута и процессором, соединенным с блоком прокладки маршрута.

Второй канал применяется для передачи информации между блоками прокладки маршрута в X направлении.

Третий канал применяется для передачи информации между блоками прокладки маршрута в Y направлении.

Четвертый канал применяется для передачи информации между блоками прокладки маршрута в Z направлении.

Сообщения, передаются в сети A и B путем использования информации о маршрутизации, содержащейся в каждом сообщении.

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

В течение передачи сообщения в X и Y измерениях, если канал немедленно не предоставляется, запрос делается для Z канала. Запрос для X или Y канала и запрос для Z канала поддерживаются до тех пор, пока не будет представлен один канал. Сообщение передается на предоставленный канал, а другой запрос отменяется. Если оба запрашиваемых канала (X или Y) и Z канал находятся в состоянии занятости, то сообщение блокируется и не передается на Z канал.

Блок прокладки маршрута не фиксируется для маршрутизации на канале до тех пор, пока канал не будет представлен. Заголовок обычной маршрутизации адреса не изменяется при переходе через Z измерение. Когда сообщение поступает на блок прокладки маршрута узла назначения, сообщение передается на канал, связанный с процессором. Этот метод адаптивной маршрутизации требует, чтобы блок прокладки маршрута проверял адрес маршрутизации для определения, поступило ли сообщение в узел назначения. Такая проверка выполняется всякий раз, когда сообщение переходит Z измерение. Если имеет место переход от первой сети ко второй и все желаемые каналы второй сети недействительны, сообщение будет блокироваться и не будет передаваться на Z канал.

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

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

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

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

Изобретение поясняется чертежами, где на фиг. 1 изображен пример реализации для четырехмерной сети, на фиг. 2 - 4 - узел коммутации сети, на фиг. 5 - маршрутизатор, на фиг. 6 - схема определения оптимальных маршрутов, на фиг. 7 - блок прокладки адаптивных маршрутов, на фиг. 8 - блок прокладки неадаптивных маршрутов, на фиг. 9 - блок программирования, на фиг. 10 - коммутатор каналов, на фиг. 11 - коммутатор буферов, на фиг. 12 - буфер, на фиг. 13 - выходной автомат, на фиг. 14 - входной автомат, на фиг. 15 - приемник, на фиг. 16 - 17 - передатчик, на фиг. 18 - арбитр буферов, на фиг. 19 - арбитр маршрутизатора, на фиг. 20 - схема сравнения, на фиг. 21 - схема кодирования ответов блока прокладки адаптивных маршрутов, на фиг. 22 - таблица соответствия входных и выходных сигналов схемы кодирования ответов, на фиг. 23 - схема шифратора, на фиг. 24 - таблица соответствия входных и выходных сигналов шифратора, на фиг. 25 - дешифратор блока прокладки неадаптивных маршрутов, на фиг. 26 - схема кодирования ответов блока прокладки неадаптивных маршрутов, на фиг. 27 - 31 - блок-схема алгоритма работы маршрутизатора, на фиг. 32 - 33 - пример маршрутизации сообщения в сети.

Работа сети возможна как в синхронном, так и в асинхронном режиме.

Пример реализации изобретения приведем для синхронной сети, построенной на основе линейной N-мерной решетки с отдаленными связями, которая строится следующим образом:
- задается требуемая размерность сети;
- каждому узлу сети присваивается обозначение в виде последовательности координат в сети;
- все смежные узлы соединяются между собой;
- добавляются связи между отдаленными узлами.

Число узлов в сети должно быть равно произведению протяженности решетки по каждой координате сети. Смежные узлы - это узлы, у которых отличается не более одной координаты и не более, чем на 1. При этом максимальное расстояние между узлами решетки будет равно сумме протяженности решетки по каждой координате минус N. Связи между отдаленными узлами сети позволяют сократить это расстояние при прокладке маршрута.

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

Приведенный пример четырехмерной сети для маршрутизации сообщений (см. фиг. 1) содержит множество узлов коммутации, например, 1.0, 1.1, ..., 1.P, . . . , 1R и т.д. Узлы коммутации соединены между собой посредством каналов связи, например, 2(1.0, 1.2), 2(1.2, 1.5) и т.д.

В соответствии с измерениями четырехмерной решетки в сети выделяются четыре направления (координаты X1, X2, X3 и X4), определяющие размерность сети и координаты всех узлов коммутации. Так, для приведенной сети размерность составляет: в направлении X1 - F, где F > 5; в направлении X2 - 2; в направлении X3 - 2; в направлении X4 - 2. Основа топологии определяется каналами связи между смежными узлами коммутации. Так, например, для узла коммутации 1.0 связь с четырьмя смежными узлами 1.1, 1.2, 1.3, 1.4 по всем четырем направлениям X. 1, X. 2, X. 3, X.4 осуществляется посредством каналов связи 2(1.0,1.1), 2(1.0, 1.2), 2(1.0, 1.3) 2(1.0, 1.4) соответственно.

Полная топология представленной сети определяется помимо описанных связей дополнительными каналами связи между отдаленными узлами коммутации. Так, например, канал связи 2(1.0, 1.P) соединяет два отдаленных узла коммутации 1.1 и 1.P, координаты которых в направлении X1 отличаются более, чем на единицу.

В узле коммутации 1 входные каналы 2.1.1,...,2.N.1 соединены с канальными входами-выходами адаптеров входных каналов 3.1,...,3.N соответственно (см. фиг.2 - 4). Входы адаптеров входных каналов 3.1,...,З.N соединены с выходами ответов DO входных автоматов 4.1,...,4.N соответственно. Инжекционные каналы 5.1,...,5.M соединены с канальными входами-выходами передатчиков 6.1, . . .,6.M соответственно. Выходы запросов RQ входных автоматов 4.1,...,4.N и передатчиков 6.1,...,6.M соединены с группой входов запроса арбитра буферов 7, группа выходов разрешения EN которого соединена со входами разрешения входных автоматов 4.1, ...,4.N и передатчиков 6.1,..., 6.M. Группа выходов номера источника NI арбитра буферов 7 соединена с группой входов номера источника коммутатора буферов 8, группа выходов ответа DO которого соединена с первыми входами ответа входных автоматов 4.1,...,4.N и передатчиков 6.1,..., 6. M. Группа выходов выбора CS арбитра буферов 7 соединена с группой входов выбора коммутатора буферов 8 и со входами выбора буферов 9.1,..., 9.K, информационные входы DI которых соединены с группой информационных выходов коммутатора буферов 8, группа входов ответов DO которого соединена с выходами ответов буферов 9.1,..,9.K, выходы занятости WS которых соединены с группами входов занятости арбитра буферов 7 и коммутатора буферов 8. Выходы запросов RQ буферов 9.1,...,9.K соединены с группой входов запроса арбитра маршрутизатора 10, группа выходов разрешения EN которого соединена со входами разрешения буферов 9.1,...,9.K и группой входов разрешения коммутатора буферов 8. Информационные выходы буферов DI объединены и соединены с группой информационных входов маршрутизатора 11, группа выходов ответов DO которого соединена с группами входов ответа буферов 9.1,...,9.K. Выход подтверждения информации ED арбитра маршрутизатора 10 соединен с одноименным входом маршрутизатора 11, выход блокировки LK которого соединен со входом блокировки арбитра буферов 10. Выходы адаптеров каналов 3.1,...,З.N соединены с информационными входами входных автоматов 4.1,...,4.N соответственно. Группы информационных входов коммутатора буферов 8 и коммутатора каналов 12 объединены и соединены с выходами адаптеров канала 3.1,..., 3.N и информационными выходами передатчиков 6.1,...,6.M. Вторые входы ответов DO входных автоматов 4.1, . ..,4.N и передатчиков 6.1,...,6.N соединены с группой выходов ответов коммутатора каналов 12, группа входов номера источника NI которого объединена с одноименной группой входов маршрутизатора 11 и соединена с группой выходов номера источника коммутатора буферов 8. Группа выходов выбора CS маршрутизатора 11 соединена с группой входов выбора коммутатора каналов 12 и входами выбора выходных автоматов 13.1,...,13.N и приемников 14.1,...,14.L. Выходы занятости WS выходных автоматов 13.1,..., 13.N и приемников 14.1,..., 14. L соединены с группами входов занятости маршрутизатора 11 и коммутатора каналов 12, группа входов ответов DO которого соединена с выходами адаптеров выходных каналов 15,1,..., 15.N и выходами ответов приемников 14.1,...,14.L. Выходы адаптеров выходных каналов 15.1...,15.N соединены с входами ответов DO выходных автоматов 13.1,...,13.N. Группа информационных выходов DI коммутатора каналов 12 соединена со входами адаптеров выходных каналов 15.1,... , 15. N и информационными входами приемников 14.1,...,14.L, канальные входы-выходы которых соединены с реципиентными каналами 16.1,...,16.L. Канальные входы-выходы адаптеров выходных каналов 15.1,...,15.N соединены с выходными каналами 2.1.2,...,2.N.2.

Канал сети образуется соединением входного канала 2.n.1 узла коммутации, например, 1.0, с выходным каналом 2.s.2 узла коммутации, например, 1.1, и соединением выходного канала 2.s.2 узла коммутации 1.0 со входным каналом 2. s.1 узла коммутации 1.1.

В маршрутизаторе (см. фиг. 5) группа информационных входов соединена с группами информационных входов схемы сравнения 17, схемы определения оптимальных маршрутов 18, блока прокладки неадаптивных маршрутов 19 и блока прокладки адаптивных маршрутов 20, группа входов оптимальных маршрутов которого соединена с группой выходов схемы определения оптимальных маршрутов 18. Выход схемы сравнения 17 соединен со входом равенства блока прокладки адаптивных маршрутов 20, группы выходов ответа которого объединены с одноименными группами выходов блока прокладки неадаптивных маршрутов 19, а также являются соответствующими выходами маршрутизатора 11, группа входов номера источника которого соединена с группой входов номера источника блока прокладки адаптивных маршрутов 20. Вход готовности данных маршрутизатора 11 соединен с входами разрешения блоков прокладки неадаптивных 19 и адаптивных маршрутов 20 и блока программирования 22, группа выходов программирования которого соединена с группами входов программирования блока прокладки адаптивных маршрутов 20, схем сравнения 17 и определения оптимальных маршрутов 18. Группа входов занятости маршрутизатора 11 соединена с группами входов занятости блоков прокладки неадаптивных 19 и адаптивных 20 маршрутов, входы блокировки которых объединены с выходом блокировки маршрутизатора 11 и с выходом блокировки блока программирования 22, стартовый вход которого соединен с выходом программирования блока прокладки неадаптивных маршрутов 19. Первая группа выходов выбора блока прокладки неадаптивных маршрутов соединена с первыми входами группы элементов 21 ИЛИ, вторые входы которых соединены с группой выходов выбора блока прокладки адаптивных маршрутов. Выходы группы элементов 21 ИЛИ и вторая группа выходов выбора блока прокладки неадаптивных маршрутов являются выходами выбора маршрутизатора.

В схеме определения оптимальных маршрутов 18 (см. фиг. 6) группа информационных входов соединена с группами информационных входов регистров маски 23.1,...,23.N, координаты 24.1,...,24.N, условия 25.1,...,25.N, связи 26.1,. ..,26.N и первыми входами групп элементов 27.1,...,27.N, вторые входы которых соединены с группами выходов регистров маски 23.1,..., 23.N. Группа входов программирования схемы 18 определения оптимальных маршрутов соединена с входами записи регистров маски 23.1,..., 23.N, координаты 24.1,...,24.N, условия 25.1,...,25.N, связи 26.1,..., 26.N. Выходы групп элементов 2И 27.1, . . .,27.N соединены с первыми группами входов схем сравнения 28.1,.., 28.N, вторые группы входов которых соединены с группами выходов регистров координат 24.1,.., 24.N. Выходы схем сравнения 28.1,...,28.N соединены с первыми входами элементов 29.1,..,29.N, 2-2-2-И-ЗИЛИ вторые входы которых соединены с выходами регистров условий 25.1,...,25.N. Выходы элементов 29.1,...,29.N соединены с первыми входами групп элементов ИЛИ 30.1,..,З0.N, вторые входы которых соединены с выходами регистров связи 26.1,..,26.N. Выходы групп элементов 30.1, . .,30.N ИЛИ соединены со входами элементов 31.1,..,31.N, И выходы которых и являются выходами схемы определения оптимальных маршрутов.

В блоке прокладки адаптивных маршрутов 20 (см. фиг. 7) группа входов оптимальных маршрутов соединена с прямыми входами группы элементов 33 И и информационными входами мультиплексора 39, адресные входы которого и объединены со входами дешифратора 32 и соединены с группой входов номера источника. Группа информационных входов блока прокладки адаптивных маршрутов соединена с информационными входами регистра 34 числа и регистра 35 связей и с первым входом элемента 36 И, второй и инверсный входы которого соединены с входами разрешения и блокировки соответственно блока прокладки адаптивных маршрутов, группа входов программирования которого соединена со входами записи регистров 34 числа и 35 связей. Выходы группы элементов 33 И соединены с прямыми входами группы элементов 37 И и входами сумматора 38. Выходы дешифратора 32 соединены с инверсными входами группы элементов 33 И. Выходы сумматора 38 соединены с первыми входами схемы сравнения 40, вторые входы которой соединены с выходами регистра 34 числа. Выходы группы элементов 37 И соединены с первыми входами групп элементов 41 И, с прямыми входами группы элементов 42 И и входами элемента 45 ИЛИ.

Группа входов занятости блока прокладки адаптивных маршрутов соединена с инверсными входами группы элементов 37 И и первыми инверсными входами группы элементов 43 И, вторые инверсные входы которой объединены с инверсными входами группы элементов 42 И и вторыми входами групп элементов 41 И и соединены с выходами регистра 35 связей. Выходы группы элементов 41 И соединены со входами приоритетного шифратора 47 и входами элемента 44 ИЛИ. Выходы группы элементов 42 И соединены со входами приоритетного шифратора 48. Вход равенства блока прокладки адаптивных маршрутов соединен с третьим входом схемы 49 кодирования ответов, группа выходов которого является группой выходов ответов блока прокладки адаптивных маршрутов. Выходы группы элементов 43 И соединены со входами элемента 46 ИЛИ и приоритетного шифратора 50. Выход элемента 36 И соединен с пятым входом схемы 49 кодирования ответов, первый вход которой объединен с прямым входом разрешения приоритетного шифратора 48, инверсным входом разрешения приоритетного шифратора 50 и соединен с выходом элемента 45 ИЛИ. Выход мультиплексора 39 соединен со вторым входом схемы кодирования ответа 49, четвертый вход которой соединен с выходом схемы сравнения 40. Выход схемы 46 ИЛИ соединен с шестым входом схемы 49 кодирования ответов, выход разрешения которой соединен с входом разрешения дешифратора 51, группа выходов которого является группой выходов выбора блока прокладки адаптивных маршрутов. Выходы приоритетных шифраторов 47, 48 и 50 объединены со входами дешифратора 51. Выход элемента 44 ИЛИ соединен со входом разрешения приоритетного шифратора 47 и инверсным входом разрешения приоритетного шифратора 48.

В блоке прокладки неадаптивных маршрутов 19 (см. фиг. 8) группа информационных входов соединена со входами дешифратора 52, выходы которого соединены с прямыми входами группы элементов 53 И, инверсные входы которой соединены с группой входов занятости блока прокладки неадаптивных маршрутов, вход блокировки которого соединен с инверсным входом дешифратора 52. Выходы группы элементов 53 И соединены со входами шифратора 54, выход готовности которого соединен со вторым входом схемы 55 кодирования ответов и входом разрешения дешифратора 56, выходы которого являются двумя группами выходов выбора блока прокладки неадаптивных маршрутов, группа выходов ответа которого является выходами схемы 55 кодирования ответов, первый вход которой соединен с выходом готовности дешифратора 52. Группа выходов дешифратора 54 соединена с группой входов дешифратора 56. Вход готовности данных блока 19 соединен со вторым входом дешифратора 52, выход программирования которого соединен с выходом программирования блока 19, вход блокировки которого соединен с третьим входом схемы 55 кодирования ответов.

9 В блоке программирования 22 (фиг. 9) стартовый вход соединен со входом установки триггера 57, выход которого соединен с инверсным входом сброса счетчика 58 и является выходом блокировки блока программирования, вход готовности которого соединен со счетным входом счетчика 58 и входом разрешения дешифратора 59, остальные входы которого соединены с выходами счетчика 58. Выходы дешифратора 59 являются группой выходов программирования блока программирования. Вход сброса триггера 57 соединен с последним выходом дешифратора 59.

В коммутаторе каналов 12 (см. фиг. 10) группа входов номера источника соединена с информационными входами регистров 60.1,...,60.N+L, входы записи которых соединены с группой входов выбора коммутатора каналов, группа информационных входов которого соединена с информационными входами мультиплексоров 61.1, . ..,61.N+L. Группа входов ответов коммутатора каналов соединена с информационными входами демультиплексоров 62.1,..., 62.N+L; n-й вход занятости группы входов занятости коммутатора каналов соединен со входами разрешения мультиплексора 61. n и демультиплексора 62.n, адресные входы которых соединены с выходами регистра 60.n. Выходы мультиплексоров 61.1,..., 61.N+L являются группой информационных выходов коммутатора каналов, группой выходов ответов которого являются выходы элементов ИЛИ 63.1,.., 63.N+L, k-й вход элемента 6З.n ИЛИ соединен с n-м выходом демультиплексора 62.k.

В коммутаторе буферов 8 (см. фиг. 11) группа входов номера источника соединена с информационными входами регистров 64.1,...,64.K, входы записи которых соединены с группой входов выбора коммутатора буферов, группа информационных входов которого соединена с информационными входами мультиплексоров 65.1, ...,65.K. Группа входов ответов коммутатора буферов соединена с информационными входами демультиплексоров 66.1,..,66.K; k-й вход занятости группы входов занятости коммутатора буферов соединен со входами разрешения мультиплексора 65.k и демультиплексора 66.k, адресные входы которых соединены с выходами регистра 64.k. Выходы мультиплексоров 65.1,..., 65.K являются группой информационных выходов коммутатора буферов, группой выходов ответов которого являются выходы элементов ИЛИ 67.1,...,67.N; k-й вход элемента ИЛИ 67.n соединен с n-м выходом демультиплексора 66.k. Входы разрешения коммутатора буферов соединены со входами разрешения буферных элементов 68.1,...,68. K, объединенные выходы которых являются выходами номера источника коммутатора буферов. Информационные входы буферного элемента 68.k соединены с выходами регистров 64.k.

В буфере 9 (см. фиг. 12) вход выбора соединен с входом установки J триггера 69 занятости буфера, выход которого является выходом занятости буфера 9. Вход разрешения буфера соединен с входом установки J триггера 70 разрешения сброса и с входом E разрешения записи регистра 71 ответа, информационные входы которого являются группой входов ответа буфера 9. Входы элемента 72 ИЛИ соединены с выходами регистра 71 ответа и триггера 70 разрешения сброса, выход элемента 72 ИЛИ соединен с входами сброса К триггеров 69 занятости буфера и 70 разрешения сброса. Тактовые входы триггеров 69 занятости буфера и 70 разрешения сброса, регистров 71 ответа и 73 информационного соединены с шиной синхронизации. Информационный вход DI буфера 9 соединен с информационным входом регистра 73 информационного, вход R сброса которого соединен с входом разрешения буфера 9, который соединен также входом E разрешения буферного элемента 74, информационные входы D которого соединены с выходами информационного регистра 73, выход старшего разряда которого соединен со своим входом E разрешения сдвига и является выходом запроса буфера 9, информационные выходы которого соединены с выходами буферного элемента 74. Выход ответа буфера 9 соединен с выходом старшего разряда регистра 71 ответа.

В выходном автомате 13 (фиг. 13) вход выбора соединен со входом установки J триггера 75, выход которого является выходом занятости выходного автомата 13, вход ответа которого соединен с входом D регистра сдвига 76, тактовый вход C которого, а также тактовый вход триггера 75 соединены с шиной синхронизации сети. Выходы регистра 76 сдвига соединены со входами дешифратора 77 ответов, выход которого соединен со входом сброса K триггера 75 и входом сброса R регистра 76 сдвига.

Информационный вход входного автомата 4 соединен с входом установки J триггера 78 запроса (см. фиг. 14), выход которого является выходом запроса входного автомата, вход разрешения которого соединен со входом установки J триггера 79 занятости, выход которого соединен со входом сброса R триггера 78 запроса. Первый вход ответа входного автомата 4 соединен со входом D регистра 80, а также с первым входом дешифратора 81 ответов буфера, остальные входы которого соединены с выходами регистра 80, вход сброса R которого соединен с вторым выходом дешифратора 81 ответов буфера. Второй вход ответа входного автомата соединен с входом D регистра 82, а также с первым входом (дешифратора 83 ответов канала, остальные входы которого соединены с выходами регистра 82, вход сброса R которого соединен с вторым выходом дешифратора 83 ответов канала. Тактовые входы C триггеров 78 и 79 и регистров 80 и 82 соединены с шиной синхронизации сети. Первые выходы дешифраторов 81 ответов буфера и 83 ответов канала соединены со входами элемента 84 ИЛИ, выход которого соединен с входом сброса R триггера 79 занятости. Выходом ответов входного автомата 4 является выход элемента 85 ИЛИ, входы которого соединены с входом разрешения входного автомата 4 и первыми выходами регистров 80 и 82.

В приемнике 14.l (см. фиг. 15) информационный вход соединен с входом D регистра 86 данных, выходы которого соединены с входами буферного элемента 87, выходы которого являются информационными выходами реципиентного канала 16. l. 1. Старший разряд регистра 86 данных соединен с входом E регистра 86 данных и входом S триггера 88 требования канала, выход которого является выходом требования реципиентного канала 16. l.2. Вход 16.l.3 реципиентного канала соединен со входами E разрешения записи и D2 информационным регистра 89 ответа, с входом сброса R триггера 88, входом E разрешения выдачи буферного элемента 87. Вход 16.l.4 последнего цикла реципиентного канала соединен со входом D0 регистра 89 ответа и входом установки J триггера 90 сброса канала, инверсный выход которого соединен со входом элемента 91 ИЛИ-НЕ, остальные входы которого соединены с выходами регистра 89 ответа, старший из которых соединен со входом R разрешения сброса регистра 86 данных, а также является выходом ответа приемника 14.l, вход выбора которого соединен с входом установки J триггера 92 занятости, выход которого является выходом занятости приемника 14. l, а инверсный выход соединен с входом сброса K триггера 90 сброса канала. Выход элемента 91 ИЛИ-НЕ соединен со входом сброса K триггера 92 занятости. На входы D1 и D3 регистра 89 ответа подается уровень логического нуля. Тактовые входы регистров 86 данных и 89 ответа и триггеров 90 сброса канала и 92 занятости соединены с шиной синхронизации коммутатора.

В передатчике 6.m (см. фиг. 16 и 17) информационные входы 5.m.1 инжекционного канала 5.m соединены с информационными входами регистра 93 данных, вход C разрешения записи которого соединен со входом 5.m.2 записи инжекционного канала 5.m. На вход D0 мультиплексора 94 подается уровень логического нуля, на вход D1 - уровень логической единицы, остальные D входы мультиплексора 94 соединены с выходами регистра 93 данных. Выходы счетчика 95 соединены с адресными входами мультиплексора 94 и входами дешифратора 96, выход которого соединен с инверсным входом E1 разрешения счетчика 95 и входами E разрешения регистра 97 ответов и дешифратора 98 ответов. Первый и второй входы ответов передатчика 6.m соединены с входами элемента 99 ИЛИ, выход которого соединен с D входом регистра 97 ответов, выходы которого соединены со входами дешифратора 98 ответов. Входы сброса R счетчика 95 и регистра 97 ответов соединены с выходом элемента 100 ИЛИ, первый, второй, третий, четвертый и пятый входы которого соединены с первым, вторым, третьим, четвертым и пятым выходами дешифратора 98 ответов соответственно. Информационный выход передатчика 6. m соединен с выходом элемента 101 ИЛИ, первый вход которого соединен с выходом мультиплексора 94, второй, третий и четвертый входы - с третьим, четвертым и пятым выходами дешифратора 98 ответов соответственно, а пятый вход - с выходом элемента 102 И, первый вход которого соединен со входом записи 5.m.2 инжекционного канала 5.m.

Входы элемента 103 ИЛИ соединены с вторым, третьим и пятым выходами дешифратора 98 ответов, а выход - с входом установки J триггера 104, инверсный выход которого соединен с вторым входом элемента 105 И, выход которого соединен с входом установки J триггера 106, выход которого является выходом запроса передатчика 6.m. Входы сброса K триггеров 104 и 106 соединены с входом разрешения передатчика 6.m. Первый вход элемента 105 И соединен с выходом элемента 101 ИЛИ. Входы элемента 107 ИЛИ соединены с первым и вторым выходами дешифратора 98 ответов, а выход - со входом установки J триггера 108, вход сброса K которого соединен с входом записи 5.m.2 инжекционного канала 5. m, выход 5.m.3 требования канала которого является выходом триггера 108. Входы элемента 109 ИЛИ соединены со входом разрешения передатчика 6.m и выходом элемента 99 ИЛИ, а выход - с нулевым входом мультиплексора 110, первый вход которого соединен с входом записи 5.m.2 инжекционного канала, а выход - с входом установки J триггера 111, вход сброса К которого соединен с выходом дешифратора 96, а выход - с входом E2 разрешения счета счетчика 95. Входы элемента 112 И соединены с первым выходом дешифратора 98 ответов и выходами D0 и D1 регистра 93 данных, а выход - со входом установки J триггера 113, вход сброса K которого соединен со вторым выходом дешифратора 98 ответов. Выход триггера 113 соединен с адресным входом мультиплексора 110, а инверсный выход - со вторым входом элемента 102 И. Тактовые входы С счетчика 95, регистра 97 ответов и триггеров 104, 106, 108, 111 и 113 соединены с шиной синхронизации сети.

В арбитре 7 буферов (см. фиг. 18) входы запроса соединены со входами шифратора 114 и элемента 115 ИЛИ. Входы занятости арбитра 7 буферов соединены с входами шифратора 116 и элемента 117 ИЛИ. Выходы элементов 115и 117 ИЛИ соединены со входами элемента 118 И, выход которого соединен со входами разрешения дешифраторов 119 и 120. Выходы шифратора 114 являются выходами номера источника арбитра 7 буферов; кроме того, они соединены с входами дешифратора 119, выходы которого являются выходами разрешения арбитра 7 буферов. Выходы шифратора 116 соединены с входами дешифратора 120, выходы которого являются выходами выбора арбитра 27 буферов.

В арбитре 10 маршрутизатора входы запроса соединены со входами шифратора 121 и с информационными входами мультиплексора 122 (см. фиг. 19), выход которого является выходом подтверждения информации арбитра 10 маршрутизатора, а также соединен с входом разрешения дешифратора 124. Вход блокировки арбитра 10 маршрутизатора соединен со входом разрешения записи регистра-защелки 123, входы которого соединены с выходами шифратора 121. Выходы регистра-защелки 123 соединены с входами дешифратора 124, выходы которого являются выходами разрешения арбитра 10 маршрутизатора. Адресные входы мультиплексора 122 соединены с выходами регистра защелки 123.

Информационные входы схемы сравнения 17 маршрутизатора 11 соединены со входами регистра 125 (см. фиг. 20) и входами A элемента 126 сравнения. Выходы регистра 125 соединены со входами B элемента 126 сравнения, выход A=B которого является выходом схемы сравнения 17 маршрутизатора 11. Вход программирования схемы сравнения 17 соединен со входом записи регистра 125.

Входы инверторов 127, 128, 129, 130 и 131 (см. фиг. 21) соединены с первым, вторым, третьим, четвертым и пятым входами схемы 49 кодирования ответов соответственно. Входы элемента 132 И соединены с выходами инверторов 127, 128, 129 и четвертым входом схемы 49 кодирования ответов. Входы элемента 133 И соединены с первым входом схемы 49 кодирования ответов и выходом инвертора 129. Входы элемента 134 И соединены с выходами инверторов 127, 128, 129 и 130 и шестым входом схемы кодирования ответов. Входы элемента 135 ИЛИ-НЕ соединены с выходами инвертора 129 и элементов 132, 133 и 134 И. Пятый вход схемы 49 кодирования ответов соединен с вторыми входами элементов 136, 137 И, первые входы которых соединены с выходами элементов 133, 134 И соответственно. Выходом разрешения схемы 49 кодирования ответов является выход элемента 138 ИЛИ, входы которого соединены с выходами элементов 136, 137 И. Инверсный вход разрешения буферного элемента 139 соединен с выходом инвертора 131. На первый вход буферного элемента 139 подана логическая "1". Второй, третий и четвертый входы буферного элемента соединены с выходами инвертора 129, элемента 132 И и элемента 135 ИЛИ-НЕ. Выходы буферного элемента 139 являются выходами ответа схемы 49 кодирования ответов.

Один из вариантов шифраторов 114, 116, используемых в арбитре 7 буферов, приоритетных шифраторов 47, 48 и 50, используемых в блоке 20 прокладки адаптивных маршрутов, шифратора 54 блока прокладки неадаптивных маршрутов 19 и шифратора 121, используемого в арбитре 10 маршрутизатора, приведен на фиг. 23 для случая, когда число входов шифратора равно семи. Четвертый, пятый, шестой и седьмой входы шифратора соединены со входами элемента 140 ИЛИ. Первый, второй и третий входы шифратора соединены с первой группой входов мультиплексора 141, вторая группа входов которого соединена с пятым, шестым и седьмым входами шифратора. Входы элемента 142 ИЛИ соединены со вторым и третьим выходами мультиплексора 141, адресный вход которого соединен с выходом элемента 140 ИЛИ. Первый и третий выходы мультиплексора 141 соединены с первым и вторым входами мультиплексора 143, адресный вход которого соединен с выходом элемента 142 ИЛИ. Инверсный и прямой входы разрешения шифратора соединены с инверсным и прямым входами соответственно элемента 144 И, выход которого соединен со входом разрешения буферного элемента 145, входы которого соединены с выходами мультиплексора 143 и элементов 142 и 140 ИЛИ. Выходами шифратора являются выходы буферого элемента 145.

Выход готовности, который используется при построении шифратора 54 блока 19 прокладки неадаптивных маршрутов, является выходом элемента 146 ИЛИ, входы которого соединены с выходами мультиплексора 143 и элементов 142 и 140 ИЛИ.

Дешифратор 52 блока 19 прокладки неадаптивных маршрутов (см. фиг. 25) содержит, например, инвертор 147, соединенный с одним из информационных входов дешифратора 52, элемент 148 И, входы которого соединены с выходом инвертора 147 и входами готовности данных и блокировки дешифратора 52, и дешифратор 149, вход разрешения которого соединен с выходом элемента 148 И. Входы дешифратора 149 соединены с информационными входами дешифратора 52, выход готовности которого соединен с выходом инвертора 147 Первые N выходов дешифратора 52 являются первыми М выходами дешифратора 149.(N+1)-й выход дешифратора 149 соединен с остальными M выходами дешифратора 52. (N+2)-й выход дешифратора 149 является выходом программирования дешифратора 52.

Схема 55 кодирования ответов блока 19 прокладки неадаптивных маршрутов содержит элемент 150 ИЛИ (см. фиг. 26), входы которого соединены с первым и третьим входами схемы 55 кодирования ответов элемент 151 ИЛИ-НЕ, входы которого соединены со вторым и третьим входами схемы 55 кодирования ответов, и буферный элемент 152, выходы которого являются выходами ответа схемы 55 кодирования ответов. Выход элемента 150 ИЛИ соединен со входом разрешения буферного элемента 152, второй и третий входы которого соединены с выходом элемента 151 ИЛИ-НЕ. На первый и четвертый входы буферного элемента 152 подаются логические "1" и "0" соответственно.

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

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

Особым случаем управляющей информации является программирование маршрутизатора 11 (фиг. 2 - 4).

Рассмотрим работу маршрутизатора 11 в соответствии с его алгоритмом работы (см. фиг. 27 - 31).

В исходном состоянии маршрутизатор 11 ожидает информацию о готовности данных (шаги 153 и 154).

Когда данные готовы (шаг 155), производится анализ управляющей информации (шаги 156, 157, 158).

Полученный код может содержать:
- адаптивный адрес (шаг 159);
- неадаптивный адрес (шаг 160) или
- команду программирования маршрутизатора (шаг 161).

Если получена команда программирования (шаг 161), маршрутизатор 11 устанавливает сигнал блокировки (см. фиг. 5), присваивает счетчику 58 (см. фиг. 9) значение "1" и формируется ответ "Передать следующее слово" (шаг 162). После этого ожидается поступление данных (шаги 163 и 164).

При поступлении очередного кода данных (шаг 165) производится программирование одного или нескольких регистров 23, 24, 25, 26 (см. фиг. 6), 34, 35 (см. фиг. 7), 125 (фиг. 20) в соответствии с состоянием счетчика 58 (см. фиг. 9).

При этом счетчика 58 (фиг. 9) наращивается на "1" и формируется ответ "Передать следующее слово" (шаг 166).

После этого проверяется (по новому значению счетчика 58), все ли регистры 23, 24, 25, 26 (см. фиг. 6), 34, 35 (см. фиг. 7), 125 (фиг. 20) запрограммированы (шаг 167).

Если все регистры запрограммированы (шаг 169), то сигнал блокировки снимается (шаг 170), и маршрутизатор 11 переходит в начальное состояние (шаг 153). Иначе программирование продолжается с шага 163.

Если получен неадаптивный адрес (шаг 160), то проверяется (шаг 195) необходимость маршрутизации на n-й выходной канал (фиг. 4).

Если "да" (шаг 197), то проверяется, свободен ли требуемый выходной канал 2.n.2 (фиг. 4) (шаг 198).

Если требуемый выходной канал 2. n.2 (фиг. 4) свободен (шаг 199), то маршрутизатор 11 прокладывает затребованный маршрут и формирует ответ "Передать следующее слово" (шаг 200); в противном случае (шаг 201) формируется ответ "Повторить маршрутизацию в данном узле" (шаг 202). Если неадаптивный адрес задает маршрут на реципиентный канал 16.l (фиг. 4) (шаг 196), то проверяется, есть ли хотя бы один свободный реципиентный канал (шаг 203). При наличии положительного ответа на данный вопрос (шаг 204) маршрутизатор 11 прокладывает затребованный неадаптивный маршрут и формирует ответ "Передать следующее слово" (шаг 205). Иначе (шаг 206) формируется ответ "Повторить маршрутизацию в данном узле" (шаг 207).

Если получен адаптивный адрес (шаг 159), проверяется, достигнут ли узел назначения сообщения (шаг 171), и если "да", формируется ответ "Передать следующее слово" (шаг 174), а если "нет", то производится попытка адаптивной маршрутизации (шаг 172).

Проверяется наличие свободного оптимального канала, связанного с отдаленным узлом (шаг 175). Если таковой имеется (шаг 176), производится коммутация сообщения на этот канал и формируется ответ "Повторить передачу слова" (шаг 177).

Если такого свободного канала, связанного с отдаленным узлом, нет, проверяется наличие свободного оптимального канала, связанного со смежным узлом (шаг 178) и производится коммутация на этот канал и формирование ответа "Повторить передачу слова" (шаги 179 и 180).

Если оптимальных свободных каналов не оказалось (шаг 181), проверяется, является ли оптимальным канал, по которому пришло сообщение (шаг 182). Если канал, по которому пришло сообщение, является оптимальным (шаг 183), формируется ответ "Повторить маршрутизацию в предыдущем узле" (шаг 184).

Если канал, по которому пришло сообщение является неоптимальным (шаг 185), то проверяется количество измерений, по которому не достигнуты координаты узла назначения (шаг 186). Если таких координат больше, заданного числа в предпочтительном применении больше единицы (шаг 187), формируется ответ "Повторить маршрутизацию, в данном узле" (шаг 188), т.е. реализуется ожидание освобождения одного из оптимальных каналов.

Если ни одно из условий шагов 175, 178, 182, 186 не выполнилось (шаг 189), проверяется наличие хотя бы одного свободного канала, связанного со смежным узлом (шаг 190). Если такой канал находится (шаг 191), предпринимается попытка проложить неоптимальный маршрут: коммутируется сообщение на этот канал и формируется "Повторить передачу слова" (шаг 192).

Если же невозможно проложить неоптимальный маршрут (шаг 193), формируется ответ "Повторить маршрутизацию в предыдущем узле" (шаг 194).

После формирования ответов в шагах 174, 177, 180, 184, 188, 192, 192, 194, 200, 202, 204 и 207 маршрутизатор 11 переходит в исходное состояние (шаг 153).

Рассмотрим передачу сообщения из узла 1.2 в узел 1.P.

Узел 1.2 имеет координаты (0,1,0,0), узел 1.P имеет координаты (P, 0,0,0). Соответственно для передачи сообщения необходимо пройти один канал в направлении X2 и P каналов в направлении X1. Однако имеются в сети связи с отдаленными узлами, которые позволяют сократить число каналов, используемых для передачи сообщения. В нашем примере для передачи сообщения из узла 1.2 в узел 1.P можно использовать последовательно каналы 2(1.0, 1.2), 2(1.0, 1.1) и 2(1.1, 1. P). Прокладку такого маршрута можно осуществлять неадаптивной маршрутизацией, задавая направления передачи сообщения для каждого узла по заранее определенному направлению, т.е. определяя как промежуточные узлы, так и каналы.

Когда в сети передается множество сообщений, определение маршрута по заранее выбранному направлению не представляется возможным, поскольку неизвестна загруженность промежуточных узлов в сети. В этом случае применяется адаптивная маршрутизация. Тогда в узле 1.2 может быть выбран канал 2(1.0, 1.2) или 2(1.2, 1.5), так как оба эти канала передают сообщения в узел, расстояние от которого до узла 1.P меньше, чем из узла 1.2. Таким образом, в каждом узле направление передачи выбирается по свободным каналам к узлу, который ближе к узлу назначения. Если в узле имеются каналы, связанные с отдаленными узлами, удовлетворяющие критериям минимизации, то эти каналы используются в первую очередь. Так, сообщение, переданное из узла 1.2. в узел 1. P по каналу 2(1.2, 1.5) в узле 1.5 будет направлено в канал 2(1.5, 1.6), если этот канал свободен.

Таким образом, сообщение из узла 1.2 в узел 1.P при адаптивной маршрутизации может быть передано по каналам 2(1.0, 1.2), 2(1.0, 1.1), 2(1.1, 1. P), или 2(1.2, 1.5), 2(1.5, 1.6), 2(1.P, 1.6) или 2(1.2, 1.5), 2(1.1, 1.5), 2(1.1, 1.P).

Однако, если сообщение достигло узла 1.1 и канал 2(1.1, 1.P) занят, то для дальнейшей передачи будет использован канал 2(1.1, 1.7).

В узле коммутации (см. фиг. 2 - 4) возможна передача информации:
- из инжекционного канала 5.m - на выходной 2.n.2;
- из входного канала 2.n.1 - в реципиентный канал 16.l;
- из входного канала 2.R.1 - на выходной 2.S.2, причем, R≠S, R=1,...,N, S =1,...,N.

Направление передачи информации определяется маршрутизатором 11, устанавливающим коммутатор каналов 12 в соответствующее состояние.

Передача информации из инжекционного канала 5.m в выходной канал 2.n.2 осуществляется с помощью передатчика 6.m. Прокладка маршрута из передатчика 6.m в выходной канал 2.n.2 осуществляется также, как и из входного канала 2. R.1 в выходной канал 2.S.2. Передатчик 6.m осуществляет согласование протоколов передачи информации инжекционного канала 5.m, в качестве которого может использоваться, например, стандартный канал прямого доступа к памяти (ПДП), и протоколом передачи данных по каналам связи.

При записи в передатчик 6.m первого слова из инжекционного канала 5.m передатчик переходит в режим прокладки маршрута. В этом режиме до передачи данных передатчик 6.m выдает на информационный выход DI активизирующую посылку и ожидает прихода ответа на один из входов ответа для начала передачи данных. Так как в начальном состоянии информационный выход DI передатчика 6. m еще не скоммутирован ни на один из адаптеров выходного канала 15.1,...,15. N, то активизирующая информация не используется ни в узле коммутации, ни в сети, а передатчик 6.m устанавливает сигнал запроса, получив который арбитр 7 буферов проверяет наличие по крайней мере одного свободного буфера 9.k по состоянию своих входов занятости. Если таковые имеются, то арбитр 7 буферов устанавливает на выходе NI номера источника код, присвоенный передатчику 6.m в арбитре 7 буферов. Сигналом выбора с k-го выхода группы выходов выбора арбитр 7 буферов записывает код номера источника в коммутатор 8 буферов и переводит буфер 9.k в состояние занятости и сигналом с (N+m)-го выхода выбора переводит передатчик 6.m в активное состояние и разрешает ему передачу слова управляющей информации в буфер 9.k. При этом коммутатор 8 буферов соединяет информационный выход DI передатчика 6.m с информационным DI входом буфера 9. k и выход ответа DO буфера 9.k - со вторым входом ответа DO передатчика 6.m. Управляющая информация принимается буфером 9.k и на выходе запроса буфера 9. k появляется сигнал запроса RQ, который поступает на вход RQ арбитра маршрутизатора 10. Арбитр маршрутизатора 10, если маршрутизатор 11 не занят обработкой информации с другим буфером, устанавливает на k-ом выходе EN сигнал разрешения, который, поступив на k-ый вход EN коммутатора буферов 8 и на вход EN разрешения буфера 9.k, разрешает, тем самым, установку на входах маршрутизатора 11 кода номера источника, подключенного к буферу 9.k и управляющей информации. Одновременно арбитр буферов 7 устанавливает на выходе ED сигнал подтверждения информации. Маршрутизатор 11, проанализировав состояние своих входов, определяет выходной канал 2.n.2, на который будет передано сообщение. Код ответа, выбранный маршрутизатором 11, с выхода DO маршрутизатора передается в буфер 9. k параллельным кодом, который в последующих тактах передается через коммутатор буферов 8 на второй вход DО ответа передатчика 6.m. При этом возможны следующие варианты:
1. В слове управляющей информации содержался код принудительной маршрутизации и коммутация произведена.

В этом случае код ответа разрешает передачу следующего слова. Передатчик 6. m запрашивает следующее слово из инжекционного канала 5.m и получив его передает активизирующую информацию через коммутатор 12 каналов и адаптер 15. n выходного канала в выходной канал 2.n.2.

2. В слове управляющей информации содержался код принудительной маршрутизации и коммутация не произведена (т.к. выходной канал 15.n занят).

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

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

3. В слове управляющей информации содержался код адаптивной маршрутизации и коммутация произведена.

В этом случае код ответа разрешает повторную передачу слова управляющей информации. Передатчик 6.m передает активизирующую информацию через коммутатор 12 каналов на адаптер 15.n выходного канала в выходной канал 2.n.2 и ожидает прихода на первый вход ответа DО через коммутатор 12 каналов и адаптер 15.n выходного канала кода ответа из следующего узла коммутации, разрешающего передачу слова управляющей информации. Далее процесс маршрутизации происходит в следующем узле коммутации, и передатчик 6.m может получать три варианта ответа:
- " повторить передачу слова" - и процесс повторяется с момента (см. п. 3);
- "повторить маршрутизацию в предыдущем узле" - передатчик 6.m переходит в неактивное состояние и устанавливает на своем выходе сигнал запроса, после чего процесс предоставления буфера 9.k, передачи в него слова управляющей информации и маршрутизации повторяется;
- "передать следующее слово " - передатчик 6.m запрашивает следующее слово из инжекционного канала 5.m и получив его передает активизирующую информацию через коммутатор 12 каналов и адаптер 15.n выходного канала в выходной канал 2.n.2.

Последнее слово управляющей информации содержит команду коммутации входного канала 2. n. 1 на приемник 14.l узла назначения. Передатчик 6.m, получив код ответа - "передать следующее слово", после передачи этой команды переходит в режим передачи данных. В этом режиме, т.к. маршрут проложен, активизирующая информация не передается. Получив очередное слово информации из инжекционного канала передатчик 6.m передает его на информационный выход и ожидает прихода кода ответа. Процесс продолжается до тех пор, пока не придет код ответа сбросить канал, после которого передатчик 6.m переходит в исходное состояние.

Прокладка маршрута из входного канала 2.n.1 в реципиентный канал 16.l происходит аналогично прокладке маршрута из входного канала 2.R.1 в выходной канал 2. S.2 и отличается только кодом управляющего слова. Маршрутизатор 11 подключает первый из свободных приемников 14.1,...,14.L. Если все приемники 14.1,...,14.L заняты, то повторяется маршрутизация в этом узле коммутации до освобождения одного из приемников 14.1,...,14.L.

Особым случаем прокладки маршрута является программирование маршрутизатора.

Получив из буфера 9. k слово управляющей информации, задающее начало программирования, маршрутизатор 11 устанавливает на своем выходе сигнал блокировки, запрещающий арбитру 10 маршрутизатора подключение на вход маршрутизатора 11 информации из других буферов 9.1,...,9.K до того момента, когда все слова управляющей информации, необходимые для программирования маршрутизатора, не будут приняты через буфер 9.k.

При программировании маршрутизатора 11 буфер 9.k не освобождается после получения каждого слова.

При программировании маршрутизатора 11 записывается информация, необходимая ему для прокладки адаптивных маршрутов, т.е. определяет координаты узла коммутации в сети и привязывает каналы 2.1,...,2.N к направлениям в системе координат в сети (X1, X2,...).

В исходном состоянии узла коммутации входные автоматы 4.1,...,4.N и передатчики 6.1,...,6.M находятся в неактивном состоянии, выходные автоматы 13.1, . . . , 13.N и приемники 14.1,...,14.L также неактивны и на их выходах занятости установлено состояние "свободен". Информация с выхода адаптеров каналов 3.1, ...,3.N поступает только на информационные входы входных автоматов 4.1,...,4.N.

Рассмотрим прокладку маршрута сообщения, поступающего на входной канал 2.R.1.

Входной автомат 4.R, находящийся в неактивном состоянии, анализирует состояние своего информационного DI входа и при появлении на нем активизирующей информации устанавливает сигнал запроса на выходе RQ запроса. Арбитр буферов 7, получив сигнал запроса RQ из входного автомата 4.R, проверяет наличие по крайней мере одного свободного буфера 9.k по состоянию его входов WS занятости. Если такой имеется, то арбитр буферов 7 устанавливает на выходе NI номера источника код, соответствующий номеру входного автомата 4.R, сигналом выбора на k-м выходе группы выходов CS выбора записывает код номера источника NI в коммутатор буферов 8 и переводит буфер 9.k в состояние занятости и, сигналом на R-м выходе EN разрешения, переводит входной автомат 4.R в активное состояние. При переходе в активное состояние входной автомат 4.R передает на вход адаптера 3.R входного канала код ответа, сообщающий, что свободный буфер 9.k подключен к входному каналу 2.R.1 и управляющая информация может быть принята. При этом коммутатор буферов 8 соединяет выход адаптера 3.R входного канала с информационным входом DI буфера 9.k и выход ответа DO буфера 9.k с первым входом ответа DO входного автомата 4.R.

Управляющая информация принимается буфером 9.k и на выходе RQ запроса буфера 9.k появляется сигнал RQ запроса, который поступает на вход RQ арбитра маршрутизатора 10. Арбитр маршрутизатора 10, если маршрутизатор 11 не занят обработкой информации с другим буфером, устанавливает на k-м выходе сигнал EN разрешения, который, поступив на k-й вход EN разрешения коммутатора буферов 8 и на вход EN разрешения буфера 9.k, разрешает установку на входах маршрутизатора 11 кода номера источника NI, подключенного к буферу 9.k, и управляющей информации DI. Одновременно арбитр буферов 10 устанавливает на выходе сигнал подтверждения информации. Маршрутизатор 11, проанализировав состояние своих входов, определяет выходной канал 2.S.2, на который будет передано сообщение. При этом код ответа с выхода DO маршрутизатора 11 передается в буфер 9. k, который затем передается через коммутатор буферов 8 и входной автомат 4.R и адаптер канала 3.R во входной канал 2.R.1. Одновременно с выдачей кода ответа маршрутизатор 11 устанавливает сигнал CS выбора на S-м выходе, который переведет выходной автомат 13.S в состояние занятости и запишет номер источника в коммутатор каналов 12. Коммутатор каналов соединит выход адаптера канала 3.R с входом адаптера канала 15.S, а выход адаптера канала 15.S - с вторым входом DO входного автомата 4.R.

После того, как буфер 9. k передаст ответ, он переходит в состояние "свободен" и может быть использован для прокладки других маршрутов.

Дальнейшая управляющая информация и данные передаются из входного канала 2.R.1 в выходной канал 2.S.2 без изменений. Коды ответов при передаче из выходного канала 2.S.2 на входной канал 2.R.1 анализируются выходным автоматом 13. S. При прохождении кодов ответов, управляющих сбросом каналов, выходной автомат 13. S переходит в состояние "свободен" и может быть использован для прокладки других маршрутов. Сигнал "свободен" с выхода WS занятости выходного автомата 13.S прерывает цепь коммутации адаптера канала 15.S в коммутаторе каналов 12. Входной автомат 4.R также анализирует коды ответов и переходит в неактивное состояние при обнаружении ответов, сбрасывающих канал. При этом входной автомат 4.R может модифицировать коды ответов для того, чтобы участок маршрута до входного канала 2.R.1 не был сброшен. Этот механизм позволяет производить повторную маршрутизацию в этом же узле коммутации, если дальнейшая прокладка маршрута в выбранном на предыдущем шаге маршрутизации узле коммутации не возможна.

Маршрутизатор (см. фиг. 5) работает в двух режимах:
- программирование;
- прокладка маршрута.

В зависимости от кода слова управляющей информации выбор направления дальнейшей передачи информации и определение кода ответа осуществляется блоком 19 прокладки неадаптивных маршрутов или блоком 20 прокладки адаптивных маршрутов при наличии на их входах разрешения сигнала готовности данных. Блок 19 прокладки неадаптивных маршрутов принимает решения на основе анализа слова управляющей информации и состояния входов занятости. Блок 19 прокладки неадаптивных маршрутов также переводит маршрутизатор 11 в режим программирования, подав сигнал программирования на стартовый вход блока 22 программирования, после которого блок 22 программирования устанавливает на своем выходе сигнал блокировки LK, который блокирует работу блоков 19 прокладки неадаптивных маршрутов и 20 прокладки адаптивных маршрутов. Коды, поступающие на информационный вход маршрутизатора 11, каждый из которых сопровождается сигналом готовности на входе готовности блока программирования 22 будут последовательно записаны в схему 17 сравнения, схему 18 определения оптимальных маршрутов, и блок 20 прокладки адаптивных маршрутов импульсами, вырабатываемыми блоком 22 программирования на выходах программирования.

Схема 17 сравнения сравнивает адрес узла коммутации с адресом узла назначения сообщения при адаптивной маршрутизации.

Схема 18 определения оптимальных маршрутов определяет выходные каналы, связанные с узлами сети, расположенными ближе к узлу назначения, чем данный узел при адаптивной маршрутизации.

Блок 20 прокладки адаптивных маршрутов принимает решения в результате анализа слова управляющей информации, номера источника, состояния входов занятости и состояния выходов схемы 17 сравнения и схемы 18 определения оптимальных маршрутов.

Группа 21 схем ИЛИ пропускает на выходы выбора маршрутизатора 11 сигналы выбора выходных каналов 2.n.2 выработанные блоком прокладки неадаптивных или адаптивных маршрутов.

При программировании схемы 18 определения оптимальных маршрутов коды с информационных входов (см. фиг. 6) импульсами программирования записываются в регистры. Программирование схемы 18 определения оптимальных маршрутов осуществляется однократно до начала прокладки адаптивных маршрутов в сети.

Адрес узла назначения, содержащийся в слове управляющей информации, схемами 27.1,...,27.N И, разбивается на значения координат, соответствующих узлу назначения. Регистр маски 23.n содержит "1" в битах, соответствующих одной из координат сети, т.к. число координат в сети может быть меньше или равно N. С выходов схем 27.1,...,27.N И значения координат поступают на схемы 28.1, . ..,28.N сравнения на которых сравниваются со значениями координат, заданными в регистрах 24.1,...,24.N координаты. Схемы 29.1,...,29.N выбирают один из результатов сравнения: "больше", "равно" или "меньше", в зависимости от значений кодов, записанных в регистрах 25.1,...,25.N условия. Сигналы с выходов схем 29.1,...,29.N поступают на первые входы элементов 30.1, . . . ,30.N ИЛИ, на вторые входы которых поступают сигналы с регистров 26.1,...,26.N связи. Результаты логического сложения сигналов с выходов схем 29.1,...,29.N и регистров 26.1,...,26.N связи поступают на входы схем 31.1,. . . ,31.N И, на выходах которых формируются сигналы логической "1" для каналов, которые могут быть использованы для прокладки оптимальных маршрутов.

Каждые три регистра 23.n, 24.n и 25.n маски, координаты и условия соответственно задают координаты узлов назначения в сети, для которых может быть использован хотя бы один выходной канал 2.S.2. Регистры 26.1,...,26.N связи задают соответствие между выходным каналом 2.S.2 и координатами узлов назначения. Регистр связи 26.S содержит логические "0" только в тех позициях, которые соответствуют условиям, которые должны быть выполнены для того, чтобы выходной канал 2.S.2 мог быть выбран в качестве оптимального.

Например, для узла 1.1 (см. фиг. 1) необходимо задать условия:
1) X1 = 0;
2) X1 > 1;
3) X1 > P;
4) X2 = 1;
5) X3 = 1;
6) X4 = 1.

Выходной канал 2(1.0, 1.1) может быть использован при выполнении первого условия, выходной канал 2(1.1, 1.7) - при выполнении второго условия, выходной канал 2(1.1, 1. P) - при выполнении третьего условия, выходной канал 2(1.1, 1.5) - при выполнении четвертого условия, выходной канал 2(1.1, 1.8) - при выполнении пятого условия и выходной канал 2(1.1, 1.9) - при выполнении шестого условия.

Каждый канал связи в сети, соединяющий узлы коммутации между собой, например, канал 2(1.0, 1.1) между узлами 1.0 и 1.1 может быть образован, например, соединением выходного канала 2.1.2 узла коммутации 1.0 с входным каналом 2.2.1 узла коммутации 1.1 и 'соединением выходного канала 2.2.2 узла коммутации 1.1 и входного канала 2.1.1 узла коммутации 1.0.

Например, в узле 1.1:
канал связи 2(1.0,1.1) образуется каналами 2.1.1 и 2.1.2;
канал связи 2(1.1,1.7) образуется каналами 2.2.1 и 2.2.2;
канал связи 2(1.1,1.5) образуется каналами 2.3.1 и 2.3.2;
канал связи 2(1.1,1.8) образуется каналами 2.4.1 и 2.4.2;
канал связи 2(1.1,1.9) образуется каналами 2.5.1 и 2.5.2;
канал связи 2(1.1,1.Р) образуется каналами 2.6.1 и 2.6.2.

В этом случае регистры 26.1,...,26.6 связи будут содержать коды: 011111, 101111, 111011, 111101, 111110 и 110111 соответственно.

В блоке 20 прокладки адаптивных маршрутов (см. фиг. 7) при программировании коды с информационных входов импульсами программирования записываются в регистр 34 числа и регистр 35 связей. Регистр 34 числа содержит условие, при котором блок прокладки адаптивных маршрутов может выбрать неоптимальный маршрут. Схема сравнения 40 разрешает выбирать неоптимальный маршрут если число возможных оптимальных маршрутов, вычисленное сумматором 38, меньше числа, записанного в регистр 34 числа. Регистр 35 связей содержит единицы в тех битах, номера которых соответствуют номерам каналов связи, соединенных с отдаленными узлами коммутации. Эти каналы имеют высший приоритет при выборе оптимальных маршрутов и не могут быть использованы при выборе неоптимальных маршрутов.

Сигналы со входов оптимальных маршрутов поступают на группу схем 33 И, которые исключают из оптимальных маршрутов направления прихода сообщения, и на информационные входы мультиплексора 39, который это направление выделяет. Дешифратор 32 преобразует двоичный код номера источника в позиционный код. Если сообщение пришло с оптимального направления, то на выходе мультиплексора 39 появится логическая "1", которая поступит на второй вход схемы 49 кодирования ответов и запретит выбор неоптимального канала. Сигналы с выходов схем И 33 поступают на вход сумматора 38, который подсчитывают число логических "1" на входах, которое затем сравнивается в схеме 40 сравнения с числом, хранящимся в регистре 34 числа. Если число в регистре 34 числа больше, тогда на выходе схемы 40 сравнения устанавливается логическая "1", которая поступает на четвертый вход схемы 49 кодирования ответов. На первые входы группы схем 37 И поступают сигналы с выходов схем 33 И, содержащие "1" на выходах соответствующих каналов, которые могут быть выбраны в качестве оптимальных маршрутов; на вторые входы группы схем И 37 поступают сигналы со входов занятости, содержащие "0" на входах, соответствующих свободным каналам; на выходах группы схем И 37 устанавливаются "1" в позициях, соответствующих свободным каналам, которые можно использовать в качестве оптимальных. Схема 45 ИЛИ формирует логическую "1", если такие каналы имеются. В этом случае разрешается работа приоритетного шифратора 48 и запрещается работа приоритетного шифратора 50, на первый вход схемы 49 кодирования ответов поступает логическая "1". Группы схем И 41 и 42 разделяют свободные оптимальные каналы, связанные с отдаленными узлами и смежными соответственно. Если имеется по крайней мере один свободный канал, связанный с отдаленным узлом, элемент 44 ИЛИ запрещает работу приоритетного шифратора 48 и разрешает работу приоритетного шифратора 47, который формирует на своих выходах номер, соответствующий этому каналу.

Если каналов, связанных с отдаленными узлами, нет, то код, соответствующий номеру канала, формирует приоритетный шифратор 48. Группа схем 43 И выделяет свободные каналы, связанные со смежными узлами. Схема 46 ИЛИ определяет наличие выделенных каналов. Сигнал с выхода элемента 46 ИЛИ поступает на шестой вход схемы 49 кодирования ответов. Если оптимальных свободных каналов нет, на инверсном входе разрешения приоритетного шифратора 50 присутствует логический "0" и приоритетный шифратор 50 формирует номер свободного неоптимального канала, который может быть использован для дальнейшей прокладки маршрута.

Принятие решения о выборе дальнейшего маршрута происходит при наличии сигнала разрешения, отсутствия сигнала блокировки и при наличии на одном из информационных входов блока 20 прокладки адаптивных маршрутов логической "1", подтверждающей, что на входе блока 20 прокладки адаптивных маршрутов установлен адаптивный адрес. В этом случае элемент 36 И формирует сигнал разрешения схеме 49 кодирования ответов. Если принимается решение о прокладке маршрута в один из свободных каналов, схема 49 кодирования ответов формирует сигнал разрешения дешифратору 51.

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

Схема 49 кодирования ответов формирует в зависимости от состояния входов следующие коды ответов:
- "передать следующее слово", если сообщение достигло узла назначения, на третьем входе присутствует логическая единица;
- "повторить передачу слова", если для дальнейшей прокладки маршрута выбран оптимальный или неоптимальный маршрут (канал);
- "повторить маршрутизацию в данном узле", если оптимальных каналов больше, чем число записанное в регистр 34 числа, но они заняты, и сообщение пришло не с оптимального направления, в узле коммутации, направившем сообщение в данный узел, был выбран оптимальный маршрут:
- "повторить маршрутизацию в предыдущем узле" - в остальных случаях.

В блоке 19 прокладки неадаптивных маршрутов (см. фиг. 8) при отсутствии сигнала блокировки и наличии сигнала готовности данных на входах, а также при наличии на одном из информационных входов логического "0", подтверждающего, что на входе установлен неадаптивный адрес, дешифратор 52 формирует логическую "1" на n-м выходе, если в управляющем слове содержится команда "Код принудительной маршрутизации на n-й канал", или логические "1" на (N+1), . . . (N+L) выходах, если в управляющем слове содержится команда "Код принудительной маршрутизации на реципиентный канал", или логическую "1" на выходе программирования, если в управляющем слове содержится команда "Программирование", и логическую "1" на выходе готовности. Группа элементов 53 И пропускает на вход шифратора 54 логические "1" с выхода дешифратора 52, соответствующие незанятым каналам. Если такие имеются, шифратор 54 на выходе готовности формирует логическую "1", разрешающую работу дешифратора 56 и формирование кода ответа "Передать следующее слово" схемой 55 кодирования ответов, а также на группе выходов номер n-го выходного канала или свободного реципиентного канала, который декодируется дешифратором 56 в сигнал выбора на соответствующем выходе. Если свободного нет, схема 55 кодирования ответов формирует ответ "Повторить маршрутизацию в данном узле".

В исходном состоянии триггер 57 (см. фиг. 9) блока 22 программирования сброшен, логический "0" с выхода триггера 57 устанавливает счетчик 58 в нулевое состояние.

Стартовый импульс взводит триггер 57 и на выходе блока 22 программирования устанавливается сигнал блокировки. Сигнал готовности разрешает работу дешифратора 59 и своим окончанием переводит счетчик 58 в следующее состояние. Таким образом, последовательность сигналов готовности преобразуется в последовательность импульсов программирования на выходах блока 22 программирования. При этом, выход дешифратора 59, соответствующий нулевому состоянию счетчика 58 не используется, так как в это время на информационных входах маршрутизатора 11 присутствует команда программирования маршрутизатора. Окончание последнего импульса программирования сбрасывает триггер 57.

В коммутаторе 12 каналов сигнал на s-м входе CS выбора (см. фиг. 10) записывает номер r, соответствующий номеру входного 2.n.1 или инжекционного 5. m канала, из которого поступило сообщение, прокладывающее маршрут, в регистр 60.s. Сигнал WS занятости на s-м входе занятости разрешает работу мультиплексора 61.s, коммутирующего r-й информационный вход DI на s-й информационный выход DI коммутатора 12 каналов, и демультиплексора 62.s, коммутирующего s-й вход DO ответов на свой r-й выход. Далее код ответов через схему 63.r ИЛИ поступает на r-й выход ответов DO коммутатора 12 каналов. Когда маршрут, проложенный через узел коммутации, сбрасывается, выходной автомат 13.s (см. фиг. 2 - 4) либо приемник 14.l сбрасывает сигнал WS занятости и коммутация прекращается.

Коммутатор 8 буферов работает аналогично коммутатору 12 каналов с той лишь разницей, что комммутация производится не с выходными каналами или приемниками, а с буферами. Кроме того, при появлении сигнала разрешения на k-м входе EN разрешения номер источника, записанный в регистр 64.k (см. фиг. 11) через буферный элемент 68. k передается на выход NI номера источника коммутатора 8 буферов.

В исходном состоянии триггеры 69 и 70 (см. фиг. 12) буфера 9 сброшены, а регистры 71 и 73 установлены в нулевое состояние. Сигнал на входе CS выбора устанавливает триггер 69 занятости, и на выходе WS занятости появляется сигнал занятости. Последовательный код с информационного входа DI поступает в регистр 73. Когда стартовый бит кода достигает старшего разряда, сдвиг информации в регистре 73 прекращается и на выходе буфера 9 появляется сигнал RQ запроса. При поступлении на вход буфера 9 сигнала разрешения информация из регистра 73 передается через буферный элемент 74 на выход буфера 9. Сформированный маршрутизатором 11 код ответа записывается в регистр 71 ответа и взводится триггер 70 разрешения сброса. Код ответа из регистра 71 ответа последовательным кодом передается на выход ответа из старшего разряда, младшие разряды при этом заполняются нулями. Когда ответ передан и все биты регистра 71 ответа содержат нули, схема 72 ИЛИ формирует сигнал, сбрасывающий триггеры 69 занятости и 70 разрешения сброса. Информационный регистр 73 обнуляется по сигналу разрешения одновременно с записью ответа в регистр 71 ответа.

Выходной автомат 13 переводится в состояние занятости сигналом выбора (см. фиг. 13). Код ответов последовательным кодом поступает в регистр 76. Дешифратор 77 сбрасывает триггер 75 занятости и регистр 76 при наличии в регистре 76 кода ответа "Сбросить канал" или "Повторить маршрутизацию в предыдущем узле".

В исходном состоянии триггеры 78 запроса и 79 занятости входного автомата 4 (см. фиг. 14) сброшены. При поступлении на информационный вход активизирующей информации триггер 78 запроса устанавливается и на выходе входного автомата 4 появляется сигнал RQ запроса. При подключении буфера 9 сигнал на входе EN разрешения устанавливает триггер 79 занятости, который сбрасывает триггер 78 запроса. Сигнал разрешения через элемент 85 ИЛИ передается на выход ответов, в качестве ответа разрешающего передатчику 6 передающего узла коммутации передавать управляющую информацию. Триггер 79 занятости удерживает триггер 78 запроса в сброшенном состоянии и поступление информации на информационный вход входного автомата 4 не вызывает установки сигнала запроса. Коды ответа последовательным кодом заносятся в регистр 80 из буфера 9 или в регистр 82 из адаптера выходного канала 15. Дешифратор 81 формирует на первом выходе сигнал, сбрасывающий через элемент 84 ИЛИ триггер 79 занятости при поступлении в регистр 82 кодов ответа "Сбросить канал", "Повторить маршрутизацию в этом узле", или "Повторить маршрутизацию в предыдущем узле". Код ответа "Повторить маршрутизацию в этом узле" вызывает появление на втором выходе дешифратора 81 сигнала, сбрасывающего регистр 80 ответа. Поскольку первый вход дешифратора 81 соединен непосредственно с первым входом ответа входного автомата 4, а на выход ответа передается информация с первого выхода регистра 80, последняя "1" в коде "Повторить маршрутизацию в этом узле" не будет передана. Таким образом, ответ "Повторить маршрутизацию в этом узле" преобразуется в ответ "Повторить передачу слова". Регистр 82 и дешифратор 83 работают аналогично регистру 80 и дешифратору 81, но с другими кодами ответов, поступающими из выходных каналов. Коды ответов "Сбросить канал " или "Повторить маршрутизацию в предыдущем узле" сбрасывают триггер 79 занятости, а код "Повторить маршрутизацию в предыдущем узле" преобразуется в код ответа "Повторить передачу слова".

В исходном состоянии в приемнике 14 триггеры 88, 90 и 92 сброшены, регистры 89 и 86 установлены в нулевое состояние (см. фиг. 15). Сигнал выбора на входе CS приемника 14 взводит триггер 92 занятости. Информация последовательным кодом с информационного DI входа заносится в регистр 86 данных до тех пор, пока стартовый бит не достигнет старшего разряда регистра 86 данных, чем запретит дальнейший сдвиг и взведет триггер 88 требования канала. На входе 16.l.2 появится активный уровень. Сигнал 16.l.4 предоставления канала разрешает выдачу данных из регистра 86 данных через буфер 87 на выходы 16.l.1 в реципиентный канал, запись в регистр 89 ответа кода ответа и сбрасывает триггер 88 требования канала. Если было принято последнее слово сообщения, то сигнал последнего цикла взводит триггер 90 сброса канала, а в регистр 89 ответа записывается код ответа "Сбросить канал", иначе в регистр 89 ответа записывается код ответа "Передать следующее слово". Код ответа последовательным кодом передается из регистра 89 ответа на выход DO ответа приемника 14, сбрасывая при этом регистр 86 данных, чем разрешает прием следующего слова в регистр 86 данных. Когда триггер 90 сброса канала установлен, после передачи ответа триггер 92 занятости сбрасывается посредством схемы 91 ИЛИ-НЕ и своим инверсным выходом сбрасывает триггер 90 сброса каналов.

В исходном состоянии в передатчике 6.m триггеры 104, 106, 108, 111, 113 сброшены (см. фиг. 16 - 17). На инверсном выходе триггера 108 установлен сигнал требования канала 5.m.3. Когда канал предоставляется, данные с инжекционного канала 5.m записываются в регистр 93 данных а триггер 108 устанавливается и снимает сигнал требования канала 5.m.3. Одновременно, так как триггер 113 сброшен, импульс записи со входа 5.m.2 через схемы 102 И и 101 ИЛИ передается на информационный выход передатчика 6.m в качестве активизирующей информации. Сброшенный триггер 104 разрешает во время записи данных через схему 105 И установить триггер 106 и соответственно сигнал запроса на выходе передатчика 6.m. При подключении через коммутатор 8 буферов к передатчику 6. m буфера 9.k сигнал разрешения EN сбрасывает триггер 106 и устанавливает триггер 104. Таким образом сигнал запроса RQ не будет устанавливаться в передатчике 6.m до тех пор, пока триггер 104 не будет сброшен одним из ответов "Сбросить канал", "Повторить маршрутизацию в этом узле" или "Повторить маршрутизацию в предыдущем узле". Сигнал разрешения, пройдя через схему 109 ИЛИ и мультиплексор 110 взводит триггер 111, который своим выходом разрешает работу счетчика 95. Счетчик 95 управляет последовательной передачей мультиплексором 94, через схему 101 ИЛИ на информационный выход передатчика 6.m, стартового бита и данных, хранящихся в регистре 93. После завершения передачи дешифратор 96 запрещает работу счетчика 95 и сбрасывает триггер 111. Передатчик 6.m принимает код ответа с одного из входов ответа DO в регистр 97. Дешифратор 98 декодирует принятый в регистр 97 ответ. Схема 100 ИЛИ сбрасывает счетчик 95 и регистр 97 ответов при обнаружении дешифратором 98 одного из ответов:
"Передать следующее слово";
"Сбросить канал";
"Повторить маршрутизацию в данном узле".

"Повторить передачу слова";
"Повторить маршрутизацию в предыдущем узле".

Последние три ответа возможны только при прокладке маршрута и требуют повторной передачи слова, хранящегося в регистре 93. Сигналы дешифрации этих ответов передаются через схему 101 ИЛИ на информационный выход передатчика 6. m в качестве активизирующей информации. Если код ответа требует повторной маршрутизации, то триггер 104 будет сброшен, а триггер 106 установлен.

Триггер 108 будет сброшен ответами "Передать следующее слово", или "Сбросить канал" и соответственно установит сигнал требования канала 5.m.3 на выходе передатчика 6. m. Триггер 113 устанавливается, если нулевой и первый биты управляющей информации хранящейся в регистре 93 содержат "1", что является признаком команды программирования маршрутизатора или неадаптивного адреса реципиентного канала, и принят ответ "Передать следующее слово". Установленный триггер 113 констатирует окончание прокладки маршрута. После окончания прокладки маршрута, сигналы записи данных 5.m.2 не передаются через схему 102 И в качестве активизирующей информации, а через мультиплексор 110 взводят триггер 111, разрешающий передачу данных на информационный выход. Триггер 113 сбрасывается ответом "Сбросить канал".

Арбитр 7 буферов работает следующим образом (см. фиг. 18). При поступлении на один из входов RQ запроса сигнала запроса на выходе шифратора 114 устанавливается код, соответствующий номеру входа, на котором присутствует сигнал запроса. Если появилось несколько сигналов запроса одновременно, шифратор 114 формирует номер NI одного из них, имеющего высший приоритет. Сигналы запроса низшего приоритета будут обработаны после того, как снимается запрос высшего приоритета. Шифратор 116 формирует номер одного из свободных буферов. Если имеются, по крайней мере, один сигнал запроса и один свободный буфер, элементы 115 и 117 ИЛИ формируют логические "1", которые через элемент 118 И разрешают работу дешифраторов 119 и 120, формирующих сигналы разрешения EN и выбора CS соответственно.

При поступлении на один их входов запроса арбитра 10 маршрутизатора сигнала запроса шифратор 121 (см. фиг. 19) формирует номер буфера 9, установившего запрос. Регистр-защелка 123 при отсутствии сигнала блокировки на входе блокировки пропускает код номера буфера 9 на входы дешифратора 124 и адресные входы мультиплексора 122. Сигнал запроса, пройдя через мультиплексор 122, разрешает дешифратору 124 установить на выходе, соответствующем номеру буфера, сигнал разрешения и подтверждает, что на информационные входы маршрутизатора 11 передается слово управляющей информации.

При поступлении на входы арбитра 10 маршрутизатора нескольких запросов одновременно последние обслуживаются с разделением по времени в соответствии с приоритетами, реализуемыми шифратором 121.

Если в маршрутизатор 11 буфер 9.k передал слово управляющей информации, задающее начало программирования маршрутизатора 11, маршрутизатор 11 до окончания сигнала запроса на k-ом входе установит сигнал блокировки, который зафиксирует номер k в регистре-защелке 123. Таким образом, запросы других буферов 9 не будут обслуживаться до снятия сигнала блокировки.

При программировании маршрутизатора 11 в регистр 125 (см. фиг. 20) схемы сравнения 17 записывается адрес узла коммутации 1 в сети. При работе маршрутизатора 11 коды управляющего слова сравниваются с адресом, записанным в регистре 125, и на выходе схемы сравнения 17 появится логическая "1", если код управляющего слова совпадает с адресом узла коммутации 1 в сети.

Схема 49 кодирования ответов (см. фиг. 21) осуществляет преобразование входных сигналов в выходные сигналы в соответствии с таблицей, приведенной на фиг. 22, где указаны все возможные состояния входов и выходов схемы кодирования ответов 49, причем "
"0" - логический ноль;
"1" - логическая единица;
X - "0" или "1";
Z - третье состояние (или состояние высокого импеданса).

Шифратор (см. фиг. 20) осуществляет преобразование входных сигналов в выходные в соответствии с таблицей, приведенной на фиг. 24, где приведены все возможные варианты состояния входов и выходов шифратора, причем
"0" - логический ноль;
"1"- логическая единица;
X -"0" или "1";
Z - третье состояние (или состояние высокого импеданса).

На незадействованные разрешающие входы шифратора подается разрешающий сигнал при реализации схем 114, 117, 119 и 120.

Функции, реализуемые дешифратором 52 (см. фиг. 25), приведены выше при описании работы блока 19 прокладки неадаптивных маршрутов.

Схема 55 кодирования ответов (см. фиг. 26) формирует ответ при неадаптивной прокладке маршрута и при программировании и может формировать код 0001 "Передать следующее слово" или 0111 "Повторить маршрутизацию в данном узле". При адаптивной прокладке маршрута выходы схемы 55 кодирования ответов отключены.

В случае реализации сети на элементах вычислительной техники узел коммутации 1 (см. фиг. 1) выполняется в виде микросхемы, например, серии 1578ХМ8.

Каналы 2, как входные, так и выходные, могут быть выполнены в виде проводных линий связи, например кабелей, витых пар и т.п. Инжекционные 5 и реципиентные 16 каналы обеспечивают связь с аппаратурой, подключенной к узлу коммутации. Например, при работе сети в многопроцессорной вычислительной системе инжекционные 5 и реципиентные 16 каналы являются каналами прямого доступа к памяти процессора (процессоров) и могут быть реализованы на интегральных микросхемах (ИМС) как отечественного, так и зарубежного производства, например: КР580ИК57.

Адаптеры 3 и 15, как входных, так и выходных каналов представляют собой пару передатчика и приемника, например буферные элементы микросхемы 1578ХМ8. А также могут применяться внешние адаптеры входных и выходных каналов. При использовании кабельных линий связи, внешние адаптеры могут быть выполнены по схеме, изображенной на рис. 9.40 (см. П. Хоровиц, У. Хилл "Искусство схемотехники", М., Мир, 1993, т. 2, с. 231).

Рассмотрим пример достижения технического результата (см. фиг. 32 - 33) при использовании изобретения.

Принимая за τ время прохождения сообщения по концу связи между двумя узлами коммутации, соединенными этим каналом, получим общее время прохождения сообщения между исходным узлом и узлом назначения:
- для фиг. 32 - T1 = 10 τ - для прототипа;
- для фиг. 33 - T2 = 6 τ - для предлагаемой сети.

Таким образом, время прохождения сообщения в предлагаемой сети уменьшилось в 1,7 раза.

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

Изобретение относится к построению многопроцессорных вычислительных систем с синхронной и асинхронной работой процессоров. Технический результат заключается в уменьшении среднего времени прохождения сообщений в сети. Сеть для маршрутизации сообщений содержит по крайней мере три узла коммутации, смежные узлы коммутации соединены друг с другом каналами связи, по крайней мере один узел коммутации соединен по крайней мере с одним отдаленным узлом коммутации. 3 з.п. ф-лы, 33 ил.

1. Сеть для маршрутизации сообщений, состоящая по крайней мере из трех узлов коммутации, каждый из которых содержит маршрутизатор, причем смежные узлы коммутации соединены друг с другом каналами связи, отличающаяся тем, что по крайней мере один узел коммутации соединен дополнительным каналом связи по крайней мере с одним удаленным узлом коммутации, причем под удаленным узлом коммутации понимается узел коммутации, хотя бы одна из координат которого отличается более чем на единицу, а в узел коммутации введены N входных, N выходных, M инжекционных (M = 1,..., N) и L реципиентных (L = 1, . .., N) каналов, N входных и T выходных автоматов, K буферов (K = 1,..., N-1), L приемников, M передатчиков, арбитры буферов и маршрутизатора, коммутаторы буферов и каналов, 2N адаптеров входных и выходных каналов, причем n-ный входной канал соединен с группой канальных входов-выходов n-го адаптера входного канала, вход которого соединен с выходом ответов n-го входного автомата, информационный вход которого соединен с выходом n-го адаптера входного канала, который соединен с n-ми входами групп информационных входов коммутатора каналов и коммутатора буферов, первый вход ответов n-го входного автомата соединен с n-ным выходом группы выходов ответа коммутатора буферов, а второй вход ответов n-го входного автомата соединен с n-ным выходом группы выходов ответа коммутатора каналов, выход запроса n-го входного автомата соединен с n-ным входом группы входов запросов арбитра буферов, вход разрешения n-го входного автомата соединен с n-ным выходом группы выходов разрешения арбитра буферов, m-ный инжекционный канал соединен с группой канальных входов-выходов m-го передатчика, информационный выход которого соединен с (N + m)-ми входами групп информационных входов коммутатора каналов и коммутатора буферов, первый вход ответов m-го передатчика соединен с (N + m)-ным выходом группы выхода ответов коммутатора буферов, а второй вход ответов m-го передатчика соединен с (N + m)-ным выходом группы выходов ответа коммутатора каналов, выход запроса m-го передатчика соединен с (N + m)-ным входом группы входов запросов арбитра буферов, вход разрешения m-го передатчика соединен с (N + m)-м выходом группы выходов разрешения арбитра буферов, информационный вход K-го буфера соединен с K-тым выходом группы информационных выходов коммутатора буферов, выход ответа K-го буфера соединен с Kтым входом группы входов ответов коммутатора буферов, выход занятости K-го буфера соединен с K-ми входами группы входов занятости арбитра буферов и коммутатора буферов, K-тый выход группы выходов выбора арбитра буферов соединен с входом выбора K-го буфера и с K-тым входом группы входов выбора коммутатора буферов, группа выходов номера источника арбитра буферов соединена с группой входов номера источника коммутатора буферов, группы информационных выходов буферов объединены и соединены с группой информационных входов маршрутизатора, группы входов ответов буферов соединены с группой выходов ответов маршрутизатора, выход запроса K-го буфера соединен с K-тым входом группы входов запроса арбитра маршрутизатора, группа выходов арбитра маршрутизатора соединена с группой входов разрешения коммутатора буферов и с входами разрешения буферов, группа выходов номера источника коммутатора буферов соединена с группами входов номера источника коммутатора каналов и маршрутизатора, вход подтверждения информации которого соединен с выходом подтверждения информации арбитра маршрутизатора, вход блокировки которого соединен с выходом блокировки маршрутизатора, группа выходов выбора которого соединена с группой входов выбора коммутатора каналов, а также с входами выбора выходных автоматов и приемников, выходы занятости выходных автоматов и выходы занятости приемников соединены с группой входов занятости маршрутизатора и группой входов занятости коммутатора каналов, группа выходов данных которого соединена с входами адаптеров выходных каналов и входами приемников, выход n-го адаптера выходного канала соединен с входом ответов n-го выходного автомата и с n-ным входом группы входов ответа коммутатора каналов, выход ответа l-го приемника соединен с (N+l)-м входом группы входов ответов коммутатора каналов, n-й выходной канал соединен с группой канальных входов-выходов n-го адаптера выходного канала, l-й реципиентный канал соединен с группой канальных входов-выходов l-го приемника. 2. Сеть по п. 1, отличающаяся тем, что маршрутизатор содержит блоки прокладки адаптивных и неадаптивных маршрутов, N схем ИЛИ, блок программирования, схему сравнения и схему определения оптимальных маршрутов, причем группа информационных входов маршрутизатора соединена с группами информационных входов схемы сравнения, схемы определения оптимальных маршрутов и блоков прокладки адаптивных и неадаптивных маршрутов, группа входов номера источника маршрутизатора соединена с группой входов номера источника блока прокладки адаптивных маршрутов, группа входов занятости маршрутизатора соединена с группами входов занятости блоков прокладки неадаптивных и адаптивных маршрутов, группы выходов ответов которых объединены и соединены с группой выходов ответа маршрутизатора, выход готовности данных маршрутизатора соединен с входами разрешения блока программирования, блоков прокладки адаптивных и неадаптивных маршрутов, группа выходов блока программирования соединена с группами входов программирования блока прокладки адаптивных маршрутов, схемы определения оптимальных маршрутов и схемы сравнения, выход которой соединен с входом равенства блока прокладки адаптивных маршрутов, группа входов оптимальных маршрутов которого соединена с группой выходов схемы определения оптимальных маршрутов, первая группа выхода выбора блока прокладки неадаптивных маршрутов соединена с первыми входами группы элементов ИЛИ, вторые входы которой соединены с выходами выбора блока прокладки адаптивных маршрутов, выход программирования блока прокладки неадаптивных маршрутов соединен со стартовым входом блока программирования, выход блокировки которого соединен с входами блокировки блоков прокладки адаптивных и неадаптивных маршрутов и с выходами блокировки маршрутизатора, группа выходов выбора маршрутизатора соединена с выходами элементов ИЛИ и с второй группой выходов выбора блока прокладки неадаптивных маршрутов. 3. Сеть по п.2, отличающаяся тем, что схема определения оптимальных маршрутов содержит N регистров маски, N регистров условия, N регистров координат, N регистров связи, N схем сравнения, N элементов 2-2-2И-3ИЛИ, N групп элементов ИЛИ по N элементов в каждой, N групп элементов 2И по (S-1) элементов в каждой и N элементов И, причем группа информационных входов схемы определения оптимальных маршрутов соединена с группами информационных входов регистров и с первыми входами групп элементов 2И, вторые входы которых соединены с группами выходов регистров маски, группа входов программирования схемы определения оптимальных маршрутов соединена с входами записи регистров, выходы групп элементов 2И соединены с первыми группами входов схем сравнения, вторые группы входов которых соединены с группами выходов регистров координат, выходы схемы сравнения соединены с первыми входами элементов 2-2-2И-3ИЛИ, вторые входы которых соединены с выходами регистров условий, выходы элементов 2-2-2И-3ИЛИ соединены с первыми входами групп элементов ИЛИ, вторые входы которых соединены с выходами регистров связи, выходы групп элементов ИЛИ соединены с входами элементов И, выходы которых и являются выходами схемы определения оптимальных маршрутов. 4. Сеть по п.2, отличающаяся тем, что блок прокладки адаптивных маршрутов содержит пять групп элементов И по N элементов в каждой, мультиплексор, три N-входовых элемента ИЛИ, сумматор, регистры, схему сравнения, три приоритетных шифратора, схему кодирования ответа, два дешифратора, элемент И, причем группа информационных входов блока прокладки адаптивных маршрутов соединена с информационными входами регистров, входы записи которых соединены с группой входов программирования блока прокладки адаптивных маршрутов, вход равенства которого соединен с третьим входом схемы кодирования ответа, группа выходов которой является группой выходов ответа блока прокладки адаптивных маршрутов, группа входов оптимальных маршрутов которого соединена с информационными входами мультиплексора и пятыми входами первой группы элементов И, группа входов занятости блока прокладки адаптивных маршрутов соединена с инверсными входами второй группы элементов И и первыми инверсными входами пятой группы элементов И, вторые инверсные входы которой объединены с вторыми входами третьей группы элементов И и инверсными входами четвертой группы элементов И и соединены с выходами регистра связей, группа входов номера источника блока прокладки адаптивных маршрутов соединена с адресными входами мультиплексора и группой входов первого дешифратора, группа выходов которой соединена с инверсными входами первой группы элементов И, выход мультиплексора соединен с вторым входом схемы кодирования ответов, пятый вход которого соединен с выходом элемента И, первый вход которого соединен с одним из входов группы информационных входов блока прокладки адаптивных маршрутов, входы разрешения и блокировки которого соединены с вторым и инверсным входами элемента И соответственно, выходы первой группы элементов И соединены с прямыми входами второй группы элементов И и входами сумматора, выходы которого соединены с первыми входами схемы сравнения, вторые входы которой соединены с выходами регистра числа, выход схемы сравнения соединен с четвертым входом схемы кодирования ответа, первый вход которой объединен с входом разрешения второго приоритетного шифратора и инверсным входом разрешения третьего приоритетного шифратора и соединен с выходом второго элемента ИЛИ, входы которого объединены с первыми входами третьей группы элементов И и прямыми входами четвертой группы элементов И и соединены с выходами второй группы элементов И, выходы третьей группы элементов И соединены с входами первого приоритетного шифратора и входами первого элемента ИЛИ, выход которого соединен с входом разрешения первого приоритетного шифратора и инверсным входом разрешения второго приоритетного шифратора, входы которого соединены с выходами четвертой группы элементов И, выходы пятой группы элементов И соединены с входами третьего приоритетного шифратора и входами третьего элемента ИЛИ, выход которого соединен с шестым входом схемы кодирования ответов, выход разрешения которой соединен с входом разрешения дешифратора, входы которого соединены с объединенными выходами приоритетных шифраторов, выходы выбора блока прокладки адаптивных маршрутов соединены с выходами дешифратора.