11.3 ネットワークの設計

目次

11.3.1 二次元格子

もう一つの通信ネットワークの形状として二次元格子 (2-dimensional grid/array) が考えられる。\(4\) 入力 \(4\) 出力の二次元格子ネットワークを図 \(\text{11.3}\) に示す。

N=4 の二次元格子ネットワーク
図 11.3\(N=4\) の二次元格子ネットワーク

このネットワークの直径は \(8\) である: \(\text{in}_{0}\) と \(\text{out}_{3}\) を結ぶ路は全て \(8\) の長さを持ち、これより長い路は存在しない。一般に、\(N\) 入力 \(N\) 出力の二次元格子ネットワークの直径は \(2N\) だと示せる。これは完全二分木ネットワークの \(2 \log N + 2\) より大幅に劣る値である。ただ、その代わり二次元格子ネットワークは完全二分木ネットワークの大きな欠点を克服している: 輻輳がほとんど起こらない。

定理 11.3.1

\(N\) 入力 \(N\) 出力の二次元格子ネットワークの輻輳は \(2\) である。

証明 まず、輻輳が \(2\) 以下だと示す。\(\pi\) を任意の置換とする。ルーティング問題 \(\pi\) に対する解 \(P = \left\{ P_{0}, \ldots, P_{N-1} \right\} \) を次のように構築する: 路 \(P_{i}\) は入力端末 \(i\) を出発して第 \(\pi(i)\) 列まで右に進み、そこで下に方向転換して出力端末 \(\pi(i)\) まで進む。このルーティング \(P\) において第 \(i\) 行 \(j\) 列にあるスイッチを通り抜けるパケットの個数は最大で \(2\) である: このスイッチを通り抜ける可能性があるのは、入力端末 \(i\) から右に進んできたパケットと、出力端末 \(j\) に向かって下に進むパケットしかない。

続いて、輻輳が \(2\) 以上だと示す。\(\pi(0) = 0\) と \(\pi(N-1)=N-1\) を満たす任意のルーティング問題 \(\pi\) において、二つのパケットが通る路はどこかのスイッチで必ず交差しなければならないことから、輻輳が \(2\) 以上だと分かる。 ■

完全二分木ネットワークと同様に、二次元格子ネットワークでも輻輳を最小化するときのネットワークレイテンシが直径と一致する。これは任意の入力端末と出力端末の組を結ぶ全ての路が同じ長さである事実から分かる。

二次元格子ネットワークの特徴を以前の表に書き加えよう:

\[ \def\arraystretch{1.2}\begin{array}{l|c|c|c|c} \text{ネットワーク} & \text{直径} & \text{スイッチの形状} & \text{スイッチの個数} & \text{輻輳} \\ \hline \text{完全二分木} & 2 \log N + 2 & 3 \times 3 & 2N - 1 & N \\ \text{二次元格子} & 2 N & 2 \times 2 & N^{2} & 2 \end{array} \]

新しく追加された行で注目に値する要素がスイッチの個数 \(N^{2}\) である。これは二次元格子ネットワークの大きな欠点と言える: サイズが \(N = 1000\) なら百万個の \(2 \times 2\) スイッチが必要となる！ ただ、\(N\) が小さい場面では、単純さと小さい輻輳のおかげで二次元格子ネットワークは魅力的な選択肢となる。

11.3.2 バタフライ

通信ネットワーク設計の聖杯は完全二分木の利点 (直径とスイッチの個数が小さい) と二次元格子の利点 (輻輳が小さい) を合わせたものだろう。二つの妥協点として広く用いられる設計としてバタフライネットワーク (butterfly network) がある。

バタフライネットワークは再帰的データ型として説明できる。再帰的定義は入力端末と出力端末を除いてスイッチだけを考えると単純になるので、これからバタフライネットワークのスイッチとそれらの接続を示す \(F_{n}\) の再帰的な定義を示す。これまで通り入力端末と出力端末の個数はそれぞれ \(N ::= 2^{n}\) とする。

ベースケースの \(F_{1}\) は \(2\) 個の入力スイッチと \(2\) 個の出力スイッチを図 \(\text{11.4}\) のように接続したネットワークである。

