Closネットワーク

テンプレート:孤立 電気通信の分野において、Closネットワーク（クロス・ネットワーク）とは、マルチステージの回路交換ネットワークの一種であり、実用的なマルチステージのスイッチングシステムの論理的な理想形を表したものである。1938年にEdson Erwinが発明し、1952年にテンプレート:仮リンク（テンプレート:IPA-fr）によって初めて形式化された。

複数のステージを加えることにより、Closネットワークは大規模なクロスバースイッチを構成するために必要な交差点を削減している。Closネットワークのトポロジー（下にダイアグラムを示す）は、3つの整数$n,m,r$でパラメタ化されている。$n$は ingressステージの各クロスバースイッチ（crossbar switch）への入力の数を表し、$m$は ingressステージの各クロスバースイッチの出力の数を表す。ingressステージにはクロスバースイッチが$r$個あり、middleステージのクロスバースイッチの数は$m$である。

回路のスイッチングにより、接続の間だけ持続するエンドポイントとエンドポイントを接続する1つの通信経路が形成される。この方法では、接続された経路の利用率が低い場合、利用可能な総バンド幅が無駄になる。しかし、接続とバンド幅はより予測可能なものになり、そして、現代的なパケットスイッチングネットワークがパケットのハンドリングのたびに制御が必要であるのに対して、Closネットワークでは、接続の初期段階での制御のオーバーヘッドしか必要としない。

Closネットワークが最初に考案されたときは、クロスポイントの数は、スイッチングシステムの総コストによく近似できた。この事実は電気機械式クロスバーには重要だったが、相互接続を直接シリコンに実装することが可能であるVLSIの出現や、比較的小さなボードのクラスタには不要であったため、重要性は薄れていった。ところが、光ファイバーの接続をベースとした非常に大規模な相互接続構造を持つ複雑なデータセンターの出現によって、Closネットワークは再び重要性を取り戻した。 Closネットワークの一種であるBenešネットワークは、近年の応用先として機械学習での利用を見い出した。

トポロジー

Closネットワークには3つのステージがある。すなわち、ingressステージ、middleステージ、egressステージの3つである。各ステージは、複数のクロスバースイッチから構成され（下の図を参照）、それらはしばしば単にクロスバー（crossbars）と呼ばれる。ingressのクロスバースイッチに入力される呼び出し（call）は、それぞれ任意の利用可能なmiddleステージのクロスバースイッチを経由して、対応するegressステージのクロスバースイッチにルーティングされる。ある新しい呼び出しに対して利用できるmiddleステージのクロスバーは、middleステージのスイッチからegressステージのスイッチに接続されたリンクがフリーである場合のみである。

Closネットワークは3つの整数$n,m,r$によって定義される。$n$は、$r$個あるingressステージの各クロスバースイッチへの入力の数を表す。各ingressステージのクロスバースイッチには$m$個の出口があり、middleステージには$m$個のクロスバースイッチがある。ingressステージの各スイッチとmiddleステージの各スイッチの間の接続は、ちょうど1本である。egressステージには$r$個のスイッチがあり、それぞれのスイッチは$m$個の入力と$n$個の出力を持っている。middleステージの各スイッチは、egressステージの各スイッチとちょうど1本で接続されている。したがって、ingressステージには$r$個のスイッチがあり、そのそれぞれは$n$個の入力と$m$個の出力を持つ。middleステージには$m$個のスイッチがあり、そのスイッチのそれぞれは、$r$個の入力と$r$個の出力を持つ。egressステージには$r$個のスイッチがあり、そのそれぞれは$m$個の入力と$n$個の出力を持つ。

ブロッキング特性

$m$と$n$という相対的な値は、Closネットワークのブロッキング特性を定めている。

3つ以上のステージを持つClosネットワーク

Closネットワークは奇数個のステージに一般化することが可能である。中央のステージの各クロスバースイッチを3-ステージのClosネットワークで置き換えれば、5ステージのClosネットワークを構成することができる。同じ手順を繰り返せば、7, 9, 11, …段階のステージを作れる。

Benešネットワーク（m = n = 2）

m = n = 2 であるとき、このタイプのネットワークはBenešネットワークと呼ばれる。

入力および出力の数が N = r×n = 2r である場合、ネットワークは 2log₂N − 1 個のステージからなる。各ステージは N/2 個の 2×2 クロスバースイッチからなり、全部で N log₂N − N/2 個の 2×2 クロスバースイッチがある。例えば、8×8 Benešネットワーク（つまり、N = 8 の場合）は、下図に示すように、2 log₂ 8 − 1 = 5 個のステージを持ち、各ステージには N/2 = 4 個の 2×2 クロスバースイッチがあり、全部で Nlog₂N − N/2 = 20 個のスイッチが使われる。内側の3つのステージは２つの小さい 4×4 Benešネットワークになっており、 中央のステージにおいては、各2×2のクロスバースイッチそのものが 2×2 Benešネットワークを構成している。この例は、このタイプのネットワークの再帰的な構造を良く表している。

関連項目

• クロスバースイッチ Closネットワークのスイッチ要素について説明している。
• テンプレート:仮リンクClosネットワークのスイッチングアルゴリズムについて説明している。
• テンプレート:仮リンク別のネットワーク構成方法の1つ。
• テンプレート:仮リンク別のネットワーク構成方法の1つ。
• テンプレート:仮リンク別のネットワーク構成方法の1つ。