インターネットプロトコル階層とOSI

ネットワーク層（ルーティング）
1
ルーティング
Destination
Source
メトリック：最適化すべき指標
・ホップ数
・所要時間
：最適ルート（経路）
：迂回ルート
2
ルーティングとは
ルーティングとは，「転送する経路を選ぶこと」
3
ルーティングとは
サブネットAから192.168.2.10という宛先パケットを受信すると，
マスクをかけ算して，192.168.2.0とわかる．これはサブネットB行
きとわかり，eth2という出口にパケットを送る
4
ルーティングとは
ルーターAは，サブネットA,B,C以外への経路を知らない．
それ以外のパケットが来たらデフォルトゲートウェイであるルー
タBにパケットを送る
5
ルータ
ルータの主な機能
 ルーティングテーブルの管理
この宛先へ送るにはどのルータへ飛ばせば良いか
 ＩＰデータグラムのフォワーディング
次のルータへデータグラムを送る
 ＩＰデータグラムのフィルタリング
不正なデータグラムの廃棄
 ルーティングプロトコルによるテーブル作成情報交換
経路情報の交換
（最適）経路の計算
6
ルーティング方法

静的ルーティング(static routing)
 利点：制御トラフィックが生じない
 欠点：設定管理が困難、動的経路変更が不可能
 動的ルーティング(dynamic routing)
 利点：設定が容易、動的経路変更が可能
大規模ＮＷ向き
 欠点：制御トラフィックが発生
それぞれ設定
（トラフィック）
情報交換
それぞれ設定
Routing
table
Routing
table
Static routing
Routing
table
Routing
table
Dynamic routing
7
ルーティングの階層
 黎明期のインタネットは，単一の「ネットワーク」
であり，フラットな経路制御が行われていた（「ド
メイン」は１つだけ）．
 その後，インタネットをＡＳに分割し，ＡＳ内とＡ
Ｓ間のニ階層での経路制御に移行．
 ＮＷ規模の拡大に伴う経路制御オーバヘッドおよび経路
表エントリ数の増大への対処．
 遠隔ネットワークの障害情報による経路再計算の回避．
 組織内ネットワークの詳細の隠蔽．
 組織のポリシーに基づく独自の経路制御設定の許容．
8
ルーティングの階層
 ＡＳ：Autonomous System(AS),自律系，自律ＮＷ
（ルーティング）ドメイン
 「管理主体を同じくするルータおよびネットワークの集
合（A set of routers and networks under the same
administration）」
 ドメイン間経路制御の単位．転送・経路制御に関して，
独自のポリシーを持つ．
 同一ＡＳ内のトラフィックはＡＳ内部のみを通る．
 ＡＳ内部の構造は外部に隠蔽
 ＡＳ番号：２byte，IANA（Internet Assigned Numbers
Authority）が割当．
9
ＩＧＰ，ＥＧＰ
 IGP：Interior(Internal) Gateway Protocol
 ＡＳ内部の経路制御のためのプロトコルの総称．
 １つのＡＳ内で複数のＩＧＰを協調動作させても構わない．
 EGP：Exterior(External) Gateway Protocol
 ＡＳ間の経路制御のためのプロトコルの総称．
10
ルーティングアルゴリズム
 距離ベクトル (Distance Vector) アルゴリズ
ム
 各ルータは，自分がどのネットワークに(直接 or 間
接に)配送可能かを隣接ルータに公告
 IGPであるRIPで使用
 リンクステート (Link State) アルゴリズム
 各ルータは，自分が直接接続しているネットワーク
を全てのルータに公告(flooding)
 全ルータがネットワーク全体のトポロジを把握
 IGPであるOSPFで使用
