20180429 14 : Distance Vector

d_x(y) = min{c(x,v) + d_v(y)}

위의 내용을 재귀적으로 구하는 형태이다. 각 노드는 Distance Vector(Distance List) 를 자신과 이웃한 노드들에게 넘겨주고 계산을 취한다.

Link state 는 전체 그래프를 알고있는 상태에서 다익스트라 알고리즘을 수행한 것이고 Distance Vector 는 부분적으로 값들을 전달, 전달하는 모습으로 결과적으로 특정 결과값이 나오는 형태이다.

예시를 보자

아래와 같은 그래프가 존재한다.

해당 그래프를 Distance Vector 로 재귀적 계산을 실시할 수 있다.

시간 0

시간 1

시간 2

...

시간 n 

이렇게 있는 상황에서 특정 노드에 대한 distance vector 가 변하는 이상 업데이트가 없을 때 까지 재귀적으로 값을 계산해나간다. 라운드를 계속해서 나아가도록 한다. 부분 부분 있는 정보들에 대해서 전달하면서 최종적으로 가장 최적의 비용을 가지도록 한다.

만약에 안정화가 되어버리면, (업데이트가 없는 상태) 에 X 와 Y 의 link cost 가 4 에서 1로 변경되었음을 가정한다면 어디를 바꾸어야 하는가?

link cost 가 들어간 모든 부분을 변경해주어야 한다. c(x, y) & c(y, x)의 값을 변경시켜주어야 한다. link cost 가 줄어든 경우는 큰 문제없이 변경이 완료되지만, link cost 가 늘어난 경우는 좀 더 많은 작업들을 거치게 된다. y에서 x로 가는 값이 4에서 50으로 변경된다면 라운드를 거쳐가면서 계속 작업을 수행한다. 그리고 이 현상을 count - infinite 라고 하며, 이러한 현상이 생기는 이유는 전체 큰 그림을 가지지 못한채 부분적인 정보에 의존해 계산을 하다보니 상대방이 보내는 값이 자기 자신을 의존하는 값인지 모르고 블라인드인 상태에서 계속 계산하는 것이다.

count-infinite 문제를 해결하기 위해서, 무한대의 값을 넘겨주어야 한다. 의존하는 정보에 대해서 무한대인 값을 넘겨주고 해당 값을 다시 계산하는 경우 올바르게 값이 계산될 수 있도록 한다. 그 후 라운드를 적게 이용하여 값이 넘어갈 수 있다.

여러가지 시나리오를 생각하는 것이 매우 중요하다.

link state 와 distance vector 는 모든 잠재적인 목적지를 향한 최단거리를 구하는 것이다. link state 는 전체 그래프를 알고 있는 상태이다. broad cast 를 해야하지만, 해당 broad cast 의 범위는 하나의 네트워크에 국한되서 내부에서 라우팅 되어 사용되는 알고리즘이다. 각각의 네트워크에서의 자치권이 틀리며 해당 라우터 알고리즘이 link state 냐 혹은 distance vector 이냐를 결정할 수 있다. 그리고 각각의 네트워크를 거쳐서 라우터를 거쳐가는 경우에는 distance vector 알고리즘을 사용하는 것이다. 

[ 참고 동영상 ]

[ 컴퓨터 네트워크 ]

정리 )

• distance vector 알고리즘 계산
• distance vector 의 두 개의 노드의 값이 기존의 값보다 작게 변경되었을 때
• distance vector 의 두 개의 노드의 값이 기존의 값보다 크게 변경되었을 때
• distance vector 에서 count - infinite 란 무엇인가
• link state 알고리즘에서 broad cast 의 범위
• distanace vector 알고리즘은 어느 부분에서 사용되는가