🚀

라우팅 프로토콜 (Routing Protocols) 🔗

라우팅 프로토콜 목표

라우터 네트워크를 통해 송신 호스트에서 수신 호스트로 가는
좋은 경로
(또는 라우트)를 결정한다
- 경로: 주어진 초기 송신 호스트에서 주어진 최종 목적지 호스트로 가기 위해 패킷이 통과할 라우터들의 순서
- 좋은 경로: 최소 비용, 가장 빠른(최소 지연, 최고 처리량), 최소 혼잡 등

🚀

네트워크 그래프 추상화 (Network Graph Abstraction) 🔗

graph: G = (N, E)

N = set of routers =

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

E = set of linkes =

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

c(x, x') = link (x-x')의 비용

ex) 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) 🔗

라우팅 알고리즘은 두 가지 기본 분류로 나뉜다

Global
또는
Decentralized
Static
또는
Dynamic

✅

Global vs. Decentralized 🔗

Global

: 네트워크 전체 정보를 모든 라우터가 가지고 있는 경우

네트워크 전체 정보를 사용하여 최적 경로를 결정

Decentralized

: 각 라우터가 자신의 이웃 라우터에 대한 정보만 가지고 있는 경우

자신의 이웃 라우터에 대한 정보만 사용하여 최적 경로를 결정

✅

Static vs. Dynamic 🔗

Static

네트워크 링크 상태가 천천히 변하는 경우에 사용

Dynamic

네트워크 링크 상태가 빠르게 변하는 경우에 사용

💡

5.2.1 라우팅 프로토콜 - 링크 상태 (Link State Routing Protocol) 🔗

🚀

링크 상태 라우팅 알고리즘 (Link State Routing Algorithm) 🔗

다익스트라 알고리즘 (Dijkstra's Algorithm)

네트워크 토폴로지와 링크 비용이

모든 노드

에 알려져 있다

링크 상태 브로드캐스트
를 통해 달성된다
모든 노드가 동일한 정보를 가진다

하나의 노드 (라우터)에서 다른 모든 노드까지의 최단 경로를 찾는다

해당 노드의 포워딩 테이블을 구성한다

반복적:

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 vs. DV 라우팅 알고리즘 비교 (LS vs. DV Routing Algorithm Comparison) 🔗

메시지 복잡도

LS: $n$ 개의 노드, $E$ 개의 링크에 대해 $O(nE)$
DV: 이웃 간에만 메시지를 교환하므로 더 작은 메시지 복잡도

수렴 속도

LS: $O(n^2)$ 알고리즘은 $O(nE)$ 메시지를 필요로 함
진동이 발생할 수 있음
DV: 수렴이 느릴 수 있음

견고성

LS: 노드는 잘못된 링크 비용을 광고할 수 있음
DV: 노드는 잘못된 경로 정보를 전파할 수 있음

추천 포스트

라우팅 프로토콜Routing Protocols