Routing algorithm - Distance vector

---

Distance vector

Distance vector algorithm은 전체 Topology를 이용하여 최단경로를 분석하는 것이 아니라 Dynamic programming 기법과 유사하게 부분부분에서 최선의 선택을 하여 결론적으로 적절한 경로로 네트워킹을 할 수 있도록 하는 알고리즘이다. 아래와 같이 최선의 경로를 조금씩 쌓아가는 것이다.

예를 통해 살펴보면 이해가 훨씬 쉽다.

dv(z)는 v에서 z까지 가는 최단 경로라는 뜻이다. u에서 z까지 가는 최단경로를 구하고 싶다면 u의 주변노드에서 z까지 가는 최단 경로를 구했다고 가정하였을때 인접노드인 v,x,w까지의 시간은 u가 알고 있으므로 인접노드까지 가는 시간+해당 노드에서 z까지 걸리는 시간을 한 3가지 값중 최소값을 구하면 그 경로가 최단경로가 되는 것이다.

Node가 XYZ 세개만 있는 단순한 상황에서 노드들이 최단경로를 파악하는 과정을 살펴보자.

서로서로 본인상황에서 주변 노드로 가는 최단시간을 알려주면서 최단경로를 갱신하여 시간을 갱신해주는 모습이다. 결국 모든 노드의 테이블에서 같은 값을 갖게 되면 최적화가 완료되었다고 볼 수 있다.

---

Link cost changes

link의 cost는 언제든 바뀔 수 있는 dynamic한 상태이다. 이에 대처할 수 있도록 전체 topology를 따지는 방식이 아닌 Distance Vecter를 이용하는 것이니 DV 알고리즘이 대처하는 방법을 살펴보자.

우선 아래와 같이 link cost가 줄어들어 네트워크 상황이 개선되는 case를 보자.

t0 시점: 'y' 라우터가 링크 비용 변경을 감지하고, 자신의 거리 벡터(DV)를 업데이트한 후 이웃들에게 알린다. 

t1 시점: 'z' 라우터가 'y'로부터 업데이트를 받고, 자신의 테이블을 업데이트하여 'x'로 가는 최소 비용을 계산한 후, 자신의 이웃들에게 자신의 DV를 전송한다.

t2 시점: 'y' 라우터가 'z'로부터의 업데이트를 받지만, 'y'의 최소 비용은 변하지 않으므로 'z'에게 메시지를 보내지 않는다.

 

Good news travels fast라는 말이 있다. 좋은 방향으로 개선이 되면 빠르게 네트워크 길을 찾을 수 있는 것이다.

이번에는 cost가 4였던 link가 60까지 늘어난 네트워크 상태가 안좋아진 케이스이다.

위의 케이스에서는 44번의 소통이 있어야 알고리즘이 안정화가 된다. 정말 단순한 세개의 노드 사이의 네트워킹인데도 문제가 생긴 것을 알 수 있다.

 

Bad news travels slow라는 말이 왜 있는지 알 수 있는 대목이다.

왜 이런 일이 발생하는지 자세히 살펴보자.

노드가 4개인 경우에 대한 예시이다. 바로 위의 표를 보면 X와 Y사이의 cost가 바뀌었다는 사실을 알게 되고 Y가 X로 가는 최적 경로를 변경하는데 전체 구조를 모르니 Z에서 X로 6만에 갈 수 있다는 오래된 정보를 기반으로 그럼 Y에서 Z까지의 cost가 3이니 둘을 더하면 9여서 변화된 60보다 훨씬 효율적이니 그 경로가 최적 경로라고 인지하고 9로 바뀌고 X,Y 경로를 지나가던 모든 네트워크들이 지난 정보를 통해 계속해서 수정해서 6->9->10->11->15->16... 계속해서 반복해야한다. 이값이 60을 넘게 되면 그때야 알고리즘이 안정된다. 치명적인 문제라고 볼 수 있다.

---

Link State VS Distance Vecter

message complexity

LS: 노드 n개, 링크 E개가 있을 때, O(nE) 메세지들이 전송된다. 

DV: 이웃과만 정보 교환한다.

 

speed of convergence

LS: O(n²) 알고리즘으로 O(nE) 메시지가 요구된다. 때때로 (oscillations)이 발생할 수 있다.

DV: 수렴 시간은 다양하고 라우팅 루프나 무한 카운트(count-to-infinity) 문제가 발생할 수 있다.

 

라우터 오작동 시의 robustness

LS: 노드가 잘못된 '링크' cost를 알릴 수 있다. 각 노드는 자신의 테이블만 계산한다.

DV: 노드가 잘못된 '경로' cost를 알릴 수 있다. 각 노드의 테이블이 다른 노드에 의해 사용된다. 오류가 네트워크를 통해 전파될 수 있다.

---