Distance vertor algorithm

distnace vertor 알고리즘은 Bellman-Ford 알고리즘 즉, Dynamic Programming에 기반한다.

• u부터 z까지의 거리를 재귀적으로 구한다.
• 라우터는 목적지까지의 모든 경로를 테이블에 저장하지 않고, 비용이 제일 적게 드는 인접 라우터만 저장한다.
• 자기가 알고 있는 라우터 정보를 이웃 라우터에게 전달해준다. 이때 라우터 정보를 vector(array)로 보낸다고 해서 distance vector algorithm 이란 이름이 붙었다.
• 인접한 라우터가 가진 테이블을 서로 교환하며 각자의 테이블을 갱신한다.

Key idea

각 노드는 각자의 distance vector 측정치를 이웃에게 전달한다.

만약 x가 새로운 distance vector (이하 DV)를 이웃으로부터 전달받았다면, x는 B-F equation을 사용해서 자신의 DV를 업데이트한다.

B-F equation은 다음과 같다.

이렇게 구한 Dx(y)는 실제 최소 비용인 dx(y)에 수렴한다.

iterative, asynchronous

반복적이고 비동기적으로 발생한다.

각각의 local iteration은 local 경로 비용이 변경되었을 때 또는 이웃으로부터 업데이트된 DV를 받았을 때 발생한다.

distributed

각 노드들은 자신의 DV가 변경되었을 때 이웃 노드들에게 알려준다.

Distance vertor algorithm

참고
네트워크 계층