練習問題

次の通信ネットワークを考える:

1. このネットワークの輻輳を求めよ。

2. 最大の輻輳を与える入出力の設定を表す置換 \(\pi_{0}\) を示せ。

3. 最小の輻輳を与える入出力の設定を表す置換 \(\pi_{1}\) を示せ。

4. 置換 \(\pi_{1}\) のレイテンシを求めよ。

Beneš ネットワーク (第 11.3.3 項) の輻輳は \(1\) である ── どんな置換に対しても、任意のスイッチを通り抜けるパケットが \(1\) 個になるようなルーティングが存在する。この事実が分かる例を見よう。\(N = 8\) の Beneš ネットワーク \(B_{3}\) を図 \(\text{11.7}\) に示す。このネットワークには \(N = 4\) の部分ネットワークが二つ存在し、それぞれ破線で囲まれている。以降では、これら二つの部分ネットワークをそれぞれ上段および下段の部分ネットワークと呼ぶ。

1. 次の置換で与えられるルーティング問題を考える:

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

   各パケットは上段または下段の部分ネットワークにルーティングする必要がある。\(0\) 以上 \(7\) 以下の整数を頂点に持つ単純グラフであって、\(B_{3}\) の二番目の列でパケットの衝突を避けるために同じ部分ネットワークにルーティングされてはいけない頂点の組の間に辺を持つものを示せ。辺は破線で書くこと。

2. \(\text{(a)}\) で解答したグラフに、最後から二番目の列でパケットの衝突を避けるために同じ部分ネットワークにルーティングされてはいけない頂点の組を結ぶ辺を実線で書き加えよ。

3. 完成したグラフの頂点に赤または青の色を割り当てよ。ただし、破線または実線で結ばれた頂点が同じ色になってはいけない。この彩色がどんな置換 \(\pi\) に対しても可能なのはなぜか？

4. 赤い頂点を上段の部分ネットワークに、青い頂点を下段の部分ネットワークに割り当てるルーティングにおいて、最初のリンクと最後のリンクを通り抜けるパケットをそれぞれ答えよ。図 \(\text{11.6}\) を参考にせよ。

5. 後は上段および下段の部分ネットワーク内部におけるルーティングを示せばよい。一つ方法として、ここまでに実行した手続きを二つの部分ネットワークに対して再帰的に適用すればルーティングは得られる。ただ、部分ネットワークは十分小さいので、試行錯誤でもルーティングは見つけられるだろう。この方法で完全なルーティングを示せ。

多重二分木ネットワーク (multiple binary-tree network) は \(N\) 個の入力と \(N\) 個の出力を持つ (\(N\) は \(2\) の冪)。それぞれの入力に対応して \(N/2\) 個の葉を持つ二分木が存在し、各入力から対応する二分木の根に向かう辺が存在する。これら二分木は根から遠ざかる方向に辺を持ち、入力木と呼ばれる。同様に、それぞれの出力に対応して \(N/2\) 個の葉を持つ二分木が存在し、各出力に向かう二分木の根からの辺が存在する。これらの二分木は根に向かう方向に辺を持ち、出力木と呼ばれる。

全ての入力木の全ての葉からは \(2\) 個の辺が伸びており、その終点は出力木の葉である。その対応は「入力木と出力木の任意の組が辺で結ばれる」と「全ての出力木の全ての葉には \(2\) 個の辺が向かう」を満たす。

1. \(N = 4\) の多重二分木ネットワークを図示せよ。

2. 次の表を埋め、解答の理由を説明せよ:

   \[ \def\arraystretch{1.2}\begin{array}{c|c|c|c|c} \text{ネットワーク} & \text{直径} & \text{スイッチの形状} & \text{スイッチの個数} & \text{輻輳} \\ \hline \text{多重二分木} & & & & \end{array} \]

