Routing Information
Protocol Ver.2
RFC:2453
情報工学専攻 廣川研究室
古賀 康則

発表の手順• ルーティング
• IGPとEGP• RIPの概要• トポロジーの変更– スプリットホライズン、ポイズンドリバース、トリガー更新• RIP2の拡張機能とパケットフォーマット
• routedと実行結果

ルーティングとは？
Network B• ルーターが正しい方向へパケッ
トを転送で
host B.1
きるように制御
ルータA

ルータB

Network A
host A.1

ルータC
Network C

Network A
はあっち静的制御と動的制御• スタティックルーティング– ネットワーク管理者が手作業でルートを設定する– 安定している– トラフィックや伝送障害の影響を受けない– ルーティングプロトコルのためのトラフィックが発生しない• ダイナミックルーティング– 自動的に経路を設定する– ネットワークの変化に自動的に対応– 自動的に最適な経路を選択– 障害時にバックアップ経路に自動切換え

ルーティングプロトコルの必要性• ネットワークの変化に対応しなければならない• 設定が多くて面倒• 自動的に最適経路を選択できる– あまりにも複雑なネットワークトポロジー• 自動的にバックアップ経路を選択できる– 障害に強いネットワーク

IGPとEGP• AS(Autonomous System：自律システム)– 独自の技術や方針で経路制御をしているもの（ISPなど）• IGP(Interior Gateway Protocol)– AS内部でルーティングに使われるプロトコル• RIP,RIP2,OSPF• EGP(Exterior Gateway Protocol)– AS外部でルーティングに使われるプロトコル• EGP, BGP, IDRP

距離ベクトルアルゴリズム• ベクトル＝ネットワーク
ルーターを通過するたびに距離１が追加される• 距離＝通過するルーターの数

133.5.7.0

R

Destination = 133.5.7.0
Distance = 0

RDestination = 133.5.7.0
Distance = 1

R

Destination = 133.5.7.0
Distance = 2

同じ宛先には距離の小さいほうを選択
メトリックと呼ぶ
Metric = 1

start R

Metric = 2

R

選択される
Metric = 3

goal
RMetric = 4
選択されないMetric = 1

R

Metric =2

Metric = 3

R

同じ宛先で距離が同じ時には、最初に到達した経路を選択

経路情報の広告

133.5.7.0

R

３０秒ごとに自分の持っている経路情報をブロードキャスト

133.5.17.0

