1 ネットワーク層（ルーティング）. 2 ルーティング メトリック：最適化すべき指標 ・ホップ数 ・所要時間 Destination Source ：最適ルート（経路） ：迂回ルート.

Presentation on theme: "1 ネットワーク層（ルーティング）. 2 ルーティング メトリック：最適化すべき指標 ・ホップ数 ・所要時間 Destination Source ：最適ルート（経路） ：迂回ルート."— Presentation transcript:

1 1 ネットワーク層（ルーティング）

2 2 ルーティング メトリック：最適化すべき指標 ・ホップ数 ・所要時間 Destination Source ：最適ルート（経路） ：迂回ルート

3 3 ルーティングとは ルーティングとは，「転送する経路を選ぶ こと」

4 4 ルーティングとは サブネット A から 192.168.2.10 という宛先パケットを受信す ると，マスクをかけ算して， 192.168.2.0 とわかる．これは サブネット B 行きとわかり， eth2 という出口にパケットを送 る

5 5 ルーティングとは ルーター A は，サブネット A,B,C 以外への経路を知らない． それ以外のパケットが来たら デフォルトゲートウェイであ るルータ B にパケットを送る

6 6 ルータ ルータの主な機能 ルーティングテーブルの管理  この宛先へ送るにはどのルータへ飛ばせば良いか ＩＰデータグラムのフォワーディング  次のルータへデータグラムを送る ＩＰデータグラムのフィルタリング  不正なデータグラムの廃棄 ルーティングプロトコルによるテーブル作成情報交換  経路情報の交換  （最適）経路の計算

7 7 ルーティング方法 l 静的ルーティング (static routing) 利点：制御トラフィックが生じない 欠点：設定管理が困難、動的経路変更が不可能 動的ルーティング (dynamic routing) 利点：設定が容易、動的経路変更が可能 大規模ＮＷ向き 欠点：制御トラフィックが発生 Routing table Routing table Dynamic routing Static routing Routing table Routing table それぞれ設定 （トラフィック） 情報交換

8 8 ルーティングの階層 黎明期のインタネットは，単一の「ネットワーク」 であり，フラットな経路制御が行われていた（「ド メイン」は１つだけ）． その後，インタネットをＡＳに分割し，ＡＳ内とＡ Ｓ間のニ階層での経路制御に移行． ＮＷ規模の拡大に伴う経路制御オーバヘッドおよび経路 表エントリ数の増大への対処． 遠隔ネットワークの障害情報による経路再計算の回避． 組織内ネットワークの詳細の隠蔽． 組織のポリシーに基づく独自の経路制御設定の許容．

9 9 ルーティングの階層 ＡＳ： Autonomous System(AS), 自律系，自律ＮＷ （ルーティング）ドメイン 「管理主体を同じくするルータおよびネットワークの集 合（ A set of routers and networks under the same administration ）」 ドメイン間経路制御の単位．転送・経路制御に関して， 独自のポリシーを持つ． 同一ＡＳ内のトラフィックはＡＳ内部のみを通る． ＡＳ内部の構造は外部に隠蔽 ＡＳ番号：２ byte ， IANA （ Internet Assigned Numbers Authority ）が割当．

10 10 ＩＧＰ，ＥＧＰ IGP ： Interior(Internal) Gateway Protocol ＡＳ内部の経路制御のためのプロトコルの総称． １つのＡＳ内で複数のＩＧＰを協調動作させても構わない． EGP ： Exterior(External) Gateway Protocol ＡＳ間の経路制御のためのプロトコルの総称．

11 11 ルーティングアルゴリズム 距離ベクトル (Distance Vector) アルゴリズム 各ルータは，自分がどのネットワークに ( 直接 or 間接 に ) 配送可能かを隣接ルータに公告 IGP である RIP で使用 リンクステート (Link State) アルゴリズム 各ルータは，自分が直接接続しているネットワーク を全てのルータに公告 (flooding) 全ルータがネットワーク全体のトポロジを把握 IGP である OSPF で使用

