BGP (Border Gateway Protocol) 8 章経路制御 電子情報工学科 3 年前期ネットワークアーキテクチャ情報科学センター / ネットワークデザイン研究センター福田豊 初期のインターネット すべてIGPによってルータが経路情報を交換 インターネットの発展 経路情報交換のためのトラヒックが増大 多種多様なルータが導入されたが, それらの管理が困難 インターネットを AS に分割して管理 64 BGP (2) EGP AS 間において経路を交換するプロトコル BGP EGP の後継 パスベクトル情報に基づく経路制御方式 隣接する境界ルータは UDP ではなく TCP で通信 一度経路表を交換した後は, 経路表が変化する毎に通知 8.5 インターネットにおける経路制御および関連プロトコル IP 層 現在は IPv4 ( 以後単にIPと略記 ) 表記方法, 枯渇対策技術など 次世代 IP : IPv6 表記方法, アドレス空間 経路制御 RIP/OSPF 65 66 IPv4 IPv4 IP アドレス 32 ビット 表示方法としては,8ビットずつ4つに分け, それぞれを10 進数で表し,. でつなげて表示 ex. 131.206.37.20 IP アドレス (1) IP アドレスの構成 ネットワーク部 ネットワーク部 : クラス A~E クラス A: ホスト部が 24bit (16777214 台 ) クラス B: ホスト部が 16bit (65534 台 ) クラス C: ホスト部が 8bit (254 台 ) クラス D: マルチキャスト用 クラス E: 実験用 ホスト部 67 68 1
IP アドレス (2) IP アドレスの構造と種類 ( 図 1.10 教 P8) classa: ホスト部 24bit (16777214 台 ) 0 net 7bit classb: ホスト部 16bit (65534 台 ) 1 0 net 14bit classc: ホスト部 8bit (254 台 ) 1 1 0 net 21bit host 24bit host 16bit host 8bit? それぞれ 2 台ずつ少ない IP アドレス (3) IP アドレスにおける 0 と 255 最初と最後 それぞれ特別な意味で用いられる 0 : そのネットワーク全体を示す 例 255 : ブロードキャスト X.Y.Z.0 : X.Y.Z ネットワーク全体を示す X.Y.Z.255 : 宛先アドレスとして,X.Y.Z ネットワークに接続されているすべてのホストが対象 69 70 IP アドレス (4) IPアドレス : 当初はネットワーク部とホスト部の2つの要素により構成 階層化が進む 組織内のアドレス管理サブネット (subnet) 化 経路の簡単化 ホスト部を幾つかのネットワークに分けて, サブネット化する サブネットはサブネットマスク (subnet mask) により識別 マスクの各ビットと IP アドレスの各ビットの論理積 (and) を取ると, その結果がネットワークおよびサブネットを表す 71 IP アドレス (5) 例 :131.206.101.20 2 進数で表現すると : 10000011.11001110.01100101.00010100 最上位の 2 ビットが 10 なので, クラス B クラス B なので, ホスト部は通常下位 16 bit 例 1: マスクが FFFFC000 (255.255.192.0) 11111111.11111111.11000000.00000000 (255.255.192.0) 上位 18 ビットがネットワークアドレス クラス B の IP アドレスは上位 16 ビットがネットワークアドレス 上位から 17,18 ビット目がサブネットアドレス 131.206.101.20 との論理積は,131.206.64.0 よって 131.206.64.0/18 のネットワークに所属 ( プレフィックス表示 ) 72 IP アドレス (6) 例 2: マスクが FFFFE000 (255.255.224.0) 11111111.11111111.11100000.00000000 上位 19 ビットがネットワークアドレス クラスBのIPアドレスは上位 16ビットがネットワークアドレス 上位から17ビット,18ビット,19ビット目がサブネットアドレス 131.206.101.20 との論理積は,131.206.96.0 10000011.11001110.01100101.00010100 (131.206.101.20) よって 131.206.96.0/19 のネットワークに所属 73 IP アドレスが足りなくなった! インターネットの爆発的な成長 新興国でのインターネット接続の増加 クラウドサービスの充実による, サーバに対する IP アドレス消費の増加 IPv6 のように,IP アドレスを長くすること IPv6 では,128bit 32 ビットから 128 ビットへ 例 : 1A2B:3C4D:5E6F:7081:92A3:B4C5:D6E7:F809 IPv4 でなされた枯渇問題対策 キーワード NAPT CIDR 74 2
IP アドレスの枯渇問題 (1) クラス B,C ごとにできることを考えてみる クラス B のアドレス 約 65000 台のホストを 1 つのネットワークに接続可能 一方,14 ビット分 ( 約 16000 程度 ) のネットワークしかつくることができない 世界規模で考えれば全く足りない IP アドレスの枯渇問題 (2) プライベート IP アドレスの導入 : セキュリティ向上,End-to-End 間の通信に制限 グローバルな一意性を緩和 NAT(Network Address Translator) でアドレス変換 クラス区分アドレス範囲サブネットマスク Class A Class B Class C 10.0.0.0 ~ 10.255.255.255 172.16.0.0~ 172.31.255.255 192.168.0.0~ 192.168.255.255 利用可能な IP アドレス 255.0.0.0 1677 万 7214 255.255.0.0 6 万 5534 255.255.255.0 254 75 76 IP アドレスの枯渇問題 (3) クラス C のアドレス 200 万以上のネットワークを提供可能 アドレスが枯渇してきたので 一時クラス A,B を返納させ, クラス C を複数割り当てる取り組みがなされた IBM 等はクラス A を持っている 九工大はクラス B を 2 つ ( このような努力が払われているが, 枯渇してしまった!) 無秩序に割り当てると, 経路表の規模が膨大になる 工夫が必要 CIDR (1) Classless Inter-Domain Routing (CIDR) 要求に応じて連続するクラス C の IP アドレスを集約化し,1 つのアドレス空間とする 先ほどのプレフィックスを利用 例 :192.50.66/23 11000000.00110010.0100001 (192.50.66.) クラスC 192.50.66.X と 192.50.67.Y が集約されている 11000000.00110010.01000010 (192.50.66) 11000000.00110010.01000011 (192.50.67) 77 78 CIDR (2) 例 :10.0.1.66/26 00001010.00000000.00000001. 01000010 サブネットマスクは,255.255.255.192 11111111.11111111.11111111.11000000 所属するネットワークは,10.0.1.64 この場合はクラス C を 4 つに分割 10.0.1.0~63 10.0.1.64~127 10.0.1.128~191 10.0.1.192~255 注意 : ネットワークとブロードキャストアドレス 10.0.1.192/26 の場合,10.0.1.192 がネットワークアドレスを示し, 10.0.1.255 がブロードキャストアドレスを示す CIDR (3) CIDR 導入例 : 日本の場合 CIDR 導入前, バックボーンルータのエントリ数は3200 エントリ CIDR 導入後約半分に削除 しかし現在ではバックボーンのエントリ数はさらに増大 膨大な経路表から適切な経路を選択しなければならない より軽減する方法について盛んに研究がなされている 79 80 3
IPv4 アドレス在庫の遷移 APNIC では 2011 年に在庫が枯渇! IPv6 アドレス空間の拡張 IPv4 では 32 ビット 4,294,967,296 IPv6 では 128 ビット 340,282,366,920,938,463,463,374,607,431,768, 211,456 構造化されたアドレス割り当て 地域 国 プロバイダ 組織 サブネット コンピュータ http://www.potaroo.net/tools/ipv4/index.html 81 84 128bitの広さ IPv4 2 32 =4,294,967,296 =4.3 10 9 世界の人口は? 一人一つIPアドレスを必要とすると?? 2 128 一 : 10 0 十 : 10 1 百 : 10 2 千 : 10 3 萬 : 10 4 億 : 10 8 兆 : 10 12 京 : 10 16 垓 : 10 20 禾予 : 10 24 ( じょ ) 壌 : 10 28 ( じょう ) 溝 : 10 32 ( こう ) 澗 : 10 36 ( かん ) 正 : 10 40 ( せい ) 載 : 10 44 ( さい ) 極 : 10 48 ( ごく ) 恒河沙 : 10 52 ( ごうがしゃ ) 阿僧祇 : 10 56 ( あそうぎ ) 那由他 : 10 60 ( なゆた ) 不可思議 : 10 64 ( ふかしぎ ) 無量大数 : 10 68 ( むりょうたいすう ) 85 86 2 128 2 128 =340,282,366,920,938,463,463,374,607,431,768,211,456 340 澗 2823 溝 6692 壌 0938 禾予 4634 垓 6337 京 4607 兆 4317 億 6821 万 1456 =3.4 10 38 配分 一人あたり 3.4 10 27 陸地 1cm 2 あたり 2.2 10 20 ほぼ無限! IPv6 アドレス 表記方法 fe80:0000:0000:0000:4163:ee0e:40ff:8b23 87 88 4
IPv6 アドレスの構造 以下の 2 つの要素から構成 ネットワークプレフィックス インターフェース識別子 (ID) ネットワークプレフィックス ネットワークアドレス部に相当 表記 : プレフィックス値 / プレフィックス長 インターフェース ID 自動生成 or 手動設定 IPv6 アドレスの種類 宛先の指定方法によって, 次の3 種類に分類可能 ユニキャストアドレス (Unicast Address) マルチキャストアドレス (Multicast Address) エニーキャストアドレス (Anycast Address) 89 90 ユニキャスト 同じIPアドレスを持つインターフェースは 1 つだけ存在 マルチキャスト 同じアドレスを持つインターフェースが複数存在 その全てに届けられる 近隣探索に利用 91 92 エニキャスト 同じアドレスを持つインターフェースが複数存在 そのうちのいずれかの届けられるが, どのインターフェースに届けられるかは経路に依存 利用しているルーティングプロトコルの基準に応じてもっとも近いインターフェースに送信される IPv6 ユニキャストアドレス分類 以下の 3 種類に分類可能 グローバルユニキャストアドレス (global unicast address) ユニークローカルユニキャストアドレス (unique local unicast address) リンクローカルユニキャストアドレス (link local unicast address) 93 94 5
グローバルユニキャストアドレス (1) インターネット内で一意 ( 重複しない ) 現時点で実際に配布されるグローバルアドレス 上位 3 ビットが 001 固定 次の 61~45 ビットがグローバルルーティングプレフィックス 次の 16~0 ビットがサブネット ID 下位 64 ビットがインターフェース識別子 グローバルユニキャストアドレス (2) グローバルルーティングプレフィックスに /48 (48 ビット ) が割り当てられると 280 兆強個のネットワークを割り振ることが可能 各ネットワークでは, サブネットとして 16 bit を利用可能 ユーザは 65,536 個のサブネットの割り振りが可能 各サブネット毎に,64 bit 分 (18,446,774,073,709,551,616 個 ) の IP アドレスを利用可能 95 96 ユニークローカルユニキャストアドレス IPv4 のプライベートアドレスに相当 組織内で閉じたイントラネットなどで利用 ユニークローカルアドレスの上位 7 ビットは 1111110 で, アドレスの範囲は fc00::/7 ただし,8 桁目が 0 のアドレスの使用が禁止されているため, 現時点でイントラネットで実際に使えるアドレスの範囲は fd00::/8 に限られる リンクローカルユニキャストアドレス ノードの起動時にインターフェイスに自動的に割り当てられるアドレス リンク内では一意性が保証されるが, ルーターを超える通信では使用できない 上位 10ビットが 1111111010, 次の54ビットがすべて0, 下位 64ビットがインターフェイス識別子 インターフェイス識別子は ノードの起動時やインターフェイスを有効にした際に例外なく自動設定 ( 手動設定不可 ) リンクローカルアドレスは fe80:: インターフェイス識別子 と表記でき プレフィクスは fe80::/64 98 99 まとめ (1) 経路制御とは? 到着したパケットを適切な出線に転送 適切な経路を判断 経路制御方式 ソースルーティング IPはoptionとしてソースルーティング機能を持つ ホップバイホップルーティング 経路表の作成方法により2つに分類できる 静的な経路制御 (static routing) 管理者が経路表を静的に作成 ( 動的に更新されない ) 動的な経路制御 (dynamic routing) まとめ (2) ネットワークの階層化 インターネット : 異なる方針で管理されているネットワークAS の集合体 AS (Autonomous System) 学術研究用ネットワーク, 大学のネットワーク等 ASは互いに独立 各 ASごとに利用規程 (AUP: Acceptable-Use Policy) を持つ AS 内で用いられる経路制御プロトコル IGP (Interior Gateway Protocol): RIP, OSPF AS 間で用いられる経路制御プロトコル EGP(Exterior Gateway Protocol): BGP 107 108 6
まとめ (3) Bellman-Ford アルゴリズム (1) 各ノードが宛先ノードとそこまでのコストをお互いに交換 各ノードがその情報を元に宛先ノードまでの最短経路を求める 問題点 ノード, もしくはノード間のリンクの故障による経路情報の変化が生じたとき, その情報に基づく経路の更新は緩やかになってしまう 経路においてループが形成される可能性がある まとめ (4) Bellman-Ford アルゴリズム (2) 改良方法 ループの発生によるネットワークの全体への悪影響を緩和 RIP において採用 2 つの方法 split horizon 法 変化に応じた更新情報の通知 (triggered updates) 109 110 まとめ (5) ダイクストラ法 (1) 仮定 各ノードはネットワーク全体の 地図 ( ネットワークのトポロジとノード間を接続するリンクに関する情報 ) を知っている リンクに関する情報 : ホップ数や伝送容量 経路情報の同期を取る必要がある OSPF では Exchange プロトコルで同期を取る 1 組のノードが最初に接続を確定した後に互いのデータベースに同期を取る手続きを規定 まとめ (6) ダイクストラ法 (2) データベースの同期後 変更が生じたごとに隣接するノードに変更を通知 通知を受けたノードは送信先以外の隣接ノードすべてに同一の情報を送る Flooding 111 112 まとめ (7) ダイクストラ法 (3) 受け取る経路情報に対してどの情報が最新かを識別する必要がある データには更新番号を付加 データベースにおいて各リンク情報の更新番号を格納 その番号を比較し, 数字が新しい場合はデータベースを更新し, その情報を隣接ノードへ通知 番号が小さい場合は自分が持つ新しいデータを通知 同じ番号の情報であればデータベースの更新も隣接ノードへの通知も行わない まとめ (8) RIP Bellman-Fordアルゴリズムに基づくプロトコル ノード間のコストとしてはホップ数を採用 ホップ数は15まで許容し,16は無限大を表す RIPメッセージはUDPで運ばれ, ブロードキャストにより30 秒毎に隣接ノードに通知 リンク状態が変化した場合はその都度通知 180 秒の間あるノードからRIPパケットを受け取らなかった場合は, そのノードへのコストは 113 114 7
OSPF まとめ (9) IETF で開発 設計 RIP の後継 全ノードはネットワークトポロジー, リンク情報に関する同一の情報を持つ その情報をもとにダイクストラ法によって経路を計算 3つのプロトコルから構成 Hello,Exchange,Flooding BGP パスベクトル情報に基づく経路制御方式 隣接する境界ルータは UDP ではなく TCP で通信 一度経路表を交換した後は, 経路表が変化する毎に通知 まとめ (10) IP アドレスにおける 0 と 255 IPアドレス : 当初はネットワーク部とホスト部の2つの要素により構成 組織内のアドレス管理サブネット (subnet) 化 経路の簡単化 サブネットマスク マスクの各ビットと IP アドレスの各ビットの論理積 (and) を取ると, その結果がネットワークおよびサブネットを表す 115 116 まとめ (11) IPv4 枯渇対策 NAPT と CIDR の導入 NAPT プライベートアドレスの導入 CIDR 要求に応じて連続するクラス C の IP アドレスを集約化し,1 つのアドレス空間とする 10.0.1.1/23 10.0.1.0, 10.0.2.0 まとめ (12) IPv6 IPv4 アドレス在庫枯渇 アドレスは以下の 2 つの要素から構成ネットワークプレフィックスインターフェース識別子 (ID) IPv6 アドレス種別は, 宛先の指定方法によって, 次の3 種類に分類可能 ユニキャストアドレス (Unicast Address) マルチキャストアドレス (Multicast Address) エニーキャストアドレス (Anycast Address) 117 118 まとめ (13) ユニキャストアドレスは以下の 3 種類に分類可能 グローバルユニキャストアドレス (global unicast address) ユニークローカルユニキャストアドレス (unique local unicast address) リンクローカルユニキャストアドレス (link local unicast address) アドレスの自動取得 ルータから RA を受信することで, プラグ & プレイ可能 参考文献 岩波講座インターネット第 2 巻 ネットワークの相互接続 堀良彰, 池永全志, 門林雄基, 後藤滋樹編 ISBN4-00-011052-7 インターネットルーティング入門 友近剛史, 池尻雄一, 小早川知昭 ISBN4-7981-0038-2 翔泳社 http://www.soi.wide.ad.jp/iw2001/slides/04/04-1/ 119 120 8