JPS63501672A - 向上されたメッシュベ−ス交換網 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 向上されたメツシュ　ベース交換網 技術分野 本発明はローカル　エリア　ネットワーク（ＬＡＮ）の分野に関する。より詳細 には、本発明は複数の交互する方向の経路に基づくメツシュ　トポロジーを持つ 改良されたＬＡＮに関する。

発明の背景 ローカル　エリア　ネットワーク（ＬＡＮ）は、一般に比較的小さな地理エリア に制限されたデータ通信網であると考えられる。

地域的に集中されるという理由からＬＡＮは多くの面で長距離網と異なる。例え ば、ノードが必ずしも最も近いノードに接続される必要がないことからＬＡＮの トポロジーの決定には大きな自由度が与えられる。またＬＡＮは長距離網と比較 してエラー率も低い。このためエラー　チェックをリンク間ベースでなく終端間 ベースで行なうことが可能である。また、ＬＡＮの方がコストの低い通信ライン を使用することができる。

パーソナル　コンピュータの進歩及びコンピュータの普及により、数年前に開発 されたＬＡＮより処理能力が高く信頼性の優れた］、　Ａ　Ｎに対する需要が高 まっている。さらに通信網に接続されるデバイスの高度化及びＶＬＳＩの進歩に よって、より高度の網インタフェースが可能となり、このため実現可能な網の構 造及びアクセス計画の範囲が広がっている現状である。

スター、リング、バス、及びトリー　トポロジーが現在使用されている４つの標 準のＬＡＮ構造である。スター　トポロジーは中央スイッチ、つまり、ハブを持 ち、リンクによってハブが個々のデバイスに接続される。任意のデバイスから送 くられるデータパケットは必ずハブを通ってその着信先に送くられる。従って、 ハブがシステムの中央コントローラである。リンク、つまり、ループ　トポロジ ーはデバイスに接続された複数のリング　インタフェース　ユニットを接続する 複数の単方向リンクから構成される。バス　トポロジーは長い伝送チャネルであ り、これにバスインタフェース　ユニットを通じて全てのデバイスが接続される 。

デバイスはバスにアクセスするために競合するが、どのバスがアクセスできるの か選択は所定の規則に基づいて遂行される。最後に、トリー構造は木の枝状に相 互接続されたリンクから構成される。この構造においては、パケットは発信ノー ドから木の根、つまり、ヘッド終端に運ばれ、次にここから木を通って着信先に 再伝送される。

これらトポロジーは幾つかの短所を持つ。バス及びリング　トポロジーでは、個 々のパケットを伝送するために通信網の非常に多くの部分が使用される。従って 、１度に非常に少数のメツセージ、場合によっては、一度に１つのメツセージを 伝送できるのみである。スター　トポロジーはこの点においては優れ、個々の伝 送に対して通信網のより小さな部分が使用される。ただし、全てのパケットは中 央ハブを通過することが要求される。従って、中央コントローラがボトルネック となり、これによって同時に伝送できるパケットの数が制限される。トリー　ト ポロジーに関しても同様なことが言える。

もう１つの方法は、イミニ（Ｙｅｍｉｎｉ）によって、［チンカーネット：　Ｌ ＡＮとＰＢＸとの間にライフが存在するか（Ｔｉｎｋｅｒ口ｅｔ：叶Ｉｓ　Ｔｈ ｅｒｅ　Ｌｉｆｅ　Ｂｅｔｗｅｅｎ　ＬＡＮ５　ａｎｄ　ＰＢＸｓ）　］、Ｉ　 ＣＣＩ　９８３年議事録、Ｖｏｌ、３（ボストン、１９８４年）、ベージ１５０ １−５において紹介される新たなトリー　トポロジー、及びサダウイ（Ｓａａｄ ａｗｉ）及びスクワーツ（Ｓｃｈｗａｒｔｚ）によって、［双方向ＣＡＴνを通 じてのデータ伝送のための分散交換方式（Ｄｉｓｔｒ　ｉｂｕｔｅｄＳｗｉｔｃ ｈｉｎｇ　ｆｏｒ　Ｄａｔａ　Ｔｒａｎｓｍｉｓｓｉｏｎ　０ｖｅｒ　Ｔｗｏ− Ｗａｙ　ＣＡＴＶ　）　）、ＩＣＣｌ９８４年議事録、（アムステルダム、１９ ８４年５月）、ベージ１４０９−１３に紹介のこの変形である。これら通信網に おいては、ノードが交換ポイントとなり、全てのパケットが木のヘッド終端を通 過する必要性が排除される。この方法においては、個々のメツセージに対して通 信網の小さな部分が使用され、また１つのタイプの要素のみが必要とされるが、 サダウイ（Ｓａａｄａｗｉ）の方法ではパケットを格納して前送りすることが必 要であり、イミニ（Ｙｅｍｉｎｉ）の方法では、同報通信網の距離制約をとどめ る。

これら新たな方法はある程度まではリング及びバス　システムの処理能力上の制 約を解決する。ただし、これらは１つの弱い部分を持つ。通信網の信頼性を高め るためには、つまり、効率を大きく落すことなく故障できるリンクあるいはノー ドの数を増加するためには、個々の発信元と着信先との間に複数の経路を持つこ とが必要である。経路の数を適当に増加すると、ノード間の平均及び最大距離が 縮小され、メツセージは通信網のより小さな部分を使用することとなり、従って 、処理能力が向上される。さらに、複数の経路を使用すると通信網の一部に大き な負担がかかるのを回避し負荷を均一にするこきができる。

