JPH0365750A

JPH0365750A - ネツトワークの宛先指定方法及び装置

Info

Publication number: JPH0365750A
Application number: JP2190891A
Authority: JP
Inventors: Jr Alexander H Frey; アレクサンダーハミルトン・フレイ、ジユニア; Joel M Gould; ジヨエル・マーク・ゴールド; Jr Charles M Higgins; チヤールズ・マリオン・ヒギンズ、ジユニア
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1989-07-27
Filing date: 1990-07-20
Publication date: 1991-03-20
Anticipated expiration: 2011-06-05
Also published as: EP0410568B1; CA2015968C; KR910003969A; PE10891A1; CN1049066A; AU622815B2; CA2015968A1; EP0410568A2; BR9003630A; DE69029766T2; JP2505060B2; CN1020533C; AR245303A1; US5181017A; KR930004910B1; DE69029766D1; EP0410568A3; AU5786390A

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】Ａ、産業上の利用分野本発明は、一般に、パラレル・コンピユーテイング・シ
ステムにおけるデータ処理アプリケ−シーンの改良に関
するものであり、とりわけ、多重相互結合経路（例えば
、多次元円環体ネットワーク）を備えた相互結合ネット
ワークを介して、ノマラレル・コンピユーテイング・エ
レメント間におけるデータの宛先指定を行なうための有
効な方法に関するものである。

Ｂ、従来技術及び問題点本発明は、今日のパラレルコンピュータに見受けられる
長持ち時間メツセージ処理の問題を扱うものである。こ
うしたコンピュータシステムは、高速通信ネットワーク
を介して相互結合された多数の“ノード”から構成され
る。各ノードは、−般に、プロセッサとメモリから構成
される。ノードは別個に動作し、通信ネットワークを介
してメツセージ及びデータブロックを送ることにより互
いにインターラフシロンする。

通信ネットワークは、ノードを相互結合するが、ノード
の数は、潜在的に極めて大きいので（例えば、数千）、
該システムにおいて、各ノード毎に結合リンクには、通
常、各ノードが少数の隣接ノードに対する直接リンクし
か備えないようにして用いられるものもある。こうした
ネットワークの場合、直接接続されていないノード間で
情報の伝送を行なうには、中間ノード、及び、それによ
って得られるブリッジングリンクを利用して、経路を見
つけ出さなければならない。

こうした環境では、あるノードが非隣接ノードにメツセ
ージを送らなければならない場合、利用する中間リンク
及びノードを決め、遅延を最小限におさえて、中間リン
クによりメツセージを送るための機構が必要になる。レ
ギュラネットワークの場合、所定の２つのノード間には
可能性のある多数の経路が存在する。メツセージ配送機
構は、使用中または中断された中間リンク及びメートを
避けて、多数の可能性のある経路から１つの経路を選択
することができる。また、メツセージ配送機構は、各中
間ノード毎に、プロセッサーとは関係なく動作すること
ができる。

一般に、本発明のネットワークトポロジは、多数のノー
ドを備え、各ノードが全ての側における隣接ノードと通
信リンクを共用するネットワーク案に適用することがで
きる。このタイプのトポロジ案の一例として、多次元円
環体ネットワークがある。

第１図には、２次元円環体ネットワークのトポロジが示
されている。各ボックス１０は、ノードを表わしており
、各ライン２０は、通信リンクを表わしている。第１図
では、２０のノードが、横が５つ、縦が４つのノードに
よる円環体をなすように相互結合されている。３次元円
環体ネットワークは、論理的に３次元をなすようにスタ
ックされた複数の２次元ネットワークを有している。各
ノードは、２つの追加リンクを備えており、１つは、上
方の２次元円環体ネットワークにおける相対物に対する
ものであり、１つは、下方の２次元円環体ネットワーク
における相対物に対するものである。さらに高次元の円
環体ネットワークも可能である。

パラレルコンピユーテイングシステムについては、米国
特許第４，６３Ｇ、９４８号、米国特許第４，５１４，
８０７号、米国特許第４．８１４．９８０号、第４．７
３０．３２２号、米国特許第４，８１１，２１４号、米
国特許第４・、８１４．９７９号、第４，４４５，１７
１号、第４，５４３，６３０号、米国特許第４，７４８
、ＧＨ号、米国特許第４，５９８，４００号に記載され
ている。これらの特許は、パラレル処理に関する各種ア
ーキテクチャについて記載したものであり、本発明と同
様の初期に開発された宛先指定システムの説明を行なっ
ている。

本発明は、これまでパラレル処理環境では不可能であっ
た下記の要件を扱うように設計されている。主たる要件
は、利用可能な最短経路を動的に見つけ出し、たとえ直
接接続されていなくても、多次元ネットワークにおける
任意のノードから任意の他のノードへその経路を介して
メツセージを送る能力である。この能力と、もとのまま
の通信リンクの速度に比べほんのわずかだけ遅い総伝送
時間とが組み合わせられる。通信リンクは、また、必要
時には、代替経路を利用して、混雑及び不動作リンクを
含むネットワーク状態の変化に動的に適応する能力も必
要とする。宛先指定は、中間ノードによる緩衝手法を用
いずに行なわれる。この結果、コストが低下し、ネット
ワーク資源のブロッキングとの遭遇時にわける順次探索
が排除される。最後に、ネットワーク資源は、メツセー
ジの進行が一時的にブロックされた場合、解放される能
力を備えていなければならない。

