[Network] 라우팅 알고리즘

✅ 개요

✅ 라우팅 알고리즘 분류

Global / Decentralized을 기준으로 분류

Global

• 모든 라우터가 모든 링크에 대한 비용을 알고 있다면:
→ Link State Algorithm을 사용하자.

Decentralized

• 각 라우터는 인접한 링크에 대한 비용만 알고 있고,

• 반복적인 계산을 통해 인접한 라우터끼리 정보를 교환한다면:
→ Distance Vector Algorithm을 사용하자.

Static / Dynamic을 기준으로 분류

Static

• 라우팅 경로가 천천히 바뀜 (거의 바뀌지 않음)

Dynamic

• 라우팅 경로가 빠르게 바뀜
• 링크 비용 변경에 대해 주기적으로 업데이트

✅ Link State

• 클러스터 안에서 Centralized한 기법이다.

• 대표적으로 다익스트라 알고리즘이 있다.

Dijkstra Algorithm

• 모든 노드에 대한 링크 비용을 알고 있다.

• 모든 노드가 같은 정보를 가진다.

• 하나의 출발지에서 하나의 도착지까지 최소 비용을 계산한다.

<단점>

• n개 노드가 있다고 가정

• 시간복잡도 O(n^2)

• 최대한 줄여도 O(n log n)
→ 너무 느리다!

Notation

• C(x, y)
• x에서 y까지의 링크 비용을 나타낸다
• ∞라면 도달할 수 없다는 뜻이다.

• D(v)
• v로 가기 위한 링크의 현재 비용이다.

• P(v)
• v로 도달하기 바로 직전 노드이다.

• N’
• 최단 비용으로 계산된 경로의 집합이다.

예제

✅ Distance Vector

• 클러스터 안에서 Decentralized한 기법이다.

• 대표적으로 벨만 포드 알고리즘이 있다.

Bellman-Ford Algorithm

• dx(y)
• x에서 y까지의 최소 비용
• 만약 중간 지점 v를 거친다면, dx(y) = min { c(x,v) + dv(y)}로 나타낼 수 있다.

예시 1

• du(z) (u → z)를 구하고 싶을 때 위와 같이 구할 수 있다.

예시 2

• 오른쪽 그림과 같이 x, y, z 라우터가 연결되어 있을 때, distance vector 알고리즘을 통해 최소 비용을 구하는 과정을 나타낸 그림이다.

한계점

• 링크의 비용이 더 저렴하게(좋게) 바뀔 때는 아무 이상이 없다.

• 하지만, 링크의 비용이 비싸게(나쁘게) 바뀔 때는 이터레이션이 발생한다.



→ 이러한 현상을 Bad news travels slow 라고 부른다.

✅ Link State와 Distance Vector 비교

Message Complexity

• LS → Bad
• n개 노드, e개 링크일 때 O(ne)번 메시지 전송

• DV → Good
• 이웃으로부터만 받으면 됨

Speed of convergence

• LS → Good
• O(n^2)으로 O(ne)개 메시지 한 번씩만 계산하면 됨

• DV → Bad
• Bad news travel slow 문제로 인해 무한루프 생성 가능성

Robustness

• LS → Good
• 각 노드별로 테이블 보유

• DV → Bad
• 잘못된 정보가 모든 네트워크에 전파될 가능성

✅ Hierarchical rounting

• 기본적으로 같은 클러스터(AS) 내에서는 같은 라우팅 프로토콜 사용
→ intra-AS

• 다른 클러스터와의 연결은 Gateway router를 통해 연결
→ inter-AS

여러 AS를 거쳐야할 때 AS를 선택하는 방법

• 어떠한 라우터에서 x로 간다고 가정한다.

1. 먼저, x로 가는 경로 중 AS 개수가 적은 쪽으로 선택한다.

2. AS 개수가 같다면, 클러스터 내부에서 게이트웨이까지 더 짧은 경로(비용이 적은)로 선택한다.
→ Hot Potato 기법

3. 2번마저 같다면, 랜덤하게 선택한다.