もう１つの試みは双方向ループを使用する方法である。この方法は双方向ループ によって円形に接続された複数のノードから構成される。この通信網は任意の数 のノードに対して定義され、地理的センスを持つ。これはまた単純な拡張規則及 び経路指定規則を持つ。ただし、この２つの規則は互いに互いを複雑にする。つ まり、経路指定規則はノードの順次アドレスに依存するが、これらアドレスは網 が拡張されると変更を受ける。従って、ノードアドレスに依存しない経路指定規 則を使用するか、網が変更されるたびに新たなセットのノード　アドレスを指定 することが必要となる。さらに、任意のノード間には２つの異なる経路のみが存 もう１つの一層効果的な方法は、ピアス（１’１ｅｒｃｅ）によって〔ループは どこまで延ばすことができるか（ｆｌｏｗ　Ｆａｒ　Ｃａｎ　ＬｏｏｐｓＧｏ） ）、ＩＥＥＥ　）ランザクジョン　オン　コミュニケーション、Ｖｏｌ、Ｍ−２ ０、ｋ３．１９７２年、ベージ５２７−５３０において説明の試みである。ピア ス（Ｐｉｅｒｃｅ）によるトポロジーは交換要素によって相互接続された複数の ループから構成される。

メツセージは単一ループのシステムの場合より通信網の小さな部分を使用し、従 って、最大処理能力は向上される。ユーザのサブグループ間の干渉は互いに主に 交信するユーザを同一ループ上におくことによって最小化される。この方法の主 な短所は、この方法は２つの異なるタイプの要素、つまり、交換のための要素、 及びデバイスにアクセスするだめの要素を必要とすることである。

交換要素には複雑な格納及び前送り機能が要求される。

ノード間に複数の経路を与え、上に説明のループ及びトリーシステムの短所の多 くを克服できるＬＡＮ）ボロジーの一層クラスはメツシュＬＡＮである。メツシ ュＬＡＮは中央ノードを持たず、ノード間のポイント間通信チャネルから構成さ れ、従って、安価なライン　ドライバ及び受信機が使用できる。これに加えて、 これら構造では無数の長距離接続は不用であり、互いに主に交信を行なうコミユ ニティ、つまりノードの一層を自然に形成できるという長所を持つ。メツシュＬ ＡＮにノードを加えることは比較的簡単であり、またこれら通信網は新しいファ イバ　オプティック技術対して適応し易い。

ＦＬＯＯＤＮＥＴと呼ばれるメツシュＬＡＮの１つの実現が、ヘティットヒア（ Ｐｅｔｉｔｐｉｅｒｒｅ　）によって、［メツシュド　ローカルコンピユータ網 （Ｍｅｓｈｅｄ　Ｌｏｃａｌ　Ｃｏｍｐｕｔｅｒ　Ｎｅｔｗｏｒｋｓ）　］、Ｉ ＥＥＥ　ＣｏｍｍｌＭａｇ、Ｖｏｌ、２２、Ｎ（１８、（１９８４年８月）、ペ ージ３６−４０において説明されている。ＦＬＯＯＤＮＥＴにおいては、パケッ トがあるノード４こ入って来ると、これはパケットが到着したリンクを除いてそ こから出る全てのリンク上に再伝送される。

外部パケットを除去するためのルーチンが実行され、次に、個々のパケットは通 信網全体に“ｆｌｏｏｄ　（流す）”される。

メツシュ　トポロジーを特徴とするもう１つの通信網は修正されたシャフル交換 網である。これはＮ個のノードに対して定義されるが、ここで、Ｎは厳密には２ のべき数である。個々のノードｉはノード２１モジユロＮ及び（２ｉ＋１）モジ ュロＮに接続される。このシステムの処理能力は双方向ループの処理能力より高 いが、これは地理的センスを持たず、小さなエリア内でのみ使用が可能である。

Ｎは２のべき数に制約されるため、一度に１つのノードを加える方法は知られて いない。この通信網はノード間に代替経路を提供するが、これら経路を主経路よ りもかなり長い。

つまり、ローカル　エリア　ネットワークに対する向上されたトポロジーが必要 とされることが理解できる。

発明の要約 ここに開示の通信網は偶数の交互の方向を持つ経路から構成されるグリッド　ベ ースのメツシュ通信網である。デバイスが経路の交点の所に存在し経路に接続す るノードを介して通信網に接続される。個々のデバイスがノードに接続される相 互接続とは別に、個々のノードは２つの入りリンク及び２つの出リンクを持つ。

経路の両端は接続され、従って、この経路は交差する横列ループ及び縦行ループ であるとみることもできる。このセットの交差する横列ループ及び縦行ループは 平面上ではなく円形隆起の表面上に形成されると考えて良い。本発明によると、 入りリンクに到着したそのノードに接続されたデバイスを着信先きしないパケッ トは出リンクの１つに接続され、従って、ノード内でめパケット緩衝動作は不用 である。本発明による通信網構造では、任意の２つのノード間に異なる多数の経 路が存在し、従って、第１図の通信網は多くの長所を持つ。

図面の簡単な説明 第１図は本発明の通信網の大局的な相互接続構造を示し；第２図は第１図内のノ ード１００に対する１つの実施態様のブロック図を示し； 第３図は第１図のノード１００に対するもう１つの異なる実施態様を示し； 第４図は第１図の通信網に対する経路指定アルゴリズムに従って確立される象限 及び主経路を示し； 第５図はノード１００のより詳細なブロック図を示し；第６図から第１１図は第 １図の通信網に少数の追加のノードを接続するための各種の相互接続パターンを 示し；そして第１２図は本発明の原理に従かう通信網の階層構成を示す。

詳細な説明 第１図は本発明の原理に従かう要素網の一般構造を示す。この構造は個々のセッ トが互いに平行で他方のセットの道路に垂直の２つのセットの道路から成る都市 にみられる一般的な交通レイアウトに基づく。この構成は格子を形成する。より 詳細には、第１図のトポロジーは隣接するストリート（及びアベニュウ）が一方 通行で、反対方向のマンハッタンのストリート構成に類似する。

ただし、このトポロジーは個々の経路の両端が接続され、個々の経路がループを 形成する点において都市スートリートの構成と異なる。