N = 2^{1} のバタフライネットワーク F_{1}
図 11.4\(N = 2^{1}\) のバタフライネットワーク \(F_{1}\)

構築ステップでは、\(2^{n+1}\) 個の入力スイッチを持つ \(F_{n+1}\) が二つの \(F_{n}\) を使って図 \(\text{11.5}\) のように構築される。図から分かるように、\(i\) 番目の入力と \(2^{n} + i\) 番目の入力が接続される二つのスイッチは同一であり、それは二つの \(F_{n}\) に対する \(i\) 番目の入力である (\(i = 1, \ldots, 2^{n}\))。また、\(F_{n+1}\) の出力は二つの \(F_{n}\) の出力をそのまま並べたものに等しい。

N = 2^{n+1} のバタフライネットワーク F_{n+1} は二つの F_{n} を持つ
図 11.5\(N = 2^{n+1}\) のバタフライネットワーク \(F_{n+1}\) は二つの \(F_{n}\) を持つ

\(F_{n+1}\) の各列には \(2^{n+1}\) 個のスイッチが含まれる。\(F_{n+1}\) の列数は \(F_{n}\) の列数より \(1\) だけ大きく、\(F_{1}\) は \(2\) 個の列を持つので、\(F_{n+1}\) は \(n+2\) 個の列を持つ。よって \(F_{n+1}\) に含まれるスイッチの個数は列数と各列に含まれるスイッチの個数の積 \(2^{n+1}(n+2)\) だと分かる。\(n = \log N\) を思い出せば、\(N\) 入力 \(N\) 出力の \(F_{n}\) に含まれるスイッチの個数は \(N (\log N + 1)\) だと結論できる。

\(F_{n+1}\) において入力スイッチと出力スイッチを結ぶ任意の路の長さは \(n + 1\) である。完全なバタフライネットワークにはスイッチとは別に入力端末と出力端末 (これまで四角で表してきた) が存在するので、\(N\) 入力 \(N\) 出力のバタフライネットワークの直径は \(n + 2 = \log N + 2\) と分かる。

バタフライネットワークでパケットをルーティングする簡単な再帰的手続きが存在する。ベースケースの \(F_{1}\) では \(2\) 個の入力スイッチと \(2\) 個の出力スイッチを結ぶ路がそれぞれの組ごとに一つしか存在しないので、ルーティングは一意に定まる。続いて、\(F_{n+1}\) の入力スイッチから出力スイッチへパケットをルーティングしたいとする。注目している入力スイッチに対応する出力スイッチが「上段」の \(F_{n}\) に属するなら、最初のステップで入力スイッチと上段の \(F_{n}\) を結ぶリンクを選択する。同様に出力スイッチが「下段」の \(F_{n}\) に属するなら、最初のステップで入力スイッチと下段の \(F_{n}\) を結ぶリンクを選択する。両方の場合において、以降のルーティングは \(F_{n}\) の内部で再帰的に行われる。実は、この議論は全ての \(F_{n}\) でルーティングが一意である事実を示している: 任意の入力スイッチと出力スイッチの組に対して、両者を結ぶ路が一つしか存在しない。このため輻輳を最小化するときのネットワークレイテンシは直径に等しい。

バタフライネットワークの輻輳は約 \(\sqrt{N}\) である。正確に言えば、\(N\) が \(2\) の偶数乗のとき \(\sqrt{N}\) となり、\(N\) が \(2\) の奇数乗のとき \(\sqrt{N/2}\) となる。この事実の簡単な証明を問題 11.8 に示してある。

バタフライネットワークのデータを表に書き加えよう:

\[ \def\arraystretch{1.2}\begin{array}{l|c|c|c|c} \text{ネットワーク} & \text{直径} & \text{スイッチの形状} & \text{スイッチの個数} & \text{輻輳} \\ \hline \text{完全二分木} & 2 \log N + 2 & 3 \times 3 & 2N - 1 & N \\ \text{二次元格子} & 2 N & 2 \times 2 & N^{2} & 2 \\ \text{バタフライ} & \log N + 2 & 2 \times 2 & N (\log N + 1) & \sqrt{N} \text{ または } \sqrt{N/2} \end{array} \]

