二分帯域幅

コンピュータネットワークでは、ネットワークを2つの等しいサイズのパーティションに分割することができます。ネットワークトポロジの二分帯域幅は、任意の2つのパーティション間で利用可能な最小帯域幅です。^[1]頂点、辺、および辺の重みを持つグラフを考えると、の二分帯域幅は ${\displaystyle G}$${\displaystyle V}$${\displaystyle E}$${\displaystyle w}$${\displaystyle G}$

${\displaystyle BB(G)=\min _{S\subset V:|S|={\frac {1}{2}}|V|}\quad \sum _{u\in S,v\not \in S}w(u,v)}$。

言い換えれば、ネットワークは、 2 つのパーティション間の帯域幅が最小になるように 2 分割されます。 ^[2]ネットワークは、の場合に完全 2 分割帯域幅を持つと見なされます。^[3]直感的には、完全 2 分割帯域幅とは、ネットワーク内のすべての頂点が送信元と送信先のペアとして一致し、すべてのペアが同時にレート 1 でフローを送信する場合、2 分割ボトルネックがないことを意味します。したがって、2 分割帯域幅は、2 分割されたネットワーク全体のボトルネック帯域幅を説明します。 ${\displaystyle BB(G)\geq {\frac {1}{2}}|V|}$

n 個のノードを持つ線形アレイの場合、二分帯域幅は 1 つのリンク帯域幅です。線形アレイの場合、ネットワークを 2 つのパーティションに二分するには、1 つのリンクを分割するだけで済みます。

n 個のノードを持つリングトポロジの場合、ネットワークを二分するには 2 つのリンクを切断する必要があるため、二分帯域幅は 2 つのリンクの帯域幅になります。

n 個のノードを持つツリートポロジの場合、1 つのリンクを切断することでルートで二分できるため、二分帯域幅は 1 つのリンク帯域幅になります。

n 個のノードを持つメッシュトポロジの場合、ネットワークを二分するためにリンクを分割する必要があるため、二分帯域幅は リンクの帯域幅になります。 ${\displaystyle {\sqrt {n}}}$${\displaystyle {\sqrt {n}}}$

n 個のノードを持つハイパーキューブトポロジの場合、ネットワークを二分するには n/2 個のリンクを分割する必要があるため、二分帯域幅は n/2 個のリンクの帯域幅になります。

^[2]

ネットワーク性能のこの指標の重要性に対する理論的裏付けは、クラーク・トンプソン（旧姓クラーク・トンプソン）の博士研究で開発されました。^[4] トンプソンは、ソート、高速フーリエ変換、行列-行列乗算の重要なアルゴリズムは、二分帯域幅が不十分なコンピュータでは、CPU やメモリではなく通信によって制限されることを証明しました。F . トムソン・レイトンの博士研究^[5]は、シャッフル交換ネットワークとして知られる計算上重要なDe Bruijn グラフの変形の二分帯域幅に関するトンプソンの緩い境界^[6]を強化しました。ビル・ダリーによる、様々なmに対するm次元nキューブネットワークのレイテンシ、平均スループット、ホットスポットスループットの分析^{[2]に基づくと、同じ二分帯域幅（例えば、}トーラス）を持つ高次元ネットワーク（例えば、バイナリnキューブ）と比較して、低次元ネットワークはレイテンシが短く、ホットスポットスループットが高いことがわかります。^[7]

なお、二分帯域幅とネットワークスループットは漸近的に異なる指標であり、ネットワークトポロジに応じて異なる速度で増加する可能性があるという主張もある。 ^{[3] [8]}