11
ＲＩＰ(Routing Information protocol）




Distance vector型
30秒おきに自分の持つ経路情報をbroadcast
180秒間経路情報がこない → 経路を削除
最大ホップカウント＝ 16
 大規模ネットワークでは利用不可
○
×
×
×
直感的に理解しやすく、実装が簡単
経路数に比例して交換される経路情報が増加
経路の変動が伝わるのに時間がかかる
サブアドレスを認識しない
12
IGP系プロトコル
ＲＩＰにおける経路情報の伝播
NW A
Router 2
NW D
NW C
Router 1
経路情報
NW B
Network Metric
A 1
B 1
D 1
到達可能ＮＷと距離情報
経路情報
Network Metric
A
B
C
D
2
2
1
1
13
距離ベクトルアルゴリズム
 数字はネットワークアドレス相当．リンクコストは全て１とする．
step1：初期化時，各ルータは自分自身への経路のみを持つ．
ルータＡ上の経路表：to A，local，cost 0 [A1]
ルータB上の経路表：to B，local，cost 0 [B1]
step2：各ルータは保持する経路表を接続するサブネットにブロードキャスト．
step3：経路情報を受信したルータでは
 当該経路を持っていない場合，
 or受信したリンクのコストを加えて，すでに持っているコストより小さい場
合に経路情報を更新
[A1]到着後のBの経路表：to B，local，cost 0 [B2]
to A，
1，cost 1
 そうでなければ捨てる
step4：step2に戻って繰り返し
14
経路の伝搬
Aに関する経路情報の伝搬を示す
(1)初期化時，Aに関する情報はAにのみある．
ルータA上の経路表：to Ａ, local, cost 0
[A1]
(2)Aは[A1]をリンク1,3にブロードキャスト．B,Dが[A1]を受信し，経路表に加える．
ルータB上の経路表：to Ａ,
1, cost 1
[B2]
ルータD上の経路表：to Ａ,
3, cost 1
[D2]
(3)Bは[B2]をリンク1,2,4にブロードキャスト．A,C,Eが[B2]を受信．C,Eは経路表に加える．
ルータC上の経路表：to Ａ,
2, cost 2
[C3]
ルータE上の経路表：to Ａ,
4, cost 2
[E3]
(4)同様にDは[D2]をリンク3,6にブロードキャスト．A,Eともすでに持っている経路のコスト
が新たな経路以下なので[D2]を捨てる．
(5)C,Eもそれぞれ[C3],[E3]をブロードキャストするが，到着ルータでの経路コストは改善
しないため捨てられる．
(6)Aに関する経路は収束（安定）．
15
収束後の経路表
 収束後も，経路表が定期的に交換され，経路到達性を維持．
16
リンク障害時
 A-B間のリンク1に障害が発生した場合：
 リンク1に隣接するA,Bは，リンク1を送出先とする経路のコス
トを無限大(infinity)とする．RIPではコストの最大値は15で，
16が無限大を示す．
 A,Bからの「コスト無限大」の経路情報が網内に伝搬する．
例えば，Eは，Bからの経路情報に基づき「to A,link 4,cost2」を
用いていたが，Bからは｢to A,link 4,cost infinity｣が伝わる．
一方DからEに「Aへのコスト1の経路」が伝搬する．
したがってＥは「to A,link 6,cost2」の経路に切替える．
 新たな経路で安定
17
RIP：｢無限へのカウント｣
to
to
to
to
A
B
C
D
local
x
x
x
0
1
2
3
to
to
to
to
A
B
C
D
x
local
y
y
1
0
1
2
to
to
to
to
x
A
to
to
to
to
A
B
C
D
local
x
x
x
to D
to
to
to
to
3
x
A
to D
x
local
y
x
1
0
1
4
to D
5
to D
to D
7
to
to
to
to
A
B
C
D
y
y
local
z
C
to
to
to
to
A
B
C
D
z
z
z
local
z
3
2
2
1
D
2
1
0
16
z
D
to D
6
to D
Split horizon：もらった経路をくれた本人に
は返さない（AはBに対して返さない）
5
6
Poison reverse：無限大(16)として返す
7
・
・
・
・
15
2
1
0
1
C
16
y
y
y
local
z
4
to D
to D
A
B
C
D
B
to D
to D
y
B
0
1
2
3
A
B
C
D
15
to D
8
to D
16→無限
18
OSPF
 “Open Shortest Path First”：“Shortest Path First”アルゴリ
ズム(ダイクストラ・アルゴリズム)により経路を計算するアルゴリ
ズムであり，かつIETFでいう“Open”な場で標準化が行われた事を
示す．
 現行バージョンはOSPFv2(RFC2328)．CIDRに対応．
 リンクステート：各ルータは自分が直接接続しているリンクに関す
る情報を網内すべてのルータに（直接間接に）広告
 全ルータが，ネットワーク全体のトポロジーを同様に把握．
 経路ループが発生せず，経路収束が高速．
 経路メトリックの柔軟な設定が可能
 基本的には経路変更のみを広告
 隣接ルータの生存はHelloプロトコルで定期的に確認．
 二階層エリア構成が可能
 比較的大規模なドメインでも使用できる．
19
ダイクストラアルゴリズムによる最短路計算
 ダイクストラ(Dijkstra)アルゴリズム動作概要
Ａ
1
出発点
2
スタート
出発点
3
4
１段目
1
Ｂ
1
出発点
２段目
2
1
出発点
3
Ｃ
Ｂ
Ｂ
1
4
Ａ
1
4
2
6
Ｃ
2
出発点から点Ａへの仮のコストは１，点Ｂは
２となる．
出発点から点Ａ，Ｂ，Ｃへの
最短路を求める
5
3
4
2
Ｃ
Ａ
1
1
1
3
4
2
３段目
Ａ
1
3 Ｃ
Ｂ
2
1
3
出発点から点Ａを経由して点Ｂへのコストは５
であり，仮のコスト２より大きいため，仮のコス
ト２を持つ経路が最短となる．点Ａも同様．．
点Ｃへのコストは３と４があり，コストの
小さい３の経路が最短となる．
20
OSPF：リンクステート・データベース
 全てのルータが同一のリンクステート･データベース(LSDB)を保持
 LSDBの作成：各ルータが直接接続リンクの情報を網内全域に配布
（flooding）
 各ルータが計算する最適経路(ﾀﾞｲｸｽﾄﾗ法)が一致する→経路ループは発生
しない
 メトリック：リンクコスト
 遅延や帯域等を反映．方向別．
 小さいほど「良い」リンク(選択されやすい)
21
フラッディング
 各ルータは直接接続しているリンクの情報(LSA,Link State
Advertisement)を各リンクから送出．LSAには番号(Sequence number)が付
いている．
 LSAを受け取ったルータは




そのLSAを持っていなければLSDBに加えて，LSAをブロードキャスト
すでに持っているLSAより新しければ，入れ替えてLSAをブロードキャスト
すでに持っているLSAより古ければ手持ちのLSAを送出ルータに送付
さもなくば何もしない
 上記によりLSAは網内全域に配布される
22
世界のASの現状
BGP経路数
 全世界で1万4千のAS，1万9千のAS間リンク，14万経路
（2002年11月現在，http://bgp.potaroo.net/)
23

Download Report