この表を見ると、バタフライネットワークは完全二分木より小さい輻輳を持ち、二次元格子より小さい直径と少ないスイッチを持つと分かる。ただ、それぞれの設計が最も優れる性質では劣っており、両者の中間にある設計と言える。ルーティングネットワークの聖杯を探す旅はまだ終わらない。

11.3.3 Beneš ネットワーク

1960 年代、Bellベル 研究所の研究者 Václavバーツラフ E. Benešベネシュ が目覚ましいアイデアを発表した。彼は二つのバタフライネットワークを背中合わせに合体させると輻輳が \(1\) の驚異的な通信ネットワークが得られることに気が付いた。この設計は現在 Benešベネシュ ネットワーク (Beneš network) と呼ばれる。Beneš ネットワークの再帰的な構築では各ステージで二つの列が追加される。\(N ::= 2^{n}\) 個の入力スイッチおよび出力スイッチを持つ (入力端末と出力端末を除いた) Beneš ネットワークを \(B_{n}\) とするとき、その再帰的定義は次の通りである。

まず、ベースケースの \(B_{1}\) は図 \(\text{11.4}\) に示した \(F_{1}\) と同じ \(2\) 個の入力スイッチと \(2\) 個の出力スイッチを持つネットワークである。

続いて構築ケースでは、\(B_{n+1}\) が二つの \(B_{n}\) を使って図 \(\text{11.6}\) のように構築される。\(B_{n+1}\) が持つ \(2^{n+1}\) 個の入力スイッチと \(2^{n+1}\) 個の出力スイッチは両方とも \(B_{n+1}\) で新しく追加される。

N = 2^{n+1} の Beneš ネットワーク B_{n+1} は二つの B_{n} を持つ
図 11.6\(N = 2^{n+1}\) の Beneš ネットワーク \(B_{n+1}\) は二つの \(B_{n}\) を持つ

\(i = 1, \ldots, 2^{n}\) に対して、\(i\) 番目と \(2^{n} + i\) 番目の入力スイッチは同じ二つのスイッチに接続される: 二つの \(B_{n}\) の \(i\) 番目の入力である。この部分はバタフライネットワークと全く変わらない。しかし Beneš ネットワークでは、\(i\) 番目と \(2^{n} + i\) 番目の出力スイッチも同様に (二つの \(B_{n}\) の \(i\) 番目の出力に) 接続される。

\(B_{n+1}\) の各列には \(2^{n+1}\) 個のスイッチが含まれる。\(B_{n+1}\) の列数は \(B_{n}\) より \(2\) だけ大きく、\(B_{1}\) は \(2\) 個の列を持つので、\(B_{n+1}\) は \(2(n+1)\) 個の列を持つ。よって \(B_{n+1}\) に含まれるスイッチの個数は列数と各列に含まれるスイッチの個数の積 \(2 (n+1) 2^{n+1}\) だと分かる。\(n = \log N\) を思い出せば、\(N\) 入力 \(N\) 出力の \(B_{n}\) に含まれるスイッチの個数は \(2 N \log N\) だと結論できる。

\(B_{n+1}\) で任意の入力スイッチと任意の出力スイッチを結ぶ路の長さは全て \(2(n + 1) - 1\) である。完全なネットワークでは入力端末と出力端末が加わるので、\(N\) 入力 \(N\) 出力の Beneš ネットワークの直径は \((2n - 1) + 2 = 2 \log N + 1\) と分かる。

よって、バタフライネットワークと比べたとき Beneš ネットワークはスイッチの個数と直径が倍になる。しかし、その代わりに輻輳の問題が完全に解決される！ この事実の数学的帰納法を使った賢い証明を示す前に、Beneš ネットワークのデータを表にまとめておく:

