"N個の入力ポートIa-IhおよびM個の出力ポートOa-Ohを有する、コンピュータ相互接続ネットワーク100の部分を接続するように適合されたスイッチングデバイスSi,jにおいて、Mは好ましくはNに等しく、前記デバイスが、直接クロスポイントCPx,yによってデータパケットをルーティングするために適合され、前記直接クロスポイントが、前記コンピュータ相互接続ネットワークの接続性の要求に従って、前記N個の入力ポートの各々と前記出力ポートのサブセットm<Mとの間のみの直接接続性を可能とするために構成されている、デバイス。NM-N1N1≦Min[N,M]以下の数の直接クロスポイントを含み、これによって前記デバイスが、同一のポートに対応する少なくともN1個の入力ポートおよびN1個の出力ポートのサブセット間の直接接続性を阻止する、請求項1に記載のスイッチングデバイス。N1<Nであって、1つ以上の第1のネットワークエンティティからデータを受信するように適合された、N1個の入力ポートと、N2<Mであって、1つ以上の第2のネットワークエンティティにデータを送信するように適合された、N2個の出力ポートと、を含み、前記直接クロスポイントの数がNM-N1N2以下である、請求項1に記載のスイッチングデバイス。M=Nであり、前記直接クロスポイントの数がN2-N1N2-N-MinN1、N2であり、好ましくはN1=N2=N/2である、請求項3に記載のスイッチングデバイス。追加回路Lおよび追加クロスポイントAPx,L、APL,yを更に含み、前記追加回路および前記追加クロスポイントが、前記スイッチングデバイスの前記入力ポートの少なくともいくつかが前記追加回路を介して前記スイッチングデバイスの前記出力ポートの少なくともいくつかに間接的に接続可能となるように構成されている、請求項1から4のいずれか1項に記載のスイッチングデバイス。前記追加クロスポイントが、-各々が、1つ以上の直接クロスポイントCPx,yにすでに接続されている前記デバイスの入力ポートIxを前記回路Lに接続する、少なくとも1つの第1のクロスポイントAPx,Lのセットと、-各々が、前記回路を、1つ以上の直接クロスポイントCPx,yにすでに接続されている前記デバイスの出力ポートOyに接続する、少なくとも1つの第2のクロスポイントAPL,yのセットと、を含む、請求項5に記載のスイッチングデバイス。請求項1から6のいずれか1項に記載の少なくとも1つのスイッチングデバイスSi,jを含むコンピュータ相互接続ネットワーク100。請求項3または4に記載の少なくとも1つのスイッチングデバイスSi,jを含み、前記1つ以上の第1のネットワークエンティティSi-1,jおよび前記1つ以上の第2のネットワークエンティティSi1,jを更に含む、請求項7に記載のコンピュータ相互接続ネットワーク。請求項4に記載の少なくとも1つのスイッチングデバイスSi,jを含み、-前記1つ以上の第1のネットワークエンティティSi-1,jが各々、前記コンピュータ相互接続ネットワークにおける下位のスイッチングデバイスであり、-前記1つ以上の第2のネットワークエンティティSi1,jが各々、前記コンピュータ相互接続ネットワークにおける上位のスイッチングデバイスであり、M=Nであり、かつN1=N2=N/2であり、前記少なくとも1つのスイッチングデバイスが、-前記デバイスの同一のポートに対応する入力ポートおよび出力ポート、-上位のスイッチングデバイスからデータを受信するように適合されたN/2個の入力ポートおよび上位のスイッチングデバイスにデータを送信するように適合されたN/2個の出力ポート、の間の直接接続性を阻止する等のために、3N2/4-N/2個の直接クロスポイントを含むようになっている、請求項8に記載のコンピュータ相互接続ネットワーク。好ましくはアップ/ダウンルーティングアルゴリズムに基づいた、前記コンピュータ相互接続ネットワークのためのコンピュータ化ルーティング方法を更に含み、前記コンピュータ相互接続ネットワークが更に、前記コンピュータ化ルーティング方法により決定される接続性の要求に従って前記少なくとも1つのスイッチングデバイスSi,jの前記直接クロスポイントCPx,yが前記入力ポートIxを前記出力ポートOyのサブセットのみに直接接続することができるように構成されている、請求項7、8、または9に記載のコンピュータ相互接続ネットワーク。請求項7から10のいずれか1項に記載の前記コンピュータ相互接続ネットワークを提供することと、前記コンピュータ相互接続ネットワークの前記少なくとも1つのスイッチングデバイスのクロスポイントCPx,yを介してデータをルーティングすることと、を含む、データをルーティングするためのコンピュータ実施方法。前記提供されたコンピュータ相互接続ネットワークが、請求項5に記載の少なくとも1つのスイッチングデバイスSi,jを含み、前記データをルーティングするステップが、-直接クロスポイントによって接続されていない1対の入力ポートI8および出力ポートO8のためのデータパケットを受信したら、前記データパケットを、前記デバイスの前記追加のクロスポイントAP8,L、APL,8および回路Lの一部を介してルーティングすることを含む、請求項11に記載の方法。前記提供されたコンピュータ相互接続ネットワークが、請求項6に記載の少なくとも1つのスイッチングデバイスを含み、前記データをルーティングするステップが、-直接クロスポイントによって接続されていない1対の入力ポートI8および出力ポートO8のためのデータパケットを受信したら、-前記データパケットが受信された前記入力ポートI8に接続された、前記少なくとも1つの第1のセットのクロスポイントAP8,Lに前記パケットを送出し、-前記回路Lを介して、前記データパケットが宛てられた出力ポートO8に接続された、前記第2のセットのクロスポイントAPL,8に前記パケットをループバックする、ことによって、前記データパケットをルーティングすることを含む、請求項11に記載の方法。前記提供するステップの前に、前記入力および出力ポートにおけるデータパケット到着の既知のまたは予想される強度によって前記接続性の要求を決定するステップを更に含み、前記提供するステップが、少なくとも1つのスイッチングデバイスSi,jを含む前記コンピュータ相互接続ネットワーク100を提供することを含み、前記スイッチングデバイスの直接クロスポイントが、前記コンピュータ相互接続ネットワークの前記決定した接続性の要求に従って前記N個の入力ポートの各々と前記出力ポートのサブセットm<Mとの間のみの直接接続性を可能とするために構成されている、請求項11に記載の方法。コンピュータ読み取り可能記憶媒体と、請求項7から10のいずれか1項に記載のコンピュータ相互接続ネットワークの少なくとも1つのスイッチングデバイスのクロスポイントCPx,yを介してデータをルーティングするためのプログラム命令と、を含み、前記プログラム命令が前記コンピュータ読み取り可能記憶媒体上に記憶されている、データをルーティングするためのコンピュータプログラム。この複雑度は本質的に、いかなる1対1通信パターン順列も衝突なしでルーティング可能とすることを要求するノンブロッキング要求から生じる。複雑度の軽減を可能とするには、この要求を緩和する、すなわち、異なるポートとの通信間でも衝突の発生を許容するしかない。これは、通常バス等の共有媒体またはマルチステージ構成に基づくスイッチアーキテクチャのブロッキングを招く。かかる手法の欠点は、例えばバスベースの実施の物理的な制限によって達成可能な全スループットが限られていることである。ほとんどの既存のシングルステージのスイッチングノード実施は、ノンブロッキング要求を満足させる。すなわち、それらは、あらゆる入力ポートからあらゆる出力ポートへと全容量で送信する機能を提供する。クロスバーベースのアーキテクチャこれはバッファありの場合もバッファなしの場合もあるの特定の場合、これは、スイッチングノードがN2のクロスポイントを含むことを意味する。更に、バッファありのクロスバーアーキテクチャの場合、各クロスポイントが含むバッファは、全往復を通して全リンク利用を可能とするような大きさである。多くの場合、このバッファリング容量の多くは概ね未使用のままであり、これが貴重なリソースの無駄となることが認められている。第1の態様によれば、本発明は、N個の入力ポートおよびM個の出力ポートを有する、コンピュータ相互接続ネットワークの部分を接続するように適合されたスイッチングデバイスとして具現化される。Mは、好ましくはNに等しい。このデバイスは、直接クロスポイントによってデータパケットをルーティングするために適合され、直接クロスポイントは、コンピュータ相互接続ネットワークの接続性の要求に従って、N個の入力ポートの各々と出力ポートのサブセットm<Mとの間のみの直接接続性を可能とするために構成されている。実施形態において、前記デバイスは以下の特徴の1つ以上を含むことができる。スイッチングデバイスは、NM-N1N1≦MinN,M以下の数の直接クロスポイントを含み、これによってデバイスは、同一のポートに対応する少なくともN1個の入力ポートおよびN1個の出力ポートのサブセット間の直接接続性を阻止する。スイッチングデバイスは、N1<Nであって、1つ以上の第1のネットワークエンティティからデータを受信するように適合された、N1個の入力ポートと、N2<Mであって、1つ以上の第2のネットワークエンティティにデータを送信するように適合された、N2個の出力ポートと、を含み、直接クロスポイントの数がNM-N1N2以下である。M=Nであり、直接クロスポイントの数がN2-N1N2-N-MinN1、N2であり、好ましくはN1=N2=N/2である。スイッチングデバイスは追加回路および追加クロスポイントを更に含み、この追加回路および追加クロスポイントは、スイッチングデバイスの入力ポートの少なくともいくつかが追加回路を介してスイッチングデバイスの出力ポートの少なくともいくつかに間接的に接続可能となるように構成されている。追加クロスポイントは、各々が、1つ以上の直接クロスポイントにすでに接続されているデバイスの入力ポートを回路に接続する、少なくとも1つの第1のクロスポイントのセットと、各々が、回路を、1つ以上の直接クロスポイントにすでに接続されているデバイスの出力ポートに接続する、少なくとも1つの第2のクロスポイントのセットと、を含む。第2の態様によれば、本発明は更に、本発明の実施形態による少なくとも1つのスイッチングデバイスを含むコンピュータ相互接続ネットワークとして具現化される。実施形態において、前記ネットワークは以下の特徴の1つ以上を含む。コンピュータ相互接続ネットワークは、本発明の実施形態に従った少なくとも1つのスイッチングデバイスを含み、更に、1つ以上の第1のネットワークエンティティおよび1つ以上の第2のネットワークエンティティを含む。コンピュータ相互接続ネットワークは、本発明の一実施形態に従った少なくとも1つのスイッチングデバイスを含み、1つ以上の第1のネットワークエンティティが各々、コンピュータ相互接続ネットワークにおける下位のスイッチングデバイスであり、1つ以上の第2のネットワークエンティティが各々、コンピュータ相互接続ネットワークにおける上位のスイッチングデバイスであり、M=Nであり、かつN1=N2=N/2であり、少なくとも1つのスイッチングデバイスが、デバイスの同一のポートに対応する入力ポートおよび出力ポート、上位のスイッチングデバイスからデータを受信するように適合されたN/2個の入力ポートおよび上位のスイッチングデバイスにデータを送信するように適合されたN/2個の出力ポート、の間の直接接続性を阻止する等のために、3N2/4-N/2個の直接クロスポイントを含むようになっている。コンピュータ相互接続ネットワークは、好ましくはアップ/ダウンルーティングアルゴリズムに基づいた、コンピュータ相互接続ネットワークのためのコンピュータ化ルーティング方法を更に含み、コンピュータ相互接続ネットワークは更に、コンピュータ化ルーティング方法により決定される接続性の要求に従って少なくとも1つのスイッチングデバイスの直接クロスポイントが入力ポートを出力ポートのサブセットのみに直接接続することができるように構成されている。更に別の態様において、本発明は、本発明の実施形態に従ったコンピュータ相互接続ネットワークを提供することと、コンピュータ相互接続ネットワークの少なくとも1つのスイッチングデバイスのクロスポイントを介してデータをルーティングすることと、を含む、データをルーティングするためのコンピュータ実施方法として具現化される。実施形態においては、前記方法は以下の特徴の1つ以上を含むことができる。提供されたコンピュータ相互接続ネットワークは、本発明の一実施形態に従った少なくとも1つのスイッチングデバイスを含み、データをルーティングするステップは、直接クロスポイントによって接続されていない1対の入力ポートおよび出力ポートのためのデータパケットを受信したら、前記データパケットを、デバイスの追加のクロスポイントおよび回路の一部を介してルーティングすることを含む。提供されたコンピュータ相互接続ネットワークは、本発明の一実施形態に従った少なくとも1つのスイッチングデバイスを含み、データをルーティングするステップは、直接クロスポイントによって接続されていない1対の入力ポートおよび出力ポートのためのデータパケットを受信したら、データパケットが受信された入力ポートに接続された少なくとも1つの第1のセットのクロスポイントにパケットを送出し、回路を介して、データパケットが宛てられた出力ポートに接続された第2のセットのクロスポイントに前記パケットをループバックすることによって、前記データパケットをルーティングすることを含む。この方法は更に、提供するステップの前に、前記入力および出力ポートにおけるデータパケット到着の既知のまたは予想される強度によって前記接続性の要求を決定するステップを更に含み、提供するステップは、少なくとも1つのスイッチングデバイスを含むコンピュータ相互接続ネットワークを提供することを含み、スイッチングデバイスの直接クロスポイントは、コンピュータ相互接続ネットワークの決定した接続性の要求に従ってN個の入力ポートの各々と出力ポートのサブセットm<Mとの間のみの直接接続性を可能とするために構成されている。最後の態様によれば、本発明は、コンピュータ読み取り可能記憶媒体と、本発明の実施形態に従ったコンピュータ相互接続ネットワークの少なくとも1つのスイッチングデバイスのクロスポイントを介してデータをルーティングするためのプログラム命令と、を含み、前記プログラム命令が前記コンピュータ読み取り可能記憶媒体上に記憶されている、データをルーティングするためのコンピュータプログラムとして具現化される。これより、限定でない例により、添付図面を参照して、本発明を具現化するスイッチングデバイス、コンピュータ相互接続ネットワーク、およびルーティング方法について説明する。本発明は、低密度実装クロスバー構造に基づいて冗長性を低減するスイッチングデバイスを提案する。換言すると、スイッチのN個の入力ポートと出力ポートのサブセットm<Mとの間のみの直接接続性を可能とするためにクロスポイントを構成する。従って、前記クロスポイントの各々は、直接ポート対ポート接続性を可能とするので、直接クロスポイントと見なすことができる。簡略化のため、M=Nを用いるスクエアスイッチを想定する。しかしながら、以下で論じる概念の多くは、非スクエアスイッチに直接拡張することができる。後で詳細に論じるように、実施形態は、直接クロスポイント以外に追加のクロスポイントを提供し、これらは到達性reachabilityを犠牲にすることを回避するため等に配置される。しかしながら、クロスポイント数の削減はなお達成可能である。我々はここで、一般にスイッチは単独で用いるのでなく、あるトポロジーを形成するように接続された多くのかかるスイッチを含む大きなシステムの一部として用いることが意図されるという事実を利用し、そのトポロジーに従ってデータパケットをルーティングするために所与のルーティング方法を用いる。更に、所与のシステムにおいて生じるトラフィックパターン空間分布は、他のものよりも負荷がはるかに軽い接続を生じることができる。これらのファクターを考慮して、我々は、前もって決められていてもいなくても、ルーティングスキームまたはトラフィックの特徴あるいはその両方から得られた使用パターンに従って内部リソースを最適化することによってスイッチの複雑度を軽減することができる。換言すると、直接クロスポイントの不在の存在は、コンピュータ相互接続ネットワークの接続性の要求に依存する。本発明の重要な利点は、所与の次元Nのスイッチングノードを実施するために必要なクロスポイント数の削減である。低密度実装構造は基本的にデバイスの複雑度を軽減する。スイッチはバッファありまたはなしの場合があることに留意すべきである。前者の場合、バッファリング容量の使用を最適化することができる。この状況において、クロスポイントは、入力ポートを出力ポートに直接接続する包括的な手段として理解される。個別に考えると、本発明の実施形態において用いるようなクロスポイントは、例えば、既知のクロスバーベースのスイッチアーキテクチャにおいて設けられるようなN2個のクロスポイントの1つと本質的に同等である。全体的なクロスポイントの個数は、全体的なスイッチングノードのコストおよび複雑度を示す良好な指標であるので、クロスポイント数が減ると一般にそれに応じてコストが削減される。具体的な例として、バッファありのクロスバースイッチにおいては、関連付けられたバッファおよび制御論理を有するクロスポイントは、ゲートにおける全体の複雑度の大部分を占める。ここで更に詳細に述べると、データセンタまたは高性能コンピューティングHPCシステムにおける相互接続ネットワーク等のコンピュータ相互接続ネットワークは、何らかのトポロジーに相互接続された個別のパケットスイッチングノードから成る。一般的なトポロジーは、Closネットワーク、Benesネットワーク、ファットツリーk-aryn-trees、k-arynflies等の間接ネットワーク、およびトーラスネットワークk-aryncubes、メッシュ、ハイパーキューブ等の直接ネットワークを含む。所与のトポロジー上でいずれかのソースからいずれかの宛先への経路を決定するために、ルーティングアルゴリズムが必要である。経路は、ソースから宛先に達するために用いられるスイッチ間のリンクのシーケンスによって一意に決定される。多くの場合、ルーティングアルゴリズムは、特定の構造を有するか、または特定の制約を受ける。かかる制約の例は、最短経路のルートのみを取り得ること最小数のホップ、およびルートはデッドロックなしでなければならないことチャネル依存グラフにおけるサイクルなしとすることができる。図1は、ファットツリーマルチステージネットワーク100を示す。図に示すファットツリーは、3-ary3ツリーk=3基数、n=3レベル数である。これは特に、各スイッチがダウンに3つのポートおよびアップに3つのポートを有するので、最下位レベルで3つのノードをスイッチに接続可能であり、次のレベルで各スイッチを3つのスイッチに接続することを意味する。換言すると、ファットツリーは、この例では、N1からN27と標記する27のエンドノードをサポートすることができる。ネットワーク内の全ての接続は完全に双方向である。エンドノード例えばコンピューティングノードは、ネットワークの下部また、図の下部でポートI1,1,1からI1,9,3にアタッチし、アップのポートO1,1,1からO1,9,3はスイッチの別のレベルに接続してシステムをスケーリングし追加ノードをサポートする。更に一般的には、入力ポートIi,j,xx=1、2、...はノードSi,jのx番目の入力ポートを示し、Si,jはi番目のレイヤにおけるj番目のノードを示す。同様に、出力ポートOi,j,xはノードSi,jのx番目の出力ポートを示す。更に、所与のノードSi,jでは、ノードSi-1,jを下位レベルのスイッチングデバイスと呼び、ノードSi1,jを上位レベルのスイッチングデバイスと呼ぶコンピューティングノードに関して。コンピューティングノードのいくつかN2~N5、N7~N10、N12~N26は、明らかに明確さの理由で図示しない。しかしながら、他の配置/スイッチおよびコンピューティングノードの数を含む他のトポロジーも想定することができる。かかるファットツリートポロジーにおいては、いわゆるアップ/ダウンルーティングが適切なアルゴリズムであるようである。このルーティングアルゴリズムは、所与のソースsおよび宛先dについて、以下のように動作する。1.sおよびdの最も近い共通の祖先であるスイッチングノードここではncas、dと関数的に示すを見出す。多数の候補がある場合、所与のルールに従って1つを選択する。2.sからncas、dまでの一意の上昇経路上で上方向にルーティングする。3.ncas、dからdまでの一意の下降経路上で下方向にルーティングする。このアルゴリズムは、最短経路であると共にデッドロックが存在しないという特性を有する。例えば、図1は、ノードN1からノードN27までおよびノードN11からノードN27までの9個の可能な経路の1つ、ならびに、ノードN1からN6までの3つの可能な経路の1つを示す。スイッチングノードnca1,6は、ノードS2,2に対応し、例えばノードN1からN6の考えられる最も近い共通祖先の1つである。同様に、図1においてノードnca1,27およびnca11,27が示され、これらはそれぞれノードS3,1およびS3,2に対応する。より詳しく調べると、上述のルーティングアルゴリズムの結果、所与のスイッチングノードにおいて行うことができる方向転換の制限があることが認められる。具体的には、パケットがダウンするスイッチに入る時はいつでも、再びアップにルーティングすることはできない。しかしながら、従来技術のスイッチングノードは、入力および出力のいかなる組み合わせ間でも接続を可能とする方法で実施される。すなわちそれらは完全な接続性を与える。かかるスイッチングノードは、例えば、入力ラインを出力ラインに直接接続するクロスポイントの行列と考えることができる。図2に、クロスポイントの行列の一例を示す。直接クロスポイントCPx,yは、入力ポートIxを出力ポートOyに接続するインデクスi、jは簡潔さのため今後省略する。すなわち、入力ポートIxは図示したノードのx番目の入力ポートを示す。従って、完全な接続性を与えるスイッチングノードはN2個のクロスポイントを有するまたは非スクエアノードではNM個のクロスポイント。更に、各クロスポイントに関連した実際の実施の複雑度は、既知のように、特定のスイッチングノードアーキテクチャバッファなしのクロスバー、バッファありのクロスバー、共有メモリ等に依存する。所与のコンピュータ相互接続ネットワーク図1のネットワーク100等が、例えばルーティングアルゴリズムおよびトポロジーによって規定されたような禁止された方向転換を有する場合があることを考慮すると、次に、クロスポイントのいくつかを除去することを考えることができる。しかしながら、図1に示すようなネットワークおよびアップ/ダウンルーティングアルゴリズム以外に、他のネットワーク/ルーティングアルゴリズムにおいても禁止されたデータルートが生じ得ることは、当業者には認められよう。例えば、いくつかの特定のノードは、所与の第1のネットワークエンティティから所与の第2のネットワークエンティティへデータをルーティングすることを阻止される場合がある。かかる場合、先に概説したように、スイッチにおいて低密度実装のクロスポイント構造を好都合に実施することができる。例えば図3~図5のクロスポイント構造にこれを示す。この場合も、基礎にあるスイッチングデバイスはN個の入力ポートIxおよびM個の出力ポートOyを有する。これは、入力ポートの各々から出力ポートのいくつかアウトへ、直接クロスポイントCPx,yを介してデータパケットをルーティングインするように設計されている。図2~図5の例では、x=1、...、8であり、y=1、...、8である。更に、図3~図7の実施形態は、図1に示したような相互接続ネットワークのいずれかのノードSi,jに適用可能である。図3~図5の実施形態に示すように、保持されたクロスポイントCPx,yは、入力ポートと出力ポートのサブセットm<Mとの間のみの直接接続性を可能とする。これ以降、簡略化のためにスクエアスイッチM=Nを想定する。図3の具体的な例では、直接クロスポイントの数は正確にN2-Nに等しい。すなわち、直接クロスポイントCPx,y=xは除去されているまたはスイッチはクロスポイントCPx,y=xなしで構築されている。このため、このデバイスは、同一ポートx、すなわちこの場合は同一の双方向ポートに対応する入力ポートと出力ポートとの間の直接接続性を防ぐ。実際、N2が完全な接続性のために必要な直接クロスポイント数に対応する場合、Nは、同一ポートに対応する入出力ポートの全対間の直接接続性のために必要な直接クロスポイント数に対応する。このため、図3に示すクロスポイント構造は複雑度が低減している。更に一般的には、出力ポートの残りのサブセットm<Nは、ネットワークの接続性の要求に従って設計することができ、この結果、異なるレベルのノード複雑度が生じる。例えば、実際の直接クロスポイント数は、少なくとも入力ポートのサブセットすなわちN1の入力ポートと対応する数の出力ポートすなわち同一の双方向ポートに対応するとの間の直接接続性を防ぐため等のために、N2-N1N1≦N未満とすることができる。他の状況では、ネットワークエンティティの第1のサブセットからデータを受信するN1の入力ポートと、エンティティの第2のサブセットにデータを送信するN2の出力ポートとの間で、直接接続性を防ぎたい場合がある。従ってこの場合には、N2-N1N2のクロスポイントが提供される。コメントは以下の通りである。ネットワークエンティティの各サブセットは1つだけのノードから成る可能性がある。また、2つのサブセットが重複し、同一エンティティに対応する可能性がある。図4においては、特にN1×N2のクロスポイントを破棄し、ネットワークエンティティの第1および第2のサブセット間の直接接続性を防ぐ。更に正確には、この例においては、ここで考えるネットワークトポロジーの結果としてN1=N2=N/2を有する。すなわち、スイッチのアップ側に対応するN1の入来ポートは、スイッチのアップ側のN2の出立ポートに接続されない。更に、ネットワークの接続性の要求が、先に生じたような、どのポートもそれ自身に戻るようにルーティングされてはならないというものである場合、対角線上の全てのクロスポイントを更に省略することができる。かかる状況を図4に示し、ここからクロスポイントパターンを得る。図4の状況を一般化して得られる実施形態においては、N2-N1N2-N-MinN1、N2のクロスポイントが得られ、これはN1の入力ポートとN2の出力ポートとの間の直接接続性を防ぐことになり、一方で、どのポートもそれ自身に戻るようにルーティングすることはできない。N1=N2=N/2という特定の場合、以前の公式は3N2/4-N/2に変換される。このため、かかる実施形態では、直接クロスポイントの4分の1を概ね省略することができる大きいNの場合。次に、ポートIxとOyとの間の交点におけるクロスポイントを排除することは、IxがもはやOyに到達することができないことを意味するので、例えば間接的に接続性を復元させたい場合がある。このため、本発明のスイッチングデバイスは、実施形態において、デバイスの追加回路Lを介して入力ポートを間接的にスイッチの出力ポートに接続することを可能とするように構成された追加のクロスポイントを更に含むことができる。従って、直接クロスポイントによって接続されていない1対の入力ポートおよび出力ポートのためのデータパケットを受信する場合、図5に示すように、デバイスの追加のクロスポイントおよび回路Lを介して、このデータパケットをルーティングすることができる。概念上、かかる問題は結果的にクロスポイント行列構造の追加の行および列を接続することになり、いくつかの実際の実施形態を想定可能であることが認められる。しかしながら好都合なことに、図5に示すように、簡単な実施形態では、追加回路Lを介して接続された追加クロスポイントAPxLおよびAPLyの2つのセットを用いる。各追加クロスポイントAPxLは、すでに直接クロスポイントCPxyに接続されている入力ポートIxを回路Lに接続する。同様に、追加クロスポイントAPLyの第2のセットは、回路をデバイスの出力ポートOyに接続する。更に一般的には、1つ以上の完全実装された列および1つ以上の完全実装された行をスイッチング行列に追加することができる。しかしながら、これらの列および行は外部ポートに対応しない。すなわち、それらは内部使用のみのためのものである。これらの追加の行および列をバイパスと称する。全てのバイパス列は、回路Lを介してバイパス行の1つに接続されまたはその逆であり、これによって回路Lは内部ループバック経路を生成する。バイパスは、何個のまたはどのクロスポイントが排除されたかには無関係に、完全な到達性を復元させるため等のために配置することができる。図5は、1つのバイパスを有する8×8スイッチングノードの一例を示す。すなわち、バイパス列APxLは回路Lを介してバイパス行APLyに接続されている。ここでノードにおけるデータの操作を考える。パケットが未接続ポート対例えばI8およびO8に到達した場合はいつでも、このパケットはそのソースポートに対応する余分な列AP8,L上のクロスポイントにルーティングされ、そこから、回路Lを介してバイパスが接続されている余分な行APL,8にループバックされ、その宛先ポートに対応するクロスポイントに送出される。バイパスは、直接クロスポイントに直接接続されていない全てのポート対によって共有されることに留意すべきである。直接接続されたポート対からのパケットは、通常のように直接クロスポイントを介してルーティングされる。図5の例では、低密度のクロスバーバイパスを含むは、実際に3N2/4-N/22N個のクロスポイントこの中に2Nの追加クロスポイントがあるを有し、これに対して完全接続クロスバーではN2個である。低密度のクロスバーは、6より大きいあらゆるNについて複雑度が低くなることがわかる。例えばN=32では、クロスポイントの約80のみを保持する必要があるだけである。Nが大きくなると、完全接続性に対して、クロスポイントの~75に漸近的に近付くことができる。次に、実施形態において、バイパスは以下のように機能することができる。パケットがスイッチ入力に到達すると、入力インタフェースは、このパケットの宛先が実装クロスポイントであるか否かをチェックする。イエスの場合、パケットはすぐに宛先クロスポイントにルーティングされる。そうでなければ、パケットはその宛先列に直接ルーティングすることができず、従ってバイパスを介してルーティングしなければならない。入力インタフェースは、利用可能なバイパスから1つを選択し、パケットを対応するクロスポイントAPx,Lにルーティングする。好ましくは、各バイパス列はそれ自身のスケジューラを有する。バイパススケジューラは、その列からパケットを選択し、これをそのループバックを介して対応するバイパス行APL,yに、更にパケットの宛先ポートに対応する特定のクロスポイントにルーティングする。全ての出力スケジューラは、その列におけるバイパスクロスポイントからのパケットおよび正規のクロスポイントをスケジュールする。多くのスケジューリング規則を想定することができる。更に、特記事項として、バイパスがどれも利用可能でない場合、パケットはドロップしなければならない場合があることに留意すべきである例えばバッファありのクロスバーの場合。前述のように、バイパスは主として完全接続性を可能とするために、すなわち全ポートを全ての他のポートに到達可能とするために、実施される。それらは、厳密な性能要求を有する接続には適さない場合があることがわかる。上述したようなバイパスは、典型的に2つの性能上の欠点を有する。第1に、レイテンシの不利益がある。なぜなら、バイパスを通る全てのパケットは、バッファありのクロスバーにおいてスイッチから出る前に2度記憶され読み取られるからである。第2に、バイパスを用いるフローは全て、限定されたクロスポイントセットを共有し、限定された内部帯域幅のみを利用するが、これは設計上、アタッチされたポートにおいて可能な最大全スループットよりもはるかに小さい。例えば図5において、アップ側の入力からアップ側の出力までのフローの全トラフィックの最大全スループットは、単一のループバック経路の帯域幅に限定されるので、最悪の場合、影響を受けるフローのスループットはわずか25であるすなわち全ての入力が100負荷で実装されていないクロスポイントに送信する場合。しかしながら、この限定は、更にバイパスを追加することによって改善することができる。更に記載するように、クロスポイント排除パターンは、図5に示すように規則的である必要はない。低密度は、コンピュータ相互接続ネットワークの接続性要求に従って、いかなる形状も取ることができ、対称例えば図6の例示的な実施形態を参照のことまたは非対称図7も可能である。更に、バイパスの行および列は、図示したパターンから著しく変動する可能性がある。特に、厳密に言えば、全ての列/行に接続された行xまたは列yについてバイパスクロスポイントAPx,L/APL,yを追加する必要はないことに留意すべきである。また、1つのみの直接クロスポイントを除去する場合特定の接続性の要求のため、対応するバイパスに必要な2つのクロスポイントを追加するよりも、これを維持することが好ましい場合が実際ある。従って、図5~図7に対応する変形例を想定することができる。この手法は、いかなるトポロジーおよびいかなるルーティングスキームにも簡単に一般化することができる。それらが与えられると、いかなるスイッチについても、どの方向転換を行わないかを決定すること、これに応じてクロスポイントを排除することは簡単である。更に、バイパスの容量は、多数の余分な行および列図示せずを追加することによって大きくすることができる。厳密に言うと、いくつかの方向転換を行わない場合、それらの方向転換のためのバイパスは必要ないことに留意すべきである。それにもかかわらず、これを実施することが試験/診断の目的のために有用である場合がある。更に、この手法は、予想される空間トラフィック分布の特徴を考慮に入れるように一般化することができる。パケットスイッチングのいくつかの用途では、スイッチングノードにおいて観察されるトラフィックパターンは極めて非均一である場合がある。これが意味するのは、所与の入力ポートを介して入ってくるトラフィックは出力ポートセット上での分布が等しくないこと、または異なる入力ポートを介して入ってくるトラフィックは異なる分布パターンを示すこと、あるいはその両方である。所与のスイッチでは、極めて少ないトラフィックのみが予想される全ての接続を共有バイパスにマッピングすることができる。例えば、HPCアプリケーションは多くの場合、極めて独特の通信パターンを示し、例えば、ほとんどの通信が隣接ネイバーの間で行われる。この点において、本発明に従った方法は、実施形態において、例えばスイッチポートにおけるデータパケット到着の予想強度に基づいて、ネットワークの接続性要求を決定する初期ステップを含む。次いで、決定した接続性要求に従って、スイッチ構成を最適化することを可能とするすなわちネットワークにおいて用いる1つ以上のスイッチのための最適化クロスポイント構造、およびおそらく、ネットワーク内でどのようにかかるスイッチを配置可能であるか。当業者によって認められるように、本発明の態様は、ネットワーク、方法、またはコンピュータプログラムとして具現化することができる。従って、本発明の態様は、全体的にハードウェアの実施形態、全体的にソフトウェアの実施形態ファームウェア、常駐ソフトウェア、マイクロコード等を含む、または、ソフトウェアおよびハードウェアの態様を組み合わせた実施形態という形態を取ることができ、それらは全て本明細書において、回路、モジュール、またはシステムと一般的に称することができる。更に、本発明の態様は、具現化されたコンピュータ読み取り可能プログラムコードを有する1つ以上のコンピュータ読み取り可能媒体複数の媒体において具現化されたコンピュータプログラムの形態を取ることも可能である。1つ以上のコンピュータ読み取り可能媒体複数の媒体のあらゆる組み合わせを利用することができる。コンピュータ読み取り可能媒体は、コンピュータ読み取り可能信号媒体またはコンピュータ読み取り可能記憶媒体とすることができる。コンピュータ読み取り可能記憶媒体は例えば、限定ではないが、電子、磁気、光、電磁、赤外線、または半導体のシステム、装置、デバイス、または前述のもののいずれかの適切な組み合わせとすることができる。コンピュータ読み取り可能記憶媒体の更に具体的な例非網羅的な列挙は、以下を含む。すなわち、1本以上のワイヤを含む電気的接続、携帯型コンピュータディスケット、ハードディスク、ランダムアクセスメモリRAM、読み取り専用メモリROM、消去可能プログラマブル読み取り専用メモリEPROMまたはフラッシュメモリ、光ファイバ、携帯型コンパクトディスク読み取り専用メモリCD-ROM、光記憶デバイス、磁気記憶デバイス、または前述のもののいずれかの適切な組み合わせである。この文書の文脈において、コンピュータ読み取り可能記憶媒体は、命令実行システム、装置、またはデバイスによってまたはそれと接続して用いるためにプログラムを含有または記憶することが可能ないずれかのタンジブルな媒体とすることができる。コンピュータ読み取り可能信号媒体は、例えばベースバンドにおいてまたは搬送波の一部として、具現化されたコンピュータ読み取り可能プログラムコードを有する伝播データ信号を含むことができる。かかる伝播信号は様々な形態のいずれかを取ることができ、それらは限定ではないが、電磁、光、またはそれらのいずれかの適切な組み合わせを含む。コンピュータ読み取り可能信号媒体は、コンピュータ読み取り可能記憶媒体でないが、命令実行システム、装置、またはデバイスによってまたはそれと接続して用いるためにプログラムを伝達、伝播、または転送することが可能ないずれかのコンピュータ読み取り可能媒体とすることができる。コンピュータ読み取り可能媒体上で具現化されるプログラムコードは、限定ではないが、無線、有線、光ファイバケーブル、RF等、または前述のもののいずれかの適切な組み合わせを含むいずれかの適切な媒体を用いて伝送することができる。本発明の態様の動作を実行するためのコンピュータプログラムコードは、Java、Smalltalk、C等のオブジェクト指向プログラミング言語、およびCプログラミング言語または同様のプログラミング言語等の従来の手順プログラミング言語を含む1つ以上のプログラミング言語のいずれかの組み合わせにおいて記述することができる。プログラムコードは、例えば特にイーサネットネットワークについてエンドノードまたは最下位レベルスイッチS1,jの1つ以上で全体的に実行することができると好都合である。さもなければ、これは、部分的にエンドノードまたは最下位レベルスイッチ上で、および部分的に遠隔ノードまたはスイッチ例えばもっと高いレベルのスイッチ上で、またはアーキテクチャが可能とする場合には全体的に1つ以上のもっと高いレベルのスイッチ上で、実行することができる。異なるタイプのネットワークを想定することができる。既知のように、かかるスイッチは、ネットワークの機能性とは別に、単にコンピュータと見なすことができる。この点で、各スイッチはハードウェアにおいて実施することができる。しかしながら、これは、汎用コンピュータの1つ以上のプロセッサにより実行されるプログラムとして実施することができる。汎用コンピュータおよびプロセッサはそれ自体、既知である。本発明の態様のいずれの動作も、例えば相互接続ネットワークのスイッチングデバイスのクロスポイントを介してデータをルーティングするためのプログラム命令のようなコンピュータプログラム命令によって実施可能であることは理解されよう。かかる命令は、例えば、汎用コンピュータ、ノード、またはスイッチ、特殊目的スイッチ、または他のプログラマブルデータ処理装置のプロセッサに提供されて機械を生成することができ、これによって、スイッチまたは他のプログラマブルデータ処理装置のプロセッサによって実行される命令が、先に規定された機能/行為を実施するための手段を生成するようになっている。また、これらのコンピュータプログラム命令はコンピュータ読み取り可能媒体に記憶することができ、これによって、スイッチ、コンピュータ、他のプログラマブルデータ処理装置、または他のデバイスに特定の方法で機能するように指示することができ、これにより、コンピュータ読み取り可能媒体に記憶された命令が、フローチャートまたはブロック図あるいはその両方のブロックまたは複数のブロックに規定された機能/行為を実施する命令を含む製造品を生成するようになっている。また、コンピュータプログラム命令を、コンピュータ、他のプログラマブルデータ処理装置、または他のデバイスにロードして、そのコンピュータ、他のプログラマブル装置、または他のデバイス上で一連の動作ステップを実行させてコンピュータ実施プロセスを生成することができ、これによって、コンピュータまたは他のプログラマブル装置上で実行する命令が、規定された機能/行為を実施するためのプロセスを提供するようになっている。本発明について、いくつかの実施形態を参照して記載したが、本発明の範囲から逸脱することなく様々な変更を実施可能であり均等物を置換することが可能であることは、当業者には理解されよう。更に、本発明の範囲から逸脱することなく、多くの変形を実施して、特定の状況または材料を本発明の教示に適合させることも可能である。従って、本発明は開示した特定の実施形態に限定されるのではなく、本発明は添付の特許請求の範囲内に該当する全ての実施形態を含むことが意図される。例えば、ほとんどの通信が隣接ネイバー間で行われる場合、第1のネイバーにのみ対応するポート間で直接接続性を可能とするために直接クロスポイントを構成することができる。更に、本出願は本質的に例示のため双方向ポート従ってスクエアスイッチを想定するが、不平衡の入力ポート対出力ポートを有する非スクエアスイッチに対する適用も想定することができる。例えば、スイッチの少なくともいくつかがN個の入力ポートおよびM個の出力ポートを含むことができるN≠M。かかるデバイスは、コンピュータ相互接続ネットワークの接続性の要求に従って、N個の入力ポートの各々と出力ポートのサブセットm<Mとの間のみの直接接続性を可能とするために構成した直接クロスポイントによってデータパケットをルーティングするために適合させることができる。同様に、デバイスは、実施形態等において前述したように、N2-N1N1≦Nでなく、NM-N1N1≦Min[N,M]以下の数の直接クロスポイントを含むことができる。"