(57)【特許請求の範囲】
【請求項１】
Ｎ個の入力ポート（Ｉａ−Ｉｈ）およびＭ個の出力ポート（Ｏａ−Ｏｈ）を有する、コンピュータ相互接続ネットワーク（１００）の部分を接続するように適合されたスイッチング・デバイス（Ｓｉ，ｊ）において、前記デバイスが、直接クロスポイント（ＣＰｘ，ｙ）によってデータ・パケットをルーティングするために適合され、前記直接クロスポイントが、前記コンピュータ相互接続ネットワークの接続性の要求に従って、前記Ｎ個の入力ポートの各々と前記出力ポートのサブセットｍ＜Ｍとの間のみの直接接続性を可能とするために構成され、
ＮＭ−Ｎ１（Ｎ１≦Ｍｉｎ［Ｎ，Ｍ］）以下の数の直接クロスポイントを含み、これによって前記デバイスが、同一のポートに対応する少なくともＮ１個の入力ポートおよびＮ１個の出力ポートのサブセット間の直接接続性を阻止し、
Ｎ１＜Ｎであって、１つ以上の第１のネットワーク・エンティティからデータを受信するように適合された、Ｎ１個の入力ポートと、
Ｎ２＜Ｍであって、１つ以上の第２のネットワーク・エンティティにデータを送信するように適合された、Ｎ２個の出力ポートと、
を含み、前記直接クロスポイントの数がＮＭ−Ｎ１Ｎ２以下であって、
Ｍ＝Ｎであり、前記直接クロスポイントの数がＮ２−Ｎ１Ｎ２−（Ｎ−Ｍｉｎ（Ｎ１、Ｎ２））である、スイッチング・デバイス。
【請求項２】
追加回路（Ｌ）および追加クロスポイント（ＡＰｘ，Ｌ、ＡＰＬ，ｙ）を更に含み、前記追加回路および前記追加クロスポイントが、前記スイッチング・デバイスの前記入力ポートの少なくともいくつかが前記追加回路を介して前記スイッチング・デバイスの前記出力ポートの少なくともいくつかに間接的に接続可能となるように構成されている、請求項１に記載のスイッチング・デバイス。
【請求項３】
前記追加クロスポイントが、
−各々が、１つ以上の直接クロスポイント（ＣＰｘ，ｙ）にすでに接続されている前記デバイスの入力ポート（Ｉｘ）を前記回路（Ｌ）に接続する、少なくとも１つの第１のクロスポイント（ＡＰｘ，Ｌ）のセットと、
−各々が、前記回路を、１つ以上の直接クロスポイント（ＣＰｘ，ｙ）にすでに接続されている前記デバイスの出力ポート（Ｏｙ）に接続する、少なくとも１つの第２のクロスポイント（ＡＰＬ，ｙ）のセットと、
を含む、請求項２に記載のスイッチング・デバイス。
【請求項４】
請求項１から３のいずれか１項に記載の少なくとも１つのスイッチング・デバイス（Ｓｉ，ｊ）を含むコンピュータ相互接続ネットワーク（１００）。
【請求項５】
Ｎ個の入力ポート（Ｉａ−Ｉｈ）およびＭ個の出力ポート（Ｏａ−Ｏｈ）を有する、コンピュータ相互接続ネットワーク（１００）の部分を接続するように適合されたスイッチング・デバイス（Ｓｉ，ｊ）を備え、前記デバイスが、直接クロスポイント（ＣＰｘ，ｙ）によってデータ・パケットをルーティングするために適合され、前記直接クロスポイントが、前記コンピュータ相互接続ネットワークの接続性の要求に従って、前記Ｎ個の入力ポートの各々と前記出力ポートのサブセットｍ＜Ｍとの間のみの直接接続性を可能とするために構成され、
前記コンピュータ相互接続ネットワークの前記少なくとも１つのスイッチング・デバイスのクロスポイント（ＣＰｘ，ｙ）を介してデータをルーティングし、
ＮＭ−Ｎ１（Ｎ１≦Ｍｉｎ［Ｎ，Ｍ］）以下の数の直接クロスポイントを含み、これによって前記デバイスが、同一のポートに対応する少なくともＮ１個の入力ポートおよびＮ１個の出力ポートのサブセット間の直接接続性を阻止し、
Ｎ１＜Ｎであって、１つ以上の第１のネットワーク・エンティティからデータを受信するように適合された、Ｎ１個の入力ポートとし、
Ｎ２＜Ｍであって、１つ以上の第２のネットワーク・エンティティにデータを送信するように適合された、Ｎ２個の出力ポートとし、
を含み、前記直接クロスポイントの数がＮＭ−Ｎ１Ｎ２以下であって、
Ｍ＝Ｎであり、前記直接クロスポイントの数がＮ２−Ｎ１Ｎ２−（Ｎ−Ｍｉｎ（Ｎ１、Ｎ２））とする、コンピュータが実行する方法。
【請求項６】
前記コンピュータ相互接続ネットワークが更に、前記ルーティングにより決定される接続性の要求に従って前記少なくとも１つのスイッチング・デバイス（Ｓｉ，ｊ）の前記直接クロスポイント（ＣＰｘ，ｙ）が前記入力ポート（Ｉｘ）を前記出力ポート（Ｏｙ）のサブセットのみに直接接続することができるように構成されている、請求項５に記載の方法。
【請求項７】
前記提供されたコンピュータ相互接続ネットワークが、請求項１に記載の少なくとも１つのスイッチング・デバイス（Ｓｉ，ｊ）を含み、前記データをルーティングすることが、
−直接クロスポイントによって接続されていない１対の入力ポート（Ｉ８）および出力ポート（Ｏ８）のためのデータ・パケットを受信したら、前記データ・パケットを、前記デバイスの前記追加のクロスポイント（ＡＰ８，Ｌ、ＡＰＬ，８）および回路（Ｌ）の一
部を介してルーティングすることを含む、請求項５または６に記載の方法。
【請求項８】
前記提供されたコンピュータ相互接続ネットワークが、請求項６に記載の少なくとも１つのスイッチング・デバイスを含み、前記データをルーティングすることが、
−直接クロスポイントによって接続されていない１対の入力ポート（Ｉ８）および出力ポート（Ｏ８）のためのデータ・パケットを受信したら、
−前記データ・パケットが受信された前記入力ポート（Ｉ８）に接続された、前記少なくとも１つの第１のセットのクロスポイント（ＡＰ８，Ｌ）に前記パケットを送出し、
−前記回路（Ｌ）を介して、前記データ・パケットが宛てられた出力ポート（Ｏ８）に接続された、前記第２のセットのクロスポイント（ＡＰＬ，８）に前記パケットをループ・バックする、
ことによって、前記データ・パケットをルーティングすることを含む、請求項５〜７のいずれか１項に記載の方法。
【請求項９】
コンピュータ・プログラムであって、コンピュータに、
請求項５〜８のいずれか１項に記載の方法をコンピュータが実行するためのコンピュータ実行可能な、プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ相互接続ネットワークにおいてデータをルーティングするための方法およびシステムの分野に関する。具体的には、本発明は、データ・パケットを入力ポートから出力ポートへとルーティングするための最適化回路を有するスイッチング・デバイスに関する。
【背景技術】
【０００２】
シングル・ステージのパケット・スイッチング・ノード等のスイッチング・デバイスが知られている。かかるノードは、所与で固有の実施の複雑度を有する。すなわち、Ｎポートのパケット・スイッチにおいては、二次の複雑度を生じるＮ対Ｎの接続の問題がある。多くの異なるスイッチ・アーキテクチャがある（例えば入力キュー、出力キュー、組み合わせ入力および出力キュー、共有メモリ等）が、この複雑度はこれらのアーキテクチャの全てにおいて何らかの点で現れる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
この複雑度は本質的に、いかなる１対１通信パターン（順列）も衝突なしでルーティング可能とすることを要求するノンブロッキング要求から生じる。複雑度の軽減を可能とするには、この要求を緩和する、すなわち、異なるポートとの通信間でも衝突の発生を許容するしかない。これは、通常バス等の共有媒体またはマルチ・ステージ構成に基づくスイッチ・アーキテクチャのブロッキングを招く。かかる手法の欠点は、例えばバス・ベースの実施の物理的な制限によって達成可能な全スループットが限られていることである。
【０００４】
ほとんどの既存のシングル・ステージのスイッチング・ノード実施は、ノンブロッキング要求を満足させる。すなわち、それらは、あらゆる入力ポートからあらゆる出力ポートへと全容量で送信する機能を提供する。クロスバー・ベースのアーキテクチャ（これはバッファありの場合もバッファなしの場合もある）の特定の場合、これは、スイッチング・ノードがＮ２のクロスポイントを含むことを意味する。更に、バッファありのクロスバー・アーキテクチャの場合、各クロスポイントが含むバッファは、全往復を通して全リンク利用を可能とするような大きさである。多くの場合、このバッファリング容量の多くは概ね未使用のままであり、これが貴重なリソースの無駄となることが認められている。
【課題を解決するための手段】
【０００５】
第１の態様によれば、本発明は、Ｎ個の入力ポートおよびＭ個の出力ポートを有する、コンピュータ相互接続ネットワークの部分を接続するように適合されたスイッチング・デバイスとして具現化される。Ｍは、好ましくはＮに等しい。このデバイスは、直接クロスポイントによってデータ・パケットをルーティングするために適合され、直接クロスポイントは、コンピュータ相互接続ネットワークの接続性の要求に従って、Ｎ個の入力ポートの各々と出力ポートのサブセットｍ＜Ｍとの間のみの直接接続性を可能とするために構成されている。
【０００６】
実施形態において、前記デバイスは以下の特徴の１つ以上を含むことができる。
【０００７】
スイッチング・デバイスは、ＮＭ−Ｎ１（Ｎ１≦Ｍｉｎ〔Ｎ，Ｍ〕）以下の数の直接クロスポイントを含み、これによってデバイスは、同一のポートに対応する少なくともＮ１個の入力ポートおよびＮ１個の出力ポートのサブセット間の直接接続性を阻止する。
【０００８】
スイッチング・デバイスは、
Ｎ１＜Ｎであって、１つ以上の第１のネットワーク・エンティティからデータを受信するように適合された、Ｎ１個の入力ポートと、
Ｎ２＜Ｍであって、１つ以上の第２のネットワーク・エンティティにデータを送信するように適合された、Ｎ２個の出力ポートと、
を含み、直接クロスポイントの数がＮＭ−Ｎ１Ｎ２以下である。
【０００９】
Ｍ＝Ｎであり、直接クロスポイントの数がＮ２−Ｎ１Ｎ２−（Ｎ−Ｍｉｎ（Ｎ１、Ｎ２））であり、好ましくはＮ１＝Ｎ２＝Ｎ／２である。
【００１０】
スイッチング・デバイスは追加回路および追加クロスポイントを更に含み、この追加回路および追加クロスポイントは、スイッチング・デバイスの入力ポートの少なくともいくつかが追加回路を介してスイッチング・デバイスの出力ポートの少なくともいくつかに間接的に接続可能となるように構成されている。
【００１１】
追加クロスポイントは、
各々が、１つ以上の直接クロスポイントにすでに接続されているデバイスの入力ポートを回路に接続する、少なくとも１つの第１のクロスポイントのセットと、
各々が、回路を、１つ以上の直接クロスポイントにすでに接続されているデバイスの出力ポートに接続する、少なくとも１つの第２のクロスポイントのセットと、
を含む。
【００１２】
第２の態様によれば、本発明は更に、本発明の実施形態による少なくとも１つのスイッチング・デバイスを含むコンピュータ相互接続ネットワークとして具現化される。
【００１３】
実施形態において、前記ネットワークは以下の特徴の１つ以上を含む。
【００１４】
コンピュータ相互接続ネットワークは、本発明の実施形態に従った少なくとも１つのスイッチング・デバイスを含み、更に、１つ以上の第１のネットワーク・エンティティおよび１つ以上の第２のネットワーク・エンティティを含む。
【００１５】
コンピュータ相互接続ネットワークは、本発明の一実施形態に従った少なくとも１つのスイッチング・デバイスを含み、
１つ以上の第１のネットワーク・エンティティが各々、コンピュータ相互接続ネットワークにおける下位のスイッチング・デバイスであり、
１つ以上の第２のネットワーク・エンティティが各々、コンピュータ相互接続ネットワークにおける上位のスイッチング・デバイスであり、
Ｍ＝Ｎであり、かつＮ１＝Ｎ２＝Ｎ／２であり、少なくとも１つのスイッチング・デバイスが、
デバイスの同一のポートに対応する入力ポートおよび出力ポート、
上位のスイッチング・デバイスからデータを受信するように適合されたＮ／２個の入力ポートおよび上位のスイッチング・デバイスにデータを送信するように適合されたＮ／２個の出力ポート、
の間の直接接続性を阻止する等のために、３Ｎ２／４−Ｎ／２個の直接クロスポイントを含むようになっている。
【００１６】
コンピュータ相互接続ネットワークは、好ましくはアップ＊／ダウン＊・ルーティング・アルゴリズムに基づいた、コンピュータ相互接続ネットワークのためのコンピュータ化ルーティング方法を更に含み、コンピュータ相互接続ネットワークは更に、コンピュータ化ルーティング方法により決定される接続性の要求に従って少なくとも１つのスイッチング・デバイスの直接クロスポイントが入力ポートを出力ポートのサブセットのみに直接接続することができるように構成されている。
【００１７】
更に別の態様において、本発明は、本発明の実施形態に従ったコンピュータ相互接続ネットワークを提供することと、コンピュータ相互接続ネットワークの少なくとも１つのスイッチング・デバイスのクロスポイントを介してデータをルーティングすることと、を含む、データをルーティングするためのコンピュータ実施方法として具現化される。
【００１８】
実施形態においては、前記方法は以下の特徴の１つ以上を含むことができる。
【００１９】
提供されたコンピュータ相互接続ネットワークは、本発明の一実施形態に従った少なくとも１つのスイッチング・デバイスを含み、データをルーティングするステップは、直接クロスポイントによって接続されていない１対の入力ポートおよび出力ポートのためのデータ・パケットを受信したら、前記データ・パケットを、デバイスの追加のクロスポイントおよび回路の一部を介してルーティングすることを含む。
【００２０】
提供されたコンピュータ相互接続ネットワークは、本発明の一実施形態に従った少なくとも１つのスイッチング・デバイスを含み、データをルーティングするステップは、直接クロスポイントによって接続されていない１対の入力ポートおよび出力ポートのためのデータ・パケットを受信したら、データ・パケットが受信された入力ポートに接続された少なくとも１つの第１のセットのクロスポイントにパケットを送出し、回路を介して、データ・パケットが宛てられた出力ポートに接続された第２のセットのクロスポイントに前記パケットをループ・バックすることによって、前記データ・パケットをルーティングすることを含む。
【００２１】
この方法は更に、提供するステップの前に、前記入力および出力ポートにおけるデータ・パケット到着の既知のまたは予想される強度によって前記接続性の要求を決定するステップを更に含み、提供するステップは、少なくとも１つのスイッチング・デバイスを含むコンピュータ相互接続ネットワークを提供することを含み、スイッチング・デバイスの直接クロスポイントは、コンピュータ相互接続ネットワークの決定した接続性の要求に従ってＮ個の入力ポートの各々と出力ポートのサブセットｍ＜Ｍとの間のみの直接接続性を可能とするために構成されている。
【００２２】
最後の態様によれば、本発明は、コンピュータ読み取り可能記憶媒体と、本発明の実施形態に従ったコンピュータ相互接続ネットワークの少なくとも１つのスイッチング・デバイスのクロスポイントを介してデータをルーティングするためのプログラム命令と、を含み、前記プログラム命令が前記コンピュータ読み取り可能記憶媒体上に記憶されている、データをルーティングするためのコンピュータ・プログラムとして具現化される。
【００２３】
これより、限定でない例により、添付図面を参照して、本発明を具現化するスイッチング・デバイス、コンピュータ相互接続ネットワーク、およびルーティング方法について説明する。
【図面の簡単な説明】
【００２４】
【図１】コンピュータ相互接続ネットワークを概略的に示す。
【図２】Ｎ２個のクロスポイントを有し、従来技術から既知の、クロスバー・ベースのアーキテクチャを有するスイッチング・デバイスを概略的に示す。
【図３】本発明の実施形態に従った、低密度実装クロスバー構造として表されるスイッチング・デバイスを示す。１つ以上のかかるデバイスは、例えば図１に示すようなコンピュータ相互接続ネットワークにおいて構成可能である。
【図４】本発明の実施形態に従った、低密度実装クロスバー構造として表されるスイッチング・デバイスを示す。１つ以上のかかるデバイスは、例えば図１に示すようなコンピュータ相互接続ネットワークにおいて構成可能である。
【図５】本発明の実施形態に従った、低密度実装クロスバー構造として表されるスイッチング・デバイスを示す。１つ以上のかかるデバイスは、例えば図１に示すようなコンピュータ相互接続ネットワークにおいて構成可能である。
【図６】本発明の実施形態に従った、低密度実装クロスバー構造として表されるスイッチング・デバイスを示す。１つ以上のかかるデバイスは、例えば図１に示すようなコンピュータ相互接続ネットワークにおいて構成可能である。
【図７】本発明の実施形態に従った、低密度実装クロスバー構造として表されるスイッチング・デバイスを示す。１つ以上のかかるデバイスは、例えば図１に示すようなコンピュータ相互接続ネットワークにおいて構成可能である。
【発明を実施するための形態】
【００２５】
本発明は、低密度実装クロスバー構造に基づいて冗長性を低減するスイッチング・デバイスを提案する。換言すると、スイッチのＮ個の入力ポートと出力ポートのサブセットｍ＜Ｍとの間のみの直接接続性を可能とするためにクロスポイントを構成する。従って、前記クロスポイントの各々は、直接ポート対ポート接続性を可能とするので、直接クロスポイントと見なすことができる。簡略化のため、Ｍ＝Ｎを用いる（スクエア・スイッチを想定する）。しかしながら、以下で論じる概念の多くは、非スクエア・スイッチに直接拡張することができる。
【００２６】
後で詳細に論じるように、実施形態は、直接クロスポイント以外に追加のクロスポイントを提供し、これらは到達性（ｒｅａｃｈａｂｉｌｉｔｙ）を犠牲にすることを回避するため等に配置される。しかしながら、クロスポイント数の削減はなお達成可能である。
【００２７】
我々はここで、一般にスイッチは単独で用いるのでなく、あるトポロジーを形成するように接続された多くのかかるスイッチを含む大きなシステムの一部として用いることが意図されるという事実を利用し、そのトポロジーに従ってデータ・パケットをルーティングするために所与のルーティング方法を用いる。更に、所与のシステムにおいて生じるトラフィック・パターン（空間分布）は、他のものよりも負荷がはるかに軽い接続を生じることができる。
【００２８】
これらのファクターを考慮して、我々は、前もって決められていてもいなくても、ルーティング・スキームまたはトラフィックの特徴あるいはその両方から得られた使用パターンに従って内部リソースを最適化することによってスイッチの複雑度を軽減することができる。換言すると、直接クロスポイントの不在の存在は、コンピュータ相互接続ネットワークの接続性の要求に依存する。
【００２９】
本発明の重要な利点は、所与の次元Ｎのスイッチング・ノードを実施するために必要なクロスポイント数の削減である。低密度実装構造は基本的にデバイスの複雑度を軽減する。スイッチはバッファありまたはなしの場合があることに留意すべきである。前者の場合、バッファリング容量の使用を最適化することができる。
【００３０】
この状況において、クロスポイントは、入力ポートを出力ポートに（直接）接続する包括的な手段として理解される。個別に考えると、本発明の実施形態において用いるようなクロスポイントは、例えば、既知のクロスバー・ベースのスイッチ・アーキテクチャにおいて設けられるようなＮ２個のクロスポイントの１つと本質的に同等である。全体的なクロスポイントの個数は、全体的なスイッチング・ノードのコストおよび複雑度を示す良好な指標であるので、クロスポイント数が減ると一般にそれに応じてコストが削減される。具体的な例として、バッファありのクロスバー・スイッチにおいては、関連付けられたバッファおよび制御論理を有するクロスポイントは、（ゲートにおける）全体の複雑度の大部分を占める。
【００３１】
ここで更に詳細に述べると、データ・センタまたは高性能コンピューティング（ＨＰＣ）・システムにおける相互接続ネットワーク等のコンピュータ相互接続ネットワークは、何らかのトポロジーに相互接続された個別のパケット・スイッチング・ノードから成る。一般的なトポロジーは、Ｃｌｏｓネットワーク、Ｂｅｎｅｓネットワーク、ファット・ツリー（ｋ−ａｒｙ  ｎ−ｔｒｅｅｓ）、ｋ−ａｒｙ  ｎ  ｆｌｉｅｓ等の間接ネットワーク、およびトーラス・ネットワーク（ｋ−ａｒｙ  ｎ  ｃｕｂｅｓ）、メッシュ、ハイパーキューブ等の直接ネットワークを含む。
【００３２】
所与のトポロジー上でいずれかのソースからいずれかの宛先への経路を決定するために、ルーティング・アルゴリズムが必要である。経路は、ソースから宛先に達するために用いられるスイッチ間のリンクのシーケンスによって一意に決定される。多くの場合、ルーティング・アルゴリズムは、特定の構造を有するか、または特定の制約を受ける。かかる制約の例は、最短経路のルートのみを取り得ること（最小数のホップ）、およびルートはデッドロックなしでなければならないこと（チャネル依存グラフにおけるサイクルなし）とすることができる。
【００３３】
図１は、ファット・ツリー・マルチ・ステージ・ネットワーク１００を示す。図に示すファット・ツリーは、３−ａｒｙ３ツリー（ｋ＝３（基数）、ｎ＝３（レベル数））である。これは特に、各スイッチがダウンに３つのポートおよびアップに３つのポートを有するので、最下位レベルで３つのノードをスイッチに接続可能であり、次のレベルで各スイッチを３つのスイッチに接続することを意味する。換言すると、ファット・ツリーは、この例では、Ｎ１からＮ２７と標記する２７のエンド・ノードをサポートすることができる。ネットワーク内の全ての接続は完全に双方向である。エンド・ノード（例えばコンピューティング・ノード）は、ネットワークの下部（また、図の下部）でポートＩ１，１，１からＩ１，９，３にアタッチし、アップのポート（Ｏ１，１，１からＯ１，９，３）はスイッチの別のレベルに接続してシステムをスケーリングし追加ノードをサポートする。更に一般的には、入力ポートＩｉ，ｊ，ｘ（ｘ＝１、２、．．．）はノードＳｉ，ｊのｘ番目の入力ポートを示し、Ｓｉ，ｊはｉ番目のレイヤにおけるｊ番目のノードを示す。同様に、出力ポートＯｉ，ｊ，ｘはノードＳｉ，ｊのｘ番目の出力ポートを示す。更に、所与のノードＳｉ，ｊでは、ノードＳｉ−１，ｊを下位レベルのスイッチング・デバイスと呼び、ノードＳｉ＋１，ｊを上位レベルのスイッチング・デバイスと呼ぶ（コンピューティング・ノードに関して）。コンピューティング・ノードのいくつか（Ｎ２〜Ｎ５、Ｎ７〜Ｎ１０、Ｎ１２〜Ｎ２６）は、明らかに明確さの理由で図示しない。しかしながら、他の配置／スイッチおよびコンピューティング・ノードの数を含む他のトポロジーも想定することができる。
【００３４】
かかるファット・ツリー・トポロジーにおいては、いわゆるアップ＊／ダウン＊ルーティングが適切なアルゴリズムであるようである。このルーティング・アルゴリズムは、所与のソースｓおよび宛先ｄについて、以下のように動作する。
【００３５】
１．  ｓおよびｄの最も近い共通の祖先であるスイッチング・ノード（ここではｎｃａ（ｓ、ｄ）と関数的に示す）を見出す。多数の候補がある場合、所与のルールに従って１つを選択する。
２．  ｓからｎｃａ（ｓ、ｄ）までの一意の上昇経路上で上方向にルーティングする。
３．  ｎｃａ（ｓ、ｄ）からｄまでの一意の下降経路上で下方向にルーティングする。
このアルゴリズムは、最短経路であると共にデッドロックが存在しないという特性を有する。
【００３６】
例えば、図１は、ノードＮ１からノードＮ２７までおよびノードＮ１１からノードＮ２７までの９個の可能な経路の１つ、ならびに、ノードＮ１からＮ６までの３つの可能な経路の１つを示す。スイッチング・ノードｎｃａ（１，６）は、ノードＳ２，２に対応し、例えばノードＮ１からＮ６の考えられる最も近い共通祖先の１つである。同様に、図１においてノードｎｃａ（１，２７）およびｎｃａ（１１，２７）が示され、これらはそれぞれノードＳ３，１およびＳ３，２に対応する。
【００３７】
より詳しく調べると、上述のルーティング・アルゴリズムの結果、所与のスイッチング・ノードにおいて行うことができる方向転換の制限があることが認められる。具体的には、パケットがダウンするスイッチに入る時はいつでも、再びアップにルーティングすることはできない。
【００３８】
しかしながら、従来技術のスイッチング・ノードは、入力および出力のいかなる組み合わせ間でも接続を可能とする方法で実施される。すなわちそれらは完全な接続性を与える。かかるスイッチング・ノードは、例えば、入力ラインを出力ラインに直接接続するクロスポイントの行列と考えることができる。図２に、クロスポイントの行列の一例を示す。直接クロスポイントＣＰｘ，ｙは、入力ポートＩｘを出力ポートＯｙに接続する（インデクスｉ、ｊは簡潔さのため今後省略する。すなわち、入力ポートＩｘは図示したノードのｘ番目の入力ポートを示す）。従って、完全な接続性を与えるスイッチング・ノードはＮ２個のクロスポイントを有する（または非スクエア・ノードではＮＭ個のクロスポイント）。更に、各クロスポイントに関連した実際の実施の複雑度は、既知のように、特定のスイッチング・ノード・アーキテクチャ（バッファなしのクロスバー、バッファありのクロスバー、共有メモリ等）に依存する。
【００３９】
所与のコンピュータ相互接続ネットワーク（図１のネットワーク１００等）が、例えばルーティング・アルゴリズムおよびトポロジーによって規定されたような「禁止された」方向転換を有する場合があることを考慮すると、次に、クロスポイントのいくつかを除去することを考えることができる。しかしながら、図１に示すようなネットワークおよびアップ＊／ダウン＊ルーティング・アルゴリズム以外に、他のネットワーク／ルーティング・アルゴリズムにおいても禁止されたデータ・ルートが生じ得ることは、当業者には認められよう。例えば、いくつかの特定のノードは、所与の第１のネットワーク・エンティティから所与の第２のネットワーク・エンティティへデータをルーティングすることを阻止される場合がある。かかる場合、先に概説したように、スイッチにおいて低密度実装のクロスポイント構造を好都合に実施することができる。
【００４０】
例えば図３〜図５のクロスポイント構造にこれを示す。この場合も、基礎にあるスイッチング・デバイスはＮ個の入力ポートＩｘおよびＭ個の出力ポートＯｙを有する。これは、入力ポートの各々から出力ポートのいくつか（「アウト」）へ、（直接）クロスポイントＣＰｘ，ｙを介してデータ・パケットをルーティング（「イン」）するように設計されている。図２〜図５の例では、ｘ＝１、．．．、８であり、ｙ＝１、．．．、８である。更に、図３〜図７の実施形態は、図１に示したような相互接続ネットワークのいずれかのノードＳｉ，ｊに適用可能である。
【００４１】
図３〜図５の実施形態に示すように、保持されたクロスポイントＣＰｘ，ｙは、入力ポートと出力ポートのサブセットｍ＜Ｍとの間のみの直接接続性を可能とする。これ以降、簡略化のためにスクエア・スイッチ（Ｍ＝Ｎ）を想定する。図３の具体的な例では、直接クロスポイントの数は正確にＮ２−Ｎに等しい。すなわち、直接クロスポイントＣＰｘ，ｙ＝ｘは除去されている（またはスイッチはクロスポイントＣＰｘ，ｙ＝ｘなしで構築されている）。このため、このデバイスは、同一ポートｘ、すなわちこの場合は同一の双方向ポートに対応する入力ポートと出力ポートとの間の直接接続性を防ぐ。実際、Ｎ２が完全な接続性のために必要な直接クロスポイント数に対応する場合、Ｎは、同一ポートに対応する入出力ポートの全対間の直接接続性のために必要な直接クロスポイント数に対応する。このため、図３に示すクロスポイント構造は複雑度が低減している。
【００４２】
更に一般的には、出力ポートの残りのサブセットｍ＜Ｎは、ネットワークの接続性の要求に従って設計することができ、この結果、異なるレベルのノード複雑度が生じる。
【００４３】
例えば、実際の直接クロスポイント数は、少なくとも入力ポートのサブセット（すなわちＮ１の入力ポート）と対応する数の出力ポート（すなわち同一の双方向ポートに対応する）との間の直接接続性を防ぐため等のために、Ｎ２−Ｎ１（Ｎ１≦Ｎ）未満とすることができる。
【００４４】
他の状況では、ネットワーク・エンティティの第１のサブセットからデータを受信するＮ１の入力ポートと、エンティティの第２のサブセットにデータを送信するＮ２の出力ポートとの間で、直接接続性を防ぎたい場合がある。従ってこの場合には、Ｎ２−Ｎ１Ｎ２のクロスポイントが提供される。コメントは以下の通りである。ネットワーク・エンティティの各サブセットは１つだけのノードから成る可能性がある。また、２つのサブセットが重複し、同一エンティティに対応する可能性がある。
【００４５】
図４においては、特にＮ１×Ｎ２のクロスポイントを破棄し、ネットワーク・エンティティの第１および第２のサブセット間の直接接続性を防ぐ。更に正確には、この例においては、ここで考えるネットワーク・トポロジーの結果としてＮ１＝Ｎ２＝Ｎ／２を有する。すなわち、スイッチの「アップ」側に対応するＮ１の入来ポートは、スイッチの「アップ」側のＮ２の出立ポートに接続されない。
【００４６】
更に、ネットワークの接続性の要求が、先に生じたような、どのポートもそれ自身に戻るようにルーティングされてはならないというものである場合、対角線上の全てのクロスポイントを更に省略することができる。かかる状況を図４に示し、ここからクロスポイント・パターンを得る。
【００４７】
図４の状況を一般化して得られる実施形態においては、Ｎ２−Ｎ１Ｎ２−（Ｎ−Ｍｉｎ（Ｎ１、Ｎ２））のクロスポイントが得られ、これはＮ１の入力ポートとＮ２の出力ポートとの間の直接接続性を防ぐことになり、一方で、どのポートもそれ自身に戻るようにルーティングすることはできない。Ｎ１＝Ｎ２＝Ｎ／２という特定の場合、以前の公式は３Ｎ２／４−Ｎ／２に変換される。このため、かかる実施形態では、直接クロスポイントの４分の１を概ね省略することができる（大きいＮの場合）。
【００４８】
次に、ポートＩｘとＯｙとの間の交点におけるクロスポイントを排除することは、ＩｘがもはやＯｙに到達することができないことを意味するので、例えば間接的に接続性を復元させたい場合がある。このため、本発明のスイッチング・デバイスは、実施形態において、デバイスの追加回路Ｌを介して入力ポートを間接的にスイッチの出力ポートに接続することを可能とするように構成された追加のクロスポイントを更に含むことができる。従って、直接クロスポイントによって接続されていない１対の入力ポートおよび出力ポートのためのデータ・パケットを受信する場合、図５に示すように、デバイスの追加のクロスポイントおよび回路Ｌを介して、このデータ・パケットをルーティングすることができる。
【００４９】
概念上、かかる問題は結果的にクロスポイント行列構造の追加の行および列を接続することになり、いくつかの実際の実施形態を想定可能であることが認められる。しかしながら好都合なことに、図５に示すように、簡単な実施形態では、追加回路Ｌを介して接続された追加クロスポイントＡＰｘＬおよびＡＰＬｙの２つのセットを用いる。各追加クロスポイントＡＰｘＬは、すでに直接クロスポイントＣＰｘｙに接続されている入力ポートＩｘを回路Ｌに接続する。同様に、追加クロスポイントＡＰＬｙの第２のセットは、回路をデバイスの出力ポートＯｙに接続する。
【００５０】
更に一般的には、１つ以上の完全実装された列および１つ以上の完全実装された行をスイッチング行列に追加することができる。しかしながら、これらの列および行は外部ポートに対応しない。すなわち、それらは内部使用のみのためのものである。これらの追加の行および列を「バイパス」と称する。全てのバイパス列は、回路Ｌを介してバイパス行の１つに接続され（またはその逆であり）、これによって回路Ｌは内部ループ・バック経路を生成する。バイパスは、何個のまたはどのクロスポイントが排除されたかには無関係に、完全な到達性を復元させるため等のために配置することができる。図５は、１つのバイパスを有する８×８スイッチング・ノードの一例を示す。すなわち、バイパス列ＡＰｘＬは回路Ｌを介してバイパス行ＡＰＬｙに接続されている。
【００５１】
ここでノードにおけるデータの操作を考える。パケットが未接続ポート対（例えばＩ８およびＯ８）に到達した場合はいつでも、このパケットはそのソース・ポートに対応する余分な列ＡＰ８，Ｌ上のクロスポイントにルーティングされ、そこから、回路Ｌを介してバイパスが接続されている余分な行ＡＰＬ，８にループ・バックされ、その宛先ポートに対応するクロスポイントに送出される。バイパスは、直接クロスポイントに直接接続されていない全てのポート対によって共有されることに留意すべきである。（直接）接続されたポート対からのパケットは、通常のように直接クロスポイントを介してルーティングされる。
【００５２】
図５の例では、低密度のクロスバー（バイパスを含む）は、実際に３Ｎ２／４−Ｎ／２＋２Ｎ個のクロスポイント（この中に２Ｎの追加クロスポイントがある）を有し、これに対して完全接続クロスバーではＮ２個である。低密度のクロスバーは、６より大きいあらゆるＮについて複雑度が低くなることがわかる。例えばＮ＝３２では、クロスポイントの約８０％のみを保持する必要があるだけである。Ｎが大きくなると、完全接続性に対して、クロスポイントの〜７５％に漸近的に近付くことができる。
【００５３】
次に、実施形態において、バイパスは以下のように機能することができる。パケットがスイッチ入力に到達すると、入力インタフェースは、このパケットの宛先が実装クロスポイントであるか否かをチェックする。イエスの場合、パケットはすぐに宛先クロスポイントにルーティングされる。そうでなければ、パケットはその宛先列に直接ルーティングすることができず、従ってバイパスを介してルーティングしなければならない。入力インタフェースは、利用可能なバイパスから１つを選択し、パケットを対応するクロスポイントＡＰｘ，Ｌにルーティングする。好ましくは、各バイパス列はそれ自身のスケジューラを有する。バイパス・スケジューラは、その列からパケットを選択し、これをそのループ・バックを介して対応するバイパス行ＡＰＬ，ｙに、更にパケットの宛先ポートに対応する特定のクロスポイントにルーティングする。全ての出力スケジューラは、その列におけるバイパス・クロスポイントからのパケットおよび正規のクロスポイントをスケジュールする。多くのスケジューリング規則を想定することができる。更に、特記事項として、バイパスがどれも利用可能でない場合、パケットはドロップしなければならない場合があることに留意すべきである（例えばバッファありのクロスバーの場合）。
【００５４】
前述のように、バイパスは主として完全接続性を可能とするために、すなわち全ポートを全ての他のポートに到達可能とするために、実施される。それらは、厳密な性能要求を有する接続には適さない場合があることがわかる。上述したようなバイパスは、典型的に２つの性能上の欠点を有する。第１に、レイテンシの不利益がある。なぜなら、バイパスを通る全てのパケットは、（バッファありのクロスバーにおいて）スイッチから出る前に２度記憶され読み取られるからである。第２に、バイパスを用いるフローは全て、限定されたクロスポイント・セットを共有し、限定された内部帯域幅のみを利用するが、これは設計上、アタッチされたポートにおいて可能な最大全スループットよりも（はるかに）小さい。例えば図５において、「アップ」側の入力から「アップ」側の出力までのフローの全トラフィックの最大全スループットは、単一のループ・バック経路の帯域幅に限定されるので、最悪の場合、影響を受けるフローのスループットはわずか２５％である（すなわち全ての入力が１００％負荷で実装されていないクロスポイントに送信する場合）。しかしながら、この限定は、更にバイパスを追加することによって改善することができる。
【００５５】
更に記載するように、クロスポイント排除パターンは、図５に示すように規則的である必要はない。低密度は、コンピュータ相互接続ネットワークの接続性要求に従って、いかなる形状も取ることができ、対称（例えば図６の例示的な実施形態を参照のこと）または非対称（図７）も可能である。更に、バイパスの行および列は、図示したパターンから著しく変動する可能性がある。特に、厳密に言えば、全ての列／行に接続された行ｘまたは列ｙについてバイパス・クロスポイントＡＰｘ，Ｌ／ＡＰＬ，ｙを追加する必要はないことに留意すべきである。また、１つのみの直接クロスポイントを除去する場合（特定の接続性の要求のため）、対応するバイパスに必要な２つのクロスポイントを追加するよりも、これを維持することが好ましい場合が実際ある。従って、図５〜図７に対応する変形例を想定することができる。
【００５６】
この手法は、いかなるトポロジーおよびいかなるルーティング・スキームにも簡単に一般化することができる。それらが与えられると、いかなるスイッチについても、どの方向転換を行わないかを決定すること、これに応じてクロスポイントを排除することは簡単である。更に、バイパスの容量は、多数の余分な行および列（図示せず）を追加することによって大きくすることができる。厳密に言うと、いくつかの方向転換を行わない場合、それらの方向転換のためのバイパスは必要ないことに留意すべきである。それにもかかわらず、これを実施することが試験／診断の目的のために有用である場合がある。
【００５７】
更に、この手法は、予想される空間トラフィック分布の特徴を考慮に入れるように一般化することができる。パケット・スイッチングのいくつかの用途では、スイッチング・ノードにおいて観察されるトラフィック・パターンは極めて非均一である場合がある。これが意味するのは、所与の入力ポートを介して入ってくるトラフィックは出力ポート・セット上での分布が等しくないこと、または異なる入力ポートを介して入ってくるトラフィックは異なる分布パターンを示すこと、あるいはその両方である。
【００５８】
所与のスイッチでは、極めて少ないトラフィックのみが予想される全ての接続を共有バイパスにマッピングすることができる。例えば、ＨＰＣアプリケーションは多くの場合、極めて独特の通信パターンを示し、例えば、ほとんどの通信が隣接ネイバーの間で行われる。この点において、本発明に従った方法は、実施形態において、例えばスイッチ・ポートにおけるデータ・パケット到着の予想強度に基づいて、ネットワークの接続性要求を決定する初期ステップを含む。次いで、決定した接続性要求に従って、スイッチ構成を最適化することを可能とする（すなわちネットワークにおいて用いる１つ以上のスイッチのための最適化クロスポイント構造、およびおそらく、ネットワーク内でどのようにかかるスイッチを配置可能であるか）。
【００５９】
当業者によって認められるように、本発明の態様は、ネットワーク、方法、またはコンピュータ・プログラムとして具現化することができる。従って、本発明の態様は、全体的にハードウェアの実施形態、全体的にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコード等を含む）、または、ソフトウェアおよびハードウェアの態様を組み合わせた実施形態という形態を取ることができ、それらは全て本明細書において、「回路」、「モジュール」、または「システム」と一般的に称することができる。更に、本発明の態様は、具現化されたコンピュータ読み取り可能プログラム・コードを有する１つ以上のコンピュータ読み取り可能媒体（複数の媒体）において具現化されたコンピュータ・プログラムの形態を取ることも可能である。
【００６０】
１つ以上のコンピュータ読み取り可能媒体（複数の媒体）のあらゆる組み合わせを利用することができる。コンピュータ読み取り可能媒体は、コンピュータ読み取り可能信号媒体またはコンピュータ読み取り可能記憶媒体とすることができる。コンピュータ読み取り可能記憶媒体は例えば、限定ではないが、電子、磁気、光、電磁、赤外線、または半導体のシステム、装置、デバイス、または前述のもののいずれかの適切な組み合わせとすることができる。コンピュータ読み取り可能記憶媒体の更に具体的な例（非網羅的な列挙）は、以下を含む。すなわち、１本以上のワイヤを含む電気的接続、携帯型コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能プログラマブル読み取り専用メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、光ファイバ、携帯型コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、光記憶デバイス、磁気記憶デバイス、または前述のもののいずれかの適切な組み合わせである。この文書の文脈において、コンピュータ読み取り可能記憶媒体は、命令実行システム、装置、またはデバイスによってまたはそれと接続して用いるためにプログラムを含有または記憶することが可能ないずれかのタンジブルな媒体とすることができる。
【００６１】
コンピュータ読み取り可能信号媒体は、例えばベースバンドにおいてまたは搬送波の一部として、具現化されたコンピュータ読み取り可能プログラム・コードを有する伝播データ信号を含むことができる。かかる伝播信号は様々な形態のいずれかを取ることができ、それらは限定ではないが、電磁、光、またはそれらのいずれかの適切な組み合わせを含む。コンピュータ読み取り可能信号媒体は、コンピュータ読み取り可能記憶媒体でないが、命令実行システム、装置、またはデバイスによってまたはそれと接続して用いるためにプログラムを伝達、伝播、または転送することが可能ないずれかのコンピュータ読み取り可能媒体とすることができる。
【００６２】
コンピュータ読み取り可能媒体上で具現化されるプログラム・コードは、限定ではないが、無線、有線、光ファイバ・ケーブル、ＲＦ等、または前述のもののいずれかの適切な組み合わせを含むいずれかの適切な媒体を用いて伝送することができる。
【００６３】
本発明の態様の動作を実行するためのコンピュータ・プログラム・コードは、Ｊａｖａ、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋等のオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語または同様のプログラミング言語等の従来の手順プログラミング言語を含む１つ以上のプログラミング言語のいずれかの組み合わせにおいて記述することができる。プログラム・コードは、（例えば特にイーサネット・ネットワークについて）エンド・ノードまたは最下位レベル・スイッチＳ１，ｊの１つ以上で全体的に実行することができると好都合である。さもなければ、これは、部分的にエンド・ノードまたは最下位レベル・スイッチ上で、および部分的に遠隔ノードまたはスイッチ（例えばもっと高いレベルのスイッチ）上で、またはアーキテクチャが可能とする場合には全体的に１つ以上のもっと高いレベルのスイッチ上で、実行することができる。異なるタイプのネットワークを想定することができる。既知のように、かかるスイッチは、ネットワークの機能性とは別に、単にコンピュータと見なすことができる。この点で、各スイッチはハードウェアにおいて実施することができる。しかしながら、これは、汎用コンピュータの１つ以上のプロセッサにより実行されるプログラムとして実施することができる。汎用コンピュータおよびプロセッサはそれ自体、既知である。
【００６４】
本発明の態様のいずれの動作も、例えば相互接続ネットワークのスイッチング・デバイスのクロスポイントを介してデータをルーティングするためのプログラム命令のようなコンピュータ・プログラム命令によって実施可能であることは理解されよう。かかる命令は、例えば、汎用コンピュータ、ノード、またはスイッチ、特殊目的スイッチ、または他のプログラマブル・データ処理装置のプロセッサに提供されて機械を生成することができ、これによって、スイッチまたは他のプログラマブル・データ処理装置のプロセッサによって実行される命令が、先に規定された機能／行為を実施するための手段を生成するようになっている。
【００６５】
また、これらのコンピュータ・プログラム命令はコンピュータ読み取り可能媒体に記憶することができ、これによって、スイッチ、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイスに特定の方法で機能するように指示することができ、これにより、コンピュータ読み取り可能媒体に記憶された命令が、フローチャートまたはブロック図あるいはその両方のブロックまたは複数のブロックに規定された機能／行為を実施する命令を含む製造品を生成するようになっている。
【００６６】
また、コンピュータ・プログラム命令を、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイスにロードして、そのコンピュータ、他のプログラマブル装置、または他のデバイス上で一連の動作ステップを実行させてコンピュータ実施プロセスを生成することができ、これによって、コンピュータまたは他のプログラマブル装置上で実行する命令が、規定された機能／行為を実施するためのプロセスを提供するようになっている。
【００６７】
本発明について、いくつかの実施形態を参照して記載したが、本発明の範囲から逸脱することなく様々な変更を実施可能であり均等物を置換することが可能であることは、当業者には理解されよう。更に、本発明の範囲から逸脱することなく、多くの変形を実施して、特定の状況または材料を本発明の教示に適合させることも可能である。従って、本発明は開示した特定の実施形態に限定されるのではなく、本発明は添付の特許請求の範囲内に該当する全ての実施形態を含むことが意図される。例えば、ほとんどの通信が隣接ネイバー間で行われる場合、第１のネイバーにのみ対応するポート間で直接接続性を可能とするために直接クロスポイントを構成することができる。更に、本出願は本質的に例示のため双方向ポート（従ってスクエア・スイッチ）を想定するが、不平衡の入力ポート対出力ポートを有する非スクエア・スイッチに対する適用も想定することができる。例えば、スイッチの少なくともいくつかがＮ個の入力ポートおよびＭ個の出力ポートを含むことができる（Ｎ≠Ｍ）。かかるデバイスは、コンピュータ相互接続ネットワークの接続性の要求に従って、Ｎ個の入力ポートの各々と出力ポートのサブセットｍ＜Ｍとの間のみの直接接続性を可能とするために構成した直接クロスポイントによってデータ・パケットをルーティングするために適合させることができる。同様に、デバイスは、実施形態等において前述したように、Ｎ２−Ｎ１（Ｎ１≦Ｎ）でなく、ＮＭ−Ｎ１（Ｎ１≦Ｍｉｎ［Ｎ，Ｍ］）以下の数の直接クロスポイントを含むことができる。
【図１】
0005907954.tif 000002
【図２】
0005907954.tif 000003
【図３】
0005907954.tif 000004
【図４】
0005907954.tif 000005
【図５】
0005907954.tif 000006
【図６】
0005907954.tif 000007
【図７】
0005907954.tif 000008