[Network] Routing Algorithms, Link-State와 Distance Vector

Routing이 뭔지 기억 나시나요?

Network Layer의 두 가지 핵심기능이 포워딩과 라우팅 이었죠,

포워딩은 라우터 내부에서 적절한 Input port -> Output port를, 라우팅 테이블을 기반으로 찾아가는 것이었고요,

 

라우팅은 Source -> Destination 까지의 전체적인 경로를 결정합니다.

 

이 라우팅 기법에는 두가지가 있는데요,

 

1. Link State routing

- 다익스트라 알고리즘

- OSPF

- Complete Topology

 

2. Distance Vector routing

- 벨만포드 알고리즘

- RIP

- Partial Topology(Info)

 

아직 무슨 소리인가 싶겠지만, 차근차근 알아봅시다.

 

라우팅 알고리즘을 어떻게 분류할까요?

아 참, 잠깐 복습해봅시다.

앞서 말할 때 3계층에서는 세 가지 프로토콜이 공존하고 있다고 했죠?

 

라우팅 프로토콜 / IP 프로토콜 / ICMP 프로토콜

포워딩 테이블을 작성 / 주소를 나타냄, Datagram 포맷 / 에러를 추적하고 컨트롤...

 

우선, 라우팅 알고리즘을 분류할 때는

Global 인지, Decentralized(=국소적인 부분을 보는지)인지 에 따라 분류합니다.

Global의 경우

- 모든 라우터가 전체의 배치와 각자의 비용을 알고 있고,

- "link state" 알고리즘을 사용합니다. 

- 다익스트라 알고리즘이고, OSPF 프로토콜 이라고도 해요.

 

Decentralized의 경우, 

- 라우터끼리 직접 연결된(한두다리 건너서도 포함) 사이는, Cost를 알고 있구요

- 이웃과 교류하며 반복적으로 연산이 들어갑니다.

- "distance vector" 알고리즘이고, RIP 프로토콜이라고도 합니다. 

- 벨만 포드 알고리즘이라고도 합니다.

 

Link State 라우팅 알고리즘의 표기법을 알아봅시다.

c(i,j)는, i 노드에서 j 노드로 갈 때의 비용을 말합니다.

D(v)는, Source에서 목적지인 V 까지의, 현재 기준 Cost를 말합니다.

p(v)는, 목적지의 직전 노드를 말합니다. 경로가 (S, ..., X, V) 이면 X가 p(v)가 되겠네요.

N은, 최소 비용의 경로의 집합을 말합니다.

테이블 채우기를 하기 앞서, 이론적인 부분을 알아봅시다.

Link-State의 경우, Parent-Child의 구조를 가집니다.

그리고, Physical topology를 Logical topology로 변환하여 접근합니다.

 

일종의 반장이 존재하는데,

- 반원들이 모든 정보(Topology)를 반장에게 전달하고,

- 반장이 이를 수집하여 각 노드(반원)에게 전달합니다.

- 보이지 않는 정보를 가지고 있게 되는거죠. Global 이라고 합니다.

 

라우팅 테이블에 꼭 필요한 정보는 무엇이 있을까요?

- 목적지 주소, 인터페이스(경유지), Cost(비용, 필수는 아님)가 필요하겠습니다.

 

 

이 테이블이 비어있었어야 하는데, 다 채워져 있으니 별 흥미가 없죠?

다시 만들어봅시다.

Step	start N	D(B),p(B)	D(C),p(C)	D(D),p(D)	D(E),p(E)	D(F),p(F)
0	A	2, A	5, A	1, A	INF	INF

 

첫 단계입니다. 이 중, Cost가 가장 작은 것을 고르는게 다익스트라의 원칙이니, D를 다음 노드로 둡니다.

 

Step	start N	D(B),p(B)	D(C),p(C)	D(D),p(D)	D(E),p(E)	D(F),p(F)
0	A	2, A	5, A	1, A	INF	INF
1	AD	2, A	4, D		2, D	INF

 

소소한 업데이트가 일어났는데요, D(C), p(C)가 D를 거쳐 가면서 비용이 4로 줄어들게 되어 업데이트가 있었구요

E로 가는 경로가 없었다가, 생겨나서 D(E),p(E)가 업데이트 되었습니다.

그 다음으로, Cost가 작은 것이 B와 E인데, 기왕 이렇게 된거 둘 다 해볼까요? 우선 E를 정하고 진행해보겠습니다.

Step	start N	D(B),p(B)	D(C),p(C)	D(D),p(D)	D(E),p(E)	D(F),p(F)
0	A	2, A	5, A	1, A	INF	INF
1	AD	2, A	4, D		2, D	INF
2	ADE	2, A	3, E			4, E

 

Step	start N	D(B),p(B)	D(C),p(C)	D(D),p(D)	D(E),p(E)	D(F),p(F)
0	A	2, A	5, A	1, A	INF	INF
1	AD	2, A	4, D		2, D	INF
2	ADE	2, A	3, E			4, E
3	ADEB		3, E			4, E