12 12 ＲＩＰ (Routing Information protocol ） Distance vector 型 30 秒おきに自分の持つ経路情報を broadcast 180 秒間経路情報がこない → 経路を削除 最大ホップカウント ＝ 16 大規模ネットワークでは利用不可 ○ 直感的に理解しやすく、実装が簡単 × 経路数に比例して交換される経路情報が増加 × 経路の変動が伝わるのに時間がかかる × サブアドレスを認識しない

13 13 IGP 系プロトコル ＲＩＰにおける経路情報の伝播 Network Metric A 1 B 1 D 1 Network Metric A 2 B 2 C 1 D 1 到達可能ＮＷと距離情報 NW B NW A NW C NW D Router 1 Router 2 経路情報

14 14 距離ベクトルアルゴリズム 数字はネットワークアドレス相当．リンクコストは全て１とする． 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 に戻って繰り返し

15 15 経路の伝搬 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 に関する経路は収束（安定）．

16 16 収束後の経路表 収束後も，経路表が定期的に交換され，経路到達性を維持．

17 17 リンク障害時 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 」の経路に切替える． 新たな経路で安定

18 18 RIP ：｢無限へのカウント｣ ABCD to A local 0 to B x 1 to C x 2 to D x 3 ABCD x yz to A x 1 to B local 0 to C y 1 to D y 2 to A y 2 to B y 1 to C local 0 to D z 1 to A z 3 to B z 2 to C z 2 to D local 1 to A local 0 to B x 1 to C x 2 to D x 3 x yz to A x 1 to B local 0 to C y 1 to D x 4 to A y 2 to B y 1 to C local 0 to D z 16 to D 3to D 16 to D 4 to D 5 to D 6 to D 7 to D 15 to D 7 to D 8 to D 15 to D 16→ 無限 ・・・・・・・・ Split horizon ：もらった経路をくれた本人には返 さない（ A は B に対して返さない） Poison reverse ：無限大 (16) として返す

19 19 OSPF “Open Shortest Path First” ： “Shortest Path First” アルゴリズム ( ダイ クストラ・アルゴリズム ) により経路を計算するアルゴリズムであり， かつ IETF でいう “Open” な場で標準化が行われた事を示す． 現行バージョンは OSPFv2(RFC2328) ． CIDR に対応． リンクステート：各ルータは自分が直接接続しているリンクに関す る情報を網内すべてのルータに（直接間接に）広告 全ルータが，ネットワーク全体のトポロジーを同様に把握． 経路ループが発生せず，経路収束が高速． 経路メトリックの柔軟な設定が可能 基本的には経路変更のみを広告 隣接ルータの生存は Hello プロトコルで定期的に確認． 二階層エリア構成が可能 比較的大規模なドメインでも使用できる．

20 20 ダイクストラアルゴリズムによる最短路計算 ダイクストラ (Dijkstra) アルゴリズム動作概要 1 2 1 3 4 出発点 Ａ Ｂ Ｃ 出発点から点Ａ，Ｂ，Ｃ への最短路を求める 2 1 1 2 1 3 4 出発点 Ａ Ｂ Ｃ 出発点から点Ａへの仮のコストは１，点 Ｂは２となる． スタート１段目 2 1 1 2 1 3 4 出発点 Ａ Ｂ Ｃ 出発点から点Ａを経由して点Ｂへのコスト は５であり，仮のコスト２より大きいため， 仮のコスト２を持つ経路が最短となる．点 Ａも同様．． ２段目 5 6 2 1 3 1 2 1 3 4 出発点 Ａ Ｂ Ｃ 点Ｃへのコストは３と４があり，コ ストの小さい３の経路が最短となる． ３段目 4 3

21 21 OSPF ：リンクステート・データベース 全てのルータが同一のリンクステート･データベース (LSDB) を保持 LSDB の作成：各ルータが直接接続リンクの情報を網内全域に配布 （ flooding ） 各ルータが計算する最適経路 ( ﾀﾞｲｸｽﾄﾗ法 ) が一致する → 経路ループは発生し ない メトリック：リンクコスト 遅延や帯域等を反映．方向別． 小さいほど「良い」リンク ( 選択されやすい )

22 22 フラッディング 各ルータは直接接続しているリンクの情報 (LSA,Link State Advertisement) を各リンクから送出． LSA には番号 (Sequence number) が付いている． LSA を受け取ったルータは その LSA を持っていなければ LSDB に加えて， LSA をブロードキャスト すでに持っている LSA より新しければ，入れ替えて LSA をブロードキャスト すでに持っている LSA より古ければ手持ちの LSA を送出ルータに送付 さもなくば何もしない 上記により LSA は網内全域に配布される

23 23 世界の AS の現状 全世界で 1 万 4 千の AS ， 1 万 9 千の AS 間リンク， 14 万経路 （ 2002 年 11 月現在， http://bgp.potaroo.net/) BGP 経路数