上述の要件に合致しない先行技術によるシステムの例に
は、１９８８年、Ｎｅｗ　ＹｏｒｋのＳｐｒｉｎｇｅｒ
−Ｖｅｒｌａｇより刊行されたＤｌｓｔｒｉｂｕｔｅｄ
　Ｃｏｍｐｕｔｉｎｇ　（分散形コンピユーテイング）
に掲載の、Ｄａｌｌｙ他ニヨる論文”Ｔｈｅ　ｔｏｒｕ
ｓ　ｒｏｕｔｉｎｇ　ｃｈｉｐ”（「円環体宛先指定チ
ップ」）や、１９８８年５月に刊行されたＣｏｍｐｕｔ
ｅｒ　Ａｒｃｈｌｔｅｃｔｕｒｅ　Ｎｅｗｓ　（コンピ
ュータアーキテクチャニュース）第１６巻第２号に掲載
の、Ｃｈｏｖ他による論文”Ｈｙｐｅｒｓｗｉｔｃｈ　
Ｎｅｔｗｏｒｋ　ｆｏｒ　ｔｈｅ　Ｈｙｐｅｒｃｕｂｅ
　Ｃｏｍｐｕｔｅｒ”（「ハイバーキエーブコンピュー
タ用ハイパースイッチネットワーク」）などがある。

円環体宛先指定チップの論文には、とりわけ、多次元円
環体ネットワークにおける長待ち時間宛先指定が行なえ
るように設計されたパラレル・コンピユーテイング・ネ
ットワークの宛先指定チップの説明が行なわれている。

該チップは、宛先に届くように、中間ノードを介してメ
ツセージの宛先指定を行なう順序をあらかじめ設定する
。　′カットスルー”宛先指定として知られる技術が、
用いられる。この技法は、中間ノードにおいて各バイト
を受信するとすぐにこれを転送するものである。従って
、総伝送時間がちとのままのリンク速度に近づき、中間
ノードにおいて緩衝手法は不要になる。　“カットスル
ー”宛先指定については１１９８９年のＡＣＭ　Ｓｙｍ
ｐｏｓｉｕｍ　ｏｎ　Ｐａｒａｌｌｅｌ　Ａｌｇｏｒｉ
ｔｈｍｓａｎｄ　Ａｒｃｈｉｔｅｃｔｕｒｅ　（パラレ
ルアルゴリズム及びアーキテクチャに関するＡＣＭシン
ポジウム）における”Ａ　Ｆｒａｍｅｗｏｒｋ　ｆｏｒ
　Ａｄａｐｔｉｖｅ　Ｒｏｕｔｉｎｇ　Ｉｎ　Ｍｕｌｔ
Ｉ　Ｃａｍｐｕｔｅｒ　Ｎｅｔｗｏｒｋｓ”（「マルチ
コンピュータネットワークにおける適応宛先指定に関す
る構成」）にさらに詳細に述べられている。

円環体宛先指定チップに関する、とりわけ、“カットス
ルー”宛先指定に関する問題は、あらかじめ設定される
経路は静的であり、送り出しノードと宛先ノードとの相
対位置だけに基づくものであるという点にある。その経
路におけるリンクのどれかに中断が生じると、代替経路
の利用ができたとしても、該ネットワークを介したメツ
セージの宛先指定が行なえないことになる。また、ネッ
トワークにおけるリンクに関して回線争奪が生じる場合
、１つ以上のメツセージの転送について、その進行が一
時ブロックされることになる。この結果、さらに、１つ
以上のメツセージの転送の進行がブロックされる。ブロ
ックされたメツセージは利用している経路を解放しない
ので、これらのメツセージのブロックは、さらに他のメ
ツセージに影響を及ぼすことになる。従って、メツセー
ジの進行が一時的にブロックされると、ネットワーク資
源の解放ができなくなる。

ハイパースイッチの参考文献を用いて、ハイパーキュー
ブコンピュータにおけるメツセージの宛先指定を行なう
。ハイパーキューブは、多次元円環体ネットワークの特
殊なケースであり、各次元におけるノード数は、常に２
に等しい。ハイパースイッチネットワークは、適応宛先
指定を実施する。従って、メツセージの伝送前に、可能
性のある全ての経路の探索を実施して、混雑や中断され
たリンクのない経路を識別する。この結果、ハイパース
イッチの宛先指定は、ネットワークの状態の変化や不動
作リンクに対し動的に適応することが可能になる。該宛
先指定は、また、緩衝手法を必要とせず、ネットワーク
の初期調査において阻止されていることが検出されると
、ネットワーク資源を解放する追加能力を備えている。

上述のように、ハイパースイッチの論文に記載の能力は
、ハイパーキューブコンピュータに関してのみ用いられ
る。これは、所定の今日における多次元ネットワークの
実施を極度に制限している。

さらに、ハイパースイッチの順次予備探索は、望ましく
ないオーバヘッドである。

本発明には、前述の問題も、制限も存在しない。

Ｃ０発明の要旨本発明によれば、これらの目的は、該システムの全ての
ノードに配置された同一の宛先指定機構を用いて、ノー
ドから７−ドへと有効な情報の宛先指定を行なうことに
よって達成される。各宛先指定機構には、従来のクロス
バ−（スペース）スイッチを介して結合された送信機／
受信機対が含まれている。各送信機／受信機対には、他
の隣接ノードとの双方向性通信リンクが組み込まれてい
る。各送信機／受信機対には、常駐ノードのプロセッサ
及びメモリに対する専用リンクが含まれている。

情報は、経路記述ビットから成る見出しを利用してノー
ドからノードへ中断される。情報が宛先ノードヘガイド
される際、各７−ドの受信機／送信機対は状態を変化さ
せる。このメツセージは、いくつかのノードを介して同
時に伝搬され、該ノードを横切って迅速に宛先ノードへ
到達する。最後ノード接続が行なわれると、後続の全通
信リンクが、ネットワークを通じて送り返される指令に
よって解放される。

本発明は、直接接続されていなくても、多次元ネットワ
ークにおける任意のノードから任意の他のノードへメツ
セージを送ることが可能である。

宛先指定は、二地点間リンク速度に近い総伝送時間で行
なわれる。

