[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를 말하는 것입니다.
말로 풀어쓰자니 조금 어려운데, 자세한 것은 벨만포드 알고리즘을 복습해보면 정확히 이해가 갑니다.
[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
벨만-포드 알고리즘(Bellman-Ford Algorithm)이란?
velog.io
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 고장 시.. 등 일어납니다.