11.1 ルーティング

本章で考えるネットワークの目標は、コンピューター、プロセッサ、電話といったデバイスの間でデータを通信することである。こういったネットワークで通信されるデータの一単位をパケット (packet) と呼ぶ。現実世界のパケットは固定サイズであることが多く、\(256\) バイトや \(4096\) バイトといった量のデータが一度に通信される。

11.1.1 完全二分木

まずは完全二分木 (complete binary tree) を考えよう。図 \(\text{11.1}\) に完全二分木で表された \(4\) 入力 \(4\) 出力のネットワークを示す。

この図および以降の図において、四角形は端末 (terminal) を表す。端末はデータを含んだパケットの送信元または宛先となるデバイスである。これに対して、円はスイッチ (switch) を表す。スイッチは内向き辺からパケットを受け取り、それを外向き辺のいずれかに転送する。つまり、パケットは入力端末から送信され、有向辺で結ばれたスイッチをいくつかたどって最終的な出力端末に到着する。

図 \(\text{11.1}\) では任意の二つの端末を結ぶ路が一つだけ存在するので、パケットを入力端末から出力端末まで誘導 (ルーティング) する方法は一つしか存在しない。図では入力端末 \(\text{in}_{1}\) から出力端末 \(\text{out}_{3}\) にパケットを送るときに利用される経路を赤で示してある。

11.1.2 ルーティングの問題設定

通信ネットワークの仕事はパケットをリンクに沿って移動させながら入力端末から出力端末まで送り届けることである。これから議論する様々な種類の通信ネットワークは \(N\) 個の入力端末と \(N\) 個の出力端末を持つとする。議論を簡単にするため \(N\) は \(2\) の冪だと仮定する。

それぞれの入力端末がどの出力端末にパケットを送信するかは \([0..N-1]\) の置換で表現できる。つまり置換 \(\pi\) がルーティング問題 (routing problem) を定義する: 各 \(i\) に対して、入力端末 \(i\) が持つパケットを出力端末 \(\pi(i)\) に届ける問題が \(\pi\) によって定義される。ルーティング問題 \(\pi\) の解は入力端末から出力端末への路を全て集めた集合 \(P\) であり、ルーティング (routing) と呼ばれる。言い換えれば、ルーティング \(P\) は \(i \in [0..N-1]\) に対する \(i\) から \(\pi(i)\) への路 \(P_{i}\) を集めた集合である。