宛先指定は、必要があれば、代替経路を利用し、混雑や
動作不能リンクを含むネットワーク状態の変化に対し動
的に適応するように構成されており、メツセージの緩衝
手法は用いられない。該アーキテクチャは、ブロックさ
れたメツセージを検出し、ネットワーク資源を動的に解
放して、ネットワークの制約を緩和するのに十分な順応
性を備えている。

Ｄ、実施例本発明は１、システム内の全てのノードと１対１で連係
した多数の同一の宛先指定機構を利用する。

第２図を参照すると、ノード１０，１１．１２、及び、
１３の間の通信リンクは、宛先指定機構２００．２１０
．２２０、及び、２３０と直接結合している。

通信リンクは、ローカルエリアネットワーク、または、
今回ノード間の通信に一般に用いられている他の標準的
な各種通信媒体のうち任意のものとすることができる。

宛先指定機構、プロセッサ、及び、メモリは、８０３８
Ｂプロセツサ及び互換性メモリのような、一般に利用さ
れている各種プロセッサ及びメモリのうちから任意に選
択することができる。

各宛先指定機構は、さらに、対応するノードのプｏ　セ
ーフすまたはメーｔ：す１００，１１０１１２０゜及び
、１３０に対するリンクを備えている。ノード１０の通
信りアク２１．２２．２３、及び、２４のそれぞれは、
第３図の詳細な説明と相関させるため、別個にラベル表
示されている。

宛先指定機構にサポートされるリンクの数は可変であり
、そのネットワークの次元の数によって決まる。本発明
の詳細を簡略にするため、第１図に示すものと同様の２
次元ネットワークであると仮定する。第１図において、
各ノード１ｏは、通信リンク２０を介して４つの隣接ノ
ードに結合されている。これ以上の次元をサポートする
のに必要な事項については、後述の説明において補足す
る。

第３図には、２次元円環体ネットワークのための宛先指
定機構に関する内部アーキテクチャが示されている。２
次元円環体ネットワークの場合、各宛先指定機構は、４
つの双方向性リンク、すなわち、他の宛先指定機構（他
のノードにおける）に対する入力リンク３００及び出力
リンク３２０と、それ自体のノードのプロセッサまたは
メモリに対する１つの特殊な入力リンク３１０及び出ヵ
リンク３３０をサポートする。該リンクは、双方向性の
ため、５つの受信機３０１．３０２．３０３．３０４．
３１０と５つの送信機３２１．３２２．３２３．３２４
．３３０が必要になる。各種リンク間における情報のス
イッチに用いられるハードウェアの一例として、クロス
バ−スイッチ３５０が示されている。本発明の他の実施
例では、クロスバ−スイッチの代りにスペーススイッチ
を用いることも可能である。

各リンクは、そのリンクがデータを送る方向に従って適
当なラベル表示が施されている。例えば、Ｗ十受信機３
０１及びＷ十送信機３２１は、第２図における通信リン
ク２１に対応し、Ｗ−受信機３０２及びＷ−送信機３２
２は、通信リンク２２に対応し、Ｘ十受信機３０３及び
Ｘ十送信機３２３は、通信リンク２３に対応し、Ｘ−受
信機３０４及びＸ−送信機３２４は、通信リンク２４に
対応する。　′インジェクタ”３１０は、他のノードか
らではなく、そのノードのプロセッサまたはメモリから
データを受信する特殊な受信機である。

“エキストラクタ”３３０は、他のノードではなく、そ
のノードのプロセッサまたはメモリにデータを送る特殊
な送信機である。

クロスバ−スイッチ３５０は、リンク受信機３０１〜３
１０からリンク送信機３２１〜３３０へのｌ対多スイッ
チングを行なえるようにする。結合を行なうため、各受
信機３０１〜３１０は、送信に用いようとする送信機３
２１〜３３０を表わす選択マスクをクロスバ−スイッチ
３５０に提示する。特定の送信機の利用が可能な場合に
限り、クロスバ−スイッチ３５０によって結合される。

経路が開くと、送信機は、クロスバ−スイッチが、前に
結合されていた通信リンクを解放するように要求する。

選択マスク選択マスクは、各受信機によってクロスバ−スイッチに
加えられる４ビツトの指令ワードから構成される。選択
マスクが全くゼロの場合、クロスバ−スイッチは、その
受信機からエキストラクタへの経路を開始する。選択マ
スクが非ゼロの場合、各ビットを用いて、対応する送信
機に対しである経路を開放すべきか否かを指示する。例
えば、０００１の選択マスクは、クロスバ−スイッチ３
５０に対し、そのマスクを提示した受信機、例えば、受
信機３０１からＷ十送信機３２１への経路を開放する試
みを行なうように命じる。１０１０の選択マスクは、２
つの経路、すなわち、受信機３０１からＷ−送信機３２
２への経路、及び、受信機３０１からＸ−送信機３２４
への経路を要求する。

クロスバ−スイッチ３５０によって２つ以上の経路が開
放される場合、受信機によって発生する全てのバイトが
、結合されている全ての送信機に送られる。

第９図を参照すると、受信機及びインジェクタモジュー
ルの状態変化を表わすフローチャートが示されている。

各受信機は、２つの主たる状態遊休状態及び活動状態を
有している。遊休状態の場合、リンクを介して受信する
第１のバイトは、メツセージの開始を表わしており、そ
の受信機が活動状態に入るようにさせる。判定ブロック
９００では、リンクまたはメモリからのバイトの有無が
テストされる。バイトが検出されると、受信機は、活動
状態に入る。検出されなければ、受信機は、遊休状態に
戻る。機能ブロック９１０において、受信機は、クロス
バ−スイッチに対する選択マスク（上記参照）として“
最初に受信した”バイトの最下位ニブル（４ビツト）を
利用する。この選択マスクは、クロスバ−スイッチに提
示されると、１つ以上の送信機に対する１組の所望の経
路を表わす。