第１図に示されるように、１０１−１０６の番号が与えられたセットのライン及 び１１１−１１６の番号が与えられたセットの＝１０６はセットの横列ループを 形成し、経路１１１−１１６はセットの縦行ループを形成する。第１図に円１０ ０にて示されるノードは横列ループと縦行ループとの交点の所に存在する。隣接 する横列ループと縦行ループが互いに反対方向になるようなこの横列ループと縦 行ループの組合せは、偶数個の横列ループ及び縦行ループを含蓄する。この経路 網は、任意のポイントが見る者の正面にくるように２つの軸の回りに回転できる 円形隆起上にマツピングでき、従って、第１図の経路網は任意のノードを概念上 の中心に位置するように概念的に回転することができる。この回転によって、後 に詳細に説明されるように、経路指定アルゴリズムが非常に簡略化される。

ｍ個の縦行ループ（０からｍ−１の番号が与えられる）及びｎ個の横列ループ（ ０からｎ−１の番号が与えられる）を持つ網はｍＸｎ網と呼ばれる。ノード（Ｌ 　Ｊ）はノード（Ｉ＋１、Ｊ）、（■−１、月、（■、Ｊ＋１）、及び（■、Ｊ −１）にて相互接続される。ここで、■は縦行アドレスであり、Ｊは横列アドレ スである。上の■に関する加算／減算はモジュロｍにて遂行され、Ｊに関する加 算／減算はモジュロｎにて遂行される。このＩ、Ｊペアはノードの絶対アドレス とみなされる。

網内の個々のノードは網とそのノードの所に接続されたデバイス（例えば、プリ ンタ、ＰＣ，ファイル　サーバ、メイン　コンピュータ、等）との間のインタフ ェースとして機能する。網（及び対応するノード）に接続されたデバイスは特定 の地理的配列を持つ必要はないことに注意する。さらに、経路指定の目的上、持 続しない方がより意味をなす場合は、必ずも互いに最も接近して位置するデバイ スを直接に持続する必要はない。この交換方法においてはそのノードを着信先と しない個々の入りパケットは出リンクの１つに接続される。この要件は場合によ っては長い経路を選択する原因となる。この交換方法においては、あるノードの 所で好ましくない方の経路を取るようにパケットが指定されると、最悪の場合、 パケットは正方形を回わるように進行し、結果として、着信先までの経路長が４ 倍となるような経路指定アルゴリズムが使用される。ただし、実際には、殆どの 場合、経路長は全く増加されない。これは、中間ノードを特定の着信先ノードに 向かって進行する過程において、必ずしも特定の出ノードを選択する必要はない ためである。例えば、２つのノードを北に進行し、次に２つのノードを東に進行 しても、あるいはこの逆の場合も同一のノードに到達できるためである。

第２図はノード１００の１つの構造を示す。第２図において、ノード１００は入 力リンク２０１及び２０２上に信号パケットを受信し、これらパケットを出力リ ンク２２１及び２２２に伝送する。リンク２０１及び２２１は横列ループに属し 、リンク２０２及び２２２は縦行ループに属する（勿論、この横列／縦行の選択 は任意である）。パケットはまた入りリンク２０３及び出リンク２２３を介して ノード１００とローカル　デバイス２３０．！：の間で受信される。ノード１０ ０内にはスイッチ１２０が存在するが、これに全てのリンクが接続される。ただ し、この接続は必ずしも直接である必要はない。リンク２０１及び２０２はそれ ぞれ遅延要素１２１及び１２２を介してスイッチ１２０に接続され、リンク２０ ３及び２２３はそれぞれパケット　ストア１２３及び１２４を介してスイッチ１ ２０に接続される。これに加えて、ノード１００はコントロール　ブロック１１ ０を含むが、これはスイッチ１２０の動作を監視する。ノード１００はそれ自体 の絶対アドレス（Ｌ　Ｊ）を認識しており、独自のクロックにて動作する。

第２図のノード構造はスロッティッド　システム（ｓｌｏｔｔｅｄｓｙｓｔｅｍ ）と呼ばれる通信アプローチを使用する。データのパケットが対応する期間内に 伝送できる特定の数のビットに抑制され、この期間がスロットと呼ばれる。個々 のパケットはパケットに関連する幾つの情報、例えば、パケットの着信先アドレ スを含む見出し欄、伝送されるべき情報を含むデータ欄、及び異なるノード１０ ０間の通信周波数の変動を情報の損失なしに効果的に収容するための小さなマー ジン環を含む。ノード１００は、ブロック１１０の制御下において、その出リン クの個々に継続的にビットを送くり、またスロットの開始指標を定期的に送くる 。パケットはスロットの開始指標の直後にノードから送り出される。遅延要素１ ２１及び１２２は第２図のノード構造内に入力２０１及び２０２へのパケットの 到着時間の変動を補正するために含まれる。

パケット　ストア１２３及び１２４はデバイス２３０及びノード１００の異なる 伝送モードを補正するために含まれる。

ローカル　テ゛バイス２３０からのパケットは出リンクの１つが入りパケットに よって使用されてないときにのみノードによって伝送される。両方の出リンクが ビジーである場合は、発信元がスロットリングされる。このスロットリングは、 デバイス自体の所で、要素１２３によって提供される遅延以外に追加のバッファ リングが必要とならなくなるように遂行される。網がローカル　デバイス２３０ が受けることができるよりも速くパケットを送くると、パケットは出リンクの１ つに送くられ、これらはしばらくたった後に戻どってき、再度、ローカル　デバ イスへのアクセスを試る。