RIPで管理される情報• destinationのIP• next hop(destinationへの最初のルータ）• metric（１から16までの整数値）• route change flag（最近のルートの変一組ずつルーターのテーブルに登録されている更の有無）
RIP2ではsubnet maskも必要• タイマーRIPのパケットフォーマット（１）• UDPデータグラムを通信に使用– ポート５ングテーブルの要求
２０番(送受信、RIP1/2)
request:ルーティ
response:ルーティングテーブルの返送

RTEｓ
２５個

RIP or RIP2

Comman Version(must be zero(2)RIPd(1)
1) Entry (20)：
RIP Entry (20)
括弧の中の数字はオクテット

RIPのパケットフォーマット（２）RTEの部分Address Familymust be zero (2)IPv4Identifier(2) address (4)must be zero (4)must be zero (4)Metric(4)RIPではIPv4を表すAF_INETをサポート

外部からRIPパケットを受け取ったとき（１）RIPパケット

１．要求メッセージ
２．応答メッセージR
要求パケットをRIPのポート以外のUDPポートで受信したときは、単一のルータ宛の要求として処理される
要求パケットのaddress family identifierが０でメトリッ
クが16であるときには自分のテーブルを全部返す

外部からRIPパケットを受け取ったとき（２）２.Responseの場合パケットの理由

要求に対する応答
定期的な広告ルート変更に伴うトリガー更新

各エントリをチェックして必要なら自分のメトリックに１を加えてをテーブルを更新
以前のルートよりもMetricが優れているか？
新しいルート情報か？
Metricが１６を超えていないか？など

Response

RIP応答の処理
無視

port = 520?

ひとつのエントリを見る
無視

テーブルに登録
次ホップを設定
メトリックを設定
タイマーのリセット
変更フラグのセット

metric += 1
ルートはすでにある？
隣のルータから？

metric ==16?
メトリックは優れているか？

metric ==16?

metricは同じ？
タイマーのリセット

metricが16になるのは初めて？

削除タイマーを起動

YesNo外部へパケットを送る場合要求に対する応答(unicast)
定期的な広告(broad/multicast)
ルート変更に伴うトリガー更新(broad/multicast)

障害の発生とタイマー

133.5.7.0

R

１８０秒間アップデートメッセージがこないとルートのメトリックが16になり、ガーベジコレクションタイマ−が起動。
１２０秒経過するとルートは削除される。
障害発生！

133.5.17.0

その他にルートがあればそちらを選択
133.5.7.0

R

その他のルート
Metric = 16

Metric ≦ 15
133.5.17.0

トポロジーの変更への対応
１AB

１

１C

１１０

D: directly connetcted, metric 1
B: route via D, metric 2
C: route via B, metric 3
A: route via B, metric 3

D

ターゲット
ネットワーク１
BとDのリンクが切れた場合を考える１
ルータ
ーの騙し合いAB
１

１１ 障害発生！
targetCD

１
１０
BとDのリンクが切れた場合のルート情報の変化
時間

D dir, 1 dir,
B unrea C,
1C chB, 3 4A,A B, 3 4C,
4dir,C,
15A,5C,
5dir, ・・・ dir,
C,C,
1 6
1A, 6A,
11C, 6C,
1111dir,
C,
1D,
12C,
1112なぜ、騙し合いが起こるか？
AB
targetCD
Bを通るルートをB自身に広告している

お互いを通るルートを広告しあっている

D dir, 1 dir,
B unrea C,
1C ch
B, 3 4A,
A B, 3 4C,
4dir,C,
15A,5C,
5dir, ・・・ dir,
C,
C,
1 6
1A, 6A,
11C, 6C,
1111dir,
C,
1D,
12C,
1112

問題点
• 自分が広告されたルータを通るルートを、そのままそのルータに広告して返ABすことに問題がある
targetCDスプリットホライズン• シンプルスプリットホライズン– 広告されたルーターを通るルートをアップデートメッセージでは省略• ポイズンドリバース– 広告されたルーターを通るルートをメトリッ
クを１６にして返す

比較と問題点• シンプルスプリットホライズンよりもポイズンドリバースのほうが安全– お互いにルートを指し合っていても、ポイズンドリバースの場合はルートが即座に到達不可能と解釈される– シンプルスプリットホライズンの時はルートがタイムアウトするまで待つ• ポイズンドリバースは全ての逆ルートに対してメトリック１６を提示するので、アップデートメッセージが大きくなってしまう騙しトリガー更新AあいのループとB
targetCD

スプリットホライズンではループを防ぐことはできない
トリガー更新ルーターがルートのメトリックを変更するときは即座にアップデートメッセージを送信する

• Subnet
Maskのサポート
RIP２で拡張された機能– VLSM(Variable Length Subnet Mask)が利用できる• ルートタグ– AS間のEGP、BGPなどから利用する• 認証機能• マルチキャスト– 224.0.0.9がルーター間で定期的な情報交換に使われる• Next Hop– 全てのルーターでRIP2が機能していない場合に効率的
RIP2
RIP2
OSPF
OSPF

RIP２フォーマット（１）
ヘッダ のパケット
RTE１つ分を使用

Comman Version(unusedd(1)0xFFFF 1)
Authentication
Authentication(16)Type (2)plain textのパスワード
今のところ簡易パスワードを利用する方法のみ指定できる

RIP２のパケットフォーマット（２）RTEの部分Address Family
Route Tag (2)Identifier IP(2)address (4)Subnet Mask(4)Next Hop (4)Metric(4)RIPの実装とパケットのダンプ
http://matu.cc.kyushu-u.ac.jp/~koga/ds/ds.html• routed– 4.3BSDで標準配布される、RIPを実装したプログラム。最新のものはRIP２にも対応している• その他にRIP、RIP2を実装したものとしてgated,zebraなどがある

Routing Information
Protocol Ver.2
RFC:2453（つづき）
情報工学専攻 廣川研究室
古賀 康則

発表の手順
先週の内容• ルーティング
• IGPとEGP• RIPの概要• トポロジーの変更

今日はここから！

– スプリットホライズン、ポイズンドリバース、トリガー更新• RIP2の拡張機能とパケットフォーマット
• routedと実行結果

先週のまとめ（１）• RIPの動作概要– RIPを使うルータは隣り合うルータに自分の知っているルート情報を３０秒ごとにブ1〜１５までの数字が有効
１６は到達不能として解釈される
ロードキャスト（広告）
する
宛先ネット, コスト,
次ホップ, フラグ, サブネットマスク
ルート情報:(133.5.17.0, metric, 133.5.254.3, 更新フラグ, Subnet Mask)
R
133.5.17.0
R
133.5.7.0

R(133.5.254.3)
R先週のまとめ（２）• ルート情報１個の状態遷移ルート情報:(133.5.17.0, metric, 133.5.254.3, 更新フラグ, Subnet Mask)

新情報を登録ルーティングテーブル

２種類のタイマーで管理しているルーター内部
有効１

到達不能: metric →16
１８０秒

２

１２０秒

同じルートの広告を受けたらタイマーをリセット

削除
３広告パケットを受信した時の処
理

広 告

無視

port = 520?

テーブルに登録
次ホップを設定
メトリックを設定
タイマーのリセット
変更フラグのセット

ひとつのエントリを見る
無視
metric += 1
ルートはすでにある？
隣のルータから？

metric ==16?
メトリックは優れているか？

metric ==16?

metricは同じ？
タイマーのリセット

metricが16になるのは初めて？

削除タイマーを起動

YesNoトポロジーの変更
以下の順序で話を進めます• ネットワークの例とその問題点• RIPが実装している問題への対応策– ２台のルータ間での問題• 対応策１：スプリットホライズン• 対応策２：ポイズンドリバース– ３台以上のルーター間での問題• 対応策：トリガー更新

A

ネッ
トワークの例
メトリック
１
B

１

１

１C

１０

D

ターゲットネットワーク
１
ホスト

ルーター次ホッ メトリッD
直接１プ
ク
各ルータからターゲットネット
ワーク上のホストへのルート
B
D
２
情報
C
B
３
A
B
３

B 障害の発生

A

障害発生！

C

D

target１０
1.DからBへのルートの広告が途絶える。
2.180秒後、Bは「D→ターゲット」のルートのメトリックを16に設定する。この時点でA,Cは「B→D→ターゲット」のルートがあると思っている。
3.お互いにルート情報を広告する。

最初の広告B： メトリック１６のルート

A: メトリック３のルートを持っているをもっているAB
targetC
C: メトリック３のルートを持っているD

最初の広告のあと
B： C（A）を経由するメトリック

A: Cを経由するメトリック４のルートがある

A４のルートがある

BtargetC
C: Aを経由するメトリック
４のルートがあるD2回目の広告
A: メトリック４のルートを
B： メトリック４のルートを持っている

もっている

A

BtargetC
C: メトリック４のルートを持っているD2回目の広告のあと
A: Cを経由するメトリック
B： Cを経由するメトリック５の５のルートがあるA

ルートがあるB
targetC
C: Aを経由するメトリック
５のルートがあるDルーターの騙し合い

A

B

障害発生！

C

１０

Dtarget時間

D dir, 1dir, dir,B 到達不 C,
1 4 C,
1C B,
A, 4 A,5
能3
A B, 3C, 4 C,
55dir, ・・・ dir,
C,C,
1 6
1A, 6A,
11C, 6C,
1111dir,
C,
1D,
12C,
1112

なぜ、騙し合いが起こるか？
AB
targetCD

お互いを通るルートを広告しあっている

D dir, 1dir, dir,B 到達不 C,
1 4 C,
1C B,
A, 4 5A,
能3
A B, 3C, 4 5C,
5dir, ・・・ dir,
C,
C,
1 6
1A, 6A,
11C, 6C,
1111dir,
C,
1D,
12C,
1112

シンプルスプリット
ホライズン
自分が教えられたルーターには、「教えてもらったルート情報」の広告を行わない

AB

Cが広告をした場合
targetCD

AはCから聞いた情報をCに広告しない
2つのルーター間でループを作るような広告が起きないポイズンドリバース

自分が教えられたルーターには、「教えてもらったルート情報」のメトリックを16にして広告する
逆ルートの遮断AB

Cが広告をした場合

16

CDtarget

AはCから聞いたルート情報のメトリックを16にしてCへ広告
CはAからは宛先へ行けないと思う比較• シンプルスプリットホライズンよりもポイズンドリバースのほうが安全– お互いにルートを指し合っていても、ポイズンドリバースの場合はルートが即座に到達不可能と解釈される• ポイズンドリバースは全ての逆ルートに対してメトリック１６を提示するので、アップデートメッセージが大きくなってしまう騙しトリガー更新AあいのループとB
targetCD

ルート情報がループしてメトリックが16になるまで消えない

トリガー更新：メトリックの更新を加速
ルーターがルートのメトリックを変更するときは即座にアップデートメッセージを送信する

RIP２で拡張された機能（１）• Subnet Maskのサポート– VLSM(Variable Length Subnet Mask)可変長サブネットマスクが利用できる– IPアドレスの利用が効率化• ルートタグ（用途はさまざま）

BGP,EGP– RIP2のルーティングドメインで内部外部を区別
する
RIP2
RIP2
– AS間のEGP、BGPなどから利用する
BGP,EGP– その他

RIP２で拡張された機能（２）• 認証機能（次のスライド）• マルチキャスト– 224.0.0.9がルーター間で定期的な情報交換に使われる– ルーター以外はパケットの処理から開放される• Next Hop– パケットの余分なホップ数を減らす
RIP2– 特にネットワーク上の全てのルーターでRIP２
RIP2
RIP2
OSPF
OSPF
が使われていないときに効率的ルート情報を互いに交換できないオクテットRIP２のパケットフォーマット（１）ヘッダフォーマット
RIP2
RTE１つ分を使用

Comman Version(unusedd(1)0xFFFF 1)
Authentication
Authentication(16)Type (2)plain textのパスワード

RIP1
RTEｓ
２５個

今のところ簡易パスワードを利用する方法のみ指定できる

RIP1のヘッダ

Comman Version(must be zero(2)RIPd(1)
1) Entry (20)：
RIP Entry (20)

RIP２のパケッ
トフォーマット（２）RTE1個分のフォーマット
Address Family
Route Tag (2)Identifier IP(2)address (4)Subnet Mask(4)Next Hop (4)Metric(4)赤字のところはRIP１ではmust be zeroとなっていた

RIPの実装とパケットのダンプ
http://matu.cc.kyushu-u.ac.jp/~koga/ds/ds.html• routed– 4.3BSDで標準配布される、RIPを実装したプログラム。最新のものはRIP２にも対応している• その他にRIP、RIP2を実装したものとしてgated,zebraなどがある