判定ブロック９２０では、使用中または動作不能の送信
機についてテストする。利用できる送信機がなければ、
機能ブロック９８０において処理が継続され、リンク閉
鎖指令がリンクを介して送り返される。クロスバ−スイ
ッチを介して利用できる経路が少なくとも１つでもあれ
ば、判定ブロック９４０において、追加バイトによるデ
ータの有無がテストされる。データが存在すれば、機能
ブロック９５０に示すように、クロスバ−スイッチを介
して送られる。追加バイトによるデータがなければ、制
御が機能ブロック９Ｅ３０に移行する。

第１０図を参照すると、各送信機は、４つの状態−遊休
、探索、活動、及び、遅延状態−を有している。送信機
は、遊休状態で始まり、判定ブロック８０００で示すよ
うに、クロスバ−スイッチを介して受信機に結合されな
い限り、その状態にとどまる。この状態の場合、データ
の送受信は行なわれない。クロスバ−スイッチ３５０に
よって送信機と受信機が結合されると、送信機が最初に
受信するバイトは“選択マスク”バイトである。

機能ブロック８０１０では、　′選択マスク”をオペラ
ンドの１つとし、一致に基づくビットマスクをもう１つ
のオペランドとしてビットに関する論理積の演算を行な
う。この演算によって、クロスバ−スイッチ３５０を介
した経路の選択が行なわれる。可能性のある値及びそれ
に関連した機能ブロックを下記に示す。

１１１０・・・Ｗ十送信機（８０２０）１１０１・・・
Ｗ−送信機（８０３０）ｔｏｔｔ・・・Ｘ十送信機（８
０４０）０１１１・・・Ｘ−送信機（８０５０）ｏｏｏ
ｏ・・・エキストラクタ（８０５５）次に、機能ブロッ
ク８０６０において、この結果がワークと呼ばれるレジ
スタに記憶される。ワークレジスタに記憶されると、判
定ブロック８０７０において、その値が非ゼロであるか
否かが判定される。値が非ゼロの場合、機能ブロック８
０９０で処理が続行され、　′マスクバイト”が廃棄さ
れる。　′マスクバイト”の廃棄後、送信機は、探索状
態に入る。値がゼロ場合、′マスクバイト”を廃棄し、
エキストラクタとして活動状態に入ることにより、処理
が続行される。

探索状態において、送信器は、引続き受信する各バイト
に修正を加え、その結果をそのリンクから送り出す。第
１１図に示す流れ図には、送信機及びエキストラクタに
よって用いられる探索状態の論理の概略が明らかにされ
ている。

判定ブロック９１００において、受信したバイトがリン
ク閉鎖指令か否かの判定が行なわれる。

受信したバイトがリンク閉鎖指令であれば）ブロック９
１９０で処理が続行され、クロスバ−スイッチを通る経
路が閉じられて、状態は遊休状態になる。

受信したバイトがリンク閉鎖指令でなければ、判定ブロ
ック９１１０において、追加バイトがクロスバ−スイッ
チから得られるか否かの判定が行なわれる。得られなけ
れば、処理が機能ブロック９１００に戻されるか、さも
なければ、ワークレジスタのバイト及び受信バイトに従
ってビットに関する論理私演算が行なわれる。これは、
機能ブロック９１２０において行なわれる。

さらに、判定ブロック９１３０において、演算の結果が
、００００１００１１．１ｔＯＯ１及び、１１１１と比
べられる。判定ブロック９１３０のテストがうまくいか
なければ（すなわち、一致しなければ）、機能ブロック
９１４０において処理が続行され、演算結果が次のノー
ドに送られる。

一致が検出されると、機能ブロック９１５０において受
信バイト及びワークレジスタのバイトに基づいてビット
に関連した論理積演算が行なわれる。

結果は、機能ブロック９１６０に示すように、ワークレ
ジスタの新しい値になる。

判定ブロック９１７０において、受信バイトは、ｏｏｏ
ｏと比べられる。受信バイトが０ＯＯＯに等しければ、
送信機は、遅延状態に入る。等しくなければ、ワークレ
ジスタの新しい内容が判定ブロック９１８０においてｏ
ｏｏｏと比べられる。

その内容がｏｏｏｏに等しければ、機能ブロック９２０
０において、送信機は受信バイトを廃棄し、活動状態に
入る。等しくなければ、ブロック９１００において続行
することにより、処理が反復される。

活動状態及び遅延状態の場合、受信した全てのバイトは
、修正を加えずに、送信機のリンクから送り出される。

情報の宛先がエキストラクタになっている場合、これは
、そのノードのプロセッサまたはメモリがそのバイトを
直接利用できるようになるということを意味している。

これら２つの状態の差は、遅延状態の場合、余分なバイ
トを送り出す必要があるため、ワークレジスタにおいて
入力バイトが１サイクル分だけ遅延するという点にある
。

第１２図のフローチャートには、送信機及びエキストラ
クタのモジュールに関する活動状態と遅延状態の概要が
示されている。活動状態において、機能ブロック１２０
０では、受信バイトがリンク閉鎖指令であるか否かの判
定が行なわれる。受信バイトがリンク閉鎖指令である場
合、機能ブロック１２フ０において、このモジュールに
対するクロスバ−スイッチの経路を閉じることによって
、処理が続行される。受信バイトがリンク閉鎖指令でな
ければ、判定ブロック１２１０において追加バイトが存
在するか否かが判定される。存在しなければ、判定ブロ
ック１２００において処理が続行され、さもなければ、
機能ブロック１２２０において、最遅バイトが次のノー
ドに送られる。