第３図は修正されたノード１００を示ずが、これはノー１−’１５０と同定され る。ノード１５０は第２図のノード１００と出リンク２２１及び２２２がそれぞ れＦＩＦＯ出力バッファ要素２２４及び２２５を持つことを除いて全ての点にお いて等しい。バッファ要素２２４及び２２５は少数の固定サイズ　パケットを緩 衝することができ、これによってパケットが好ましくない方の経路をとる確率を 減少する。勿論、長期的に見た場合は、バッファ２２４及び２２５が空になるた めには、この２つの出リンクを通じて伝送されるパケットの数は同一にならなけ ればならない。

第１図の網の１つの大きな長所は単純な経路指定アルゴリズムが採用できること である。個々のノードは固有の絶対アドレスを持ちその絶対アドレスを認識して いる。そして、ノードによって遂行される全ての経路指定はその固有アドレスを 基準とする入りパケットの着信先アドレスに基づいて遂行される。つまり、パケ ットがノード１００に到着すると、そのパケットの着信先アドレスが同定され、 パケットが到着したノードに対する相対アドレス（ｉ、ｊ）が着信先アドレスと の関係で計算される。ここで、着信先ノードは相対アドレス（０，０）を持つも のと想定され、パケットが到着したノードによって網の中心であるとみなされる 。

それぞれ０からｍ−１及び０からｎ−１の範囲を持つ絶対アドレス値■及びそれ ぞれＪから−（ｍ／２−１．）からｍ／２及び−（ｎ／２−１＞からｎ／２の範 囲を持つ相対アドレス値ｉ及びｊへの変換は以下の式に従って遂行される。

ここで、Ｉｄ及びＪｄベアは着信先ノードの絶対アドレスを構成し、１．及びＪ 、ベアは発信ノードの絶対アドレスを構成する。

“発信ノードはパケットを送信するノードである。ここで、このパケットは入す ノード上に受信されたパケットでも、あるいはそのノードと関連するデバイスか ら受慣されたパケットでもありうる。

１−２　（Ｊｓモジュロ２）の項はｊが奇数である場合は−１の値をとり、ｊが 偶数である場合は＋１の値をとることに注意する。

これは経路が単方向であることから導入され、また以下を前提とする。つまり、 ａ）絶対アドレス（０，０）を持つノードは、絶対アドレス（０，１）を持つノ ード及び絶対アドレス（１、Ｏ）を持つノードへの２つの出経路を持つ、ｂ）ｍ １図内の相対アドレスは右側及び上側方向に増加する、及びＣ）網は必要であれ ばｉ＝０及びｊ＝０の軸を中心にリフレクト（ｒｅｆｌｅｃｔ　）でき、この結 果、着信先ノードに入いる信号流はアドレス（ｊ−０、ｊ＝１）を持つノード及 びアドレス（ｉ＝１、ｊ−０）を持つノードからとなる。

第４図はこの経路指定規則からみた場合の第１図の通信網を示す。簡素化の目的 から第４図の通信網の端の所のノード間の接続は図示されないが、これらが存在 することに注意する。ノード４０は着信先ノードとして示され、一方、網の左下 象限内のノード４１は絶対アドレス（０、Ｏ）を持つノードとして示される。

ノード４１の所で、縦行リンクは上を指し、横列リンクは右を指す。着信先ノー ドは、相対アドレス（０，０）を持ち、概念的に通信網の中心に存在し、従って 、第４図には中心に示される。これは、たまたま、奇数の絶対縦行アドレス及び 奇数の絶対横列アドレスを持つ。

（着信先ノードの奇数／偶数状態に応じて）変換式によってｉ及びｊ軸を中心と するりフレクション（ｒｅｆ　Ｉｅｃｔ　１ｏｎ）が遂行されるため、常に、横 列ｊ−０に沿ってノード４０の右に向う主経路及び縦行ｉ＝０に沿ってノード４ ０の上に向う主経路が存在する。

主経路セグメント４２及び４３はそれぞれ左及び下方向への流れをカバーできる のみであるため、上方向及び右方向への流れをカバーするために第２のセットの 主経路が生成される。上方向主経路は好ましいセグメント４２に到達する必要が あるためｉ＝１にセットされる。右への流れは好ましいセグメント４３に到達す る必要があるためｊ＝１にセットされる。この第２のセットの主経路が第４図に ライン　セグメント４４及び４５によって示される。

ライン　セグメント４２−４５は第４図の通信網を４つの概むね等しい象限に分 割する。個々の象限内での好ましい流れは一般的には着信先ノードに向う流れで あり、より具体的には、主経路に向う流れである。これは常に同一方向である。

ただし、着信先ノードの絶対アドレスの奇数／偶数状態に応じて上に説明のりフ レクションが遂行され、発信ノードを通じての流れの方向はその絶対アドレスの 奇数／偶数状態に依存する。つまり、発信ノード内での個々のパケットに対する 好ましい出リンクはこの２つのアドレスの奇数／偶数状態の組合せによって決定 される。より具体的には、この２つのアドレスの排他的ＯＲによって簡明な制御 信号が与えられる。

上に説明の経路選択に従って、テーブル１は発信ノードの相対アドレスによって 決定される異なる位置（象限）内の経路選択をその絶対アドレスの奇数（１）／ 偶数（０）状態と着信先アドレスの奇数（１）／偶数（０）状態との間の排他的 ＯＲ関数として示す。

テーブル１ 以下に上に説明の手順をステップごとに要約する。

ステップ１２つの入り情報パケットが存在するか、あるいは１つのパケットのみ が存在するかの決定が行なわれる。１つの入り情報パケットのみがノードに入い る場合は、ローカル　デバイス２３０がパケットを送信することを望むか否か調 べられる。

ステップ１の手順の結果として、ノードの横列及び縦行リンクに１つあるいは２ つのパケットの経路指定が考慮される。１つのパケットのみが考慮される場合は 、経路選択が以下のステップ２からステップ４に従って保証される。しかし、２ つのパケットを考慮する必要がある場合は、これらの選択はパケット間の衝突を 解決するステップ５によって調節される。

