インターネットルーティング：OSPFとBGP
実際のインターネットは数十億台のデバイスで構成された巨大なネットワークです。単一のルーティングアルゴリズムでインターネット全体の経路を計算することは、スケーラビリティと管理の観点から不可能です。
この記事では、インターネットが**自律システム（AS）**単位で階層的ルーティングを行う方式、AS内部ルーティングプロトコルの**RIP**と**OSPF**、そしてAS間ルーティングプロトコルの**BGP**を見ていきます。
1. 階層的ルーティングの必要性
1.1 スケーラビリティの問題
すべてのルータがインターネット全体のトポロジを保存して計算するとすれば：
- **記憶容量**：数十億の宛先に対するフォワーディングテーブル
- **計算コスト**：全体トポロジに対するルーティングアルゴリズムの実行
- **メッセージオーバーヘッド**：リンク状態の更新が世界中に伝播
1.2 管理の自律性
各組織（ISP、企業、大学）は自分のネットワーク内部のルーティングを独立して管理したいと考えています。使用するルーティングアルゴリズム、ポリシー、機器を自由に選択できる必要があります。
階層的ルーティング構造
========================
[AS 1: ISP-A] [AS 2: ISP-B] [AS 3: Google]
+-----------+ +-----------+ +-----------+
| R1---R2 | | R5---R6 | | R8---R9 |
| | | |<-------->| | | |<-------->| | | |
| R3---R4 | | R7 | | R10--R11 |
+-----------+ +-----------+ +-----------+
AS内部：OSPF、RIPなど（intra-ASルーティング）
AS間： BGP（inter-ASルーティング）
2. 自律システム（Autonomous System）
2.1 ASの定義
自律システム（AS）は、同一のルーティングポリシーの下で管理されるルータのグループです。各ASには固有のAS番号（ASN）があります。
ASの種類
=========
1. Stub AS：1つの他のASとのみ接続（企業、大学）
[外部] <---> [Stub AS]
2. Multihomed AS：複数のASと接続されるがトランジットトラフィック不可
[AS A] <---> [Multihomed AS] <---> [AS B]
3. Transit AS：トラフィックの通過を許可するAS（ISP）
[AS A] <---> [Transit AS] <---> [AS B]
通過許可
2.2 ゲートウェイルータ
ゲートウェイルータ（Gateway Router）は、他のASに属するルータと直接接続されたルータです。AS内部ルーティングとAS間ルーティングの両方を実行します。
3. RIP（Routing Information Protocol）
3.1 基本特性
RIPはDistance-VectorアルゴリズムをベースとしたAS内部ルーティングプロトコルです。
RIPの特性
==========
- アルゴリズム：Distance-Vector（ベルマン-フォード）
- メトリック：ホップ数（hop count）、最大15ホップ
- 更新周期：30秒ごとに隣接ノードに距離ベクトルを送信
- タイムアウト：180秒間更新がなければ経路を無効化
- 転送方式：UDPポート520
- 適用範囲：小規模ネットワーク（15ホップ制限）
3.2 RIPの限界
- 最大15ホップで大規模ネットワークに不向き
- 収束が遅い（count-to-infinityの可能性）
- ホップ数のみをメトリックとして使用し帯域幅の違いを反映できない
4. OSPF（Open Shortest Path First）
4.1 基本特性
OSPFはLink-StateアルゴリズムをベースとしたAS内部ルーティングプロトコルです。RIPの限界を克服するために設計されました。
OSPFの特性
===========
- アルゴリズム：Link-State（ダイクストラ）
- メトリック：帯域幅、遅延など管理者が設定可能
- 更新：変更時に即座に（または30分周期）
- 転送方式：IP直接（プロトコル番号89）
- 認証：MD5認証サポート
- 適用範囲：大規模ネットワーク
4.2 OSPFの主な利点
**セキュリティ**：OSPFメッセージは認証可能で、信頼できるルータのみがルーティングに参加します。
**等コストマルチパス（Equal-Cost Multipath）**：同じコストの経路が複数ある場合、トラフィックを分散できます。
**階層的構造**：1つのASを複数のエリア（Area）に分けることができます。
OSPF階層的構造
=================
[バックボーンエリア（Area 0）]
/ | \
[エリア1] [エリア2] [エリア3]
+------+ +------+ +------+
|R1 R2| |R4 R5| |R7 R8|
| R3 | | R6 | | R9 |
+------+ +------+ +------+
- バックボーンエリア（Area 0）：すべてのエリアを接続する中心エリア
- エリア境界ルータ（ABR）：2つのエリアにまたがるルータ
- AS境界ルータ（ASBR）：他のASと接続されたルータ
4.3 OSPFエリア間ルーティング
OSPFエリア間ルーティング
==========================
エリア1のR1からエリア3のR9へパケット送信：
R1（エリア1）
|
| エリア1内部OSPFルーティング
v
ABR1（エリア1/バックボーン境界）
|
| バックボーン（Area 0）OSPFルーティング
v
ABR3（バックボーン/エリア3境界）
|
| エリア3内部OSPFルーティング
v
R9（エリア3）
各エリア内部：詳細なトポロジ情報を交換
エリア間：要約された距離情報のみを交換
5. BGP（Border Gateway Protocol）
5.1 BGPの役割
BGPはインターネットでAS間ルーティングを担当する唯一のプロトコルです。インターネットのすべてのASを接続する「インターネットの接着剤」の役割を果たします。
BGPの2つの形態
=================
1. eBGP（External BGP）：異なるASのルータ間
AS1のゲートウェイ <---eBGP---> AS2のゲートウェイ
2. iBGP（Internal BGP）：同じAS内部のルータ間
AS1のゲートウェイ <---iBGP---> AS1の内部ルータ
eBGP：AS間の経路情報交換
iBGP：学習した経路情報をAS内部に伝播
5.2 BGP経路と属性
BGPにおける経路は、宛先プレフィックスと経路属性（Path Attributes）の組み合わせです。
BGP経路広告の例
=================
AS2がAS1に広告：
プレフィックス：138.16.64.0/24
AS-PATH：AS3 AS2
NEXT-HOP：201.44.13.1
主要な経路属性：
- AS-PATH：経路が通過するASのリスト
例：AS3 AS2 --> AS2を経由してAS3に到達
- NEXT-HOP：次のASに向かうゲートウェイルータのIPアドレス
- LOCAL-PREF：AS内部での経路選好度（高いほど選好）
- MED：他のASに選好経路を伝える値（低いほど選好）
5.3 BGP経路選択アルゴリズム
複数の経路が存在する場合、BGPは以下の順序で最良の経路を選択します。
BGP経路選択の優先順位
=======================
1. LOCAL-PREFが最も高い経路（ポリシーベース）
2. AS-PATHが最も短い経路
3. NEXT-HOPに最も近い経路（Hot-Potatoルーティング）
4. BGP識別子が最も小さい経路
例：
経路A：LOCAL-PREF=200, AS-PATH=[AS2, AS5], NEXT-HOP=R1
経路B：LOCAL-PREF=100, AS-PATH=[AS3], NEXT-HOP=R2
--> 経路Aを選択（LOCAL-PREFがより高い）
5.4 Hot-Potatoルーティング
Hot-Potatoルーティングは、パケットをできるだけ早く自分のAS外に送り出す戦略です。AS内部コストのみを考慮して最も近いゲートウェイを選択します。
Hot-Potatoルーティング
========================
AS1内部：
iBGP iBGP
[R1] <-------> [R2] <-------> [R3]
| | |
| 内部コスト2 | 内部コスト5 | 内部コスト3
| | |
[GW1] [GW2] [GW3]
|eBGP |eBGP |eBGP
v v v
[AS2] [AS3] [AS2]
R2がAS2のプレフィックスに到達するには：
- GW1経由：内部コスト2（R2->R1->GW1）
- GW3経由：内部コスト3（R2->R3->GW3）
--> GW1を選択（Hot-Potato：最も近い出口）
6. BGPルーティングポリシー
6.1 顧客-プロバイダ-ピア関係
AS間の関係
============
[Tier-1 ISP A] <--ピアリング--> [Tier-1 ISP B]
/ \ / \
プロバイダ プロバイダ プロバイダ プロバイダ
/ \ / \
[顧客AS1] [顧客AS2] [顧客AS3] [顧客AS4]
- 顧客はプロバイダに費用を支払いトラフィック転送を受ける
- ピアは互いの顧客トラフィックを無料で交換
- プロバイダは顧客の経路を他に広告
6.2 ルーティングポリシーの規則
BGPポリシー規則
=================
AS Xの立場で：
1. 顧客から受けた経路：すべてに広告（収益発生）
2. ピアから受けた経路：顧客にのみ広告（ピアやプロバイダには広告しない）
3. プロバイダから受けた経路：顧客にのみ広告（ピアや他のプロバイダには広告しない）
原則：トラフィックが自分を通過するとコストが発生するため、
収益となる顧客トラフィックのみ積極的に中継
7. OSPFとBGPの相互作用
実際のルータではOSPFとBGPが連携して動作します。
OSPFとBGPの相互作用
=====================
AS内部：
- OSPFがAS内部のルータ間最短経路を計算
- 各ルータはAS内部のすべての宛先への経路を把握
AS間：
- eBGPで外部ASのプレフィックス情報を学習
- iBGPで学習した情報をAS内部に伝播
- NEXT-HOPまでの経路はOSPFが提供
フォワーディングテーブル構成：
宛先プレフィックス | 次ホップ | 出典
-------------------+--------------+-------
10.1.0.0/16 | 192.168.1.2 | OSPF
172.16.0.0/12 | 192.168.1.5 | OSPF
8.8.8.0/24 | 10.0.0.1 | BGP
0.0.0.0/0 | 10.0.0.1 | BGP
8. まとめ
| 概念 | 核心内容 |
| ------------------ | -------------------------------------------------- |
| 階層的ルーティング | AS単位で内部・外部ルーティングを分離 |
| RIP | DVベース、ホップ数メトリック、最大15ホップ、小規模 |
| OSPF | LSベース、柔軟なメトリック、エリア階層化、大規模 |
| eBGP | AS間の経路情報交換 |
| iBGP | AS内部への外部経路情報伝播 |
| AS-PATH | BGP経路が通過するASのリスト |
| Hot-Potato | 最も近い出口にトラフィックを送る戦略 |
| LOCAL-PREF | BGP経路選択の最優先基準（ポリシー反映） |
次の記事では、ネットワークスタックの1つ下の層であるリンク層のエラー検出と多重アクセスプロトコルを見ていきます。
参考資料
- James F. Kurose, Keith W. Ross, "Computer Networking: A Top-Down Approach", 6th Edition, Chapter 4
- RFC 2328 - OSPF Version 2
- RFC 4271 - A Border Gateway Protocol 4 (BGP-4)
- RFC 2453 - RIP Version 2
현재 단락 (1/182)
実際のインターネットは数十億台のデバイスで構成された巨大なネットワークです。単一のルーティングアルゴリズムでインターネット全体の経路を計算することは、スケーラビリティと管理の観点から不可能です。