第１３図のフローチャートには、遅延状態の処理が示さ
れている。処理は、受信バイトがリンク閉鎖指令である
か否かの判定を行なう判定ブロック１２３０におけるテ
ストで開始される。受信バイトがリンク閉鎖指令であれ
ば、機能ブロック１２８０において、このモジュールに
対するクロスバ−スイッチの経路を閉じることによって
、処理が続行される。受信バイトがリンク閉鎖指令でな
ければ、判定ブロック１２４０において追加バイトが存
在するか否かの判定が行なわれる。存在しなければ、処
理はブロック１２３０に戻るか、さもなければ、機能ブ
ロック１２５０においてワークレジスタ１２５０の内容
が次のノードに送られる。次に、機能ブロック１２６０
において、受信バイトがワークレジスタに記憶される。

最後に、機ｔブロック１２９０に示すように、受信バイ
トが廃棄される。

探索、活動、遅延状態のいずれかにある間に、送信機が
データを送り込んでいる受信機（すなわち、そのリンク
のもう一方の側にある受信機）からリンク閉鎖指令が送
り返される場合、送信機は、そのメツセージの転送に対
する関与を終了し、クロスバ−スイッチに対し、現在そ
れにデータを送っている受信機からそれを切断するよう
に命じ、遊休状態に戻る。受信機に接続された全ての送
信機が遊休状態に戻ると、該受信機には、もはやどの送
信機にも接続されていないことが伝えられ、該受信機は
、遊休状態に戻る。リンクが動作しない場合、そのリン
クを駆動する送信機は、決して遊休状態を出ることがな
い。不動作リンクに対しクロスバ−スイッチを介してバ
イトを受信すると、リンク閉鎖指令を受信した場合のよ
うに、送信機はｔぐにクロスバ−スイッチに命令し、そ
の接続をドロップさせる。最後に、伝送途中でリンクが
動作しなくなると、送信機は、すぐに同様にしてその接
続を中断する。

データに加え、各リンク及びクロスバ−スイッチを介し
て少数の指令を送り出したり、送り返したりすることが
できる。これらの指令は、独立した制御ワイヤとして、
または、データにおいて縦に並べた特殊な拡張文字とし
て実施される。この実施は、リンクの設計によって異な
る。

リンク閉鎖指令は、あるノードの受信機から別のノード
の送信機へ、リンクを介して（データの流れとは逆の方
向に）送り返される。前述のように、リンク閉鎖によっ
て、送信機は遊休状態に戻り、クロスバ−スイッチを介
してその接続を閉じる。クロスバ−スイッチを通る経路
が１つしか開いてなければ、さらに、今度は送出しノー
ドに１ホツプだけ近いリンクを介して、もう１つのリン
ク閉鎖指令を送り出す。

メツセージの終り指令が、送出しノードから宛先ノード
ヘリンク及びクロスバ−スイッチを介して送られる。デ
ータバイトの場合と同様に、中間の受信機及び送信機が
、該システムを介してメツセージの終り指令を送信する
。宛先ノードがメツセージの終り指令を受信すると、巡
回欠員検査（ｃＲＣ）のチエツクを行なう。ＣＲＣが適
正であれば、肯定応答指令を送り返し、これに続いてリ
ンク閉鎖指令が送り返される。ＣＲＣに間違いがあれば
、リンク閉鎖指令だけが送り返される。

肯定応答指令は、各リンクを介して受信機から送信機へ
送り返され、また、各クロスパースイ。

チを通じて、送信機から受信機へ送り返される。

それは、メツセージをうまく受信した後に限って、宛先
ノードによって発生する。各中間宛先指定機構は、何ら
のアクションも起さずに、肯定応答指令を送出しノード
に送り返す。送出しノードにおいて、肯定応答指令を用
い、メツセージの受信がうまくいったことを表示する。

メツセージを送るため、送出しノードは、後続セクシ目
ンから戒るデータストリーム（転送順にリストされてい
る）を発生する。データは、ネットワークにおける各リ
ンクと同じ速度で送出しノードの宛先指定機構における
インジェクタに送られるのが望ましい。

１、宛先指定見出しくゼロ以上のバイト）２、ゼロバイ
ト（見出しを終了させる）３、送られるメツセージ（ゼ
ロ以上のバイト）４、メツセージのＣＲＣ（見出しを含
まない）５、メツセージの終り指令メツセージの受信が正確に行なわれると、送出しノード
は、そのインジェクタから肯定応答指令を受信し、引続
き、リンク閉鎖指令を受信する。

肯定応答指令がなくて、リンク閉鎖指令を受信する場合
、送出しノードは、メツセージが受信されなかったので
、再度送り出さねばならないものと理解する。

メツセージがその宛先ノードに到達すると、送られたバ
イトが、ネットワークにおけるリンクと同じ速度で、宛
先ノードの宛先指定機構におけるエキストラクタから送
られた順序で現われる。見出しくその終りを表わしたゼ
ロバイトを含む）は、宛先には現われず、メツセージ、
ＣＲＣｌ　及び、メツセージの終り指令だけが、エキス
トラクタに生じる。

メツセージの終り、肯定応答、及び、リンク閉鎖指令の
ＣＲＣ及び発生に関するチエツクは、宛先指定機構とノ
ードのプロセッサまたはメモリとの間のハードウェアが
取扱う。最後のリンク閉鎖指令が生じるまで、宛先指定
機構は、送出しノードへ戻る経路を開いた状態に保持す
ることになるので、メツセージの終り指令と肯定応答ま
たはリンク閉鎖指令との間の遅延は、できるだけ短くす
るのが望ましい。

基本見出し送出しノードによって発生し、メツセージの始めに送ら
れる見出しは、メツセージがどの１つまたは複数の経路
をとるべきかを指定する。２次元円環体ネットワークの
場合、各見出しの最下位ニブルだけが用いられる。見出
しの各バイトは、下記のように解釈される。　（ビット
Ｏは、最下位のビット。）ビット０　１にセットし、Ｗ＋の方向にリンク１つ分だ
け移動するビット１　１にセットし、Ｗ−の方向にリンク１つ分だ
け移動するビット２　１にセットし、Ｘ＋の方向にリンク１つ分だ
け移動するビット３　１にセットし、Ｘ−の方向にリンク１つ分だ
け移動するビット４〜７　２次元ネットワークにおいてＯをセット
する最も単純なタイプの見出しを構成するため、送出しノー
ドは、それと、各方向における宛先との相対距離を確め
る。見出しの長さ（バイトで表わした）は、最長の方向
における移動距離と全てがゼロからなる１バイトを加え
たものに等しい。