ステップ２　経路指定されるべき個々のパケットから着信先ノードの絶対アドレ スが抽出され、横列及び縦行アドレスが偶数であるか奇数であるか調べられる。

ステップ３　発信ノードの相対アドレスが計算され、発信ノードがセグメント４ ２．４３．４４あるいは４５上に存在するか、あるいはＱｌ、Ｑ２、Ｑ３、ある いはＱ４内に存在するか調べられる。

ステップ４　発信ノードの絶対アドレスの奇数／偶数状態に関する知識及びステ ップ２及びステップ３の結果を使用して、テーブル１に従ってパケットの経路選 択が決定される。

ステップ５　衝突は両方の出パケットが１つの特定の出リンクを要求する場合に のみ発生する。平均では、これは１／８のみの確率で発生し、これが発生した場 合、衝突を解決する必要がある。

この衝突を解決するための１つの有効な方法として、パケットの見出し構内にそ のパケットが経路選択を拒否された回数を含む方法が考えられる。高い数を持つ パケットの選択が保証される。ただし、２つの数が同一である場合は、ランダム に選択される。

第５図はノード１００のより詳細な線図を示す。つまり、スイッチ１２０の構造 及びコントロール１１０とノード内の他の要素との間の通信をより具体的に示す 。第５図に示されるように、デバイス２３０はデータ　ライン２０３及びクロッ ク　ライン１１８を介してパケットを１２３に送くる。入り横列リンクはデータ ライン２０１及びクロック　ライン１１９を介してパケットをＦＩＦＯ（先入れ 先出し）メモリ１２１に送くり、入り縦行リンクはデータ　ライン２０２及びク ロック　ライン１０９を介してパケットをＦＩＦＯメモリ１２２に送くる。メモ リ１２１及び１２２は通常のＦＩＦＯメそりであり、入りクロック信号を使用し て片方のポートの所のデータを格納し、出力クロック信号を使用して他方のボー トの所のデータを先入れ先出しベースにて読み出す。第５図に示されるごとく、 メモＩＪ　１２１及び１２２並びにパケット　ストア１２３はライン１４７上の 共通りロック信号に応答してリード１４４−１４６上に信号出力を与える。ライ ン１４７のクロック信号はノード内のクロック回路１５０から発生される。

要素１２１−１２３に加えられるデータ及びクロック信号はマイクロプロセッサ として示される制御要素１１０に加えられる。

ライン１４８を介してローカル　タロツク１５０を受信するマイクロプロセッサ １１０としては、上に説明の経路指定規則によって指定される演算動作を遂行す る従来のデバイスが使用される。

マイクロプロセッサ１１０は、パケットの到着の開始を決定しくスロット　ビッ ト　パターンの開始を検出）、パケットの着信先アドレスを調べ、また（パケッ トが優先経路を拒否された数、及び／あるいは他の優先基準に基づき）入りパケ ットの優先レベルを決定する。これはバス１６０を介して上に説明の経路指定ア ルゴリズムに従ってノード１００の動作を制御する。スイッチ動作自体は非常に 単純である。入りパケットはスイッチ１６１によって出横列あるいは出縦行のい ずれかにスイッチされる。入りパケットの１つが失なわれている場合は、スイッ チ１６２及び１６３によってこの代わりとしてパケット　ストア１２３．からの パケットを提供することができる。入りパケットがデバイス２３０に向けられる 場合は、パケットはスイッチ１６４及び１６５を介してパケット　ストア１２４ に送くられる。

本発明においては、個々のノードは独自のクロックにて動作するため、常に入り リンク間（ご位相ズレ（ｐｈａｓｅ　ｓｋｅｗ）が発生する可能性がある。つま り、入り横列リンクに入いるパケットの開始時間が入り縦行リンクに入いるパケ ットの開始時間と異なる可能性がある。これはマイクロプロセッサ１１０によっ て以下のように解決される。ローカル　タロツク１５０によってスロットの開始 前の所定の時期に、ライン１４８はマイクロプロセッサ１１０に対して、ノード １００の入力の所にパケットが到着したことを示す内部レジスタを読み出すよう に命令する。パケットの到着が確認され、その一部が対応するＦＩＦＯメモリに 格納された後にはじめて、そのパケットが選択された出リンクに向けられる。１ つのパケットが横列あるいは縦行リンクのいずれかに（ただし、両方でない）到 着したことが確認され、また１つのパケットがデバイス２３０から到着した場合 は、この２つのパケットは上に説明の経路指定アルゴリズムに従って経路を決定 される。横列及び縦行入すリンクの両方が到着パケットを持つ場合は、これらパ ケットは上に説明のように方路され、デバイス２３０はバス１６０の一部である ライン１５１を介して絞められる。勿論、このプロセスを開始させるライン１４ ８信号は、到着パケットによって提供される情報を読み出し、必要な経路決定を 行なうのに十分な時間だけのみクロック１５０のスロットの開始に先行される。

上に説明のアドレシング計画においては、横列及び縦行ループは０からｍ及び０ からｎ（絶対アドレス）の番号を与えられる。

もう４つのアドレシング計画においては、モジュロ２分数アドレシング計画が使 用される。この方法は、通信網が最初率さな規模で建設され後に拡張する場合に もあるいは通信網が最初からフルサイズに建設される場合にも有効である。この アドレシング計画は、２つの縦行ループから開始され、個々の拡張において、（ 信号流の方向が交互する計画を保証するために）個々の現存する縦行ループのベ ア間に２つの追加の縦行ループが加えられるような通信網において最も良く理解 できる。最初の２つの縦行ループが０及び１の番号を与えられ、追加された縦行 ループの最初のレベル番号は現存ループからの距離の分岐に゛て与えられる。つ まり、０と１との間のこの２つの縦行ループには番号１／３及び２／３が与えら れ、１と０との間の２つの縦行ループには１・１／３及び１・２／３が与えられ る。追加のレベルに拡張する場合、アドレスは位置番号Ｎ＝ｋｔｌｔ２ｔ３・・ ・ｔｎによって与えられる。ここで、ｋは０あるいは１を取り、個々が１つのレ ベルを表わすｔｉは１あるいは２を取る。つまり上の式に従かうと、Ｎは２以下 に拘束される。このモジュロ２レンジのため、着信先ノードを基準とする発信ノ ードの象限を決定することが非常に簡単になる。簡単な減算、モジュロ２によっ て、単に減算結果が１より大きいか小さいか観察するのみで所望の決定が遂行で きる。

