[3. Network Layer] Routing Algorithm - Link State and Distance Vector

송신자로부터 수신자까지 어떤 라우터를 통과해야 하는지 결정하는 알고리즘이 라우팅 알고리즘이다.

라우팅 알고리즘에는 Link State 알고리즘과 Distance Vector 알고리즘이 있다.

 

Link State Algorithm

LS 알고리즘은 링크 비용과 네트워크 토폴로지가 이미 알려져 있는 상태라고 가정하고 해당 값을 사용하여 경로를 결정하는 알고리즘이다.

즉 모든 노드는 자신의 상태를 브로드캐스트를 통해서 자신의 현상태를 알린다. 

링크 상태 알고리즘의 대표적인 알고리즘은 다익스트라 알고리즘이다. 네트워크의 모든 경로와 비용이 알려져 있기 때문에 다익스트라 알고리즘을 통해서 최적의 경로를 찾을 수 있다.

 

LS 알고리즘을 수행 하면 라우터는 각 노드에 대해 최소 비용을 알 수 있게 된다.

 

Distance Vector Algorithm

DV 알고리즘은 LS 알고리즘과 달리 노드들에 대한 정보가 없는 상태이다. 그렇기 때문에 반복적, 비동기적, 분산적으로 자신과 직접 연결된 노드로 부터 정보를 제공받고 계산을 한다. 그 계산된 정보를 다시 자신의 이웃들과 공유한다. 이러한 과정은 더 이상 정보를 업데이트 할 필요가 없을 때 까지 진행된다. 

 

최소 비용을 결정 하는 식은 벨만-포드 식으로 나타낼 수 있다.

Dx(y) = minV { c(x,v) + Dv(y)}

 

x 에서 y로 가는 경로는 x 에서 v까지 가는 비용에 v에서 y까지의 거리이다

 

DV 알고리즘에서는 각 라우터는 제공 받은 정보를 통해서 자신의 포워딩 테이블의 엔트리를 갱신하게 된다. 

 

DV 알고리즘에서 링크의 상태의 변화에 따른 문제점이 있다.

첫번째 경우 링크의 비용이 줄어들면 큰 문제는 없다. 하지만 반대로 링크의 비용이 증가하게 되면 무한 계수 (count to infinity)문제가 발생하게 된다. 이 문제를 해결하기 위해서 Poison Reverse를 통해서 거리를 무한대로 설정하는 것이다. 역경로를 차단하면서 올바른 거리로 계산되게 할 수 있는 것이다.