ルーティングプロトコル

📅

loading..🐩🐩🐩🐩

ルーティングプロトコル（Routing Protocols） 🔗

ルーティングプロトコルの目的

ルーターで構成されるネットワークを通り、送信ホストから受信ホストへ向かう
適切な経路
を決めます。
- 経路とは、指定された送信ホストから最終目的地のホストまで、パケットが通過するルーターの順序です。
- 適切な経路とは、コストが最小、最速（遅延が最小、スループットが最大）、混雑が最小といった経路です。

ネットワークをグラフとして表す（Network Graph Abstraction） 🔗

グラフ G = (N, E)

N = ルーターの集合 =

{u, v, w, x, y, z}

E = リンクの集合 =

{(u, v), (u, x), (v, x), (v, w), (x, w), (x, y), (w, y), (w, z), (y, z)}

c(x, x') = リンク (x-x') のコスト

例 c(w, z) = 5

コストは一律に1とすることも、帯域幅に反比例させたり、遅延や混雑を反映させたりすることもできます。
経路 $(x_1, x_2, ..., x_n)$ のコストは $c(x_1, x_2) + c(x_2, x_3) + ... + c(x_{n-1}, x_n)$ です。

問題。

u

と

z

の間で最もコストが小さい経路はどれでしょうか。

ルーティングアルゴリズムは、この最小コストの経路を探します。

ルーティングアルゴリズムの分類（Routing Algorithm Classification） 🔗

ルーティングアルゴリズムには、基本となる2つの分類軸があります。

Global
（大域型）か
Decentralized
（分散型）か
Static
（静的）か
Dynamic
（動的）か

大域型と分散型 🔗

Global

では、すべてのルーターがネットワーク全体の情報を持ちます。

ネットワーク全体の情報を使って最適な経路を決めます。

Decentralized

では、各ルーターは隣接ルーターに関する情報だけを持ちます。

隣接ルーターの情報を使って最適な経路を決めます。

静的と動的 🔗

Static

ネットワークのリンク状態がゆっくり変化する場合に使います。

Dynamic

ネットワークのリンク状態が急速に変化する場合に使います。

5.2.1 ルーティングプロトコル - リンクステート（Link State Routing Protocol） 🔗

リンクステートルーティングアルゴリズム（Link State Routing Algorithm） 🔗

ダイクストラ法（Dijkstra's Algorithm）

ネットワークトポロジーとリンクコストは、

すべてのノード

に知られています。

リンクステートのブロードキャスト
で情報を共有します。
すべてのノードが同じ情報を持ちます。

1つのノード（ルーター）から、ほかのすべてのノードまでの最短経路を求めます。

そのノードの転送テーブルを作ります。

反復処理を行い、

k

回の反復で

k

個のノードへの最短経路が見つかります。

表記

$N'$ は、最短経路が判明したノードの集合です。
$D(v)$ は、ノード $v$ までの最短経路の長さです。
$p(v)$ は、ノード $v$ への最短経路で $v$ の直前にあるノードです。
$c(x, x')$ は、リンク $x-x'$ のコストです。

def dijkstra(G, s):
		N' = {s}
		for each node v in G:
				if v != s:
						D(v) = c(s, v)
						p(v) = s
		while N' != N:
				find v not in N' such that D(v) is a minimum
				add v to N'
				update D(w) for each neighbor w of v and not in N':
						D(w) = min{D(w), D(v) + c(v, w)}
						p(w) = v

計算量の分析（Complexity Analysis） 🔗

$O(n^2)$ 。各ノードへの最短経路を求めるのに $O(n)$ かかります。

ヒープによる最適化

$O(n\log n + m)$ 。 $n$ 個のノードと $m$ 本のリンクがある場合です。

5.2.2 ルーティングプロトコル - ディスタンスベクター（Distance Vector Routing Protocol） 🔗

ディスタンスベクタールーティングアルゴリズム（Distance Vector Routing Algorithm） 🔗

**ベルマン–フォード法（Bellman-Ford Algorithm）**は、動的計画法を使います。

d_x(y)

は、ノード

x

からノード

y

までの最短経路の長さです。

$d_x(y) = \min_v\{c(x, v) + d_v(y)\}$ $d_{x} (y) = min_{v} {c (x, v) + d_{v} (y)}$
- $c(x,v)$ は、 $x$ から隣接ノード $v$ までのコストです。
- $d_v(y)$ は、隣接ノード $v$ から目的地 $y$ までのコストです。
- $\min$ は、 $x$ のすべての隣接ノード $v$ について計算します。
$D_x(y)$ $D_{x} (y)$ は、 $x$ $x$ から $y$ $y$ までの最小コストの推定値です。
- $x$ はディスタンスベクター $D_x = [D_x(y) : y \in N]$ を保持します。

反復的かつ非同期に、隣接ノードへディスタンスベクターを送ります。

各ノードの反復処理は、次のイベントで始まります。
- 自分のリンクコストが変化したとき
- 隣接ノードからディスタンスベクターの更新を受け取ったとき
分散型の動作
- 各ノードは、自分のディスタンスベクターが変わったときだけ隣接ノードに知らせます。

LSとDVのルーティングアルゴリズムの比較（LS vs. DV Routing Algorithm Comparison） 🔗

メッセージ複雑度

LSは、 $n$ 個のノードと $E$ 本のリンクに対して $O(nE)$ です。
DVは、隣接ノード間でのみメッセージを交換するため、メッセージ複雑度が小さくなります。

収束速度

LSの $O(n^2)$ のアルゴリズムには $O(nE)$ のメッセージが必要です。振動が起こる場合があります。
DVは、収束が遅い場合があります。

堅牢性

LSでは、ノードが誤ったリンクコストを通知する可能性があります。
DVでは、ノードが誤った経路情報を伝播する可能性があります。

ルーティングプロトコル | PromleeBlog