見出しのバイトを、各バイトが行を表わし、各列が方向
を表わしたテーブルとみなすと（上述のように）、各列
には、その方向における宛先ノードに達するまでに存在
するのと同じ数の１が充填されることになる。各列にお
いて、１は、全て、ゼロより前に現われる。従って、見
出しの最初のバイトは、最上位のビットがセットされて
おり、最後のバイトは、全てゼロである。

例えば、ノードＯ１Ｏからノード３．２へメツセージを
送るためには、Ｗ生方向に３つ移動し、Ｘ子方向に２つ
移動することになる。この移動を表わした基本見出しは
、下記に示すように、長さが４バイトになる。

００００　０１０１−最初に送られるバイトｏｏｏｏ　
　ｏｔｏｉ００００　　０００１０００〇−終りの見出し見出しを受信すると、宛先指定機構が、送出しノードと
宛先ノード間において可能性のある全ての直接経路を探
索する。宛先ノードに到達する最初のバイトストリーム
が利用される（メツセージの終りまで、開放された状態
に保持される）。他の全ての経路は、宛先に到達するの
に失敗するとすぐに放棄される（リンク閉鎖を利用して
）。

前述の例において、下記の経路が、全て、パラレルに探
索される：Ｏ２Ｏ→０，１→０，２→１，２→２，２→３，２０．
０→０，１→　１，１→１，２→２，２→３，２０．０
→０，１→１，１→２，１→２，２→３，２０、Ｏ→０
．！→２，０→２，１→３，１→３，２０、Ｏ→１，０
→　１．ｌ＋　１，２→２，２→３，２０．０→１，０
→１，１→２，１→３，１→３，２０．０→１，０→２
，０→２，１→２，２→３，２０．０→！、０→２．０
→２．！→３，１→３，２０．０→１，０→２，０→３
，０→３，１→３，２これは、この見出しの利用時に探
索されるネットワークのサブセットを示すことによって
図形で表わすことができる。第４図において、送出しノ
ードは“Ｓ”４００で表示され、宛先ノードは、“Ｄ”
４０１で表示されている。図示の他のノー１’４０２は
、全て探索時に巡回される（不動作リンクがなければ）
。

該ネットワークの１つ以上のリンクが使用中か動作不能
の場合、それらのリンクを含む経路に沿って移動するデ
ータは、宛先に到達しない。少なくとも１つの探索を受
ける経路が宛先に到達する確立を増すため、大がかりな
探索パターンが用いられる。宛先に到達する経路がなけ
れば、肯定応答指令を伴わずにリンク閉鎖指令が送出し
ノードに戻される。その場合、送出しノードは、そのメ
ツセージを再度伝送しようとするのが望ましい。

探索時、同じメツセージに対応する複数のデータストリ
ームが、はぼ同時に中間ノードと宛先ノードに集中する
。２つのストリームが同じノードに到達すると、２つの
受信機がクロスバ−スイッチに選択マスクを送って、同
じ組の送信機を求める。その各種入力に対する調停を行
なって、各送信機が１つの出力だけにしか接続されない
ように保証するのが、クロスバ−スイッチの責務である
。

調停がうまくいかなかった受信機は、どの送信機にも接
続されないことが知らされ、その結果、リンク閉鎖指令
を送り返すことになる。

代替見出しパターン宛先指定機構は、見出しに指定されたパターンを利用し
てネットワークの探索を行なう。無効な見出しが存在し
ない。前述の基本見出しの変更により探索経路数を所望
に従って増減させることができる。

例えば、宛先までの移動数の合計（プラス１）に等しい
数のバイトを利用し、各見出し毎にｌビットだけセット
することによって、単一経路を指定することができる。

第５図において、（０，０）５０１から（１，２）５０
２への宛先指定を行なうめたの見出し５００と、結果生
じる探索パターンについて考察する。

余分なゼロピットを見出し６００の列の中央に挿入する
ことによって、多数のノードを介して送られているメツ
セージについて、探索パターンを狭くすることができる
。この例が、第６図に示されている。最後の行を除く全
ての行が非ゼロでなければならない点に留意されたい。

冗長移動（同じ方向における正と負の移動）を含めるこ
とによって、探索パターンを拡張し、第７図において７
００１　第８図において８００で示すような代替経路を
含めることが可能になる。

結合性の拡張下記の２例においては、１次元の経路が２次元の探索に
拡張される。両方の場合とも、直接経路が最初に見つか
るので、それが利用可能であれば、宛先指定機構はそれ
を利用する。本発性の結合性は、多種多様なやり方で拡
張することができる。

結合性を拡張する最も簡単なやり方は、３次元以上のネ
ットワークに本発明を利用することである。

次元数を増すため、追加受信機及び送信機を加えること
により、各ノードの宛先指定機構が拡張される。例えば
、４次元円環体ネットワークに本発明を用いるのに必要
な変更の概要は、次の通りである：１、ノード毎に４つのリンクが加えられる（Ｙ＋、　　
ｙ−、ｚ＋、　　及び、　　Ｚ−）；２、受信機の数を
ふやして８にする；３、送信機の数をふやして８にする；４、クロスバ−スイッチを９ポートにふやす；５、ここ
で、各見出しバイトの８ビツトを全て利用する；６、抑制された見出し値のリスト（探索状態参照）を１
６にふやす。