\[ \def\arraystretch{1.2}\begin{array}{l|c|c|c|c} \text{ネットワーク} & \text{直径} & \text{スイッチの形状} & \text{スイッチの個数} & \text{輻輳} \\ \hline \text{完全二分木} & 2 \log N + 2 & 3 \times 3 & 2N - 1 & N \\ \text{二次元格子} & 2 N & 2 \times 2 & N^{2} & 2 \\ \text{バタフライ} & \log N + 2 & 2 \times 2 & N (\log N + 1) & \sqrt{N} \text{ または } \sqrt{N/2} \\ \text{Beneš} & 2 \log N + 1 & 2 \times 2 & 2 N \log N & 1 \end{array} \]

Beneš ネットワークは少ないスイッチと小さい直径、そして最小限の輻輳を持つ。ルーティングネットワークの聖杯は私たちのものとなった！

定理 11.3.2

\(N\) 入力 \(N\) 出力の Beneš ネットワークの輻輳は \(1\) である。

証明 \(N = 2^{n}\) として、\(n\) に関する数学的帰納法で示す。次の述語 \(P(n)\) を帰納法の仮定とする:

\[ P(n) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \text{\(B_{n}\) の輻輳は \(1\) である} \]

ベースケース: \(n = 1\) のとき、\(B_{1} = F_{1}\) は図 \(\text{11.4}\) に示されたネットワークである。\(F_{1}\) において任意のルーティング問題の解は一意であり、どれも \(1\) の輻輳を持つ。

帰納ステップ: \(N = 2^{n}\) 入力 \(N\) 出力の Beneš ネットワークの輻輳が \(1\) だと仮定する。この上で、\(2N\) 入力 \(2N\) 出力の Beneš ネットワークの輻輳が \(1\) だと示す。

[余談] ちょっと待った！ 証明を進める前に、理解を深めるための具体的な例を一つ示しておく。\(N = 8\) の Beneš ネットワーク \(B_{3}\) を図 \(\text{11.7}\) に示す。破線で囲われているのは一つ小さい大きさの \(B_{2}\) である。

8 入力 8 出力の Beneš ネットワーク B_{3}
図 11.7\(8\) 入力 \(8\) 出力の Beneš ネットワーク \(B_{3}\)

帰納法の仮定から、一つ小さい大きさの \(B_{2}\) では任意の置換に対する輻輳が \(1\) である。よって最初と最後のリンクさえ正しくルーティングできれば、他の部分は数学的帰納法によって自動的に構築される！ この「自動的な構築」を具体的に見ていこう。ルーティング問題は次の置換だとする:

\[ \begin{aligned} \pi(0) &= 1 & \quad \pi(4) &= 3 \\ \pi(1) &= 5 & \quad \pi(5) &= 6 \\ \pi(2) &= 4 & \quad \pi(6) &= 0 \\ \pi(3) &= 7 & \quad \pi(7) &= 2 \end{aligned} \]

\(i\) 番目の入力スイッチ \(i\) を出たパケット \(i\) は上段または下段の \(B_{2}\) にルーティングできる。ただし、あるパケットの移動先を選択すると、別のパケットの移動先が制限される。例えばパケット \(0\) とパケット \(4\) の両方を \(B_{2}\) にルーティングすることはできない: そのとき一つのスイッチに二つのパケットが向かうので、輻輳が \(2\) になってしまう。よって二つのパケットの一方は上段の \(B_{2}\) に、もう一方は下段の \(B_{2}\) に向かわせる必要がある。同様に、パケット \(1\) とパケット \(5\)、パケット \(2\) とパケット \(6\)、パケット \(3\) とパケット \(7\) はそれぞれ異なる \(B_{2}\) にルーティングされる必要がある。この制約をグラフで表してみよう。次に示す制約グラフで点は \(8\) 個のパケットを表し、辺は二つのパケットが異なる \(B_{2}\) に向かわなければならない事実を表す:

各頂点から \(1\) 本の辺が出ていることに注目してほしい。

制約はネットワークの出力側からも加わる。例えば、宛先が \(\text{out}_{0}\) のパケット \(6\) と宛先が \(\text{out}_{4}\) のパケット \(2\) は同じ \(B_{2}\) に向かってはいけない: このとき両方のパケットが \(B_{2}\) の同じ出力スイッチに達してしまう。同様に、宛先が \(\text{out}_{1}\) と \(\text{out}_{5}\)、\(\text{out}_{2}\) と \(\text{out}_{6}\)、\(\text{out}_{3}\) と \(\text{out}_{7}\) のパケット、つまりパケット \(0\) とパケット \(1\)、パケット \(7\) とパケット \(5\)、パケット \(4\) とパケット \(3\) はそれぞれ異なる \(B_{2}\) にルーティングされる必要がある。この制約を書き加えた制約グラフを次に示す:

