このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。
画像を含めて印刷したい場合は Java の機能を切って下さい。 (firefox 1.5 では複数枚の画像の印刷はできませんでした)。
ここでは、ダイナミックルーティングの一方式であるリンクステートアルゴリズ ムを採用している OSPF について解説します。 OSPF(Open Shortest Path First Version 2 RFC 2328)はリンクステート型のルーティン グプロトコルです。
OSPF は IGP、 つまり一つのネットワーク管理下にあるネットワークで使用し
ます。
独立した一つの管理ネットワークを自律システム(Autonomous System AS)と呼
ばれます。
ネットワーク間の接続は AS で行います。
この AS という言葉を使うと、IGP は AS 内ルーティングプロトコル、 EGP
は AS 間ルーティングプロトコルと言うことができます。
AS は通常はプロバイダーなど大きなネットワークになりますが、東京電機大
は一つの AS になっています(AS番号 17943)。
OSPF で扱えるネットワークの形態は次の 4 つです。
ローカルなネットワークごとに代表ルータを決定する一旦リンクステートデータベースができた後は定期的な Hello を流すだけな ので通常のトラフィックは少ない。 また、障害が発生した際も、障害を発見したルータ自ら変更部分の LSA を流 すか、あるいは障害を他のルータが Hello などで検知した後に変更部分の LSA が一回流れるだけなので、障害時の対応は即座に行われる。
OSPF ではまず、 Hello プロトコルにより Neighbor と呼ばれる隣接ルー タを探します。 そして、 Neighbor が決まったところでネットワーク毎にDisignated(代 表)ルータ を決めます。 そして、リンクステート広告を行います。
ルータの周りの接続状況は、各ルータが自分がどのネットワークへ接続してい るかをメトリックを添えてマルチキャスト、または、 adjacent に従って広告 します。 ネットワークがそのルータと接続しているかは代表ルータが広告します。 ネットワークからルータへはメトリック 0 で送ります。
リンクステートデータベースとはネットワークとルータの接続情報のデータベー スです。 これは LSA を集めたもので、ネットワークの接続情報の有向グラフを表現し ます。 グラフの頂点になるのはルータとネットワークです。 ルータ同士が直接 Point-to-Point ネットワークにより接続している時、ルー タ同士を相互に辺で結びます。 ネットワークに対してルータがインターフェイスを持つ時、ルータからネット ワークへ有向辺がひかれます。 ネットワークからルータへ有向辺が引かれるかどうかはネットワークの種類に よります。 ネットワークがそのネットワークを通過するトラフィックを扱うか否かで、ト ランジットネットワーク、スタブネットワークに分けます。 そして、トランジットネットワークのみ、ルータへ辺を引きます。 また、ルータからネットワークへは 32bit の整数でメトリックを設定します。
すべてのルータが通信により同じリンクステートデータベースを持ちます。 これは、各要素にメトリックが入った隣接行列で表現します。 なお、ネットワークからルータへの辺のメトリックは0 とします。 次のネットワークの例に対して、隣接行列は次のようになります。
| RT1 | RT2 | RT3 | RT4 | RT5 | RT6 | RT7 | RT8 | RT9 | RT10 | RT11 | RT12 | N3 | N6 | N8 | N9 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| RT1 | 0 | |||||||||||||||
| RT2 | 0 | |||||||||||||||
| RT3 | 6 | 0 | ||||||||||||||
| RT4 | 8 | 0 | ||||||||||||||
| RT5 | 8 | 6 | 6 | |||||||||||||
| RT6 | 8 | 7 | 5 | |||||||||||||
| RT7 | 6 | 0 | ||||||||||||||
| RT8 | 0 | |||||||||||||||
| RT9 | 0 | |||||||||||||||
| RT10 | 7 | 0 | 0 | |||||||||||||
| RT11 | 0 | 0 | 0 | |||||||||||||
| RT12 | 0 | 0 | ||||||||||||||
| N1 | 3 | |||||||||||||||
| N2 | 3 | |||||||||||||||
| N3 | 1 | 1 | 1 | 1 | ||||||||||||
| N4 | 2 | |||||||||||||||
| N6 | 1 | 1 | 1 | |||||||||||||
| N7 | 4 | |||||||||||||||
| N8 | 3 | 2 | ||||||||||||||
| N9 | 1 | 1 | 1 | |||||||||||||
| N10 | 2 | |||||||||||||||
| N11 | 3 | |||||||||||||||
| N12 | 8 | 2 | ||||||||||||||
| N13 | 8 | |||||||||||||||
| N14 | 8 | |||||||||||||||
| N15 | 9 | |||||||||||||||
| H1 | 10 |
このリンクステートデータベースに対して、各ルータはダイクストラ法により、 自ルータから最短経路木を計算します。 例えば、 RT6 が最短経路木を計算すると次のようになります。 但し、外部ネットワークである N12 の取扱は次の節でしますので、ここでは二つ経路 が書かれてます。
以下のダイクストラ法により各頂点への最短距離を求めます。
これをもとにルーティングテーブルを計算すると次のようになります。
| 宛先 | 転送先 | メトリック |
|---|---|---|
| N1 | RT3 | 10 |
| N2 | RT3 | 10 |
| N3 | RT3 | 7 |
| N4 | RT3 | 8 |
| Ib | * | 7 |
| Ia | RT10 | 12 |
| N6 | RT10 | 8 |
| N7 | RT10 | 12 |
| N8 | RT10 | 10 |
| N9 | RT10 | 11 |
| N10 | RT10 | 13 |
| N11 | RT10 | 14 |
| H1 | RT10 | 21 |
| RT5 | RT5 | 6 |
| RT7 | RT10 | 8 |
外部ネットワークへのメトリックを処理するのに、二種類の方法が選べます。
ルーティングを簡単にし、ルータやネットワークの負荷を減らすために、 AS
をエリアに分割することができます。
エリアには 32 bit のエリア番号が付きます。
エリア 0 はバックボーンと呼ばれます。
そして、それ以外のエリアはすべてバックボーンに接続します。
これはスターグラフという形になります。
バックボーンが中心部のハブとなり、他のエリアはスポークになります。
このようにすると、通常のエリア内のルータはエリア内だけは、リンクステー
トデータベースを作りルーティングテーブルを計算しますが、
他のエリアへは基本的にはバックボーンへと送ります。
つまり、他のエリアの情報はエリア 0 で入ってくる外部ネットワークの情報
を Type 1 で計算したようになります。
その結果、エリア外のリンクステート情報を扱う必要がなくなりますので、効
率が上がります。
このとき、バックボーンのルータは、バックボーン内のルータと、各エリアか らのネットワークの情報を元にルーティングを計算します。 別エリアのリンクステート広告は受けとらないので、負荷は減りますが、すべ てのネットワークに対してどのエリアに含まれているかの情報は受けとります。
バックボーンと他のエリアにまたがっているルータ(エリアボーダルータ)は、 バックボーンと他のエリアの両方のルーティングを計算する必要があります。 そして、バックボーンには他のエリアにあるネットワークへのメトリックの情 報を、他のエリアにはバックボーンから得られるすべてのネットワークへのメ トリックの情報をそれぞれ流します。
なお、このエリアはすべてバックボーンと接してなければならないという原則 を破るためにバーチャルリンクという設定があります。 これは特定のルータに対してバックボーンからのスタティックルーティングを 設定することにより、そのルータもバックボーンのルータとするものです。 これにより、バックボーンに接していないエリアを作ることができます。 またさらに、バックボーンでないエリア同士が接している時、通常はバックボー ンを介さないと通信ができませんが、その接しているルータにバーチャルリン クを張ることでそのルータを介して通信をすることができます。
バックボーンと一箇所でしか接していないエリアを スタブエリア と呼びます。 このスタブエリアは他のエリアのネットワーク情報の代わりに、エリアボーダ ルータへデフォルトを指定するだけでルーティングテーブルが完成しますので、 ルータの計算が楽になります。
RIP は UDP の 520 番ポートを使用しますが、 OSPF は TCP や UDP とは別の 独自のプロトコルを IP の上で使用します。 また、 OSPF はマルチキャストを使用します。 但し、 TTL は 1 とするためルータを介した中継はしません。 使用するマルチキャストアドレスは全ルータに対しては 224.0.0.5 を、各 代表ルータには 224.0.0.6となります。