(57)【要約】制御信号を用いる制御セル経由の単一ビットルーティングの利用を通して、情報集信装置（７００）の動作を概ね向上させる相互接続構造（１００）。この相互接続構造及び作動方法によって、ワームホール・ルーティング及びメッセージの流れがサポートされる。この構造に進入する任意のパケットが確実に退出するように、メッセージ・パケットが常に構造内にバッファされて、決して廃棄されない。一例では、この相互接続構造が、非横断経路内の複数ノードに接続する相互接続ラインのリボン（１１２）を含んでいる。相互接続ラインのリボン（１１２）は、出発レベルから宛先レベルまでの複数のレベルを通して巻かれていく。巻かれる回数は、出発レベルから宛先レベルまで減少していく。相互接続構造は、横断部分内でレベルの巻き部分を通ってリボンを横切るノードを結合する相互接続ラインにより形成される複数の列を、更に含んでいる。
2004535690.tif 000002
【特許請求の範囲】
【請求項１】
相互接続構造であって、
複数のデータ送信ライン（１０４）と、
複数の前記データ送信ラインの上に配置された複数のノードとを有し、
前記データ送信ラインが、前記相互接続構造の外側からのデータの進入のために、複数のノードを備えており、
前記データ送信ラインが、データが前記システムを退出するのを可能にするデータ退出末端部を備えており、
複数の前記ノードがノードＡ、Ｂ、及びＸを含み、且つ複数の前記データ送信ラインがラインＬ１及びＬ２を含み、前記ラインＬ１上の前記ノードＡは、ラインＬ１上のノードＡの直後にある前記ノードＢにデータを送信することが可能であり、前記ノードＡは前記データ送信ラインＬ２上の前記ノードＸにデータを送信することが可能であり、前記ノードＸから送信ラインＬ２の前記データ退出末端部への距離がノードＢから送信ラインＬ１の前記データ退出末端部への距離よりも小さくなっていることを特徴とする相互接続構造。
【請求項２】
前記ノードＸは、前記ノードＸへのデータ送信に関して前記ノードＡを上回る優先権を有する、直前のノードＷを有することを特徴とする請求項１に記載の相互接続構造。
【請求項３】
前記相互接続構造に進入するメッセージが決して廃棄されないことを特徴とする請求項１に記載の相互接続構造。
【請求項４】
相互接続構造であって、
複数の送信リングと、
複数の前記送信リング内に配置された複数のノード（１０２）とを有し、
前記データ送信リングが、最上位レベルＬから最下位レベル０まで複数のレベル内に配置されており、
レベルＬ上のリングが、前記相互接続構造の外側からデータを受信することが可能である１以上のノードを備え、
複数の前記ノードが、ノードＡ、Ｂ、Ｃ、Ｘ、及びＹを含み、
前記ノードＢが、レベル０とレベルＬとの間のレベルＪ上にあり、
前記ノードＡが、前記ノードＢと同一のデータ送信リング上で前記ノードＢの直前にあり、
前記ノードＣが、前記ノードＢと同一のデータ送信リング上で前記ノードＢの直後にあり、
前記ノードＸが、前記レベルＪよりも大きいレベルＫ上にあり、
前記ノードＹが、前記レベルＫよりも小さいレベルＰ上にあり、
前記ノードＢが、前記ノードＡ及び前記ノードＸからデータを受信することが可能であり、
前記ノードＢが、前記ノードＣ及び前記ノードＹにデータを送信することが可能であり、前記データは、データ・メッセージに対してターゲットを特定するヘッダ情報を用いずに自己ルーティングされることを特徴とする相互接続構造。
【請求項５】
前記データは、少なくとも部分的にサービス品質情報に基づいて、自己ルーティングされることを特徴とする請求項４に記載の相互接続構造。
【請求項６】
相互接続構造であって、
複数のデータ送信ライン（１０４）と、
複数の前記データ送信ラインの上に配置された複数のノード（１０２）とを有し、
複数の前記ノードが、ノードＢ及びノードのサブセットＳを含み、
前記ノード・サブセットＳが、前記ノードＢにデータを送信することが可能な１以上のノードを含み、前記サブセットＳ内のノードＮ及び該ノードＮに到達するメッセージＭに関して、前記ノードＢへのメッセージ送信に対して前記ノードＮよりも低い優先権を有する前記サブセットＳ内のノードからのメッセージによって、前記ノードＮがノードＢへの前記メッセージＭの送信を決してブロックされないように、前記サブセットＳ内の前記ノードが前記ノードＢへのメッセージ送信に対して優先権関係を有し、前記メッセージＭが該メッセージＭのターゲットを示すヘッダ情報を有していないことを特徴とする相互接続構造。
【請求項７】
前記ノードＮによってメッセージのルーティングがなされる得るノード・サブセットＴＮと、
前記メッセージＭを受信するのが最も望ましいノードから、前記メッセージＭを受信するのが最も望ましくないノードまで、前記サブセットＴＮの構成要素を順位付けし、前記サブセットＴＮのブロックされていない最も望ましい構成要素に前記メッセージＭを送信する、ノードＮに関連付けられたロジックとを更に有することを特徴とする請求項６に記載の相互接続構造。
【請求項８】
前記Ｂの直前にあり、前記ノードＢへのメッセージ送信に対して最も高い優先権を更に有するノードＡを有することを特徴とする請求項７に記載の相互接続構造。
【請求項９】
相互接続構造であって、
構造内に配置された複数のノード（１０２）を有し、
複数の前記ノードが、
ソース・レベルから宛先レベルまでの複数のレベルから成る階層と、
前記レベルに沿って延びる非横断経路内にある複数のノードと、
前記レベルの非横断経路の横断部分内の複数のノードであって、前記相互接続構造が１つの集信装置になるように、前記ソース・レベルの横断部分内のノード数が、前記宛先レベルの横断部分内のノード数よりも大きくなっており、ノードの前記レベルが前記構造内の前記ノードの位置によって完全に決定される複数ノードと、
レベルＬの経路Ｐ上のノードＮに対してのものを含む、前記構造内で前記ノードを接続する複数の相互接続ライン（１０４）と、
前記レベルＬの前記経路Ｐ上の第１隣接ノードに接続されたメッセージ入力相互接続ラインと、
前記レベルＬの前記経路Ｐ上の第２隣接ノードに接続されたメッセージ相互接続ラインと、
階層内でソース方向のノードからデータを受信するために、前記ノードＮのソース方向の１以上のノードに接続され、且つ／又は階層内で宛先方向のノードにデータを送信するために、前記ノードＮの宛先方向の１以上のノードに接続された少なくとも１つのメッセージ相互接続ラインと、
ソース方向のノードに制御信号を送信するために、前記ノードＮのソース方向のノードに接続され、且つ／又は階層内で宛先方向のノードから制御信号を受信するために、前記ノードＮの宛先方向のノードに接続された少なくとも１つの制御相互接続ラインとを有することを特徴とする相互接続構造。
【請求項１０】
前記ノードＮが前記レベルＬの前記経路Ｐ上のメッセージによって占有されているか決定し、該決定に基づいてソース方向の前記ノードに制御信号を送信し、前記ソース方向のノードにおけるメッセージの進行を速めることが可能な、前記ノードＮに関連付けられたロジックを更に有することを特徴とする請求項９に記載の相互接続構造。
【請求項１１】
各列がレベル内で非横断経路の横断部分内の複数のノードを相互接続し、少なくとも１つのメッセージ相互接続ライン上及び少なくとも１つの制御相互接続ライン上のソース方向及び宛先方向の接続を含むノード間の相互接続網を含んでいる、複数の列を更に有することを特徴とする請求項９に記載の相互接続網。
【請求項１２】
前記レベルに沿って延びる非横断経路にそれぞれ接続される複数のＦＩＦＯバッファ（１１８）を更に有することを特徴とする請求項９に記載の相互接続構造。
【請求項１３】
レベルＬの経路Ｐ上の前記ノードＮに対してのものを含む、前記構造内で前記ノードを接続する複数の前記相互接続ラインは、
前記経路Ｐのソース方向のノード及び前記レベルＬ内のノードに接続された第１制御出力相互接続ラインと、
前記レベルＬのソース方向のレベル内のノードに接続された第２制御出力相互接続ラインとを更に有することを特徴とする請求項９に記載の相互接続構造。
【請求項１４】
レベルＬの経路Ｐ上の前記ノードＮに対してのものを含む、前記構造内で前記ノードを接続する複数の前記相互接続ラインは、
前記レベルＬ内のノード及び前記経路Ｐのソース方向のノードに接続されている第１メッセージ入力相互接続ラインと、
前記レベルＬのソース方向のレベル内のノードに接続されている第２メッセージ入力相互接続ラインと、
前記レベル内のノード及び前記経路Ｐのソース方向のノードに接続されている制御出力相互接続ラインとを更に有することを特徴とする請求項９に記載の相互接続構造。
【請求項１５】
レベルＬの経路Ｐ上の前記ノードＮに対してのものを含む、前記構造内で前記ノードを接続する複数の前記相互接続ラインは、
前記レベルＬ内のノード及び前記経路Ｐのソース方向のノードに接続されている第１制御出力相互接続ラインと、
前記レベルＬのソース方向のレベル内のノードに接続されている第２制御出力相互接続ラインと、
前記経路Ｐのソース方向のノードに接続されているメッセージ入力相互接続ラインとを更に有することを特徴とする請求項９に記載の相互接続構造。
【請求項１６】
複数の前記ノード間の優先ノードと、非優先ノードであるその他のノードとを更に有し、前記優先ノード及び前記非優先ノードが選択的に相互接続されることを特徴とする請求項９に記載の相互接続構造。
【請求項１７】
ソース方向経路上のｎノードを宛先方向経路上のｍノードに集約するように、相互接続ノードを集団化するロジックを更に有し、
ｎがｍよりも大きく、且つｎ：ｍが集約比になっていることを特徴とする請求項９に記載の相互接続構造。
【請求項１８】
前記非横断経路内の複数ノードに接続される相互接続ラインのリボン（１１２）であって、相互接続ラインの該リボンは、前記ソース・レベルから前記宛先レベルまで複数の前記レベルを通って巻かれ、巻かれる回数が前記ソース・レベルから前記宛先レベルに減少する、相互接続ラインのリボンと、
前記レベルの全ての巻き部分を通って、前記リボンの横断部分内の前記ノードを接続する複数の列とを更に有することを特徴とする請求項９に記載の相互接続構造。
【請求項１９】
前記相互接続ライン・リボンの前記巻き数が、前記ソース・レベルから前記宛先レベルまで、レベル毎に半分減少することを特徴とする請求項１８に記載の相互接続構造。
【請求項２０】
システムであって、
複数のスイッチ（７０２）と、
複数の前記スイッチに各々接続される、請求項９に記載の複数の集信装置（７００）とを有することを特徴とするシステム。
【請求項２１】
相互接続構造であって、
非横断経路内の複数ノードに接続される相互接続ラインのリボン（１１２）であって、相互接続ラインの該リボンは、前記ソース・レベルから前記宛先レベルまで複数の前記レベルを通って巻かれ、巻かれる回数が前記ソース・レベルから前記宛先レベルに減少する、相互接続ラインのリボンと、
前記レベルの巻き部分を通って、前記リボンの横断部分内に渡っている前記ノードに接続されている相互接続ラインによって形成される複数の列とを有することを特徴とする相互接続構造。
【請求項２２】
前記ソース・レベルの第１列内の前記ノードに接続されている複数の入力ポートを更に有することを特徴とする請求項２１に記載の相互接続構造。
【請求項２３】
前記宛先レベルの最後の列内の前記ノードに接続されている複数の出力ポートを更に有することを特徴とする請求項２１に記載の相互接続構造。
【請求項２４】
前記レベルに沿って延びる非横断経路にそれぞれ接続されている複数のＦＩＦＯバッファを更に有することを特徴とする請求項２１に記載の相互接続構造。
【請求項２５】
前記ソース・レベルから前記宛先レベルまでレベル毎に半分減少する、前記相互接続ラインの前記巻数を更に有することを特徴とする請求項２１に記載の相互接続構造。
【請求項２６】
前記相互接続構造の中へのメッセージの進入を制御するように、前記相互接続構造の内側のノードから、前記相互接続構造の外側の１以上のデバイスに延びている制御ラインを更に有することを特徴とする請求項２１に記載の相互接続構造。
【請求項２７】
ソース方向経路上のｎノードを宛先方向経路上のｍノードに集約するように、相互接続ノードを集団化するロジックを更に有し、
ｎがｍよりも大きく、且つｎ：ｍが集約比になっていることを特徴とする請求項２１に記載の相互接続構造。
【請求項２８】
ノードがレベルの前記経路上のメッセージによって占有されているか決定し、該決定に基づいてソース方向のノードに制御信号を送信し、ソース方向の前記ノードにおけるメッセージの進行を速めることが可能なロジックを更に有することを特徴とする請求項２１に記載の相互接続構造。
【請求項２９】
複数の前記ノード間の優先ノードと、非優先ノードであるその他のノードとを更に有し、前記優先ノード及び前記非優先ノードが選択的に相互接続されることを特徴とする請求項２１に記載の相互接続構造。
【請求項３０】
システムであって、
複数のスイッチ（７０２）と、
複数の前記スイッチに各々接続される、請求項２１に記載の複数の集信装置（７００）とを有することを特徴とするシステム。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明は、集信装置に関し、特に、迅速にデータのルーティングを行い、妨害物を回避することにより情報の流れを向上させ、制限なしに垂直方向にスケーラブルで、且つ低レイテンシィー及び高処理能力をサポートする集信装置に関する。
【０００２】
（背景技術）
通信ネットワーク若しくはコンピューティング・ネットワークは、例えば、金属若しくは光ファイバーのケーブル等の通信媒体経由で物理的に接続される、いくつか若しくは多数のデバイスで構成されている。ネットワーク内に含まれ得るデバイスの一種は、集信装置である。例えば、ラージスケール時分割スイッチング・ネットワークは、中央スイッチング・ネットワーク、及びこのスイッチング・ネットワーク内の別のデバイスの入力端子及び出力端子に接続されている一連の集信装置を含んでいてよい。
【０００３】
集信装置は通常、ネットワークへのマルチポート接続をサポートするのに用いられる。集信装置は、複数の共有通信ラインに接続された、より少ないライン上に情報を集めるデバイスである。集信装置は、ブロッキング及びデータ損失の発生率を増加させることによって、若しくは記憶のためにバッファ内の情報を呼び出すことによって、相互接続経路の受容能力を本質的に減少させてしまう。
【０００４】
大規模な並列コンピューティング及び通信において生じる永続的な問題は、データをプロセッサ及びユーザに移動させる際に生じる。集信装置が実装されたシステム内部においては、受容能力が本質的に減少するため、この問題が悪化する。
【０００５】
必要とされているのは、迅速にデータのルーティングを行い、妨害物を回避することにより情報の流れを向上させ、制限なしに垂直方向にスケーラブルで、且つ低レイテンシィー及び高処理能力をサポートする集信装置である。
【０００６】
（発明の開示）
制御信号を用いた制御セル経由の単一ビット・ルーティングの利用を介して、情報集信装置の動作を概ね向上させる相互接続（インターコネクト）構造である。用語「セル」若しくは「制御セル」は、単純なスイッチング要素を示している。用語「ノード」は、１つの構成単位として作動するセル若しくはセル集団を示している。この相互接続構造及び作動方法によって、ワームホール・ルーティング及びメッセージの流れがサポートされる。この構造に進入した任意のパケットが確実に退出するように、この構造に進入するメッセージ・パケットは決して廃棄されない。
【０００７】
本発明の一態様によれば、相互接続構造が、非横断部の経路内にある複数ノードに接続される相互接続ラインのリボンを含んでいる。相互接続ラインのこのリボンは、出発レベルから宛先レベルまで、複数のレベル経由で巻かれる。巻かれる回数は、出発レベルから宛先レベルまで減少していく。相互接続構造は、交差部内でレベルの巻付部分を通ってリボンを横切るノードを結合する相互接続ラインにより形成される複数の列を、更に含んでいる。相互接続構造上でデータを通信する方法には、データ・パケットを複数の階層レベルを下側にルーティングするための高速、最小ロジックの方法が組込まれている。
【０００８】
（発明を実施するための最良の形態）
図１を参照すると、３レベル及びＫ列を含む、多重レベル３２：８集信装置１００の形態でのデータ相互接続構造の一例が示されたブロック図である。レベルは、階層的で最下位から０、１、及び２と数えられており、列は左から右に０からＫ−１まで数えられている。集信装置１００は、３２の軽負荷データ輸送ラインから入力データを受信し、より重負荷の８ラインにそのデータを渡す。図示されている例では、データ・パケットは、３２ポート入力端子１２０から８ポート出力端子１２２に、８幅の「リボン」の行の中を進んで行く。このリボン１１２は、各列における制御アレイ１１０内に配置された制御セルの８幅セット、及び列Ｋの右側に配置されたシフト・レジスタ（ＦＩＦＯ）１１８を含んでいる。最下位の出力レベルはＦＩＦＯを含んでいない。リボン１１２のトポロジーは、図１に図示されるように、理髪店ポール風の巻きとして描写され得る。データは、図２に図示されるパケット２００の形式になっている。このリボン１１２は、レベル２の周囲に４回巻かれ、レベル１の周囲に２回巻かれ、更にレベル０を１回通過する。従って、レベル２は３２のセル行及び３２のＦＩＦＯを有し、レベル１は１６のセル行及び１６のＦＩＦＯを有し、更にレベル０はＦＩＦＯなしの８行を有する。リボンの幅は出力ポート数と概ね等しいが、別の構成を用いることもできる。
【０００９】
図１に示される模式的な相互構造接続は、複数のデータ送信ラインから成る８幅リボンを有する。個々のラインは、７つのセグメントに分割されており、各セグメントは１つのメッセージを含むのに十分大きくなっている。８幅リボン中の各データ送信ラインは、一連のノードに接続する。この８幅リボンは、種々の巻きの上にあるノード間にいくつかの相互接続を備えた概ね螺旋構造に巻かれる。データは、ノードからノードへデータ送信ラインに沿って、先入れ先出し動作で進められる。データは、相互接続構造経由でシステム入力ポートからシステム出力ポートに移動する。相互接続構造の上位８ライン内にある列０レベル２内のノードを除き、データ送信ラインＬ上の各ノードＢは、データ送信ライン上に直前のノードＡを有する。
【００１０】
データ送信ラインＬ上の各ノードＢは、データ送信ラインＬ上にある、若しくは出力ポートである、直後のＣを有する。このノードＡは、データＢへのデータ送信が常に可能である。ノードＢは、ノードＣへのデータ送信が常に可能である。ノードＡからノードＢに送信されたデータ、及びノードＢからノードＣに送信されたデータは、常にブロックされない。
【００１１】
いくつかのノードは、リボンのＦＩＦＯ領域内に配置される。ＦＩＦＯ領域内のノードは、１つだけの入力ポート及び１つだけの出力ポートを有する。
【００１２】
いくつかのノードは、データが送信ラインのリボンの外側から進入することを可能にする付加的な入力ポートを有する。
【００１３】
いくつかのノードは、データがノードに、送信ラインのリボンのずっと上流にあるノードから進入するのを可能にする第２入力ポートを有する。このずっと上流にあるノードは通常、現在のノードと比較して過去のリボンの巻きの上にある。
【００１４】
いくつかのノードは、出力ポートのリボン・システムのより近くのリボンへとずっと下側にデータ送信を可能にする１以上の第２出力ポートを有する。複数の出力ポートを備えたノードは、送信ラインのリボンに沿って、直後のノードへのメッセージの送信の試みをするよりもむしろ、メッセージを可能な限りシステム出力ポートへの前方へと送信することを常に試みる関連付けられたロジックを有する。
【００１５】
複数の入力ポートを備えたノードは、入力ポートに割当てられた優先権を有する。直後からのメッセージは、直後ではないノードからのメッセージを上回る優先権を常に有している。直前にないノードに接続された複数の入力ポートを備えているノードも同様に、データ受信に対して優先順位関係を有している。
【００１６】
要約すると、ノードは、可能な限り下側のリボンへのデータ送信を常に試みるが、各ノードＢに関連して、ノードＢへのメッセージ送信が可能な種々のノードからのメッセージの受信が優先権によって規定されている。最上位の優先順位は、直前のノードに付与される。セットＳは、ノードＢへのメッセージ送信が可能なノードを含んでいる。優先順位関係は、ノードＢへのメッセージ送信に対してセットＳ内のノードの間で定義される。メッセージの前方への進行を管理する規則は以下の通りである。
【００１７】
１．ノードＮがセットＳの構成要素であり、且つメッセージＭがノードＮに到達する場合、ノードＮは、セットＳ内の別ノードからの、ノードＢへの送信に対してノードＮよりも優先順位が低いメッセージによって、ノードＢへのメッセージ送信がブロックされることは決してない。
【００１８】
２．セットＳ内の各ノードＮに対応して、いずれのノードＮがメッセージ・ルーティングを行うことが可能であるノードのセットＴＮが存在している。各ノードＮに関連付けられたＴＮの構成要素は、メッセージＭを受信するのが最も望ましいノードＮＭからメッセージＭを受信することが最も望ましくないノードＮＬの範囲で、順位付けられる。ノードＮに関連付けられたロジックは、セットＴＮのブロックされていない最も望ましい構成要素にメッセージＭを送信する。
【００１９】
３．ノードＢの直前のノードＡが、メッセージのノードＢへの送信に対して最も高い優先権を有する。
【００２０】
図１では、前にある送信ラインのリボン上のノードからのメッセージ受信及びメッセージ送信の能力を備えたノード、即ち、相互接続構造のセグメントを飛越えるノードが、Ｋ個の制御セル列内に配置されている。１つだけの入力ポートを備えたノードが相互接続構造のＦＩＦＯ区間内に配置されている。
【００２１】
メッセージは、常に１に設定される単一ビット・ヘッダ−単一タイミング・ビットが前にあるペイロードを含んでいる。セグメントの各々は、レベル上の行に対応している。１つの行は、その行に広がるＫ個の制御セルを含んでいる。メッセージは、単一行上のＦＩＦＯ及びＫ個の制御セルの内部に適合する必要があるので、このメッセージの長さはＦＩＦＯ＋ＣＫの長さを越えることはできない（ここでＣは制御セル内のビット数である）。それゆえに、ＦＩＦＯの長さは少なくとも、メッセージの最大長からＣＫを引いた長さである必要がある。システムが多数のメッセージをＲの信号に集約させる場合、リボン幅はＲである。相互接続構造がＬ＋１レベル及びレベル当たりＫ列を含む場合、このシステムは、各行に、少なくともメッセージの最大長からＣＫを引いた長さである、Ｋの制御セル及びＦＩＦＯを有しているＲ・（２Ｌ＋１−１）行を含んでいる。
【００２２】
一実施例では、メッセージが、列０におけるリボンのセグメントのうちの１つに送られる。このメッセージが列１に移動する際に、このメッセージはこのシステムの出力ポートのより近くにある別のセグメントへと前方に移動することが可能である。メッセージの第１ビットが送信ラインのリボンの新セグメントに移動するとき、このメッセージが異なる送信ラインに移動してもよいし、若しくはリボン上の同一送信ライン上に留まっていてもよい。メッセージ・ヘッダが新しい列に到達すると、このメッセージは再度新セグメントへと前方の飛んでもよい。この方法により、メッセージが複数のセグメントに広がってもよいし、最下位レベルがＦＩＦＯを有さないことから、全メッセージが集信装置に進入し終わる前にメッセージの第１ビットが集信装置を退出してもよい。
【００２３】
以下の説明では、用語「パケット」は、通常は直列形式のデータの構成単位を示している。データ・パケットの例には、インターネット・プロトコル（ＩＰ）パケット、イーサネット・フレーム、ＡＴＭセル、大きいフレーム若しくはデータ・パケットの一部等のスイッチ・ファブリック・セグメント、並列コンピュータのプロセッサ間メッセージ、若しくは長さの上限を有するその他のデータ・メッセージがある。１つのレベルを横切って進むパケットは、制御セル１０２のＫ列を通過する。レベルを横切るこのパケットは、１つのセルから、同一レベル上にある次の列の内部のセルに直接、渡される。一例では、同一レベル上のセルの間を横切るパケットに対して、パケットの２ビットが各々のセル内に配置される。システム内でここで説明されたのものと同一のタイミングが用いられてよいが、本説明におけるセル設計は単純化されている。ＦＩＦＯは、適切なビット数のパケットを含み、それにより列０のアレイにパケットが進入する際に、このヘッダ・ビット２０２は、同一のレベルを横切るパケットの別のヘッダ・ビットと整列する。この例では、列０に進入するパケットのタイミングが、階層内の上側に配置されているセルから到達するパケットと同期化されるように、パケットが単一行に適合されている。
【００２４】
タイミング及び制御は、最長パケットのビット長がＦＩＦＯ内のビット数に列内のビット数の合計を加えたものよりも大きくなってしまわないようにすることで達成される。例えば、各々が２ビットを保持する制御セルで構成される１２列を備えた構造内に、４００クロック周期に到達する、上位ビットの長さが４００であるパケットに対しては、ＦＩＦＯの長さは３７６ビットとなる。パケットの第１ビットは、特定レベル上のセルから、次の列内にある同一レベル上のセルへと、２クロック刻み若しくは２クロック・ステップで移動する。パケットの第１ビットは、特定レベル上のセルから、次の列内にある１つ下位のレベル上のセルへと、１クロック刻みで移動する。それゆえに、レベル間のタイミング差異を補正するために、レベル間を接続するＦＩＦＯの長さは、１ビット少なくなっている。レベル間のタイミング差異を補正するために、レベル間を接続するＦＩＦＯの長さは、１ビット少なくなっている。レベルのタイミングは以下で詳細が説明される。
【００２５】
最上位レベル内の３２のデータ入力ポートのうちの１つから、入力アレイ１２０の中にこのパケットが挿入される。１つのデータ入力ポートによって、最上位レベル内にある３２ラインの各々に供給される。１つのパケットが直列式に各ライン中に挿入される。アレイ１２０内のリボン１１２からセルに進入するパケットは、相互接続構造の外側からセルへの進入を試みるパケットを上回る優先権を有している。パケットが構造の上位８行に進入するのをブロックすることが可能な内部パケットは１つもないが、最上位レベルの上位行を横切るパケットは、何らかのブロッキング状態で、「理髪店ポール」の周囲に巻かれて、アレイ１２０内の最上位レベルの８行下側に再進入することが可能である。構造に進入するパケットが決して廃棄されず、それにより構造に進入する任意のパケットが確実に退出できることが、従来の集信装置を上回る、非常に改善された点である。
【００２６】
このパケットは、スイッチ・アレイの次列への進行に対して、構造の外側から相互接続構造に進入を試みるパケットを上回る優先権を有する。これらの状況下で、構造への進入が試みられるこのパケットは、進入が禁止される。動作の複数の態様によって、相互接続経由の通行に影響が及ぼされるが、より古いパケットが、より新しいパケットの前に退出する優先権を有する。
【００２７】
代替実施例では、パケットが最上位レベルの複数の角にあるリボンに進入することが可能である。最上位レベルのある特定セルに対して、構造内部からセルに進入するパケットの第１ビットと、構造の外側から同一列内にあるセルに進入するパケットの第１ビットとが同時になる。
【００２８】
換言すると、最上位レベルの３２の入力ラインにおいて、構造の外側からのパケットを受信する。３２の入力ラインのうち、上位８つの入力ポートがリボンの開始点に接続され、構造内に既に存在するパケットによるブロックは不可能である。残りの２４の入力ポートは、ブロックすることが可能である。ブロッキングは、図４Ａ、４Ｂ、及び４Ｃの説明の詳細で考察される。
【００２９】
データ輸送リボン内の螺旋の周囲を進行する代わりに、パケットは、階層内で上位レベルのセルから下位レベルのセルへと、より前方に飛ぶことが可能である。この飛越し処理によってリボン内のパケットが集約され、それにより最下位レベルのリボンのセグメントが、最上位レベルのリボンのセグメントよりも平均して多くのメッセージを輸送する点が効果的である。
【００３０】
所定レベルのパケットが、制御セルアレイ１１０内の制御セル１０２に進入する。図４Ａを参照すると、パケットＰＡ４１０が制御セルＢに進入する場合、制御セルＢに関連付けられたロジックによって、セルＢ経由で同一レベル上の別セルＣにルーティングがなされてもよい。或いは、セルＢに関連付けられたロジックによって、下位レベルのセルＸへとパケットＰＡのルーティングがなされてもよく、これは、この集信装置及び動作方法の利用に対する望ましい結果である。
【００３１】
あるパケットが、上のライン１０６若しくは４０４から、例えばセルＢ若しくはＥから、セルＷに進入すると、このパケットは遅延なしで次列のセルＸへとライン１０４上に送信される。それゆえに、パケットＰＡがセルＢからセルＸへルーティングされる場合、パケットＰＡはセルＷへ進み、次にすぐにセルＸに進入する。図４Ａと共に図４Ｃを参照すると、セルＢがパケットＰＡをライン４０６に下側にルーティングすると、このパケットＰＡは同様にしてすぐにセルＸに進入する。図４Ａ及び図４Ｂに示される図は、セル間のパケット・ルーティングの例と機能的には同等である。組込みの状況によって、他方を上回る一方のルーティング方法の選択に影響が及ぼされる可能性がある。
【００３２】
パケットの下位レベルへ即座の「降下」若しくは「飛越し」によって、集信装置の相互接続構造の効率的な動作が増進される。基本的には、所定の下位レベルのセルがパケットによって占有されていない場合、即ち、データを受取るために利用可能であり、そのセルが上位レベルの別セルに接続されている場合、上位レベルのセルのパケットが、下位レベルのセル内の空の場所を満たすように降下する。いくつかの降下若しくは飛越しの処理が適切である。制御セル構造によって、降下若しくは飛越し方法が決定される。制御セル構造とデータ全体の流れ及びタイミングとが以下の詳細で説明される。
【００３３】
図１は、レベル間の比が２：１である８幅リボン及び３レベルを備えた３２：８の集信装置が図示されている実施例であり、それによって、集約比が全体で４：１である集信装置が得られる。別のリボン幅と同様に、別の集信装置の比が実用的であって、望ましくは、提供される入力及び出力ポート数は広範囲である。集約比は、更なるレベルを付加することによって、レベル間の集約比を増大させることによって、もしくは両方によって増加され得る。４：１より大きい全体比が用いられている一実施例では、３よりも多くのレベルを有している。別の実施例において、レベル間で２：１以外の比が用いられてもよい。図１に図示されている制御セルでは、データ輸送ライン及び制御信号輸送ラインの一部だけが図示されている。付加的なラインは、図３Ａ及び３Ｂで示される構造に関して以下で説明される。
【００３４】
図２は、パケットの配置が図示されている。パケット２００のヘッダ２０２は、常に１に設定されて、パケットが存在していることを示す単一ビットを含んでいる。パケットの残りは、ペイロード２０４と呼ばれる。種々のペイロードが図２に例示されている。あるパケットは、任意の退出ポートから相互接続構造１００を退出することが可能であり、それによりルーティング情報を含む付加的なヘッダ・ビットが不要となる。
【００３５】
集信装置１００を出た後に、パケットがネットワーク・ルーティング・デバイスに進む場合、ルーティング・デバイスによって利用されるためのルーティング・情報が、ペイロード内にあるデータ・ビットより前になっていてもよい。このルーティング・ビットは、集信装置１００のロジックには使用されない。この集信装置１００は、常にペイロードの内容２０４を無視する。
【００３６】
集信装置（図示せず）の代替実施例では、サービス品質を示す付加的なヘッダ・ビットが用いられてもよい。
【００３７】
図３Ａ及び図３Ｂは、セルの入力ポート及び出力ポートの例が示されている。図示されているポート構成では、セル１０２は、より上位レベルのセルから２つのデータ入力ライン１０６上のデータを受信し、且つ下位レベルのセルへと１つのデータ出力ライン１０６上にデータを送信する。垂直方向接続のこの２−１の比によって、集信装置のデータ集約動作が補助される。セル１０２は、同一レベル上にあるセルからの１つのデータ入力ライン１０４と、同一レベル上にあるセルへの１つのデータ出力ライン１０４とを、更に含んでいる。セル間のデータ入力及び出力ラインに加えて、付加的な相互接続ライン１０８によって、セル間で制御情報の輸送が行われる。この制御情報は、受信セルからのデータ・パケットをどのようにルーティングするか決定するべく、受信セルのロジックによって用いられる。この制御ラインは、相互接続構造を経由するデータの流れを管理する、位置ベースの優先順位の規則を行使するのに用いられる。
【００３８】
ここで説明されるように、第３ノードへのデータ送信を試みる２ノードは、上側の競合を解消するために制御信号を用いて通信を行う。別のネットワークでは、ノードＮに進入するパケットは、出力ポートに対して競合する。ここで説明されるシステムでは、パケットがノードの入力ポートに対して競合しており、この競合は制御信号を用いて上流で解消される。上流のデータの流れは、説明されているネットワーク内での固有のトポロジーによって許可されており、それにより２つのパケットが特定の下流のノード入力ポートに対して競合し得る。競合の解消は、ネットワーク内のノードの配置に、少なくとも部分的に基づいている。第３ノードＶへのデータ送信に対して、ノードＢを上回る優先権を有するノードＥは、その優先権を行使するべく直接的に、若しくは間接的にＢに制御信号を送信する。図３Ａは、１つの制御信号を受信し、１つの制御信号を送信するノードを示している。図３Ｂは、１つの制御信号を受信し、２つの制御信号を送信するノードを示している。
【００３９】
２種類のノードの利用は、図４Ａに示される相互接続構造の考察の中でより詳細に説明される。
【００４０】
図３Ｂは、上位レベルの１つのセルと、同一レベルの１つのセルとを上回る優先権を有するあるセルの一例を示している。
【００４１】
図４Ａは、全てのデータ及び制御ラインが示されていない、図１に示される集信装置１００の一部の拡大図である。セルＥ及びＢは同一レベルにある。セルＥ及びＢの各々を別個のノードとして見ることもできるし、若しくは２つのセルＥ及びＢを単一ノードとして１つにみなすこともできる。
【００４２】
集信装置１００は、以下の方法で作動する。同一レベル上のセルＶ、Ｗ、及びＸに対して、セルＶがパケットＰＶをセルＷに送信し、セルＷがパケットＰＶの第１ビットをセルＸに送信する場合、セルＷは、より上位レベルにあるセルＥへと制御信号を送信する。セルＷはライン１０４上のセルＸにパケットＰＶを送信する。セルＷは、ライン１０８上のセルＥに制御信号を送信し、それによりセルＥが下向きにライン１０６にデータ送信しないよう通知する。セルＥは、ライン４０２経由で制御信号を送信し、それによりセルＢが下側にライン４０４にデータを送信しないように通知する。セルＷがパケットＰＶをセルＸに送信する場合、セルＤからセルＥに進入する任意のパケットＰＤ４１２は、セルＥのロジックによって、次列のセルＦへとルーティングされる。更に、セルＡからセルＢに進入する任意のパケットＰＡが、セルＢからセルＣへ送信される。
【００４３】
所定のパケット到達時間に、セルＷがセルＸにパケットを送信しない場合、セルＷがセルＸにパケットＭを送信しないというセルＷの状態が、セルＷによってセルＥに通知される。
【００４４】
図４Ａを再度参照すると、セルＷからセルＸに送信されたパケットが１つもないことを通知するために、セルＷによってセルＥに送信された、制御ライン１０８上を輸送される制御信号内に、制御情報が含まれている。セルＷからセルＸへのライン１０４はパケットによって占有されておらず、データを受取るべく利用可能である。この状態でセルＤがパケットＰＤをＥに送信する場合、セルＥはＰＤの１ビット・ヘッダ２０２を読込むことによってパケットＰＤの存在を検出する。セルＥに関連付けられたロジックは、セルＷからの制御信号及びパケットＰＤからのヘッダ・ビットを用いて、パケットＰＤのセルＸへのルーティングをセルＷ経由にするかどうか決定する。セルＷがセルＸに別のパケットを送信するのにデータ・ライン１０４を現在用いていていないので、パケットＰＤは、セルＷからセルＸへのデータ・ライン１０４を自由に利用することが可能である。
【００４５】
上にあるレベルからセルＷに進入する任意のパケットは、常にセルＸに直接的に送信される。図示されている集信装置は、セルＷに関連付けられたロジックは、セルＷと同一レベル上にある別のセルからセルＷに到達するパケットのルーティングが可能であるが、上位レベルからセルＷに進入するパケットに対しての制御は何ら有していない。上位レベルからのパケットは、セルＷを通過して、セルＷからセルＸへとデータ相互接続ライン１０４上を進む。セルＥによって、パケットＰＤがセルＷからセルＸまでを経由して下側にルーティングされる場合、セルＥは次に制御ライン４０２を介して制御信号をセルＢに送信する。この制御信号は、この時にセルＢによるライン４０４上へのパケット送信がブロッキングされるということが指定される情報を運ぶ。セルＥからのブロッキング制御信号が存在すると、セルＢはセルＡからパケットＰＡを受信した場合に、次に、セルＢに関連付けられたロジックによって、パケットＰＡに対してセルＢからセルＣまで、ライン１０４経由でのルーティングがなされる。
【００４６】
ある場合には、特定のパケット到達時間において、セルＷに関連付けられたロジックは、セルＸへのパケットのルーティングを行わず、且つセルＥはパケットをライン１０６に下側に送信しない。セルＢは、ライン４０４に下側にパケットを自由に送信することができる。セルＷは、例えば、単一ビット形式である制御信号を制御ライン１０８経由で送信し、それにより、セルＷがセルＥ若しくはセルＢからパケットの受信がブロッキングされていないことをセルＥに対して通知する。セルＥは、制御信号をライン４０２経由で送信して、セルＷがセルＢからのパケット受信をブロッキングされていないことをセルＢに対して通知することによって、セルＷからの制御信号及びセルＤからの到達するメッセージが存在しないことに応答する。このときに、パケットＰＡがセルＢに到達すると、セルＢは、ライン４０４を介してセルＷ経由でセルＸへとパケットＰＡを送信する。パケットＰＡは、最初にライン４０４を通って進み、次にライン１０４を通る。セルＷ若しくはセルＥからセルＸへとルーティングがなされたパケットを運ぶのにライン１０４が用いられていないので、ライン１０４はパケットＰＡを自由に運ぶことができる。
【００４７】
図４Ａを参照しながら続けると、ノードＷは、単一の制御信号輸送ライン１０８を介して制御信号をノードＥに送信するように接続されている。図示された相互接続ラインに加えて、レベルＪの上にあるノードは、レベルＪ−１上のノードから制御信号を運ぶことが可能な制御信号輸送ライン（図示せず）と、レベルＪのノードからレベルＪ−１の上にあるノードにパケットを送信することが可能なデータ輸送ライン（図示せず）とを、更に有している。例えば、ノードＷは、図３Ａに図示された、３つのデータ入力ポート、２つのデータ出力ポート、１つの制御信号入力ポート、及び１つの制御信号出力ポートを含むポート構造を有している。再度、図４Ａを参照すると、ノードＥがノードＷからライン１０８経由で制御信号を受信している。ノードＥは、同一レベル上にあるノードＢに制御信号を送信し、更に、ノードＥが最上位レベルの上にない場合には、ノードＥは、レベルＪ＋２の上にあるノードにも同様に制御信号を送信する。図示された相互接続ラインに加えて、レベルＪ＋１上のノードは、最上位レベルでない場合に、レベルＪ＋２上のノードに接続されている付加的なデータ及び制御の相互接続ラインも有する。例えば、ノードＥは、図３Ｂに図示されるような、レベルＪ＋２上のノードからの２つのデータ輸送ラインが含まれるポート構造を有する。
【００４８】
セルＢが最上位レベルにない場合、セルＢは上位レベルにあるセルに制御信号を送信するための接続ライン（図示せず）に接続される。この制御ラインは、セルＷからセルＥへの制御ラインと同様の機能を有する。セルＢがセルＣにパケットＰＡを送信する場合、次にセルＢは、上にある次のレベルのセルにブロッキング信号を送信する。
【００４９】
セルＢが列Ｋ−１内にあり、且つ上位レベルの上位２４行内にある場合には、セルＢは、集信装置の外側にあるデバイスから入力データを受信するセルの中へと、ＦＩＦＯを介してメッセージを送信する位置にいる。同様に構造の外側からメッセージを受信し得る別のセルにメッセージを送信することが可能なセルＢのようなセルは、構造の外側にあるデバイスから相互接続構造の中へのメッセージの流れを制御する特別な制御信号を有する。特別な制御信号ライン上の制御信号は、構造の外側にあるデバイスにデータ入力列１２０に、生じる可能性があるビジー状態を通知する。
【００５０】
セルＢが最上位レベルの列Ｋ−１内にあるが、最上位レベルの上位２４行内にない場合には、セルＢは構造の外側に制御信号を送信しない。
【００５１】
セルＥが最上位レベルにない場合、セルＥは２つの制御信号を送信する。セルＥがセルＷにパケットを送信するときに、セルＥは制御信号ライン４０２上をセルＢへとブロッキング信号を送信する。セルＥがセルＦにパケットを送信するときに、セルＥは、次の上位レベルへと制御信号ライン４０３上を上向きにブロッキング信号を送信する。
【００５２】
セルＥが列Ｋ−１内にあり、且つ最上位レベルの上位２４行内にある場合には、セルＥは構造の外側にあるデバイスから相互接続の中へのメッセージの流れを制御する特別な制御信号を送信する。
【００５３】
一般的に言うと、階層内で下側にパケットを送信する優先権を有するノードは、図４Ｂに示されているような２つの制御信号送信ラインを有する。下側へのパケット送信に対する優先権を有さないノードは、制御信号送信ラインを１つだけ有する。
【００５４】
図４Ａ及び図４Ｂは、論理的に同一な相互接続構造の代替実施例を示している。図４Ｂに示される構造がパケットをセルＢからセルＸに、最初はセルＥ経由で、次にセルＷ経由で送信することが物理的な差異である。メッセージは、セルＥがそうでない場合にデータ送信にライン１０６を用いず、且つセルＥ及びセルＷのいずれもがセルＸへのデータ送信にライン１０４を用いない場合は、メッセージはセルＢからセルＸへの飛ぶことが可能である。図４Ａ及び図４Ｂに示されているこの制御構造は同じであり、制御ラインを含んでいる。
【００５５】
図４Ｃは、図４Ａ及び図４Ｂに示されている相互接続構造と論理的に同一である相互接続構造の第３番目の実施例を示している。図４Ｃでは、セルＥ及びセルＢは直接的にセルＸにパケットを送信し、隣接ノードを経由しない。制御ライン構造は、図４Ａ、図４Ｂ、及び図４Ｃに示されている構造の内部のものと同様である。図４Ａ、図４Ｂ、及び図４Ｃは物理的には異なっているが、論理的には同等である。
【００５６】
集信装置の動作がうまく成功するかどうかは、少なくとも部分的にはタイミングに依存する。パケットＰＶの第１ビットは、所定のパケット到達時間にノードＷに到達する。ノードＷに関連付けられたこのロジックは、パケットＰＶの単一ビット・ヘッダ及びレベルＪ−１のノードから入力される制御信号に基づいてルーティングの決定を行う。パケットＰＶがノードＷに存在し、且つ下位レベルにあるノードからブロッキングされない場合、ノードＷは下位レベルにパケットＰＶを送信し、更に、上位レベルのノードＥに制御信号を送信する。ノードＷから制御信号は、そのパケットがノードＥに到達するのと同じ時間若しくはそれに近い時間にノードＥに到達する。このパケットがノードＥに到達する前にパケットがノードＷに到達するように、ロジックによってタイミングが制御される。
【００５７】
図４Ｃを参照すると、例えば光学的な実施例では、パケットがノードＸに到達するためのパケット到達時間が、ロジックによってあらかじめ決定される。ノードＥからノードＸに送信されるパケットは、パケットがノードＷからノードＸに送信されるのと同じ時間に、ノードＸに到達する必要がある。以下で説明されるように、パケットがノードＥに到達する前にパケットはノードＷに到達する。それゆえに、パケットがノードＥからノードＸに進むための時間は、パケットがノードＷからノードＸに進むための時間より小さくなっている必要がある。光学的な実施例では、ノードＷからノードＸへの相互接続ラインのファイバーの長さを、ノードＥからノードＸへの相互接続ラインのファイバーの長さよりも短く選択することによって、タイミングが調整される。この方法によって、到達時間を同期化するべく、上位レベルからのパケットが下位レベルからのパケットに追いつくことが可能である。
【００５８】
電気的な実施例では、同一レベル上にある２ノード間を進むパケットは、２つの１ビット・シフト・レジスタのセルを通過する。レベルを下側に延びているノードは、レジスタ・セルのうちの１つをバイパスしており、それにより図４Ａ、図４Ｂ、及び図４Ｃに示される構造内で、パケット・ビットは、セルＥからセルＦに２クロック周期サイクルで進み、セルＥからセルＸに１クロック周期サイクルで進む。
【００５９】
図１、図３Ａ、図３Ｂ、図４Ａ、図４Ｂ、及び図４Ｃに示される構造は、メッセージを相互接続構造経由で送信することに対して同等の優先権を有している。ノードＸの直前のノードＷは、ノードＸへの送信に対して第１番目の優先権を有する。ノードＥは、ノードＸへの送信に対して第２番目の優先権を有する。ノードＢは、ノードＸへの送信に対して第３番目の優先権を有する（ここで、ノードＸは、ノードＢよりもリボンの出力ポートに近い）。別の実施例では、リボンの出力末端から最も遠くにあるノードが優先権を有する。図５を参照すると、優先権が列に関して変更可能になっており、ノードＢがノードＡの直前にあり、且つノードＡが優先権を有さないセルである場合には、ノードＢが優先権を有するセルとなる。
【００６０】
図５には、相互接続構造の３列、３レベルの相互接続構造が図示されている。各レベル及び各列には、制御セル１０２のアレイ１１０がある。図５に示されている構造内のセル−セル相互接続網は、図４Ｂに図示されている相互接続網と同様である。セルは、対になってノード５０２を形成しており、それによりノード対の両セルが次の下位レベルの単一ノードにデータを送信するように配置される。集信装置のより適切な実施例では、制御アレイ１１０内で行１０４上のセル１０２が無作為に配置される。望ましくは、最良の実行配置が選択されるように、複数の無作為配置のソフトウェア・シミュレーションが実行される。色が塗られたボックス５０４は、ノード内でより高い方優先権を有するセルを示している。色が塗られていないボックスは、低い優先権を有するセルを示している。図示されているノードは各々、高い方の優先権を有する１つのセルと、低い方の優先権を有する１つのセルとを含んでいる。行１０４に沿って、１つの列において低い優先権を有するパケットが、常に、同一レベルの次列に高い優先権を有するという点が効果的である。
【００６１】
ノードが制御セルを１つしか含んでいないと考える場合は、各ノードが同一レベルから１つのデータ入力ラインを有する。最上位レベルにないノードは、上位レベルからの２つのデータ入力ラインを有する。各ノードは、同一レベル上にある１つのノードへのデータ出力ラインを有する。最下位レベル上にないノードは、下位レベルへの付加的なデータ出力ラインを有する。最下位レベル上にない各ノードは、１つの制御入力ポートを有する。最上位レベルにないノードは、１つ若しくは２つの制御信号出力ポートを有する。１つ若しくは複数の入力列におけるノードだけが、外部の入力源への制御信号出力ラインを有する。入力列は、全体クロック信号によって指示される時間にだけ、且つ最上位レベルのノードから対応するブロッキング信号を受信しない場合にだけ、集信装置にパケットを送信することが可能である。入力デバイスは、内部のセルが下位レベルのセルへと下側にパケットをルーティングするために従っている、パケットを集信装置へと「下側に」送信するための同一タイミング及びルーティング規則を用いる。
【００６２】
当業者は、本明細書に記載された基本的な集信装置に対して多くの変形、修正、付加、及び改良を容易に実行することが可能であろう。
【００６３】
代替的なトポロジー実施例
上記で説明された集信装置では、行Ｊ上のＦＩＦＯから出ているラインが、列０に進入する行Ｊ−８上のラインに接続すると考えられている。第１の代替的な例では、行Ｊ上のＦＩＦＯから出ているラインが、同一行Ｊ上の列０に進入するラインに接続される。最上位レベルが３２のリングを有し、階層内で下側にある次のレベルが１６リングを有し、更に、最下位レベルが８リングを有するように、トポロジーが変更される。
【００６４】
第２の代替的な例では、列Ｋ−１とＦＩＦＯの列との間で置換が行われる。行ＪでＦＩＦＯを出るラインが、同一行Ｊ上の列０に進入するラインに接続される。いくつかの置換では、できあがったトポロジーがレベルの各々に１つのリングを有する。いくつかの場合では、データがレベル０の列ｋ−１における出力ポートから集信装置を出て行くことが常に可能になっている。そのような場合に、図１に示される斬新な「理髪店ポール」構造は、構造の最上部に進入するメッセージがその構造から、固定定数による制限時間内に確実に退出するように作動する点が効果的である。
【００６５】
別の場合に、何らかの条件下にあるデータが、集信装置の出力ポートを出て行くのをブロックされてもよく、レベル毎に１つのリングを備えている構造がより適切である。
【００６６】
サービス品質の実施例
ネットワーク及び集信装置の中にサービス品質（ＱＯＳ）の優先権を組込むための単純な方法の１つは、サービス品質のレベルを指定する１以上の付加的なヘッダ・ビットを含むことである。図４Ａを参照すると、ＱＯＳ優先権の方法が実装されている。パケットＰＤがパケットＰＡと同等若しくはそれを上回る優先権を有し、且つセルＷがセルＸにパケットＰＤを送信しない場合には、パケットＰＤがセルＸに送信される。しかしながら、パケットＰＤがパケットＰＡより低い優先権を有し、且つセルＷがセルＸにパケットＰＶを送信しない場合には、パケットＰＡがセルＸに送信される。ＱＯＳ優先権の実装のために、セルＥ及びＢがＱＯＳヘッダ・ビットの読込みが可能であり、更にセルＢからセルＥへの制御ラインによってＱＯＳ情報が運ばれる。セルＢは、ライン１０８の退出を介して、若しくは付加的な制御ラインを介して、セルＥにＱＯＳ情報を送信することが可能である。
【００６７】
付加的なレベルの実施例
図示されている例では、ノードからのバッファが除外されている。しかしながら、集信装置はバッファのように機能し、従ってバースト・トラフィックを処理することが可能である。例えば、集信装置に進入するメッセージの平均数は８未満であるが、時折８より多いメッセージが集信装置に進入し、集信装置に進入するようにターゲティングされたメッセージが１つもブロックされない可能性がある。バースト・トラフィックを処理する能力は、付加的なレベル、例えばレベル３を、集信装置に付加することによって増進させることが可能である。レベル３は、最上位の３２行にデータが進入する６４つの行を有していてよい。付加的なレベルを含むことによって、全集信装置の有効バッファ・サイズが増大される。別の実施例では、いくつかの付加的なレベルが構造に付加され、それにより、バースト・トラフィックを処理する能力が更に高められる。
【００６８】
複数入力列の実施例
６４：８集信装置を実装するための一方法には、８巻リボンを用いていて、６４行を備えている付加的なレベル３を付加することが含まれる。代替的な方法では、付加的な入力ポート端子の列がレベル２に付加され、それによりレベル２内の３２行で受信されるデータの量は潜在的に２倍にされる。付加的なシフト・レジスタＦＩＦＯ列がレベル２に付加され、それにより３２ライン上のトラフィックが増大される。入力デバイスから集信装置に適用されたメッセージのタイミングは、付加的なＦＩＦＯ列が巻かれているかどうかに依存する。メッセージは、集信装置内のノードから入力列にメッセージが進入する際に、集信装置の外部から入力列に進入する。この代替的な方法は、入力チャネル当たりの平均データ速度がより低く、又、よりバースト状態である適用において有用である。
【００６９】
レベル間の異なる相互接続の実施例
各ノードが単一の制御セルを含んでおり、更に、より下位レベルにおける各ノードが、階層内でより上位レベルの１つのノードだけに接続されている。この集信装置は、特定のタイム・ステップにおいて、最下位レベルの上にある特定レベル内のラインの半分だけが、次の下位レベルへと下側にメッセージを送信するように適合され得る。
【００７０】
一実施例では、４セルにデータ送信することが可能な４つの制御セルが単一ノードに結び付けられる。当業者は、特定レベルの４つのセルが下位レベル上の２セルにデータを送信することが可能なノードを形成するように、この構造を修正することが可能である。
【００７１】
図５を再度参照すると、レベル上の２つの制御セルが、階層内で、次の下位レベル上にある単一の制御セルにデータを送信するように配置されている。ノード５０２には、１つのノード内の２セルによって、下位レベル上の１つのノードへのデータ送信が可能な２：１ノード集信装置の構造が図示されている。機能的な例では、メッセージＭ１が、列０、レベル１の行２上の制御セルから、列１、レベル１の行２上のセルに送信される。同じ作動時間周期内に、列０内にある、レベル２の行８上の制御セルにメッセージＭ２が到達する。メッセージＭ１は、メッセージＭ２をブロックするように配置され、メッセージＭ２は同一レベル上に留まる。それゆえに、図５で示されるトポロジー内で、あるレベルの上にある単一メッセージによって、より上位のレベルの上にあるメッセージのブロックが可能である。
【００７２】
図６Ａ及び図６Ｂを参照すると、セルが、例えばノード６０２内に分類され、相互接続ライン６０４上の次の下位レベル上の２セルにデータを送信するように、１つのレベルの上に４セルが配置されている。各レベル上のノードは、４つの制御セルを含んでいる。レベル２の上の最も左側にあるノードの４つのセルの各々は、レベル１の上にある２セルのいずれかにデータを送信することが可能である。図６Ａに示されている一例では、ノードＮ内の４セルが、ノードＰのセルＱ及びＲにデータを送信することが可能である。同様にして、ノードＭ内の４セルは、ノードＰ内のセルＳ及びＴにデータを送信することが可能である。あるレベルにあるメッセージで、上位レベルにあるメッセージをブロックすることが可能なものは１つも存在せず、それにより、１つのレベルから次の下位レベルへの処理能力が増大され得る。図６Ａは、１つのノード内の４セルが下位のレベルの２セルのいずれかにデータを送信することが可能な、４：２ノード集信装置の構造が図示されている。別の実施例では、例えば図６Ｂに示されているように、ノード６１０内のセル数を増大させるようにロジックを付加されてよい。例えば、ノードＴ及びＵ内の８セルが組合されて制御され、それにより、８：４ノード集信装置を形成するように、ノードＶ及びＷのいずれか若しくは両方の内部にある４セル全てにデータが送信される。ノード当たりでより多いロジックを費いやして処理能力が増大された設計では、より複雑なノードが用いられる。
【００７３】
図７を参照すると、ブロック図によって、いくつかのチップからより大きなネットワークを形成するように複数の集信装置及び複数のスイッチを用いているシステムが図示されている。ある代替実施例では、ねじれ形状の立方体の中により小さなネットワークが配置されている。図７に図示されているシステムによって、ねじれ形状立方体構造が改良されている。
【００７４】
実際には、図示されている複数チップ・モジュールを利用して、極めて大きなネットワークが構築されてよい。例えば、１２８のスイッチ・チップ及び１２８の集信装置チップが組合わされてよい。例えば、１２８のチップの各々が６４のオンライン入力ポートと６４の３ライン出力ポートとを含んでいてよい。この組合わせによって、６４２の入力ライン及び６４２の出力ラインを備えた単一チップが形成される。図７に図示されている例は、図示されている目的に対して有用である、ずっと小さいシステムである。実際的には、より大きなシステムが構築されてよい。
【００７５】
図７に示されているネットワーク７０２及び７０４は、３つのレベルと複数の列を有している。各レベルは４つの行を有している。レベル０上にある列のうちの３つは、出力ポートを含んでいる。図示されているシステムでは、チップ７０２の各々は、アドレス０に送られる３つの出力ライン、アドレス１に送られる３つの出力ライン、アドレス２に送られる３つの出力ライン、及びアドレス３に送られる３つの出力ラインを有している。最下部の集信装置は、アドレス０に接続されている全１２出力ラインを受取る。３つの別の集信装置は、アドレス１、２、及び３に適切に接続されている１２の入力ラインを各々受取る。
【００７６】
別のネットワークは種々の時間において、異なる列からデータを送信する。図７に示されるシステムでは、異なる列からのメッセージが適切な遅延ラインＦＩＦＯ（図示せず）を通過しており、それにより全ての列からのメッセージが同時に集信装置７００に到達する。
【００７７】
集信装置７００は、レベル０が４行を有し、レベル１が８行を有し、更に、レベル２が１６行を有するように、３つのレベルの上に４幅リボンの行を有している。レベル２の上では、１６行の下位の１２行が、スイッチ７０２から、集信装置７００の入力ポート（図示せず）においてデータを受信するように配置されている。
【００７８】
データが非常に混雑していることが予想される適用においては、付加的な層が集信装置７００に付加されてよい。集信装置７００は、１２チャネル出力ラインからのデータを、第１列内の各チップから第２列内の４つの入力ラインの上に集約させる。この集信装置は更に、ホット・スポットの可能性を減少させるように、時間内にこのデータを広げる、若しくは配信する。集信装置７００からのデータは、スイッチ・チップ７０４の第２列の中に適用される。
【００７９】
集信装置モジュール７００とスイッチ・チップ７０４との間でＦＩＦＯが１つも必要とされないように、メッセージは同期して集信装置７００を退出する。メッセージは、スイッチ７０４から出現して、集信装置モジュール７０６の第２列の中への進入のために、時間内にメッセージを整列させるようにＦＩＦＯ（図示せず）を通過する。集信装置チップ７０６の各々は、４つの集信装置を含んでいる。集信装置チップ７０６内にある４つの集信装置の各々は、１行の幅を備えたリボンを有する。
【００８０】
第２列の集信装置は、レベル０が１行を有し、レベル１が２行を有し、且つレベル２が４行を有する、３つのレベルで設計される。最上位レベルの４行のうちの３行は、入力データを受信することが可能である。同様に、バースト・トラフィックに対しては、集信装置チップ７０６内で集信装置に付加行が確実に付加される。
【００８１】
制御ライン（図示せず）によって、上流のチップに下流のチップのデータ・ブロック状況を通知するように、下流のチップから上流のチップに制御信号が供給される。例えば、スイッチ７０４が集信装置７００からデータを受信することが不可能である場合、このデータは集信装置７００の最上位の行のうちの１つに転送される。集信装置７００の下位の１２行だけが上流のスイッチ７０２からメッセージを受信するので、上位の４行は常に、データ受信を自由に行うことができる。
【００８２】
最上位のスイッチに戻る制御ラインは、多数の場所から来ていてよい。一実施例では、バッファは集信装置８００とスイッチ８０４との間に配置されてよい。バッファが能力レベルを越えて満たされると、満杯のバッファに供給を行ったスイッチ８０２の出力ポートに、制御信号が選択的に送信される。或いは、トラフィックが混雑しているときには、列内の上位レベルに配置されたノードから左側に制御信号を出ることが可能であるが、トラフィックが混雑していないときにメッセージを受信しないように、集信装置の内部からの制御信号が発信されてもよい。この制御信号が、集信装置内のトラフィックに基づいて、スイッチ８００の特定の出力ポートをブロックしてもよい。
【００８３】
フィードバックされるメッセージの最大数がリボン幅と等しく、且つリボン幅が集信装置の最上位の行に常に開かれているので、全ての大きさの集信装置に対して、集信装置の最上位行へのブロックされたメッセージのフィードバックは、常に成功する。
【００８４】
本発明は、種々の実施例に関して説明がなされたが、これらの実施例は例示的なものであり、本発明の範囲がそれらに制限されるものではないことを理解されたい。説明された実施例に対して多くの変形、修正、付加及び改良が可能である。例えば、当業者によって、本明細書に記載されている構造及び方法を提供するのに必要なステップが容易に実装可能であり、又、処理のパラメータ、材料、及び寸法は例のためだけに与えられたものであり、本発明の範囲内で、修正と同様に所望の構造を得るために変形がなされてもよいことを理解されたい。本発明で説明される実施例の変形及び修正が、本明細書の請求項で示される本発明の範囲及び精神から離れることなしに、本明細書に示された説明に基づいてなされてよい。例えば、当業者によって、第１及び第２の品質サービス方法が、本明細書で説明されたものとは別の相互接続構造に同様に適用されてよい。
【００８５】
本明細書の請求項では、特に断らない限りは、全てのものは「１以上」を示している。
【図面の簡単な説明】
【図１】
図１には、多重レベル３２：８の集信装置の形態であるデータ相互接続構造の一例が示されている。
【図２】
図２は、パケットの形態で相互接続構造経由して運ばれるデータ・フォーマットが示されている。
【図３Ａ】
図３Ａは、入力ポート及び出力ポートの種々の構成を含む、図１に示される相互接続構造の内部で用いられ得るセルの例が示されている。
【図３Ｂ】
図３Ｂは、入力ポート及び出力ポートの種々の構成を含む、図１に示される相互接続構造の内部で用いられ得るセルの例が示されている。
【図４Ａ】
図４Ａは、図１に示された構造等の相互接続構造の内部で用いられるのが適切なセル間の相互接続構造の複数の例が示されている模式的なブロック図である。
【図４Ｂ】
図４Ｂは、図１に示された構造等の相互接続構造の内部で用いられるのが適切なセル間の相互接続構造の複数の例が示されている模式的なブロック図である。
【図４Ｃ】
図４Ｃは、図１に示された構造等の相互接続構造の内部で用いられるのが適切なセル間の相互接続構造の複数の例が示されている模式的なブロック図である。
【図５】
図５は、レベルに関して変更可能である、相互接続構造内のセルの優先権が図示されている模式的なブロック図である
【図６Ａ】
図６Ａは、相互接続されたセルのノードへの分類の例が示されている模式的なブロック図である。
【図６Ｂ】
図６Ｂは、相互接続されたセルのノードへの分類の例が示されている模式的なブロック図である。
【図７】
図７は、複数の集信装置を用いているシステムが図示された模式的なブロック図である。
【図１】
2004535690.tif 000003
【図２】
2004535690.tif 000004
【図３Ａ】
2004535690.tif 000005
【図３Ｂ】
2004535690.tif 000006
【図４Ａ】
2004535690.tif 000007
【図４Ｂ】
2004535690.tif 000008
【図４Ｃ】
2004535690.tif 000009
【図５】
2004535690.tif 000010
【図６Ａ】
2004535690.tif 000011
【図６Ｂ】
2004535690.tif 000012
【図７】
2004535690.tif 000013
【国際公開パンフレット】
2004535690.tif 000014
2004535690.tif 000015
2004535690.tif 000016
2004535690.tif 000017
2004535690.tif 000018
2004535690.tif 000019
2004535690.tif 000020
2004535690.tif 000021
2004535690.tif 000022
2004535690.tif 000023
2004535690.tif 000024
2004535690.tif 000025
2004535690.tif 000026
2004535690.tif 000027
2004535690.tif 000028
2004535690.tif 000029
2004535690.tif 000030
2004535690.tif 000031
2004535690.tif 000032
2004535690.tif 000033
2004535690.tif 000034
2004535690.tif 000035
2004535690.tif 000036
2004535690.tif 000037
2004535690.tif 000038
2004535690.tif 000039
2004535690.tif 000040
2004535690.tif 000041
2004535690.tif 000042
2004535690.tif 000043
2004535690.tif 000044
2004535690.tif 000045
2004535690.tif 000046
2004535690.tif 000047
【国際公開パンフレット（コレクトバージョン）】
2004535690.tif 000048
2004535690.tif 000049
【国際公開パンフレット（コレクトバージョン）】
2004535690.tif 000050
2004535690.tif 000051
【手続補正書】
【提出日】平成14年10月9日(2002.10.9)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
相互接続構造であって、
並列データ経路のセットＳであって、パケット形式のデータが前記相互接続構造の外部の１以上のデバイスから前記データ経路に進入して、前記セットＳの１以上のデータ経路上をデータ出力ポートへとワームホール送信で進むことが可能な、並列データ経路のセットＳを有し、
セットＳのデータ経路Ｐ上のノードＡにおいて、
前記ノードＡからノードＢへのデータの移動が前記データ経路Ｐのデータ出力ポートにより接近する１ステップの移動であるように、データが前記データ経路Ｐ上を、ノードＡから該ノードＡの直後にあるノードＢに移動することが可能であり、
前記ノードＡからノードＣにセットＳのデータ経路Ｑ上をデータが移動可能であり、前記ノードＢの前記データ経路Ｐ出力ポートへの接近よりも、前記ノードＣが前記データ経路Ｑにより接近することを特徴とする相互接続構造。
【請求項２】
前記ノードＣの直前にある、データ経路Ｑ上のノードＤを更に有し、前記ノードＤから前記ノードＣへのデータ移動が、前記ノードＡから前記ノードＣへのデータ移動を上回る優先順位を有することを特徴とする請求項１に記載の相互接続構造。
【請求項３】
前記相互接続構造内のトラフィックによってデータの廃棄を生じさせないことを特徴とする請求項１に記載の相互接続構造。
【請求項４】
相互接続構造であって、
複数の送信リングと、
複数の前記送信リング内に配置された複数のノード（１０２）とを有し、
前記データ送信リングが、最上位レベルＬから最下位レベル０まで複数のレベル内に配置されて、
レベルＬ上のリングが、前記相互接続構造の外側からデータを受信することが可能である１以上のノードを備え、
複数の前記ノードが、ノードＡ、Ｂ、Ｃ、Ｘ、及びＹを含み、
前記ノードＢが、レベル０とレベルＬとの間のレベルＪ上にあり、
前記ノードＡが、前記ノードＢと同一のデータ送信リング上で前記ノードＢの直前にあり、
前記ノードＣが、前記ノードＢと同一のデータ送信リング上で前記ノードＢの直後にあり、
前記ノードＸが、前記レベルＪよりも大きいレベルＫ上にあり、
前記ノードＹが、前記レベルＫよりも小さいレベルＰ上にあり、
前記ノードＢが、前記ノードＡ及び前記ノードＸからデータを受信することが可能であり、
前記ノードＢが、前記ノードＣ及び前記ノードＹにデータを送信することが可能であり、前記データは、データ・メッセージに対してターゲットを特定するヘッダ情報を用いずに自己ルーティングされることを特徴とする相互接続構造。
【請求項５】
前記データは、少なくとも部分的にサービス品質情報に基づいて、自己ルーティングされることを特徴とする請求項４に記載の相互接続構造。
【請求項６】
相互接続構造であって、
複数のデータ送信ライン（１０４）と、
複数の前記データ送信ラインの上に配置された複数のノード（１０２）とを有し、
複数の前記ノードが、ノードＢ及びノードのサブセットＳを含み、
前記ノード・サブセットＳが、前記ノードＢにデータを送信することが可能な１以上のノードを含み、前記サブセットＳ内のノードＮ及び該ノードＮに到達するメッセージＭに関して、前記ノードＢへのメッセージ送信に対して前記ノードＮよりも低い優先権を有する前記サブセットＳ内のノードからのメッセージによって、前記ノードＮがノードＢへの前記メッセージＭの送信を決してブロックされないように、前記サブセットＳ内の前記ノードが前記ノードＢへのメッセージ送信に対して優先権関係を有し、前記メッセージＭに対するルーティング情報が存在せずとも複数の前記ノードが前記メッセージをルーティングすることが可能であることを特徴とする相互接続構造。
【請求項７】
前記ノードＮによってメッセージのルーティングがなされる得るノード・サブセットＴＮと、
前記メッセージＭを受信するのが最も望ましいノードから、前記メッセージＭを受信するのが最も望ましくないノードまで、前記サブセットＴＮの構成要素を順位付けし、前記サブセットＴＮのブロックされていない最も望ましい構成要素に前記メッセージＭを送信する、ノードＮに関連付けられたロジックとを更に有することを特徴とする請求項６に記載の相互接続構造。
【請求項８】
前記Ｂの直前にあり、前記ノードＢへのメッセージ送信に対して最も高い優先権を更に有するノードＡを有することを特徴とする請求項７に記載の相互接続構造。
【請求項９】
相互接続構造であって、
構造内に配置された複数のノード（１０２）を有し、
複数の前記ノードが、
ソース・レベルから宛先レベルまでの複数のレベルから成る階層と、
前記レベルに沿って延びる非横断経路内にある複数のノードと、
前記レベルの非横断経路の横断部分内の複数のノードであって、前記相互接続構造が１つの集信装置になるように、前記ソース・レベルの横断部分内のノード数が、前記宛先レベルの横断部分内のノード数よりも大きくなっており、ノードの前記レベルが前記構造内の前記ノードの位置によって完全に決定される複数ノードと、
レベルＬの経路Ｐ上のノードＮに対してのものを含む、前記構造内で前記ノードを接続する複数の相互接続ライン（１０４）と、
前記レベルＬの前記経路Ｐ上の第１隣接ノードに接続されたメッセージ入力相互接続ラインと、
前記レベルＬの前記経路Ｐ上の第２隣接ノードに接続されたメッセージ相互接続ラインと、
階層内でソース方向のノードからデータを受信するために、前記ノードＮのソース方向の１以上のノードに接続され、且つ／又は階層内で宛先方向のノードにデータを送信するために、前記ノードＮの宛先方向の１以上のノードに接続された少なくとも１つのメッセージ相互接続ラインと、
ソース方向のノードに制御信号を送信するために、前記ノードＮのソース方向のノードに接続され、且つ／又は階層内で宛先方向のノードから制御信号を受信するために、前記ノードＮの宛先方向のノードに接続された少なくとも１つの制御相互接続ラインとを有することを特徴とする相互接続構造。
【請求項１０】
前記ノードＮが前記レベルＬの前記経路Ｐ上のメッセージによって占有されているか決定し、該決定に基づいてソース方向の前記ノードに制御信号を送信し、前記ソース方向のノードにおけるメッセージの進行を速めることが可能な、前記ノードＮに関連付けられたロジックを更に有することを特徴とする請求項９に記載の相互接続構造。
【請求項１１】
各列がレベル内で非横断経路の横断部分内の複数のノードを相互接続し、少なくとも１つのメッセージ相互接続ライン上及び少なくとも１つの制御相互接続ライン上のソース方向及び宛先方向の接続を含むノード間の相互接続網を含んでいる、複数の列を更に有することを特徴とする請求項９に記載の相互接続網。
【請求項１２】
前記レベルに沿って延びる非横断経路にそれぞれ接続される複数のＦＩＦＯバッファ（１１８）を更に有することを特徴とする請求項９に記載の相互接続構造。
【請求項１３】
レベルＬの経路Ｐ上の前記ノードＮに対してのものを含む、前記構造内で前記ノードを接続する複数の前記相互接続ラインは、
前記経路Ｐのソース方向のノード及び前記レベルＬ内のノードに接続された第１制御出力相互接続ラインと、
前記レベルＬのソース方向のレベル内のノードに接続された第２制御出力相互接続ラインとを更に有することを特徴とする請求項９に記載の相互接続構造。
【請求項１４】
レベルＬの経路Ｐ上の前記ノードＮに対してのものを含む、前記構造内で前記ノードを接続する複数の前記相互接続ラインは、
前記レベルＬ内のノード及び前記経路Ｐのソース方向のノードに接続されている第１メッセージ入力相互接続ラインと、
前記レベルＬのソース方向のレベル内のノードに接続されている第２メッセージ入力相互接続ラインと、
前記レベル内のノード及び前記経路Ｐのソース方向のノードに接続されている制御出力相互接続ラインとを更に有することを特徴とする請求項９に記載の相互接続構造。
【請求項１５】
レベルＬの経路Ｐ上の前記ノードＮに対してのものを含む、前記構造内で前記ノードを接続する複数の前記相互接続ラインは、
前記レベルＬ内のノード及び前記経路Ｐのソース方向のノードに接続されている第１制御出力相互接続ラインと、
前記レベルＬのソース方向のレベル内のノードに接続されている第２制御出力相互接続ラインと、
前記経路Ｐのソース方向のノードに接続されているメッセージ入力相互接続ラインとを更に有することを特徴とする請求項９に記載の相互接続構造。
【請求項１６】
複数の前記ノード間の優先ノードと、非優先ノードであるその他のノードとを更に有し、前記優先ノード及び前記非優先ノードが選択的に相互接続されることを特徴とする請求項９に記載の相互接続構造。
【請求項１７】
ソース方向経路上のｎノードを宛先方向経路上のｍノードに集約するように、相互接続ノードを集団化するロジックを更に有し、
ｎがｍよりも大きく、且つｎ：ｍが集約比になっていることを特徴とする請求項９に記載の相互接続構造。
【請求項１８】
前記非横断経路内の複数ノードに接続される相互接続ラインのリボン（１１２）であって、相互接続ラインの該リボンは、前記ソース・レベルから前記宛先レベルまで複数の前記レベルを通って巻かれ、巻かれる回数が前記ソース・レベルから前記宛先レベルに減少する、相互接続ラインのリボンと、
前記レベルの全ての巻き部分を通って、前記リボンの横断部分内の前記ノードを接続する複数の列とを更に有することを特徴とする請求項９に記載の相互接続構造。
【請求項１９】
前記相互接続ライン・リボンの前記巻き数が、前記ソース・レベルから前記宛先レベルまで、レベル毎に半分減少することを特徴とする請求項１８に記載の相互接続構造。
【請求項２０】
システムであって、
複数のスイッチ（７０２）と、
複数の前記スイッチに各々接続される、請求項９に記載の複数の集信装置（７００）とを有することを特徴とするシステム。
【請求項２１】
相互接続構造であって、
非横断経路内の複数ノードに接続される相互接続ラインのリボン（１１２）であって、相互接続ラインの該リボンは、前記ソース・レベルから前記宛先レベルまで複数の前記レベルを通って巻かれ、巻かれる回数が前記ソース・レベルから前記宛先レベルに減少する、相互接続ラインのリボンと、
前記レベルの巻き部分を通って、前記リボンの横断部分内に渡っている前記ノードに接続されている相互接続ラインによって形成される複数の列とを有することを特徴とする相互接続構造。
【請求項２２】
前記ソース・レベルの第１列内の前記ノードに接続されている複数の入力ポートを更に有することを特徴とする請求項２１に記載の相互接続構造。
【請求項２３】
前記宛先レベルの最後の列内の前記ノードに接続されている複数の出力ポートを更に有することを特徴とする請求項２１に記載の相互接続構造。
【請求項２４】
前記レベルに沿って延びる非横断経路にそれぞれ接続されている複数のＦＩＦＯバッファを更に有することを特徴とする請求項２１に記載の相互接続構造。
【請求項２５】
前記ソース・レベルから前記宛先レベルまでレベル毎に半分減少する、前記相互接続ラインの前記巻数を更に有することを特徴とする請求項２１に記載の相互接続構造。
【請求項２６】
前記相互接続構造の中へのメッセージの進入を制御するように、前記相互接続構造の内側のノードから、前記相互接続構造の外側の１以上のデバイスに延びている制御ラインを更に有することを特徴とする請求項２１に記載の相互接続構造。
【請求項２７】
ソース方向経路上のｎノードを宛先方向経路上のｍノードに集約するように、相互接続ノードを集団化するロジックを更に有し、
ｎがｍよりも大きく、且つｎ：ｍが集約比になっていることを特徴とする請求項２１に記載の相互接続構造。
【請求項２８】
ノードがレベルの前記経路上のメッセージによって占有されているか決定し、該決定に基づいてソース方向のノードに制御信号を送信し、ソース方向の前記ノードにおけるメッセージの進行を速めることが可能なロジックを更に有することを特徴とする請求項２１に記載の相互接続構造。
【請求項２９】
複数の前記ノード間の優先ノードと、非優先ノードであるその他のノードとを更に有し、前記優先ノード及び前記非優先ノードが選択的に相互接続されることを特徴とする請求項２１に記載の相互接続構造。
【請求項３０】
システムであって、
複数のスイッチ（７０２）と、
複数の前記スイッチに各々接続される、請求項２１に記載の複数の集信装置（７００）とを有することを特徴とするシステム。
【請求項３１】
前記相互接続構造を通って移動するデータ・パケットは、該データ・パケット内に含まれるターゲット出力情報に依存しないことを特徴とする請求項２に記載の相互接続構造。
【請求項３２】
前記データ経路Ｑが前記データ経路Ｐと分離されており、且つ別個のものであることを特徴とする請求項１に記載の相互接続構造。
【請求項３３】
前記データ経路Ｑが前記データ経路Ｐと同一のデータ経路であることを特徴とする請求項１に記載の相互接続構造。
【国際調査報告】
2004535690.tif 000052
2004535690.tif 000053
2004535690.tif 000054