ルーティングアルゴリズム：Link-StateとDistance-Vector
ルーティングアルゴリズムは、送信ホストから受信ホストまでの最適経路を決定します。ネットワークをグラフとしてモデル化し、ノード間の最小コスト経路を計算することが核心です。
この記事では、2つの代表的なルーティングアルゴリズムである**Link-State（LS）**アルゴリズムと**Distance-Vector（DV）**アルゴリズムを取り上げ、それぞれの長所短所と問題点を分析します。
1. ネットワークのグラフモデル
ネットワークはノード（ルータ）とエッジ（リンク）で構成された重み付きグラフとしてモデル化されます。
ネットワークグラフの例
=======================
2
(u) -------> (v)
| \ |
1| \5 |3
| \ |
v v v
(x)---(w)---->(y)---->(z)
3 1 2
c(u,v) = 2, c(u,x) = 1, c(u,w) = 5
c(v,y) = 3, c(x,w) = 3, c(w,y) = 1
c(y,z) = 2
**目標**：出発ノードから他のすべてのノードへの最小コスト経路を見つけること
2. ルーティングアルゴリズムの分類
ルーティングアルゴリズムの分類
================================
1. 情報範囲による分類：
- 全域的（Global）：すべてのノード情報を知って計算 --> Link-State
- 分散的（Decentralized）：隣接情報のみで反復計算 --> Distance-Vector
2. 動作方式による分類：
- 静的（Static）：経路がほとんど変わらない
- 動的（Dynamic）：ネットワーク変化に応じて定期的に再計算
3. 負荷感度による分類：
- 負荷敏感（Load-Sensitive）：リンク混雑度をコストに反映
- 負荷非敏感（Load-Insensitive）：現在のインターネットルーティング方式
3. Link-Stateアルゴリズム（ダイクストラアルゴリズム）
3.1 基本原理
Link-Stateアルゴリズムはネットワークの**全体トポロジ情報**に基づいて動作します。各ノードが自分のリンク状態情報をネットワーク全体にブロードキャストし、すべてのノードが同一の情報を持つとダイクストラアルゴリズムで最短経路を計算します。
3.2 アルゴリズムの動作
ダイクストラアルゴリズム（Dijkstra's Algorithm）
=================================================
初期化：
N' = 出発ノード u
D(v) = c(u,v)（直接接続された隣接ノードのコスト）
無限大（直接接続されていないノード）
反復：
1. N'に含まれないノードのうちD(w)が最小のノードwを選択
2. wをN'に追加
3. wの隣接ノードvについて：
D(v) = min(D(v), D(w) + c(w,v))
4. すべてのノードがN'に含まれるまで反復
3.3 実行例
上のグラフでノードuを出発点としてダイクストラアルゴリズムを実行します。
ダイクストラ実行過程（出発：u）
================================
段階 | N' | D(v) | D(w) | D(x) | D(y) | D(z)
-----+-----------+------+------+------+------+------
0 | u | 2 | 5 | 1 | inf | inf
1 | u,x | 2 | 4 | 1 | inf | inf
2 | u,x,v | 2 | 4 | 1 | 5 | inf
3 | u,x,v,w | 2 | 4 | 1 | 5 | inf
4 | u,x,v,w,y | 2 | 4 | 1 | 5 | 7
5 | 全ノード | 2 | 4 | 1 | 5 | 7
最短経路ツリー：
u -> v：コスト2（直接）
u -> x：コスト1（直接）
u -> w：コスト4（u -> x -> w）
u -> y：コスト5（u -> v -> y または u -> x -> w -> y）
u -> z：コスト7（u -> ... -> y -> z）
3.4 時間計算量
基本実装の時間計算量はO(n^2)であり、優先度キュー（ヒープ）を使用するとO(n log n)に改善できます。
3.5 振動問題（Oscillation）
リンクコストがトラフィック負荷に応じて変化すると、ルーティングが振動（oscillation）する可能性があります。
LS振動問題の例
=================
時点1：A -> B経路に大部分のトラフィックが流れる
--> A -> Bリンクコスト増加
時点2：すべてのノードがA -> C -> D -> B経路に切り替え
--> A -> Cリンクコスト増加
時点3：再びA -> B経路に切り替え（振動繰り返し）
解決策：ルーティング更新タイミングをランダム化
4. Distance-Vectorアルゴリズム（ベルマン-フォード）
4.1 基本原理
Distance-Vectorアルゴリズムは**分散的**に動作します。各ノードは隣接ノードにのみ自分の距離ベクトル（すべての宛先までの推定コスト）を伝達し、隣接ノードの情報に基づいて自分の距離ベクトルを更新します。
4.2 ベルマン-フォード方程式
ノードxから宛先yまでの最小コストd(x,y)は以下のように計算されます。
ベルマン-フォード方程式
========================
d(x, y) = min { c(x, v) + d(v, y) }
v
ここでvはxのすべての隣接ノード
意味：xからyまでの最小コストは
= xから隣接ノードvまでのコスト + vからyまでの最小コスト
この値が最小となる隣接ノードvを経由して移動
4.3 アルゴリズムの動作過程
DVアルゴリズムの動作
=====================
各ノードxは以下を保持：
- c(x,v)：隣接ノードvまでのリンクコスト
- Dx：xの距離ベクトル（すべての宛先までの推定コスト）
- Dv：各隣接ノードvの距離ベクトル
動作：
1. 初期化：直接接続された隣接はリンクコスト、残りは無限大
2. 隣接ノードから距離ベクトルを受信すると：
Dx(y) = min { c(x,v) + Dv(y) }（すべての隣接ノードvについて）
3. 自分の距離ベクトルが変更されたらすべての隣接ノードに送信
4. 変化がなくなるまで反復
4.4 実行例
DVアルゴリズム実行（3ノードの例）
===================================
トポロジ：
x ---7--- y
| / |
1 / 1
| 2 |
z --------+
初期距離ベクトル：
Dx = [0, 7, 1] (x->x, x->y, x->z)
Dy = [7, 0, 1] (y->x, y->y, y->z)
Dz = [1, 1, 0] (z->x, z->y, z->z)
ステップ1：各ノードが隣接ノードのDVを受信して更新
ノードx更新：
Dx(y) = min(c(x,y)+Dy(y), c(x,z)+Dz(y))
= min(7+0, 1+1) = 2
Dx(z) = min(c(x,y)+Dy(z), c(x,z)+Dz(z))
= min(7+1, 1+0) = 1
更新後 Dx = [0, 2, 1]（x->yが7から2に変更）
ステップ2：変更されたDVを隣接ノードに伝播、変化がなくなれば終了
5. Count-to-Infinity問題
5.1 問題発生シナリオ
DVアルゴリズムの最大の問題は**bad news travels slowly**、すなわちリンクコストが増加した時の収束が非常に遅いことです。
Count-to-Infinityの例
========================
トポロジ：x ---4--- y ---1--- z
初期距離ベクトル：
Dy(x) = 4, Dz(x) = 5 (z -> y -> x)
リンク変更：c(x,y) = 4 --> 60
y更新：Dy(x) = min(60, 1+Dz(x)) = min(60, 1+5) = 6
（z経由なら6だと思うが、zもyを経由している！）
z更新：Dz(x) = min(1+Dy(x)) = 1+6 = 7
y更新：Dy(x) = min(60, 1+7) = 8
z更新：Dz(x) = 1+8 = 9
... 1ずつ増加し続けて44回反復後にようやく収束！
5.2 解決策：Poisoned Reverse
Poisoned Reverseはルーティングループを防止する技法です。zがyを経由してxに到達する場合、zはyにxまでの距離を無限大と伝えます。
Poisoned Reverseの動作
========================
zはyを通じてxに到達（z -> y -> x）
zがyに伝える情報：
Dz(x) = 無限大（実際は5だがyには無限大と通知）
理由：zがyを経由するので、yがzを経由するループを防止
リンク変更 c(x,y) = 60 発生時：
y更新：Dy(x) = min(60, 1+無限大) = 60
yがzにDy(x)=60を伝達
z更新：Dz(x) = min(1+60) = 61
--> 即座に正しい値に収束！
5.3 Poisoned Reverseの限界
Poisoned Reverseは**2ノード間のループ**のみ防止できます。3つ以上のノードが関与するループには効果がありません。
6. LSとDVアルゴリズムの比較
Link-State vs Distance-Vector
================================
項目 | Link-State (LS) | Distance-Vector (DV)
------------------+-----------------------+------------------------
情報範囲 | ネットワーク全体のトポロジ | 隣接ノードの距離ベクトルのみ
メッセージ複雑度 | O(N x E) メッセージ | 収束まで可変的
収束速度 | O(N^2) 高速 | 低速（ループの可能性）
堅牢性 | 各ノード独立計算 | エラーが伝播する可能性
| （エラーの影響限定的） | （誤ったDVの伝播）
メモリ要件 | 全体トポロジを保存 | 隣接DVのみ保存
実際の使用 | OSPF, IS-IS | RIP, BGP（経路ベクトル）
6.1 メッセージ複雑度
- **LS**：各ノードがリンク状態をすべてのノードにブロードキャスト。Nノード、Eリンクの場合O(N x E)メッセージ
- **DV**：隣接ノード間でのみ交換するが、収束までのメッセージ数は不確定
6.2 収束速度
- **LS**：O(N^2)またはO(N log N)で収束
- **DV**：収束速度が不確定で、count-to-infinity問題が発生する可能性
6.3 堅牢性（Robustness）
- **LS**：あるノードが誤ったリンクコストを通知しても、他のノードは独自に最短経路を計算するため影響が限定的
- **DV**：あるノードの誤った距離ベクトルがネットワーク全体に伝播する可能性
7. ルーティングアルゴリズムの実際の適用
実際のプロトコルとアルゴリズム
================================
ルーティングプロトコル | ベースアルゴリズム | 使用範囲
----------------------+-------------------+------------------
RIP | DV | 小規模AS内部
OSPF | LS | 大規模AS内部
IS-IS | LS | ISPネットワーク
BGP | 経路ベクトル | AS間（インターネット全体）
EIGRP | DV改良 | Ciscoネットワーク
8. まとめ
| 概念 | 核心内容 |
| ----------------------- | ------------------------------------------------ |
| Link-State | 全体トポロジベース、ダイクストラアルゴリズム使用 |
| Distance-Vector | 隣接情報のみ使用、ベルマン-フォード方程式ベース |
| ベルマン-フォード方程式 | d(x,y) = min over v of c(x,v) + d(v,y) |
| Count-to-infinity | DVでリンクコスト増加時の収束遅延問題 |
| Poisoned Reverse | 経由ノードに無限大コストを通知してループを防止 |
| LS振動 | 負荷敏感コスト時の経路振動、ランダム化で解決 |
次の記事では、これらのルーティングアルゴリズムが実際のインターネットでどのように適用されるか、OSPFとBGPプロトコルを通じて見ていきます。
参考資料
- James F. Kurose, Keith W. Ross, "Computer Networking: A Top-Down Approach", 6th Edition, Chapter 4
- E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs", 1959
- R. Bellman, "On a Routing Problem", 1958
현재 단락 (1/174)
ルーティングアルゴリズムは、送信ホストから受信ホストまでの最適経路を決定します。ネットワークをグラフとしてモデル化し、ノード間の最小コスト経路を計算することが核心です。