Система децентрализованного обмена информацией

 

Союз Советских

Социалистических

Республик

ОП ИСА

ИЗОБРЕТ

К АВТОРСКОМУ СВИД (бl) Дополнительное к авт. сви (22) Заявлено 15.01,71 (21) 16 с присоединением заявки № (23) Приоритет (43) Опубликовано 05.05. 7733ю (45) Дата опубликования описа

1) М. Кл2

6 06 Т 3/Oт

G 96 W 15/16;авва(Государственный иамитет

Совета Министров СССР

Ilo делам иэааретений и открытий

) УДК681.5:62- 50 (088.8) А. Ф. Григорович, Ю, Н. Максименко и A. А. Попов (72) Авторы изобретения (71) Заявитель (54) СИСТЕМА QEUEHTPAËHÇÎÂAHHÎÐÎ ОБМЕНА ИНФОРМАЦИЕЙ

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

Известна система обмена сетевого тица, содержащая вычислительные машттньт и ком« мутаторы, объединенные в коммутационную сеть (11. Задача управления сетью состоит в том, чтобы для различных ситуаций на 30 сети каждый раз из большого количества возможных путей между двумя машинами найти кратчайший по отношению к количеству транзитов. В известной системе обмена эта задача решается централизованно .íà l5 основе полной информации о состоянии всех элементов системы.

Эта система обмена имеет недостатки: наличие единственного центрального органа (пульт управления, программа-диспетчер ) и необходимость наличия устройств отображения текущего состояния элементов сети, что уменьшает надежность всей системы обмена. 25

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

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

557358

Белью изобретения является повышение быстродействия и надежности системы обмена информацией.

Дпя. э гого каждое. устройство управления обменом содержи г блок формирования рельефа системы и (,т1 - 1) блоков выбора направления обмена, причем входы каждого блока фоомйрования рельефа системы и пер» вые входь (,т1-1) блоков выбора направления обмена соединены с соответствующими выходами блока аппаратного контроля данной вычислительной машины, а инверсный выход блока формирования рельефа сисгемы соединен со вторыми входами блоков выбора направления обмена смежных уст у ройств управления обменом, первые выходы каждого блока выбора направления обмена соединены управляющими шинами с соответ ° ствующими вторыми входами смежных блоков выбора направления обмена, а вторые выходы 20 через шины включения с соответствующими коммутаторами, при этом прямые выходы всех блоков формирования рельефа соединены с шиной перестроения. Кроме того, каждый блок выбора направления обмена содержит 35 одновибратор, вход которого подключен к выходу элемента ИЛИ, входы которого соединены с выходами первых элементов И, первые входы которых соединены через первые элементы HE с первыми входами бло- 39

za выбора направления обмена, а вторые вхо соединены со вторыми входами блока выбора направления обмена, выход одновибратора подключен к первым входам первых элементов ИЛИ и к первым входам вторых 85 элементов ИЛИ, выходы которых подключены ко входам вторых элементов HE., выходы которых подключены к первым входам вторых элементов И, а вторые входы вторых элементов И подключены к выходу элер40 мента HIM, первые входы третьего элемента И подключены к выходам первых элемен тов И, а вторые входьг - к:выходам первых элементов ИЛИ, вторые входы которых под ключены к выходам третьих элементов И, 45 ко вторым входам вторых элементов ИЛИ и ко вторым выходам блока выбора направления обмена; каждый блок формирования рельефа системы содержит одновибраторы, вхо ды которых подключены ко входам блока 50 формирования рельефа системы, а выходы опновибраторов через элемент ИЛИ соединены с выходом блока формирования рель » фа системы.

И

На ф.п, 1 представлена блоксхема предложенной системы децечтрализованного обмена информацией четырех вычислительных машин; на фиг 2 - блок-схема устройства управления обменом, на фиг. 3 - схема бло-60 ф ка выбора направления, на фиг. 4 - схема блока формирования рельефа.

Система децентрализованного обмена информацией четырех вычислительных машин 1 содержит по числу вычислительных машин коммутаторы 2 и устройства управления обменом 3. Обмен информацией между вычислительными машинами осуществляется по информационным магистралям 4, Устрой ства управления обменом соединены управляющими магистралями 5. Устройства управления обменом подключены к коммутаторам 2 с помощью шин 6, по которым на коммутатор с устройства управления обменом выдаются сигналы-индикаторы кратчайших путей в системе.

Каждое устройство управления обменом содержит независимо работающие блоки выбора направления 7, количество которых в каждом устройстве управления на единицу меньше числа устройств управления в системе, и блок формирования рельефа 8, Входы блока формирования рельефа и блоков выбора направления . - -»го устройства управления обменом подключены к выходам соответствующего блока аппаратного контроля (на фиг. 2 не показанного). Появление сигнала S (1, ) на выходе бло» ка аппаратного контроля 1 -го узла оз-. начает отказ информационной магистрали4, связывающей i -ый узел с Р -ым узl

1 лом. (Узел системы содержит вычислительную машину, коммутатор и устройство управления обменом) ° Каждый блок формирования рельефа через элемент НЕ" 9 под ключен через управляющие шины 10 ко входам блоков выбора направления обмена смежных узлов, а выходы всех блоков фор мирования рельефов обьединены шиной перестроения 11. Шины 10 и 11 образуют упран» ляющую магистраль 5.

Блок выбора направления содержит одновибратор 15, на вход которого через элементы ИЛИ 14 и элементы И 12 поступают входные сигналы (Igw (1,1 (), "в, (j.,i,?)c блоков выбора направления смежных узлов, а выход одновибратора подключен на входы первых элементоь ИЛИ 17 и вторых элементов ИЛИ 19. Здесь 1 - индекс уз»1 ла-источника или транзитного узла, 1 — ин-. декс конечного узла. Кроме того„ блок выбора направления содержит элементы И 16, НЕ 13, 20 и элементы И 18, выходы которых подключены ко входам соответствующих блоков выбора направления смежных узлов.

Блок формированич рельефа содержит одновибраторы 21, на входы которых поступают сигналы S (1, p) с выходов блоков аппаратного контроля 23 соответствующих

557358

0 б информационных магистралей, и элемент пей ипи уэпов. В оста ;::-ьом операц,.-я,.ыре-ИЛИ 22, на выходе которого формируется. формирования Рельефа nr e» не отпичавтся сигнал, осуществляющий формирование репье- от операции формирования репьеЬа,, 1- л,с:фов. правность узла в системе эквпвален .-а яе=Ра6оТа системы управления обменом ин-, испРавностям всех его информационных маформацией основана на волновом принципе ™с i -"" e" ): поиска кратчайшего направления передачи В г-,. рпоженной сас;:.з .;е;ецентрал : эоинформации (метод рельефов), Формирова- вайыо1 бмена ик;;:..i,,..;:,.,,,. цредус:, с рено ние рельефа заключается в сопоставлении одновРеменное (параппельное) формирование каждому j -му узлу сети цепого числа «4 репьефов дпя всех конечных узпов и эт так, чтобы это число характеризовало крат= ro каждое устройс-..во управления обменом

4 чайшее расстояние от данного 4 -го узла разбивается на независимы ;функционапьна (источника информации или транзитного не связанные между собой) блоки выбора узла) до конечного узла (потребитепя ин- направлении обмена, число которых в каждом формации. или адресата). Конечный уэеп j l5 уэпе на единицу меньше количества узпов в получает число, рав О, узлы, смежные с системе. Каждый узел системы может явпять.конечным узлом, получает 1 и т.д. В сети ся как источником информации(узел-источсформирован J -рельеф, еспи устам се- н ик), так и потребителем информации (коти приписаны такие числа, а сами числа, печным узлом). B каждом j -ом (+ 1 )

4 называются высотами ) -Рельефа и являют = 26 блоке выбора направления обмена формируют= ся указателями минимального копичества ся сигналы-индикаторы направления кратчайуэпов сети, через которые j -ый узеп свя- щего пути иэ данпого s =го узла в g -ый зан с конечным узпом. В многополюсной конечный узел. Иэ этих сигналов формир отсети дпя каждого конечного узпа формиру- ся управпяющие сигналы (стробы) коммутатоется свой рельеф; число рельефов равйо ко- N ра. Блоки выбора направления обмена смеж личеству конечных узлов в сети. Если дпя ных узлов постоянно обмениваются по дуппюбого 1 -го узпа известны высоты смеж пексным управйяющим шинам информацией ных узлов всех д рельефов, то данную ин- о высотах рельефа, Обьем информации о вы формацию можно представить в виде матри- сотах репьефа уменьшен до одного бита, это цы Ф (1,. ) Строки матрицы имеют индексы 30 достигается за счет направленного движе(3 =1,2,... и ), совпадающие с ния фронта вапны от центра - конечного уэпа номерами конечных узлов; стопбцы М (1,Д и за счет выравнивания скоростей движения имеют индексы V. (К = 1,2„.„р ), соот фронта волны при движении фронта волны по ветствующие номерам ветвей, связывающих различным управпяющим шинам. (Под фрон1 «ый узеп со смежными узлами; эле- том водны понимается множество узлов, меНт матриць тп" равен минимальному ко- имеющих в данный момент небольшую высс112 личеству транзитных узлов, участвующих в ту Репьефа1. обмене i -гД узла через смежный Кый узел с ) -ым конечным узлом, На этапе формирования рельефа с течением

Поиск кратчайшего пути по репьефу йз 6 времени фронт волны, перемещаясь от цен- .1 -го yaw в j -ый сводится к тому, что тра, устанавливает в узлах соответствующие в- ой строке матрицы М.(1,j) выбирает высоты Репьефа. Ввиду неоднородностей пася минимальный элемент п. - = тп 1, ) раметров линий связи и электро;:-ных схем «K = "° 2,, Р); р= t pI Индекс узйов скорость движения фронта волны по

Ро Ф р указывает на направление смежно- Раэпичным управляющим шинам может быть го узла, через который проходит кратчай- неодинакова. В описываемой системе децентра-ший путь. Аналогичным образом в смежном пиэаванного обмена информацией скорости узле устанавливается связь по кратчайше Распространения фронта вапны оинуритепьму пути к спедующему TpagsHTgoMy узлу 86 выравниваются путем добавления к номии так далее, пока информация не достигнет яальной задержке фронта волныфиксированного конечного узла. Изменения в структуре се- интервала времени 6 . Задержка h оринати, вызванные неисправностями .нформа- кова дпя всех узлов и вепичина ее выбчраетционных магистралей или узлов, сопровож ся, исходя из условия: даются переформированием рельефа. При

55 этом неисправные магистрали (узлы) исклк = r äå 4 - номинальное время распрострачаются из процесса формирования репьефа, нения фронта волны между смежными узлатак что в результате переформирования Ре- ми; льефа поиск кратчайшего пути в сети проис- Ь - максимальный разброс времени ; ходит с учетом всех изменений вызванных

6Π— число узлов максимально возмзжнеисправностями информационных магистра- ноге контура.

55735

Направленное движение фронта волны эа ключается в том, что на этапе формирования рельефа в системе существует только один центр волны - конечный узел и только одна волна, рожденная данным центром; в сисгеме исключены условия возникновения отраженных волн. В системе децентрализо ванного обмена информацией обеспечено направленное движение фронта волны и выравнивание скоростей движения фронта волны по + различным управляющим шинам, поэтому для формирования сигналов-индикаторов кратчайших путей досгаточно иметь информацию сле-дующего типа: находится ли данный узел в данный интервал времени Ьв области дейст- 16 вия фронта волны или нет. Если в данный интервал времени 1 -ый узел по Р -ому направлению попал в область действия фронта волны, то Ро -ое направчение запоминает.ся как направление кратчайшего пути, связы-® веющего 1 -ый узел с конечным.

Работа устройства управления обменом

1-го узла происходит следующим образом.

В начальный момент сигналы S (1, pal=0 если bee информационные магистрали узла исправны. При включении питания на выходах всех элементов НЕ 9 появляются единичные уровни, которые поступают на первые входы элементов И 12 блоков выбора на правления обмена. Яа вторые входы элемен ® тов И 12 через элемент НЕ 13 поступают п налы 5 (7, р} с выхода соответствующе го блока .аппаратного контроля. Поскольку все S (, p)=(1, то первый пришедший единичный уровень (например сигнал Ив„(1 1, > по первому входному направлению по одной изуправляющихшин 10) через элемент ИЛИ14 запускает одновибратор 15 и поступает на первый вход элемента И„16, На второй вход элемента И 16 поступает сигнал с вь-® хода одновибратора 15 через элемент

ИЛИ 17. Элементы И 16 и ИЛИ 17 служат для запоминания только тех сигналов

О „(j 1 р}, которые поступают на входы блока выбора направления в течение времени и длительности работы одновибратара 15; Сигнайы i (j, р}с выхода элементов И 16, являкяпиеся индикаторами направлений кратчайшего пути в системе, по щинам 6 поступают в коммутаторы 2.

Сигналы Ри х (g, i,р)с выходов блоков вы бора направления формируютсч элементами

И 18 и поступают через управляющие ши ны 10 на соответствукхпие входы блоков выбора направлений смежных узлов. При этом сигналы 0 „, (. p} появляются на окончании времени g только на тех

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

8 фа обеспечивается тем, что сигнал (p, >,р) через элементы ИЛИ 19 и HE 20 поступает на первый вход элемента И 18, формирующего сигнал Ц г (х (g 1 1 p ), а на второй вход поступают сигналы 0 „(>, р) через элементы И 12 и ИЛИ 14.

Если в результате отказа информацйонной магистрали сработал блок аппаратного контроля и сформировал сйгнал 5 (, 1 )= 1, то появление сигнала 5(1, 1 ) на входах блоков выбора направлений приводит к блокировке соответствующих элементов И 12 по вторым входам через элементы НЕ 13.

Сигналы (вх(,1, К i = 4, 2,......, n ),ранеФ поступившие на входы блоков выбора направ .лений, блокируются сигналам 5(1 ). Кромэ того, сигнал S (, 1) поступает на соответ» ствукяпие блоки формирования рельефа 8 и через одновибраторы 21 и элемент ИЛИ 22, шину перестроения 11 и элементы НЕ 9 устанавливает нулевой уровень на управляющих шинах 10. Происходит разрушение рельефов, и по истечении времени работы одновибрато» ра 21 устанавливается новый рельеф, отражающий измененное состояние системы. Длцтельность импульса одновибратора 21 долж» на быть достаточной для полного разрушении рельефа. Блок формирования рельефа 8 позволяет осуществить переформирование рельефов в системе при наличии множества сиг налов 5 (1, p) в системе.

При восстановлении отказавших информационных магистралей необходимо выключить. соответствующие сигналы 5(, p}co входов блоков выбора направлений и запустить сооч!ветствующие блоки формирования рельефа.

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

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

1. Система децентрализованного обмена информацией, содержащая Ф вычислительных

557358 машин, соединенных с блоками аппаратного контроля, по числу вычислительных машин в системе, коммутаторы и устройства уп равления обменом, причем смежные вычис лительиые машины соединены информацион» ными магистралями через соответствующие коммутаторы, о т л и ч а ю ш а я с я тем, что, с целью повышения надежности и быстродействия системы, в ней каждое уст ройство управления обменом содержит блок )p формирования рельефа системы и (n- 1 ) блоков выбора направления обмена, причем входы каждого блока формирования рельефа системы и первые входы (ъ - 4 ) блоков выбора направления обмена соединены с соответствующими выходами блока аппаратного контроля данной вычислительной машины, а инверсный выход блока формирования рельефа системы соединен со вторыми входами олоков выбора направления обмена смежнйх устройств управления обменом, первые выходы каждого блока выбора направления обмена соединены управляюшими шинами с соответствующими вторыми входами смежных блоков выбора направления обмева, а вторые выходы - через шины включения с соответствующими коммутаторами, при этом прямые выходы всех блоков формирования рельефа соединены с шиной перестроения.

2. Система по п. 1, о т л и ч а ю m а и-

30 с я тем, что каждый блок выбора направления обмена содержит одновибратор, вход ко торого подключен к выходу элемента ИЛИ, входы которого соединены с выходаМи первых элементов И, первые входы которых сое35 динены через первые элементы НЕ с первы ми входами блока выбора направления обме- на, а вторые входы соединены со вторыми входами блока выбора направления обмена, выход одновибратора подключен к первым входам первых элементов ИЛИ и к первым входам вторых элементов ИЛИ, выходы которых подключены ко входам вторых элементов НЕ, выходы которых подключены к первым входам вторых элементов И, а вторые входы вторых элементов И подключены к выходу элемента ИЛИ, первые входы третьего элемента И подключены к выходам первых элементов И, а вторые входы - к выходам первых элементов ИЛИ, вторые входы которых подклю чены к выходам третьих элементов И, ко вторым входам вторых элементов ИЛИ и ко вторым выходам блока выбора направления обмена.

3. Система по и. l, о л и ч а юш а я с s тTеeмM,, ч тTо oкаждый блок формирования рельефа =-истемы содержит одновибраторы, входы которых подключены ко входам блока формирова.;. .ия рельефа системы, а выходы одновибраторов через элемент ИЛИ соединены с выходами йьокч формирования рельефа системы.

Источники информации, ry. инятые во внимание при экспертизе:

- 1. Алескеров С. A., Григорович A. Ф., Попов A. А., Радунский В, М. " О некоторых системах межмашинны:. связей, Сб, Электронная техника". Серия УХ, Микроэлектроника, вып. 7 (15), 1968, с. 76-82.

2. Лаптев В. И. О децентрализованной системе управления коммутируемой сетью связи". G6. "Дискретные автоматы и сети связи . М., Наука", 1970, с.23-34.

557358 (,L )

Составитель В. Максимов

Редактор И. Марховская- Техред 3. Фанта Коррекюр Л. Веселовская

Заказ 848/59 Тираж 818 Подписное

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

11ЭО35, Москва, Ж35, Раушская наб., д. 4/5

Филиал ППП Патент, r. Ужгород, ул. Проектная, 4