Network Layer
さて、ようやくここまで到達した、という感じもする。下から数えて３番目、Network層について。
かの有名な（と私は思っているのだが）TCP/IPの後ろ半分、IPはこのNetwork層に属する（厳密に言えばちょっと違うが）プロトコルだ。
まず恒例の「Network層の役割」について書いてみる。
・ネットワーク内において、パケットを始点から目的点まで届ける。この場合ネットワークはMulti-Hop-つまりいくつもの異なるプロトコル、媒体を使用したものが相互に接続されていると考える。
・Transport層（Network層の上位層だが）に対するサービスの提供。ここでは（例によって）サービスは２種類考えられる。
１）Connection - Oriented Service：信頼度の高いパケットの伝送。このサービスにおける「伝送」にはエラーの対処、パケットを順番どおりに届けること及びフローコントロールを含む。
２）Connectionless Service：単にパケットのRouting（道を設定してとどけること）だけを行ない、他には何もしない（だからエラーがあろうと気にしないし、パケットの順番がでたらめだろうが気にしないし、どこかで渋滞が起こっていたとしてもまったく気にしない。つまりフローコントロールも行われない）
さて、私がいきなり「君はNetwork層だ。君のミッションはこれだ」といわれて、上に書いたようなことをとうとうと説明されたとしよう。まず私はしばし呆然とする、
次に考えることは、
「上記のサービスを提供するために、何をすればよいのだろうか。」
である。講義では、「何をするか」について、二つのモデルをあげて説明された。
(1) Virtual Circuit
これを無理矢理日本語に訳せば、「仮想回路」である。つまりネットワークの網の上に仮想的な回路を（道筋のほうがわかりやすいかな？）を作るイメージだろうか。やること及び特徴は以下のようである。
・論理的な接続をまずセットアップする。しかしながら、この接続用にバンド幅を確保する（つまり使える周波数帯をとってしまう）ことはしない。
・接続を区別するためにVirtual Circuit番号をふる。これが送られるパケットにとってはアドレスとなる。
・全てのパケットは、接続が続いている間、最初に設定された回路（道筋）にしたがって伝送される。（したがってパケットごとにRoutingを決定する必要はない）
・したがってパケットは順番どおり伝送されるし、フローコントロールも行なわれる。
・Virtucal Cirtuit上でネットワークの障害が起こった場合には、（当然のことながら）Virtucal Circuitはきれることになる。
・複雑な制御はNetwork層で必要。
・Connection - oriented service向き
(2) Datagram
Datagramという言葉は大変聞こえがよいが、これがどのような文脈で使われる言葉かは今一つわからない。やること及び特徴は以下のようである。
・セットアップは行われない。全てのパケットは送り元と送り先のフルのアドレスを持つ。（Virtual CircuitのようにVrictual Circuit 番号だけを持てば好いわけではない）
・全てのパケットはそれぞれ他のパケットとは関係なくネットワークの中を伝送されていく。
・ネットワーク上に障害がおこったとしても、別のルートがある限り問題にはならない。
・複雑な制御はTransport 層で必要。
・Connection-Oriented, Connectionless両方のサービスに用いられる。
さて、以上がNetwork層がその与えられたTransport層に対するサービスを提供するために行なうことだ。この二つを直感的に比べてみると、Virtual Circuitのほうが、なんだかよいように思える。Datagramでは、送るパケットがそれぞれに「自分はどこに向かったものやら」と判断しながらとおることになる。Virtual Circuitではそうした道順探しは最初に一度行なえば十分だ。
しかしながら実際にInternetで使われているのはDatagramである。
さて、このようなサービスを行なう上で（それがVirtual Circuitであっても、Datagramであってもだが）避けてはとおれない要素がいくつかある。Routing, Congestion Control-渋滞解消それにInternetworking-ネットワーク相互接続だ。それぞれについて以下に詳細を述べる。
N-1 Routing
この言葉が意味するところの概略は前述のとおりだが、詳細説明にはいるまえにまずは基礎的なアリゴリズムから。
ここではネットワークを以下のようなモデルとしてあらわす。
・全てのコンピューター及びルーターはグラフの中のノードとしてあらわす。
・コンピューター及びルーター間の接続はグラフの中のリンクとしてあらわす。
・全てのリンクには「コスト」がある。ここでいう「コスト」は例えば二つのノード間の伝送遅れだったり、そもそもつながっているのかいないのか（つながっていなければコストを無限大にするとか）であったり、スループットだったりする。さらに目的によっては他の定義もできるだろう。例えば文字どおりの「コスト」-そのリンクを通すのに必要な値段であるとか。
さて、ここで目的とするのは、始点から終点までのもっとも「短い」通路を発見することである。ここで言う「短い」とは「始点から終点までの経路のコストを足しあわせていって、その総和がもっと少ない」という意味であり、物理的な距離が「短い」という意味ではない。実際インターネットなどでは、隣の都市にあるサイトにアクセスするのに、とんでもない（物理的な）距離を経由したりする。これは物理的な距離はどうあろうとも、そちらのほうが「コストが少なくて」到達する、と判断されるからなのだが。
しかしここではこのような仮定があることに注意しなければならない。「短い経路」を発見し、そこにデータを送ることが必ずしも「最適」の方法ではない、ということである。
たとえばＡからＢにデータを送ると考えたとしよう。ＡとＢの間にはほんのわずか「コスト」が異なる２本の経路がある。ここで複雑怪奇なアルゴリズムを駆使し、どちらかの経路の「コスト」が低いと判断、そちらに全部のデータを送る、というのがここで仮定している方法である。
ところが、その「経路」の太さが問題なく太ければよいが、そうでなければ、２本の経路それぞれに半分ずつデータを送ったほうが、全体としてみれば、渋滞が少なくスムーズにデータが流れるかもしれない。しかしながら今回議論する範囲では、あくまでも「最も短い経路」を求めることにして、話しをすすめる。なぜかといえば、そのほうがはるかに方式が「簡単」になるからだ。（とものの本には書いてある。最もこれから書く内容が「簡単」かどうかはまったく私の感知するところではないが）
・Dijkstra's アルゴリズム
この名前を見たとき、留学にいって最初の学期のことを思い出した（除く英語学校）私が履修したのはOperations Researchであり、最初にならった基礎的な内容のうち、一つがこのアルゴリズムだったからである。
閑話休題。まずは説明に必要ないくつかの記号の定義から。一連のノードがリンクによってつながっていると想定する。ここでノードiからノードjに行くときのコストをl(i,j)であらわすことにする。（ちなみにl(i,j)はl(j,i)と同一とは限らない）
さて、このネットワークで、ノード「ｓ」から各ノードに対する「最も短い経路」を探すことにする（それこそがこのアルゴリズムがやってくれることだ）手順は以下の通りになる。
・集合（懐かしい言葉でしょ）Nを定義する。最初はN=｛s｝である。
・Ｎにある各ノードｖについて、Ｄ（ｖ）＝ｌ（ｓ、ｖ）とする。（最初のステップでは、あたりまえだがＤ（ｓ）＝ｌ（ｓ、ｓ）であるが）
ここでＤ（ｖ）とはｓからｖまでの距離（とりあえずの）である。このアルゴリズムの動作が終了したときには全てのＤ（ｖ）がｓからの最小距離になっていることが期待されることになる。
・Ｎにないノードｗのうち、Ｄ（ｗ）が最小のものを見つける。そしてそのｗをＮに加える。
・Ｎに残っている各ノードｖに関してＤ（ｖ）を計算しなおす。ここで
Ｄ（ｖ）＝min（Ｄ（ｖ），Ｄ（ｗ）＋ｌ（ｗ，ｖ））とする。つまりＤ（ｖ）はＤ（ｖ）とさっきＮに加えたばかりのｗのＤ（ｗ）とｌ（ｗ、ｖ）の和（これはｗ経由でｓからｖに行く距離、ということを意味する）の最小値というわけだ。
・全てのノードがＮにはいったところで、計算はおしまい。
こうやって言葉でずらずら書いてもわかりにくいので実例をしめしてみよう。まず以降の説明で用いる「ネットワーク」のサンプルを以下に示す。
このネットワークに上記のアルゴリズムを適用すると結果（及び途中の計算経過）は以下のようになる。s=1、つまりノード１から他の全てのノードへの最短距離を求めることとする。
Step:0 N={1} D(2)= 2, D(3) =5, D(4) = 1, D(5) =∞、D(6)=∞
さて、ここで「Ｎにないノードｗのうち、Ｄ（ｗ）が最小のもの」はなにか、、と思うとＤ（４）＝１が一番小さい。というわけで４をＮに加える。
次に１と４以外のノードに関して、Ｄ（ｖ）の値を計算しなおす。
Step:1 N={1,4} D(2)= 2, D(3) =４（元々はＤ（３）＝５だったが、Ｄ（４）＋ｌ（４，３）＝１＋３＝４のほうが小さい）, D(4) = 1, D(5) =２、D(6)=∞
ここでＤ（ｗ）が最小なものは、、と思うとＤ（２）である。今度は２をＮに加える。
Step:2 N={1,2,4} D(2)=2, D(3)=4, D(4)=1, D(5)=2, D(6)=∞ 次にＮにはいるのは５
Step:3 N={1,2,4,5} D(2)=2, D(3)=3, D(4)=1, D(5)=2, D(6)=4 次にＮにはいるのは３
Step:4 N={1,2,3,4,5} D(2)=2, D(3)=3, D(4)=1, D(5)=2, D(6)=4 次にＮにはいるのは6（というか６しか残っていない）
Step:5 N={1,2,3,4,5,6} D(2)=2, D(3)=3, D(4)=1, D(5)=2, D(6)=4
これでおしまい。
このアルゴリズムが動いている経過及び結果を見ると、minimum spanning treeなるものができていることがわかる。（下の図参照）
つまり１からの最小経路をみると、ループのないツリー構造になって末端に各ノードがぶらさがっている状態だ。そして１からたどっていくと各ノードへの最小経路をたどることになる。
この情報が得られれば、１からどのノードに対してパケットを送る際にも、「どこを経由していけばよいか」がわかることになる。それが何を意味するせよ、とにかく「最短経路」でたどり着くことができるのだ。
このアルゴリズムを動かして、あるノードから各ノードに対する最短距離を計算する際には、（今迄の説明でわかる通り）ネットワーク全体にわたる情報が必要である。（つまり全てのリンクに関するコストの情報である）これは後で説明するBellman-fordとは対称的で、これは利点とも欠点ともなりうることは後述する。
・Bellman-Ford アルゴリズム
さて、このアルゴリズムでは、最短経路の探索は以下のように行われる。
・自分以外の各ノードｖに関して、(n,D(ｖ))というラベルをはる。ここでＤ（ｖ）とはその段階でのｖへの最短距離。ｎはＤ（ｖ）を計算した経路で、自分の次にあるノードの番号である。
・最初はすべての自分以外のノードに関して（・、∞）としておく。
・Ｄ（ｖ）←min w(D(w)+l(w,v))という数式でもってＤ（ｖ）及びｎをアップデートする。言葉で書くと
「自分にリンクがある各ノードｗごとに、Ｄ（ｗ）＋l(w,v)を求め、その値が一番小さくなるｗを求める」
ということになろうか。
・全てのＤ（ｖ）が変化しなくなったらおしまい。
例によって先ほどのサンプルネットワークにこのアルゴリズムを適用してみよう。
かような結果になる。得られるものはDijkstraのアルゴリズムと同じくminimumspanning treeだ。
本講義で配布された資料には「このアルゴリズムはより分散した環境に適する」と書いてある。これはどういうことか。
あるノードから別のノードに「最短経路」をとおってデータを送ろうとする場合、最初に一度計算してしまえばことたれり、とするわけには行かない。常にアップデートが必要なわけだ。そしてそのためには最短経路計算に必要な情報を周期的に集める必要がある。前述した２種類のアルゴリズムのうちで、どちらがそれを容易に行なうことができるか。
Bellman-Ford アルゴリズムにおいては、計算に必要な情報はすべて、自分（l(w,v)だ）か自分にリンクされたノード(D(w))に存在している。つまり定期的な情報アップデートに必要な情報交換は、隣のノードとだけ行なえばよいことになる。
それにたいしてDijkstraのアルゴリズムでは集合Ｎが大きくなるにしたがって、自分からいくつかリンクが離れたノードの情報も取得する必要がでてくる。つまり情報アップデートに必要なデータのやりとりがBellman-Ford にくらべて大変になる、ということである。
しかしhttp://www.cs.williams.edu/~tom/courses/336/outlines/lect23_2.htmlには、逆にDijkstraのほうが、ネットワーク中の状況変化（つまりはコストの変化だが）に早く対応できる、という例がしめされている。Bellman-Fordが自分の近くのノードの情報だけで「最短経路」を設定するのがあだになり、ネットワークのある場所で発生した「変化」が全体に伝わるのに時間がかかる、あるいは、自分の近くしか見ていないゆえにまったく間違ったルーティングの結論を導き出す、ということらしい。詳細に興味のある人はリンクさきを見てほしい。ここでは
「Bellman-Fordにはこのような問題があるために、Dijkstraのアルゴリズムのほうが最短経路探索においてよりよい選択とみられている」と結論づけられている。
（実際この二つのアルゴリズムの比較には、なんとなく深いものを感じる。とりあえず手短にある情報だけで判断するほうが早いのは確かだが、とんでもなく間違った結論を導き出す-私の周りではLocal Minimumと呼ばれている-ことになる。「まずは全体の状況の把握から」とは判断や決断にともなう責任を逃れるために大変有効な言い回しだが、それがその言葉どおり行われた場合には最初の情報収集に時間がかかるかもしれないが、より適切な判断を下せる可能性が高い。
さて、次には色々なルーティング技術の説明に入る。