つまり、このアドレシング計画は象限の計算が簡単であること並びに現存ノード のアドレスを再指定することなく新たなアドレスを簡単に指定できるという長所 を持つ。

前述のように、第１図の通信網は偶数個の横列ループ及び縦行ループが要求され るという点においてのみ制約を受ける。ただし、これは全ての同一ループが同数 のノードを持たなければならないという意味において、個々の横列ループ及び／ あるいは縦行ループ内にノードが完全に満されることを要求するものではない。

従って、この要件は、本発明においては、下に説明されるように必要に応じて任 意の数のノードを加えることができるため本当の制約とはならない。

第１図の通信網に２つの縦行を加え、この新たに加えられた縦行と現存する横列 との交点にはノードを加えないこともできる。

さらに、この新たに加えられた縦行の１つに１つのノードを加え、この１つのノ ードによって１つのループのみの縦行ループを形成することもできる。ただし、 この構成は、ノードの出リンクが自体の入リンクに接続されるため意味を持たな い。ただし、この問題は、第６図に示されるように、２つのノード１００の変形 バージョンを導入することによって克服できる。

第６図においては、第１図の通信網がノード１００−１．１００−２．１０（１ −３、及び１００−／Ｉの間に挿入された４つのノードを含み、縦行ループ３０ １及び３０２のメンバーはこれら４つのノードのみである。ノード２１０及び２ １１は縦行ループ３０１を構成し、ノード２１２及び２１３は縦行ループ３０２ を構成する。

１つの従来のノード（つまり、ノード１００と同一構造のノード）の導入は、タ イプＡの２つの変形ノード（ノード２１２及び２１３）、４つのタイプＢの変形 ノード（ノード２１１）によって構成される。タイプＡの変形ノードは単に１つ のリンクから１つの出リンクに通じる接続である。タイプＢの変形ノードはタイ プＡ変形ノードを通じての２つの接続である。勿論、タイプＡ及びタイプＢの変 形ノードをノード１００と２１０との間のリンク接続に併合し、結果として、第 ７図に示されるような構造を得ることもできる。ただし、この通信網を説明する 目的からは、上に説明の変形ノードの概念をとどめる方が好都合である。第７図 において、点線リンク７０１及び７０２は元の相互接続リンクを表わす。しかし 、ノード２１０を導入するためには、リンク７０１がノード２１０をまたぐリン ク　ベア７０３及び７０４を形成するように破られ、そしてリンク７０２がこれ もノード２１０をまたぐリンク　ペア７０５及び７０６を形成するように破ふら れる。

同様に、２つあるいは３つのノードを加えに場合は、非変形ノードを接続するリ ンクと併合する変形ノードを使用する相互接続は２つのノードを加えるための相 互接続パターンを図解する第８図及び３つのノードを加えるための相互接続パタ ーンを図解する第９図の構成となる。第１０図は４つのノードを加える場合に期 待される相互接続パターンを示し、そして第１１図は５つのノードを加えるだめ の相互接続パターンを示す。

上に説明の手順によると、新たな１つのノードを加えるために現存する２つのリ ンクを変更することのみが必要とされ、新たなノードが２つ接続され、これによ ってノード１つが故障した場合にも対応できる。さらに、これら新たなノードは 第６図から第１１図に示されるのとは異なる任意の順に加えることができる。た だし、通信網をできるだけ規則的に保つ配慮が必要である。この手順を継続する と、最終的には２つの完全な横列あるいは縦行通信網に加えられる結果となる。

上は第１図の通信網を通信網にノードを加えることによって拡張する方法を示す 。ユーザ　コミユニティを拡張するもう１つの方法は複数の第１図の通信網を相 互接続する方法である。このような相互接続は階層構造を生成する。階層構造は 、この通信網においては、物理的に離れた互いに密接な関係を持つコミユニティ 間の長距離経路の数を削減し、１つのコミユニティ内のノード間の通信が別のコ ミユニティ内のノード間の通信を干渉することが妨げるという点において有効で ある。この階層構造を形成する１つの方法は、第１２図に示されるように、ロー カル網内の１つあるいは複数のノードをより高いレベルの網に接続する方法であ る。

第１２図に示されるシステムにおいては、これは４つの別個の通信網（１，２， ３及び４）からのノードを一緒にリンクすることによって達成される。このより 高いレベルの網は通信網１内の転送ノード１０１０及び１０２０、通信網２内の ノード２０１０及び２０２０、通信網３内のノード３０１０及び３０２０、並び に通信網内のノード４０１０及び４０２０が垂直リンク１１．１２．１３及び１ ４並びに水平リンク１５．１６．１７及び１８によって結合されるこきによって 構成される。結合された後でも個々の転送ノード内の入りリンクの数及び出リン クの数が等しいことに注意する。転送ノードは他のノード（例えば、第５図に示 されるノード）と、スイッチ１２０が２つの追加の入力及び２つの追加の出力を 含み、信号がこれからあるいはこれに向って伝送されることを除いて同一の構造 を持つ。経路指定アルゴリズムは本質的に変更を受けない。この方法を使用して 、階層アドレシング及び経路指定構造を簡単に採用できる。つまり、個々のパケ ット内のアドレス欄に“エリア　コードサブ環を含め、パケットの−このサブ構 内のエリア　コードがパケットの位置する通信網のエリアコードと異なる場合、 パケットをその通信網内の転送ノードの１つに送り、パケットはここからリンク １１．−１８によって構成されるより高いレベルの通信網に送くられる。パケッ トが所定の通信網に到達すると、それと関連する転送ノードがパケットをその通 信網の内側に送くり、パケットはその後着信先ノードへと進む。

