[コンピュータネットワーク] 13. ルーティングアルゴリズム：Link-StateとDistance-Vector

ネットワークグラフの例
=======================

        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

ルーティングアルゴリズムの分類
================================

1. 情報範囲による分類：
   - 全域的（Global）：すべてのノード情報を知って計算 --> Link-State
   - 分散的（Decentralized）：隣接情報のみで反復計算 --> Distance-Vector

2. 動作方式による分類：
   - 静的（Static）：経路がほとんど変わらない
   - 動的（Dynamic）：ネットワーク変化に応じて定期的に再計算

3. 負荷感度による分類：
   - 負荷敏感（Load-Sensitive）：リンク混雑度をコストに反映
   - 負荷非敏感（Load-Insensitive）：現在のインターネットルーティング方式

ダイクストラアルゴリズム（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'に含まれるまで反復

ダイクストラ実行過程（出発：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）

LS振動問題の例
=================

時点1：A -> B経路に大部分のトラフィックが流れる
  --> A -> Bリンクコスト増加

時点2：すべてのノードがA -> C -> D -> B経路に切り替え
  --> A -> Cリンクコスト増加

時点3：再びA -> B経路に切り替え（振動繰り返し）

解決策：ルーティング更新タイミングをランダム化

ベルマン-フォード方程式
========================

d(x, y) = min { c(x, v) + d(v, y) }
           v

ここでvはxのすべての隣接ノード

意味：xからyまでの最小コストは
  = xから隣接ノードvまでのコスト + vからyまでの最小コスト
  この値が最小となる隣接ノードvを経由して移動

DVアルゴリズムの動作
=====================

各ノードxは以下を保持：
  - c(x,v)：隣接ノードvまでのリンクコスト
  - Dx：xの距離ベクトル（すべての宛先までの推定コスト）
  - Dv：各隣接ノードvの距離ベクトル

動作：
  1. 初期化：直接接続された隣接はリンクコスト、残りは無限大
  2. 隣接ノードから距離ベクトルを受信すると：
     Dx(y) = min { c(x,v) + Dv(y) }（すべての隣接ノードvについて）
  3. 自分の距離ベクトルが変更されたらすべての隣接ノードに送信
  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を隣接ノードに伝播、変化がなくなれば終了

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回反復後にようやく収束！

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

  --> 即座に正しい値に収束！

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（経路ベクトル）

実際のプロトコルとアルゴリズム
================================

ルーティングプロトコル | ベースアルゴリズム | 使用範囲
----------------------+-------------------+------------------
RIP                   | DV                | 小規模AS内部
OSPF                  | LS                | 大規模AS内部
IS-IS                 | LS                | ISPネットワーク
BGP                   | 経路ベクトル       | AS間（インターネット全体）
EIGRP                 | DV改良            | Ciscoネットワーク