各頂点から \(2\) 本の辺が出ていることに注目してほしい。頂点 \(2\) と頂点 \(6\) の間にある \(2\) 個の辺は、この二つのパケットが異なる \(B_{2}\) に向かわなければならない理由が二つあることを意味する。ただ、このグラフは単純グラフとして解釈する: 図に同じ二頂点を結ぶ辺が \(2\) 本あっても、図が表すグラフは二頂点を結ぶ辺を \(1\) 本しか持たないとする。

この制約グラフに関して重要な事実がある: 各頂点に赤または青の色を塗って、辺で結ばれた任意の二頂点が異なる色を持つようにできたとする。このとき、赤に塗られた頂点に対応するパケットを上段の \(B_{2}\) に、青に塗られた頂点に対応するパケットを下段の \(B_{2}\) に向かわせるルーティングは全ての制約を満たす。つまり、制約グラフの \(2\)-彩色はルーティング問題の解に対応する。最後の疑問は制約グラフが \(2\)-彩色可能かどうかである。これは簡単に検証できる:

補題 11.3.3

単純グラフの各辺が二つのグループのいずれかまたは両方に所属していて、任意の頂点に接続する辺がグループごとに高々 \(1\) 個なら、そのグラフは \(2\)-彩色可能である。

証明 ここでは証明を省略するものの、任意の単純グラフに対して「\(2\)-彩色可能」と「全ての閉歩道が偶数長」は同値である (定理 12.8.3)。よって、全ての閉歩道が偶数長だと示せばよい。二つのグループの両方に属する辺が存在する可能性もあるので、そういった辺を重複辺 (doubled edge) と呼ぶことにする。

単純グラフに含まれる閉歩道 \(C\) を任意に一つ取る。二つの場合を分けて考える:

■

例えば、上記の制約グラフは次の \(2\)-彩色を持つ:

この \(2\)-彩色があれば、最初と最後の部分に対するルーティングが得られる。残りの二つの小さな Beneš ネットワーク内のルーティングは数学帰納法から自動的に構築される！ [余談終わり]

\(\pi\) を \([0..N-1]\) の任意の置換とする。頂点がパケット \(0\), \(1\), \(\ldots\), \(N-1\) で、辺集合が次の二集合の和集合である単純グラフを \(G\) と定める:

\[ \begin{alignedat}{2} E_{1} &::= \{ \langle u\>\text{---}\>v \rangle &&\; | \; \left| u - v \right| = N / 2 \} \\ E_{2} &::= \{ \langle u\>\text{---}\>w \rangle &&\; | \; \left| \pi(u) - \pi(w) \right| = N / 2 \} \end{alignedat} \]

このとき任意の頂点 \(u\) を端点に持つ辺は高々 \(2\) 個しか存在しない: 辺 \(\langle u\>\text{---}\>v \rangle \in E_{1}\) と辺 \(\langle u\>\text{---}\>w \rangle \in E_{2}\) であり、いずれも一意である。よって補題 11.3.3 より、\(G\) の頂点に対する \(2\)-彩色が存在する。その \(2\)-彩色で一方の色に彩色される頂点を上段の部分ネットワークに、もう一方の色に彩色する頂点を下段の部分ネットワークにルーティングしたとする。\(E_{1}\) の定義より、このとき二番目の列でパケットは衝突しない。また、\(E_{2}\) に含まれる任意の辺に対して、端点の一方は上段の部分ネットワークの出力に含まれ、もう一方は下段の部分ネットワークの出力に含まれる。よって最後の列でもパケットは衝突しない。二つの部分ネットワーク \(B_{n}\) 内のルーティングは帰納法の仮定 \(P(n)\) より構築できるので、ネットワーク全体に対する輻輳が \(1\) のルーティングは存在する。 ■

広告