Step	start N	D(B),p(B)	D(C),p(C)	D(D),p(D)	D(E),p(E)	D(F),p(F)
0	A	2, A	5, A	1, A	INF	INF
1	AD	2, A	4, D		2, D	INF
2	ADE	2, A	3, E			4, E
3	ADEB		3, E			4, E
4	ADEBC					4, E

Step	start N	D(B),p(B)	D(C),p(C)	D(D),p(D)	D(E),p(E)	D(F),p(F)
0	A	2, A	5, A	1, A	INF	INF
1	AD	2, A	4, D		2, D	INF
2	ADE	2, A	3, E			4, E
3	ADEB		3, E			4, E
4	ADEBC					4, E
5	ADEBCF

 

얼추 메커니즘이 보이시죠?

그럼 앞서 2단계로 돌아가, B를 잡고 진행해보겠습니다.

 

Step	start N	D(B),p(B)	D(C),p(C)	D(D),p(D)	D(E),p(E)	D(F),p(F)
0	A	2, A	5, A	1, A	INF	INF
1	AD	2, A	4, D		2, D	INF
2	ADB		4, D		2, D	INF

Step	start N	D(B),p(B)	D(C),p(C)	D(D),p(D)	D(E),p(E)	D(F),p(F)
0	A	2, A	5, A	1, A	INF	INF
1	AD	2, A	4, D		2, D	INF
2	ADB		4, D		2, D	INF
3	ADBE		3, E			4, E

Step	start N	D(B),p(B)	D(C),p(C)	D(D),p(D)	D(E),p(E)	D(F),p(F)
0	A	2, A	5, A	1, A	INF	INF
1	AD	2, A	4, D		2, D	INF
2	ADB		4, D		2, D	INF
3	ADBE		3, E			4, E
4	ADBEC					4, E

Step	start N	D(B),p(B)	D(C),p(C)	D(D),p(D)	D(E),p(E)	D(F),p(F)
0	A	2, A	5, A	1, A	INF	INF
1	AD	2, A	4, D		2, D	INF
2	ADB		4, D		2, D	INF
3	ADBE		3, E			4, E
4	ADBEC					4, E
5	ADBECF

 

학습 도중에 진행해본 개인적인 공부라 틀릴 수는 있지만,

각 노드로 가는 가장 작은 Cost는 그대로네요.

순서를 달리 해도 결과에는 큰 영향이 없는 것 같습니다.

 

그리고 A에서 뻗어나가는 라우팅 테이블을 그릴 때는, 

 

우선 다익스트라 테이블을 만들어서 최단거리를 구한 뒤, 

이렇게, 인터페이스

즉 A에서 B쪽으로 뻗어나갈건지? D쪽으로 뻗어나갈건지? 가 기재된 테이블을 만들어야 합니다. 

 

다음으로는, Decentralized의 Distance Vector Routing Algorithm을 알아봅시다.

- 반복적이고, 

- 비동기적이고,

- 분산적인

특징이 있는데, 이것보다는 우선 DX(Y,Z)의 식을 주목해서 봅시다.

이것은 X에서 출발해서, (X, Z, ..., Y)의 경로로 간다는 이야기입니다.

즉, c(X, Z)(X에서 Z까지 가는 Cost) + min[Z에서 아무노드나 경유해서 Y로 가는 것들] 가 저 식인 것이죠.

 

이 예제도 잘 살펴봅시다.

오른쪽에, Cost via / Destination 테이블을 잘 살펴보면,

D^E, 즉 E에서 출발하여 경유할 수 있는 지점인 A, B, D가 via에 들어가 있구요,

빨간 동그라미에 속한 것은 최소 Cost를 말하는 것입니다.

말로 풀어쓰자니 조금 어려운데, 자세한 것은 벨만포드 알고리즘을 복습해보면 정확히 이해가 갑니다.

https://velog.io/@kimdukbae/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Bellman-Ford-Algorithm

[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

 

Distance Vector 알고리즘으로 라우팅 테이블을 만들면, 수렴하기까지의 과정이 필요한데요.

각각의 국소 해(테이블?)를 만들어 낸 뒤, 서로 상호작용 해서 최소 거리를 업데이트 해가며

최종적으로 테이블의 컨텐츠가 동일해지는, 수렴하는 상태로 만들어 내는 것입니다.

약간의 훈련이 필요하긴 한데요, 그건 개인적으로 조금 더 해보고

이쯤해서 이런 의문을 가질 수 있겠습니다.

 

1. 전체적으로, Distance Vector와 Link State 중에 누가 더 빠른가?

- Link State는 초기 과정, 준비 과정이 길고, Distance Vector은 테이블의 수렴까지 시간이 길기 때문에 전체 시간은 비슷합니다.

 

2. Network Topology가 바뀌었을 때는, 둘 중 어떤게 유리한가? 가령, 중간에 경유지가 하나 추가되었다던지.

- Link State가 강점을 가집니다.

 

3. Battle Field 같은, adhoc 무선 네트워크가 구축되는 상황에서는 어떤게 유리한가?

- 구성이 자주 변하는 경우는 Distance Vector가 유리합니다.

 

라우팅 테이블의 Conversion은 언제 일어날까요?

1. Network의 Topology 변화,

2. Link Failure 시,

3. Router 고장 시.. 등 일어납니다.