第 11.3.1 項で触れたように、二次元格子ネットワークの輻輳は \(2\) である。\(N\) 入力 \(N\) 出力の二次元格子ネットワークを二つ重ねた 二層配列 (\(2\)-layer array) ネットワークを考える。\(N = 4\) の二層配列ネットワークを次に示す:

一般に、\(N\) 入力 \(N\) 出力の二層配列ネットワークは二次元格子上に接続されたスイッチの層を二つ持ち、一つ目の二次元格子に含まれるスイッチから二つ目の二次元格子の対応するスイッチへの辺が存在する。入力は左側から一つ目の二次元格子に接続され、出力は両方の二次元格子から下側に接続される。

1. 任意の入力と出力の対応関係に対して、輻輳が \(1\) となるパケットのルーティングが存在する。どのようなルーティングが説明せよ。

2. レイテンシを最小化するルーティングのレイテンシを求めよ。

3. このネットワークではパケットのレイテンシを最小化するルーティングの輻輳がネットワークの輻輳より大きくなると示せ。

\(5\)-路ネットワーク (\(5\)-path network) を次に示す。これを一般化した \(n\)-路ネットワーク (\(n\)-path network) は容易に想像できるだろう。この二つのネットワークの性質をまとめた次の表を埋め、解答を説明せよ:

TA 業に退屈した Megumiメグミ は、誰も思い付いたことのない優れた通信ネットワークを発表して有名になろうと思い立った。彼女が考案したネットワークは次の通りである: 全ての入力パケットはバタフライネットワーク、Beneš ネットワーク、そして二次元格子ネットワークに接続され、これらの出力が最終的な出力に接続される (下図)。

この Megumi ネットワークでは、レイテンシを最小化するルーティングが最小の輻輳を持たない。最小輻輳レイテンシ (latency for min-congestion, LMC) とは、輻輳を最小化するルーティング全体を考えたときのレイテンシの最大値を意味する。同様に、最小レイテンシ輻輳 (congestion for min-latency, CML) とはレイテンシを最小化するルーティング全体を考えたときの輻輳の最大値を意味する。

Megumi ネットワークの性質を表す次の表の空欄を埋め、解答を説明せよ:

Louisルイ Reasonerリーズナー は次のことに気が付いた: Beneš ネットワークは確かに優れているものの、バタフライネットワークにも利点がある。具体的に言えば、バタフライネットワークの方がスイッチが少なく、直径が小さく、パケットのルーティングが簡単である。そこで Louis は両者の利点を持ち合わせる \(N\) 入力 \(N\) 出力のネットワークを設計し、Reasoner ネットワーク (Reasoner network) という控えめな名前を付けた。Reasoner ネットワークの説明を次に示す:

Reasoner ネットワークではレイテンシを最小化するルーティングが最小の輻輳を持たない。最小輻輳レイテンシ (latency for min-congestion, LMC) とは、輻輳を最小化するルーティング全体を考えたときのレイテンシの最大値を意味する。同様に、最小レイテンシ輻輳 (congestion for min-latency, CML) とはレイテンシを最小化するルーティング全体を考えたときの輻輳の最大値を意味する。

Reasoner ネットワークの性質を表す次の表の空欄を埋め、解答を説明せよ:

\(N\) 入力 \(N\) 出力のバタフライネットワーク \(F_{n}\) の輻輳は \(n\) が偶数のとき \(\sqrt{N}\) だと示せ。

ヒント:

• 入力から出力への路は一意なので、輻輳は全てのルーティング問題を考えたときの特定の頂点を通り抜けるパケットの個数の最大値に等しい。

• バタフライネットワークの \(i\) 番目の列に属する任意のスイッチ \(v\) について、入力スイッチから \(v\) への路はちょうど \(2^{i}\) 個、\(v\) から出力スイッチへの路はちょうど \(2^{n-i}\) 個ある。

• 最悪の輻輳を持つのはバタフライネットワークの何列目か？ その列の最も上にあるスイッチの輻輳を求めよ。