本発明の統合性を増すもう１つのやり方は、各ノードに
おけるインジェクタ及びエキストラクタの数をふやすこ
とである。インジェクタの数を増すには、クロスバ−ス
イッチの幅を広げるだけですむ。多数のインジェクタを
備えることは、ノードが多数のメツセージを同時に送れ
るということを意味するものである。

エキストラクタの数がふえると、各ノードは、いくつか
の別個にアドレス可能なポートを備えることが可能にな
る。エキストラクタの数をふやすため、クロスバ−スイ
ッチの幅が広げられる。追加エキストラクタのアドレス
指定を行なうため、通常は抑制されている見出し値の１
つ（例えば、００１１）が、用いられる。例えば、下記
リストは、２次元ネットワークに第２のインジェクタ／
エキストラクタ対を追加するのに必要な変更の一例であ
る。

１．１つの追加インジェクタが加えられる。

２．１つの追加エキストラクタが加えられる。

３、クロスバ−スイッチの幅が、１だけ広げられる。

４、見出し値００１１を利用して、第２のエキストラク
タが選択される。クロスバ−スイッチに００１１の選択
マスクが提示される場合、クロスバ−スイッチは、その
受信機をＷ十及びＷ−送信機に結合しない；それどころ
か、その受信機は、第２のエキストラクタにしか結合さ
れない。

５、送信機が探索状態にあり、それが受信したばかりの
バイトが００１１であった場合、その通常のアクティビ
ティの代りに、下記ステップを実施することになる：ａ、ワークレジスタの値が、Ｎ０ＴＯＯＯｏ、ｏｏｔｔ
、　　ｔｔｏｏ、　　または、１１１１の場合、この値
をリンクを介して次のノードに送る；ｂ、受信したばかりのバイ）（００１１）をワークレジ
スタに記憶する；Ｃ１遅延状態にスイッチする；ｄ、受信したばかりのバイトを廃棄する。

追加インジェクタ／エキストラクタ対を用いて、宛先指
定システムに対する外部結合を行なうことができる。こ
れを行なうため、追加インジェクタ及びエキストラクタ
が、追加双方向性りンク用の受信機及び送信機として用
いられる。さらに該“外部リンク”が、端末または広域
ネットワークゲートウェイのような外部システムに対し
配線される。外部リンクを用いて該ネットワークに結合
されると、外部システムは、直接取りつけられたのがど
のノードの宛先指定機構であるかには関係なく、該シス
テム内の任意のノードとメツセージの送受信を行なうこ
とができる。

外部リンクのもう１つの利用は、本発明を共に用いるこ
とにより、２つのシステムを結合することである。ある
システムにおける１つの７−ドのインジェクタ／エキス
トラクタ対ともう１つのシステムにおける１つのノード
のインジェクタ／エキストラクタ対を結合することによ
り、一方のシステムの任意のノードからもう一方のシス
テムの任意のノードヘメッセージを送ることが可能にな
る。システム間においてメツセージの宛先指定を行なう
見出しは、次の部分から構成される＝１、外部リンクに
よってそのノードに対する宛先指定を行なう見出し；２、外部リンクを横切るバイト００１１；３、第２のシ
ステムにおいて外部リンクによりそのノードに関する宛
先ノードへの宛先指定を行なう見出し；４、宛先ノードへの宛先指定を行なうパイ）００００゜ノード間リンクの実現に用いられるテクノロジーは、さ
まざまな可能性がある。本発明の場合は、リンクが双方
向性で、はぼ同じ速度で作動するだけでよい。例えば、
通信リンクは、ノード間に制御リンクを備えた、１バイ
ト分の幅のパラレルバスで構成することができる。もう
１つの可能性のある実施例は、各方向毎に１つの、１対
の直接結合である。このリンクは、各種プロトコルを利
用し、複数のエラー補正室に適応することができる。

本発明の説明は、特定のシステム環境における望ましい
実施例に関連して行なってきたが、当該技術の熟練者に
は明らかなように、本発明は、付属のクレームの精神及
び範囲内において、修正を施し、他の異なるオペレーテ
ィングシステムで実施することも可能である。

Ｅ０発明の詳細な説明したように、この発明によれば宛先記述ビットで
複数のルート上のリンクを予約し、同時に複数のリンク
にメツセージを伝送するようにしているので、利用可能
な最短経路を動的に見つけ出し、たとえ直接接続されて
いなくても、多次元ネットワークにおける任意のノード
から任意の他の７−ドへその経路を介してメツセージを
送ることができる。また、代替経路を利用して混雑及び
不動作リンクを含むネットワーク状態に動的に適応する
ことができる。

【図面の簡単な説明】

第１図には、本発明による従来の２次元円環体ネットワ
ークのネットワークトポロジが示されている。第２図は、本発明による宛先指定機構と７−ドとの関係
を示すものである：第３図は、本発明による宛先指定機構の内部構造を示す
ものである；第４図は、本発明によるサンプルネットワークを示すも
のである；第５図は、本発明によるサンプルネットワークの探索を
示すものである；第６図は、本発明によるもう１つのサンプルネ、トワー
クの探索を示すものである；第７図は、本発明によるもう１つのサンプルネットワー
クの探索を示すものである：第８図は、本発明によるもう１つのサンプルネットワー
クの探索を示すものである；第９図は、本発明による受信機及びインジェクタのモジ
ュールに関する状態変化を示すフローチャートである；第１０図は、本発明による送信機及びエキストラクタの
モジュールに関する遊休状態を示すフローチャートであ
る；第１１図は、本発明による送信機及びエキストラクタの
モジュールに関する探索状態を示すフローチャートであ
る；第１２図は、本発明による送信機及びエキストラクタの
そジーールに関する活動状態処理を示すフローチャート
である；第１３図は、本発明による送信機及びエキストラクタの
モジュールに関する遅延状態を示すフローチャートであ
る。１０〜１３・・・ノード、　　２０〜２４・・・通信リ
ンク、１００．１１０，１２０，１３０　　・・・プロ
セッサまたはメモリ、２００．２１０，２２０，２３０・・・宛先指定機構３
０１〜３１０・・・リンク受信機、３２１〜３３０・・・リンク送信機、３５０・・・クロスバ−スイッチ