別の見方をすると、第１図の通信網は最も高い階層１ノベルの通信網を表わし、 個々のノード１００が第１図の通信網内の“通常′ノードとして機能し、またこ れらノードの幾つかあるいは全てが第１図の通信網と第１図より階級の低い通信 網との間の転送ノードきして機能するとみることもできる。転送はデバイス２３ ０に予約されたボートを介して行なうこともあるいは第３の入／出力ペアを介し て行なうこともできる。

個々の下層レベルの通信網も第１図に示されるタイプとされ、１つあるいは複数 のノードがより高いレベルの通信網への転送ポイントとして機能する。この構造 はこの第２のレベルの通信網内の幾つかあるいは殆んどのノードを第３のレベル の通信網への転送ポイントとして選択することによってさらに拡張できる。つま り、カントリー　コード・ナショナル　エリア　コード・イクスチェンジ　テレ ホン番号（ｃｏｕｎｔｅｙ　ｃｏｄｅ−ｎａｔｉｏｎａｌ　ａｒｅａ　ｃｏｄｅ −ｅｃｈａｎｇｅ−ｔｅｌｅｐｈｏｎｅ　ｎｕｍｂｅｒ）に類似する構成を横築 に確立することが可能である。

ＦＩＧ　１ ＦＩＧ、２ ＦＩＧ、３ ＦＩＧ、４ ＦＩ（３，５ ＦＩＧ　１２ 国際調査報告 −１両Ｑｌｊ１１−ＡｌｌｌｌｆｌＮ＃＋ｉ＠１ｌｓｏ、ｐ　Ｃ７／υＳ　８６ １０１９７３　２Ａ−％’ＮＥ：＜ＴｏＴニー：ＥＩＮτ”、Ｒ：４？、Ｔｉ０ ＮユＬＳＥＡＲＣ＜ミ＝（三ｐｃ：ｑｒＯＮ

Claims (1)

