日付：2000/6/23
この文章について | ネットワークの動作概要 | Physical Layer：物理層 | Media Access Control SubLayer | Logical Link Sublayer | Network Layer | Transport Layer
Network Layer-Part2さて、ではずらずらとルーティングのアルゴリズムをならべる前にまずは分類学から。本講義の資料には「ルーティングはポプリ（ここでは混成、もしくは雑集という意味か）だが部分的に分類することは可能である」と書いてある。
・Adaptive(もしくはDynamic) ： ネットワークの込み具合、及び接続形態を考慮してルーティングを変更する。
・Non-adaptive(Static) ：最初に設定したルーティングを使いつづける。
・Centralized：ルーティングコントロールセンター（というよりはこの形容があてはまるもの）で各ノードからネットワークの情報を集め、ルーティングを決定。その情報を各ノードにダウンロードする。
・Distributed：ルーティングの決定は各ノードで行なわれる。ネットワークの情報はノード間で交換される。
・Isolated：一番単純な形態のDistributed アルゴリズム。明示的にはノード間でネットワークに関する情報を交換しない。（そんなものが可能かと思うかもしれないが、後でいくつか例がでてくる）
さて、このような分類方法を念頭において、いくつかのルーティング方法を見てみよう。
・Flooding：
Floodには「洪水」という意味もある。基本的には、受け取ったパケットを自分につながっているリンクすべて（とはいってもパケットを受け取ったリンクは除く）に送信する。（だからFloodなわけだ）
この方法はわけもへったくれもなくとにかく始点から終点までつながっている経路があればパケットが届けられるので堅牢ではある。しかし一つのパケットのコピーがやたらめったらに作成されることになる。おまけにその作成されたコピーはいつまでもネットワークの中をかけまわってしまう。
これを避けるためには
(i)ノードを追加した回数(hop count)を記録しておいて、ある回数を超えた場合にはパケットを捨てる
(ii)以前通過したことがあるパケットを捨てる
などの方法をとることができる。
また改良型として、Selective Floodingなる方法もある。これは全てのリンクに対してコピーを送信するのではなく、ある条件にあったリンクだけにコピーを送信する方法だ。例えば「一般的に言って」目的のノードに近いリンクに送信するとか。。。とノートには書いてあるのだが、どうやって「一般的に言って目的のノードに近いリンク」を識別するかは定かではない。
さて、派生型として、Random Routingというものもある。これはパケットを送信できるリンクが複数ある場合、乱数をふって送り先を選ぶ、というものだ。こんな方法ではいわば酔っ払いが千鳥足でふらふらと歩いている状況になるのではないか、と思うが、講義ノートによれば
"This technique is surprisingly efficient"
ということらしい。
根がいいかげんな私としては、このFloodingに区分される技術には大変心引かれるものがあるのだが、これらの方法が実世界でどの程度使われているかについてはわからない。-と書いていて思い出した。私はこのFloodingが使われている通信システムにかかわったことがある。そのシステムでは「リンクされている全てのノードにパケットを送り出す」方式を確かにとっていた。なぜかといえばそのシステムは
「通信を妨害されるのが当然で、その環境下で動くことが期待される」
ものだったからだ。例えば小さな赤ん坊がいる家での家庭内LANなどはこうした性質が要求されるであろうが。
・Directory Routing：
ディレクトリとはコンピュータの世界ではよく使われるが、ここでは「住所録」という意味がぴったりなのだと思う。
基本的なアルゴリズムは以下の通りである。全てのノードは、目的地ごとにどのリンクにパケットを送るか、という情報を表（テーブル）として持っている。この表はシステムコンフィグレーション時にネットワークの情報を推定したデータにより、最短経路探索アルゴリズム（前述した方法だ）を用いて計算される。
そして実際にパケットを送信する際は、目的地のアドレスと、自分が持っている表をつっつきあわせ、表にのっているリンクにパケットを送信するわけだ。
派生型としてMulti-path routingというものがある。これは目的地ごとに使用するリンクを一つ以上あげておき、実際にパケットを送信する際には「一定のアルゴリズム」にしたがってリンクを選択する、という方法だ。
この表をネットワークの状況（トポロジーとか込み具合）によってアップデートすると、Adaptiveなルーティング方法となる。
・Centralized Routing：
先ほどの説明と同じく、Routing Control Centerがノードからネットワークの情報を集め、ルートを計算、結果をノードにダウンロードする方法である。各ノードは最低Routing Control Centerにどうやって情報を送ればいいかは知っておく必要がある。
この方法では最適なルーティング方法を計算することができる可能性があるが、Routing control centerが機能しなくなった場合、もしくはノードとの間で通信ができなくなった場合にはダメージが大きい。またネットワークの情報をノードが取得して、最適ルーティング情報がダウンロードされるまで時間遅れがあるため、ネットワークの状況がそれまでに変化してしまい、せっかく計算した「最適ルーティング」が「最適」でなくなってしまう可能性もある。
・Isolated Routing
この名前で括られるものにはいくつかの方法があるようだ。
(1) hot Potato
まず講義ノートにはいきなり"Hot Potato"という言葉が出てくる。これはこれから説明するアルゴリズムの名前である。
やることは以下のようである。受け取ったパケットを「送信待ち」の状態にあるパケットの列が一番短いリンクに送り出す（正確にはそのリンクの送信待ち行列に登録する）のである。思うに手の中で高温を発する芋をとにかく早く送り出せる可能性があるところにまわす、ということであろうか。（不幸にして講義でなんと説明されたか覚えていないが）
(2) Backward Learning
全てのパケットは、自分がどこから送られたかと、いくつのノードを経過したか(hop count)を記録しておく。それを受け取ったノードは、それらの情報からあるノードに情報を送るためには、Hop countがいくつでどのリンクに送り出せばよい、ということを「学習」できるわけである。
この方式の問題は、状況が悪くなった、ということを学びようがない、ということである。パケットがこなければ「学習」のしようがないからだ。だから例えば最初はうまく動いていたリンクがダウンしたとしても
「この目的地にはこのリンクに送り出せばHop Countいくつで届くはずだ」
という情報はそのまま残ってしまう。
これを防ぐためには、周期的に学んだことをクリアしてしまう必要がある。つまり「過去の美しい思い出」にすがってルーティングをやるのを防ぐために頭を空にするのである。
・Delta Routing
これはCentralized RoutingとIsolated Routingの複合型である。アルゴリズムは以下の通り。
(1)全てのノードはリンクごとの「コスト」を測定し、定期的にRouting Centerに送る。
(2)Routing Centerでは送られてきた情報を元に、２点間の最適経路（上位ｋ個）を計算する。ただし選ばれた経路の間でコストの差がδ以下である場合にはそれらの経路は同等とみなす。
(3)Routing Centerは「同等に最適経路（複数かも）」の情報をノードに送信する。
(4)ノードは送られてきた「最適経路」のなかから前述したIsolated Routingの方法を用いてルーティングを行なう。
この方法はδの値の選び方によって、異なった挙動を見せる。δが０だとRouting Centerが全ての経路決定権利を持つことになり、Centralized Routingと同じとなる。逆にδが∞だとノードが全てのRouting決定権を持つことになる。
・Optimal Routing
(1)このルーティングを考える際には、まずSink Treeというものを考える。つまりあるノードに全てのノードからの最短経路をつないでいくと、木のような形になる。（先ほどの例であげたMinimum spanning treeのように）根っこは「あるノード」である。
(2)（とりあえずこの最初のtreeをどのように計算したかは問わないとして）通常にネットワークが動いている間はこのツリーにしたがってルーティングを行なう。
(3)ノード、もしくはリンクがダウンした場合は、そのダウンした個所より上流側（つまり目的地のノードと反対側）にあるノードは別の経路を探さなくてはならない。
この際、自分より上流側のノードに聞いてみても無駄である。なぜなら自分と同じ問題をかかえているはずだからだ。したがって「木」の別の枝にあるノードに「別の経路がない？」と聞いてみる。（そして定義によれば別の木にあるノードは他の経路を持っているはずだ。）
この例としてはChu's Algorithmなるものがあげられているが、その動作はほぼ上記の記述と同じなので省略する。
・Hierarchical routing
最初の「ネットワークは階層構造」という例をもし頭の中にちょこっとでも覚えていて、ここまでの説明を読んだ人であればある疑問が頭に浮かんでも不思議ではない。つまり
「ノードは全てのほかのノードに対する最短経路の情報をもたなければならないのか？オフィスの中で５台のマシンをつないでいるLANであればいいが、インターネットはどうやってるんだ？まさかWhite houseのWeb Pageを公開しているマシンが、私のパソコンまでの最短経路情報をもっているわけではあるまい」
使用するアルゴリズムによっては別に経路全体を覚えておかなくても、「最初の一歩」だけ覚えておけばよい例もある。しかし一台のノードが管理できる「宛先とそこへの最短経路」情報には限りがあるはずだ。ではどうするか。
一つの方法は、ネットワークを「区域」に区分することだ。そして「区域」と「区域」の間にはゲートウェイを設ける。そしてゲートウェイは他のゲートウェイに到達するにはどうすればよいか、の情報を持つ。「区域」内のノードは同じ区域内のノード（含むゲートウェイ）に到達するための情報だけを持てばよい。
この方法だと、まず「全てのノードが他の全てのノードへの行き方を知っている」ような状態からは開放される。また送り元と送り先が別の区域に属する場合には
送り元→送りもとが属する区域のゲートウェイ→送り先が属する区域のゲートウェイ→送り先
といった具合にパケットが送られていくことになる。
こうした「区域分け」は階層的（また出てきた）にすることもできる。例えば（実際こうした方法を使っているかどうかは知らないのだが）電話をとってみよう。
まず最初の市外局番でもって、どの「市外局番エリア」に送ればいいかがわかる。次に局番をみると「市外局番エリアの下位に含まれるどの局」にまわせばよいかがわかる。最後に４ケタの数字をみれば誰につなげばよいかわかる、という寸法だ。
・Broad Casting
これは「最短経路」の探索方法ではないが、ネットワークを組む上で必要になる技術だ。つまり「ネットワーク上の全てのノードに同時にパケットを送る」ことである。
これにはいくつかの方法がある。
１）ノードがすべて媒体を共有している場合（これはMAC layerのところででてきた話しだ）には話しは簡単で「送り先アドレス」のところを「全てのホスト」としておけばよい。
２）Multiple uni-casting：全てのノードの数だけパケットのコピーを作り、それぞれに送信する方法。確かに全てのノードに情報は届くのだが、無駄が多い（他のノードへのパケットを中継するノードは、それ自体にパケットが送られてこなくても情報を知ることができる。）
３）前述したFlooding。私は意味もなくこの方法が気に入っているが、パケットをやたらと量産するので、無駄が多いことでは変わりはない。
４）Multi-destination Routing：パケットを送りたい目的地をリストアップし、そこに到達するためにはどのリンクにパケットを送り出せばよいかを調べる。そのリンクにパケットを送信する。途中中継するノードでは、リンクごとにパケットをコピーし、それぞれの目的地に向かってそれぞれ送信する。
この方法ではルーターでパケットを複製するためルーターの性能を落とす可能性がある。
と書いては見たが、、、正直いって次に説明するSource spanning treeとの区別が今一つわからない。。
５）Source spanning tree：パケットを送る元から伸びるSouce spanning treeを考える。そしてノードをとおるたびにそのツリーに属するリンクだけにパケットのコピーを作成して送信する。
このアルゴリズムが働くためには、全てのノードがおなじルーティングの情報を持っていることが必要となる。
６）Revers path forwarding：前述したSink Treeを活用する。ノードＸからパケットが届いたとしよう。そしてこのパケットがノードＸに対するSink treeにあるリンクからきた場合、このパケットは最短経路をたどってきたことになる。
したがって今パケットを受け取ったばかりのリンクを除いた全てのリンクに対して同じパケットを複製して送信する。
もしパケットがSink Treeにないリンクから到達した場合、これは既に受け取ったパケットのコピーが「最短でない」ルートをたどってたどり着いたものだと考え、捨ててしまう。
某web siteには「これは簡単に実現でき、かつバンド幅を無駄遣いしない」と書いてある。私としてはただそれを左から右に書き移すしかないのだが。
さて、最後に（本当に最後かは別として）さまざまなネットワークでどのようなルーティングアルゴリズムが使われているかをあげておく。各ネットワーク名が何を意味しているかを細かく聞かないように。ただこれまで説明したいろいろなテクニックが使用されている、ということだけわかってもられればよいのだと思う。
ARAPANET：Distributed routing。伝送遅れをコストとして使用
TYMNET：Centralized routing。伝送遅れをコストとして使用
TRANSPAC（フランス）：Delta Routing
DATAPAC（カナダ）：Distributed Routing.バンド幅をコストとして使用。リンクが切れた場合のみルーティングを変更する。
SNA(IBM)：Static Routing
DECNET(DEC-Compaq):Distributed Routing.バンド幅をコストとして使用。