Claims

【特許請求の範囲】

（１）レギュラトポロジネットワークにおいて現在のネ
ットワーク情報によって第１ノードと第２ノードとの間
で情報を宛先指定する方法において、（ａ）主情報と現在のネットワーク情報とからなるデー
タトランザクションを構築するステップと；（ｂ）第２相互接続ノードに到る経路上の複数の伝送リ
ンクを決定するステップと；（ｃ）上記経路上の組をなす複数の伝送リンクを予約す
るステップと；（ｄ）予約した組をなす複数の伝送リンクのそれぞれに
よってトランザクションを伝送するステップと；（ｅ）そのトランザクションに残された情報がなくなる
まで、予約した組をなす複数の伝送リンクのそれぞれに
よってトランザクションの一部を継続して伝送するステ
ップと；（ｆ）トランザクションが第２ノードに到着するまでの
ステップ（ｂ）、（ｃ）、（ｄ）及び（ｅ）を反復する
ステップと：から構成されネットワークの宛先指定方法。
（２）（ａ）レギュラトポロジネットワークを探索し、
該ネットワークの状況を確めるステップと；（ｂ）トランザクションの見出しにその状況を納めるス
テップと；（ｃ）該状況を利用して、各中間ノードによる１組の適
応出力ネットワークリンクの選択を補助するステップと
：をさらに含むことを特徴とする、請求項１に記載のネッ
トワークの宛先指定方法。
（３）情報の同報通信を継続するのに十分な帯域幅を備
えた組をなす複数の伝送リンクを予約するステップをさ
らに含むことを特徴とする、請求項１に記載のネットワ
ークの宛先指定方法。
（４）組をなす複数の伝送リンクのそれぞれによって、
トランザクションの完全なパケットとして情報を伝送す
るステップをさらに含むことを特徴とする請求項１に記
載のネットワークの宛先指定方法。
（５）情報が次のネットワークリンクに送られるとすぐ
にリンクを解放するステップをさらに含むことを特徴と
する、請求項１に記載のネットワークの宛先指定方法。
（６）１次経路が確定すると、全ての２次経路を解放す
るステップをさらに含むことを特徴とする、請求項１に
記載のジネットワークの宛先指定方法。
（７）（ａ）ある経路がブロックされているか否かの判
定を行なうステップと；（ｂ）その経路がブロックされている場合には、その伝
送におけるそのノードの関与を終了させるステップと；をさらに含むことを特徴とする、請求項１に記載のネッ
トワークの宛先指定方法。
（８）レギュラトポロジネットワークにおいて、現在の
ネットワーク情報によって第１ノードと第２ノード間で
情報の宛先指定を行なうための装置において、（ａ）全情報と現在のネットワーク情報とから成るデー
タトランザクションを構築する手段と；（ｂ）第２相互接続ノードに到る経路上の複数の伝送リ
ンクを決める手段と；（ｃ）上記経路上の組をなす複数の伝送リンクを予約す
る手段と；（ｄ）予約した組をなす複数の伝送リンクのそれぞれに
よってトランザクションを伝送する手段と；（ｅ）そのトランザクションに残された情報がなくなる
まで、予約した組をなす複数の伝送リンクのそれぞれに
よってトランザクションの一部を継続して伝送する手段
と；（ｆ）トランザクションが第２のノードに到達するまで
、ステップ（ｂ）、（ｃ）、（ｄ）、及び、（ｅ）を反
復する手段と：から構成されるネットワークの宛先指定装置。
（９）各ネットワークのリンクが、同時に複数のメッセ
ージを伝達するための手段を備えていることを特徴とす
る、請求項８に記載のネットワークの宛先指定装置。
（１０）（ａ）レギュラトポロジネットワークを探索し
、該ネットワークの状況を確める手段と；（ｂ）トラン
ザクションの見出しにその状況を納める手段と；（ｃ）該状況を利用して、各中間ノードによる１組の適
応出力ネットワークリンクの選択を補助する手段と；をさらに含むことを特徴とする、請求項８に記載のネッ
トワークの宛先指定装置。
（１１）情報の同報通信を継続するのに十分な帯域幅が
得られるように、組をなす複数の伝送リンクを予約する
手段をさらに含むことを特徴とする、請求項８に記載の
ネットワークの宛先指定装置。
（１２）組をなす複数の伝送リンクのそれぞれによって
、トランザクションの完全なパケットとして情報を伝送
する手段をさらに含むことを特徴とする、請求項８のネ
ットワークの宛先指定装置。
（１３）情報が次のネットワークリンクに送られるとす
ぐにリンクを解放する手段をさらに含むことを特徴とす
る、請求項８に記載のネットワークの宛先指定装置。
（１４）前記第１と第２のノードが、共用双方向性リン
クを介して互いに接続された、独立したレギュラトポロ
ジネットワークに含まれていることを特徴とする、請求
項８に記載のネットワークの宛先指定装置。
（１５）前記第２のノードが、追加ノードによる双方向
性リンクを介して接続された外部相互結合端末装置であ
ることを特徴とする、請求項８に記載のネットワークの
宛先指定装置。
（１６）（ａ）ある経路がブロックされているか否かの
判定を行なう手段と；（ｂ）その経路がブロックされている場合には、その伝
送におけるそのノードの関与を終了させる手段と：をさらに含むことを特徴とする、請求項８に記載のネッ
トワークの宛先指定装置。
（１７）１次経路が確定すると、全ての２次経路を解放
する手段をさらに含むことを特徴とする、請求項８に記
載のネットワークの宛先指定装置。