1. 【特許請求の範囲】 １．個々が１つのデバイスを通信網に接続するために使用される複数のノード（ １００）、並びに第１の及び第２の入りリンク（２０１及び２０２）及び第１及 び第２の出リンク（２２１及び２２２）を持ち、該複数のノードが複数の横列グ ループ間並びに該複数の縦行グループ間に概むね等しく分割され、これによって 複数の該個々のノードか１つの横列グループ及び１つの縦行グループに属するよ うにされている通信網において；特定の横列グループ（１１１）及び特定の縦行 グループ（１０１）に属する個々のノードの第１の出リンクが該特定の横列グル ープに属する該複数のノードのもう１つのノードの第１の入りリンクに接続され 、第２の出リンクが該特定の縦行グループに属する該複数のノードのもう１つの ノードの第２の入りリンクに接続されることを特徴とする通信網。 ２．請求の範囲第１項に記載の通信網において、第１の横列グループ及び第１の 縦行グループに属する第１のノードの第１の出リンクが該第１の横列グループ内 の第２のノードの第１の入りリンクに接続され； 該第１の横列グループ及び第２の縦行グループに属する該第２のノードの第２の 出リンクが該第２の縦行内の第３のノードの第２の入りリンクに接続され； 該第２の縦行グループ及び第２の横列グループに属する該第３のノードの第１の 出リンクか該第２の横列グループ内の第４のノードの第１の入りリンクに接続さ れ； 該第２の横列グループ及び該第１の縦行グループに属する該第４のノードの第２ の出リンクか該第１のノードの該第２の入りリンクに接続されることを特徴とす る通信網。 ３．請求の範囲第１項に記載の通信網において、該複数のノードの大多数が相互 接続され 第１の横列グループ及び第１の縦行グループに属する第１のノードの第１の出リ ンクが該第１の横列グループ内の第２のノードの第１の入りリンクに接続され； 該第１の横列グループ及び第２の縦行グループに属する該縦行２のノードの第２ の出リンクが該第２の縦行グループ内の第３のノードの第２の入りリンクに接続 され；該第２の縦行グループ及び第２の横列グループに属する該第３のノードの 第１の出リンクが該第２の横列グループ内の第４のノードの第１の入りリンクに 接続され； 該第２の横列グループ及び該第１の縦行グループに属する該第４のノードの第２ の出リンクが該第１のノードの第２の入りリンクに接続されることを特徴とする 通信網。 ４．請求の範囲第１項に記載の通信網において、個々のノードがさらに： 該デバイスに接続するために使用される入力ポート（２０３）及び出力ポート（ ２２３）、 該第１及び第２の入りリンクと該第１及び第２の出リンク間で信号を交信するた めのスイッチ手段（１２０）、該入力及び出力ポートを介して信号を該デバイス に送くるための手段（１２４）及び該デバイスから受信するための手段（１２３ ）、該第１の入りリンク上に存在する該第１の入りリンク上に到達する信号を遅 延するための第１の遅延手段（１２１）、該第２の入り上に存在する該第２の入 りリンク上に到達する信号を遅延するための第２の遅延手段（１２２）、及び該 スイッチ手段並びに該第１及び第２の遅延手段を制御して該スイッチ手段の所に 到達する信号を該スイッチ手段に該信号を送くるために同期するための制御手段 （１１０）を含むことを特徴とする通信網。 ５．請求の範囲第４項に記載の通信網において、該複数のノードの個々がさらに ： 該第１の出リンク上に存在する該第１の出リンク上に伝送されるのを待つパケッ トを保持するための第１の保持手段（２２４）、及び 該第２の出リンク上に存在する該第２の出リンク上に伝送されるのを待つパケッ トを保持するための第２の保持手段（２２５）を含むことを特徴とする通信網。 ６．パケットの着信先アドレスを含む信号パケットを搬送するために使用される 請求の範囲第１項に記載の通信網において、該複数のノードの個々か絶対ノード アドレスによって同定され、 該複数のノードの個々が該ノードに入いる信号パケットを該第１あるいは第２の 出リンクに向けるための制御手段を含み、そして 該複数のノードの個々の中の該制御手段が経路指定に関する決定に従って個々の ベアの入りパケットを該第１及び第２の出リンクに送くり、該経路決定が： 該ペアの複数の入りパケットの個々の入りパケットに対して該ノードの絶対アド レス及び該入りパケットの着信先アドレスと関連する該ノードの相対アドレスを 生成する第１のステップ；該複数のベアの入りパケットの個々の入りパケットに 対して好ましい出リンク選択を評価するための第２のステップ；該第２のステッ プにおいて遂行された好ましい出リンク選択を比較するための第３のステップ； 該第３のステップにおいて好ましい出リンク選択が該ペアの入りパケットの該両 者のパケットに対して同一であることが決定された場合に衝突を解決するための 第４のステップ；及び該ペアの入りパケットを該第４のステップによる解決に従 って該出リンクに向けるステップ及び前記入りパケットのベアを前記第４のステ ップの解決に従がって前記出リンクに送るための第５のステップとを含むことを 特徴とする通信網。 ７．請求の範囲第６項に記載の通信網において、該第２のステップか第２のステ ップを遂行するノードの絶対アドレスの奇数／偶数状態及び該着信先アドレスの 奇数／偶数状態に従って評価されることを特徴とする通信網。 ８．請求の範囲第６項に記載の通信網において、該第２のステップが該ペアの入 りパケットの個々のパケットに対して：（ｉ）該通信網を該パケットの着信先ノ ードを中心とする複数のセクションに分割するステップ、 （ｉｉ）該着信先ノードが存在するセクションを決定するステップ、及び （ｉｉｉ）該着信先ノードの絶対アドレスに基づいて該パケットに対する好まし い出リンク選択を決定するステップを含むことを特徴とする通信網。 ９．請求の範囲第８項に記載の通信網において、該ノードの幾つかが変形ノード であり、該変形ノードが該ノードの入り横列リンクをその出横列リンクに接続し 、その入り縦行リンクをその出縦行リンクに接続する機能のみを遂行することを 特徴とする通信網。 １０．請求の範囲第８項に記載の通信網において、該複数のノードが入り下層レ ベル網リンク及び出下層レベル網リンクを介して下層レベル通信網とインタフェ ースするために使用され、該下層レベル通信網が： 下層レベル横列ループ及び縦行ループに配列及び相互接続された複数の下層レベ ルノードを含み、 該複数の下層レベルノードの個々が１つの下層レベル横列入りリンク及び下層レ ベル縦行出リンク並びに下層レベル縦行入りリンク及び下層レベル縦行出リンク を含み、該複数の下層レベルのノードが該下層レベル入りリンク上に到達する信 号を該下層レベル出リンクにスイッチするために使用され；該複数の下層レベル ノードの個々が１つの下層レベル横列ループ及び下層レベル縦行ループに属し、 下層レベル縦行番号及び下層レベル横列番号に対応する下層レベルアドレス番号 を持ち；第１の偶数／奇数センスを持つアドレスを持つ下層レベル横列ループが 、該下層レベル横列ループに属し特定の下層レベル縦行アドレスを持つ個々の下 層レベルノードの出リンクを該下層レベル横列ループ内の次に高い下層レベル縦 行アドレスを持つもう１つの下層レベルノードの入りリンクに接続し、該下層レ ベル横列ループ内の最も高い下層レベル縦行アドレスを持つ該下層レベルノード の出リンクを該下層レベル横列ループ内の最も低い下層レベル縦行アドレスを持 つ該下層レベルノードの入りリンクに接続することによって形成され； 該第１の偶数／奇数センスとは逆の偶数／奇数センスを持つアドレスを持つ下層 レベル横列ループが、該下属レベル横列ループに属し特定の下層レベル縦行アド レスを持つ個々の下層レベルノードの出リンクを該下層レベル横列ループ内の次 に低い下層レベル縦行アドレスを持つもう１つの下層レベルノードの入りリンク に接続し、該下層レベル横列ループ内の最も低い下層レベル縦行アドレスを持つ 該下層レベルノードの出リンクを該下層レベル横列ループ内の最も高い下層レベ ル縦行アドレスを持つ該下層レベルノードの入りリンクに接続することによって 形成され；第２の偶数／奇数センスを持つアドレスを持つ下層レベル縦行ループ が、該下層レベル縦行ループに属し特定の下層レベル横列アドレスを持つ個々の 下層レベルノードの出リンクを該下層レベル縦行ループ内の次に高い下層レベル 横列アドレスを持つもう１つの下層レベルノードの入りリンクに接続し、該下層 レベル縦行ループ内の最も高い下層レベル横列アドレスを持つ下層レベルノード の入りリンクを該下層レベル縦行ループ内の最も低い下層レベル横列アドレスを 持つ下層レベルノードに接続することによって形成され； 該第２の偶数／奇数センスと逆の偶数／奇数センスを持つアドレスを持つ下層レ ベル縦行ループが、該下層レベル縦行ループに属し特定の下層レベル横列アドレ スを持つ個々の下層レベルノードの出リンクを該下層レベル縦行ループ内の次に 低い下層レベル横列アドレスを持つもう１つの下層レベルノードの入りリンクに 接続し、該下層レベル縦行ループ内の最も低い下層レベル横列アドレスを持つ下 層レベルノードの出リンクを該下層レベル縦行ループ内の最も高い下層レベル横 列アドレスを持つ下層レベルノードの入りリンクに接続することによって形成さ れることを特徴とする通信網。