11.2 ルーティングの性能評価

11.2.1 ネットワークの直径

パケットが入力端末を離れてから宛先の出力端末に到着するまでの遅延は通信ネットワークで非常に重要な値となる。一般に、この遅延はパケットが通過する路の長さに比例する。一つのリンクを移動するのに一単位の時間がかかると仮定すれば、パケットの遅延は入力端末から出力端末までの移動で通過するリンクの個数に等しい。

通常、パケットは可能な限り短い路を使ってルーティングされる。この最短路ルーティングを使うとき、最悪の場合の遅延は最も離れた入力端末と出力端末の組が通信したときに発生する。この最悪の遅延をネットワークの直径 (diameter) と呼ぶ。言い換えれば、ネットワークの直径とは全ての入力端末と出力端末の組を考えたときの最短路の長さの最大値である¹。例えば、完全二分木で表される図 \(\text{11.1}\) のネットワークでは \(\text{in}_{1}\) から \(\text{out}_{3}\) への最短路の長さが \(6\) であり、これより長い最短路を持つ入力端末と出力端末の組は存在しない。よってネットワークの直径も \(6\) だと分かる。

さらに一般的に言えば、\(N\) 入力 \(N\) 出力の完全二分木ネットワークの直径は \(2 \log N + 2\) である。対数関数が大きくなる速度は非常に遅いので、これは優れた遅延と言える。入力端末と出力端末を \(2^{10} = 1024\) 個ずつ接続する場合でも、完全二分木ネットワークを使えば任意のパケットの入力端末から出力端末までの遅延は最悪の場合でも \(2 \log (2^{10}) + 2 = 22\) にしかならない。

スイッチの形状

大きなスイッチを使うとネットワークの直径を小さくできる。完全二分木ネットワークでは多くのスイッチが \(3\) 個の入力と \(3\) 個の出力を持つ \(3 \times 3\) スイッチである。\(4 \times 4\) スイッチが利用できるなら、完全三分木の形をした遅延のさらに小さいネットワークを構築できる。\(N \times N\) の怪物スイッチを使えば全ての入力端末と出力端末を直接接続して遅延を \(1\) にすることさえ理論的にはできる。

もちろん、この事実が役に立つわけではない。「\(N \times N\) スイッチを使います」と言ったところで、それはネットワークの設計という問題を抽象的なスイッチの中に押し込んで隠しているだけに過ぎない。この怪物スイッチを単純な構成要素から設計するときがいずれ必ずやってくるので、問題は振り出しに戻る。つまり通信ネットワークの設計では、\(3 \times 3\) スイッチのような固定サイズの基礎的デバイスを使って \(N \times N\) スイッチの機能を構築する方法を考える必要がある。

11.2.2 スイッチの個数

通信ネットワークの設計では、可能な限り少ないスイッチを使うことも目標とされる。完全二分木ネットワークでは一番上に「ルート」のスイッチが \(1\) 個あり、下に一段進むごとにスイッチの個数が \(2\) 倍になる。よって \(N\) 入力 \(N\) 出力の完全二分木ネットワーク全体で使われるスイッチの個数は \(1 + 2 + 4 + 8 + \cdots + N\) と計算できる。幾何級数の公式 (問題 5.4) を使えば、この値は \(2N - 1\) に等しいと分かる。これは \(3 \times 3\) スイッチを使う通信ネットワークとして最適に近い値である。

11.2.3 レイテンシ

ネットワークのルーティングを遅延ではない基準で選択する状況もある。例えば次項ではパケットの輻輳ふくそうの最小化を考える。遅延を最小化しないとき、最短の路を使うルーティングが最適とは限らず、一般にパケットの遅延はルーティングごとに変化する。任意のルーティングにおいて、最も遅れて到着するパケットは最も長い路にルーティングされるパケットである。その最も長い路の長さをパケットのレイテンシ (latency) と呼ぶ。

ネットワークレイテンシ (network latency) は、全てのルーティング問題に対する最適なルーティングを考えたときのレイテンシの最大値と定義される。つまり、任意のルーティング問題 \(\pi\) に対して、\(\pi\) を解く最適なルーティングが選択されると仮定して (入力端末から宛先の出力端末への最適なルーティングが常に選択されると仮定して) 計算される。ルーティングが常に遅延を最適化するときネットワークレイテンシはネットワークの直径に等しいものの、他の値を最適化するときはそれよりずっと大きくなる可能性がある。

これから考えるネットワークでは「入力端末と出力端末の組が路を一意に決定する」または「入力端末から出力端末への路の長さが全て等しい」が成り立つ (完全二分木ネットワークでは前者が成り立つ) ので、ネットワークレイテンシは常にネットワークの直径に等しい。

11.2.4 輻輳

完全二分木ネットワークには重大な欠点がある: 一番上にあるルートのスイッチがボトルネックになる。最良の場合でも、このスイッチは二分木の左側から右側、そして右側から左側に移動する全てのパケットを処理しなければならない。最悪の場合には、このスイッチで障害が起こってネットワーク全体が二つの等しい部分に分割されてしまう。

ただ、状況によっては問題が起こらないのも確かである: 例えば恒等置換 \(\text{Id}(i) = i\) で表されるルーティング問題では、入力端末 \(i\) から上に一つだけ上ってすぐに下りれば出力端末 \(i\) に到達できるのでルートのスイッチは利用されない。一方 \(\pi(i) ::= (N - 1) - i\) で表されるルーティング問題では、\(\pi\) に対する任意の解に含まれる全ての路がルートのスイッチを通過する。これら二つの状況を図 \(\text{11.2}\) に示す。

この意味でのルーティングの良し悪しは輻輳ふくそうとして表せる。ルーティング \(P\) の輻輳 (congestion) とは、ネットワークの各辺を通り抜ける \(P\) に属する路の個数の最大値と定義される。例えば図 \(\text{11.2}\) 左のルーティングの輻輳は \(1\) であるのに対して、右のルーティングの輻輳は \(4\) である (ルートのスイッチを通過する路が \(4\) 個あるため)。高負荷のスイッチは遅延を引き起こすので、輻輳が低いルーティングの方が一般に優れている。

輻輳の概念をルーティングからネットワークに拡張すれば、ボトルネックの問題を考えるときにネットワークの良し悪しを表す指標が得られる。ネットワークに対するルーティング問題 \(\pi\) に対して輻輳を最適化する (最小化する) ルーティングが選択されるという仮定の下で全てのルーティング問題を考えたときのルーティングの輻輳の最大値がそのネットワークで発生する可能性のある最大の輻輳となる。この「最大の」輻輳をネットワークの輻輳と呼ぶ。

例えば完全二分木ネットワークでは最悪の置換が \(\pi(i) ::= (N - 1) - i\) であり、この \(\pi\) に対する任意の解では全てのパケットがルートのスイッチを通り抜ける。そのため、完全二分木ネットワークの輻輳の値は \(N\) である ── 悲惨だ！

ここまでの解析結果を次にまとめる: