Routing Algorithm _ distance vector

Routing Algorithm 

 

   forwarding table의 entry를 구성하는 방법

 

   - 링크 상태 라우팅 알고리즘(Link State Routing Algorithm)

 

   - 거리 벡터 라우팅 알고리즘(Distance Vector Routing Algorithm)

 

Distance Vector 

 

   - 이웃하는 노드의 거리 테이블만을 아는 상황에서 최소의 거리를 구한다.

 

   - x에서 y로 향하는 거리의 최솟값은 { x에서 이웃한 v 노드까지의 거리 + v 노드에서 y까지의 거리의 최솟값 }의 최솟값과 같다.

distance vector // reculsion

    - 자신의 distance vector 또는 그 안의 cost 값이 변경 시 이웃한 노드에게 vector을 전달하여 update.

 

Example

그림 1

   - 그림 1은 x,y,z에서 각각에 도달하는데 걸리는 cost를 표시한 것이다. 

 

   - x,y,z에서 각각의 이웃한 노드에 도달하기 위한 cost는 알고 있으므로 초기 상태의 x,y,z의 distance table는 아래와 같을 것이다.

 

그림 2

   - 이웃한 노드까지의 거리만 알고 있는 상황에서 본인 벡터를 이웃한 노드에게 전달한다. 

 

그림 3

   - 서로의 벡터를 교환한 상태에서 x->z로 향하는 distance를 구하면 아래 식과 같고 따라서 그림 4와 같이 표가 update 되어야 할 것이다.

 

식 1, distance(x,z)

그림 4

  - x의 vector와 z의 vector가 update되었으므로 다시 이웃 노드에 벡터를 넘긴다.

 

그림 5

Issue :: Routing loop

 

그림 6

   - 그림 6은 위의 예시에서 x-y의 비용이 각각 1, 50으로 변한 예시이다. case 1처럼 비용이 줄어들 경우 변한 벡터만 이웃 노드에게 전달하고 거기에 따른 최소 distance를 다시 계산하면 되므로 한번에 update가 가능하다.

 

   - 문제는 그림 6의 아래 case 2처럼 비용이 늘어나는 경우에 있다.  

 

그림 7

   - 노드 y가 x와의 링크 비용 변화를 감지하고 새로운 최소 거리를 계산하면 위 그림 7 처럼 y는 z가 비용 5로 x에 도달할 수 있다는 사실과, 직접 x로 도달하려면 비용이 50, z까지의 비용은 1이라는 사실만을 알고 있다.

 

   - 따라서 y는 최소의 경로를 도출함에 따라 x로 도달하는 경로를 z를 거쳐 6의 비용으로 이동하려 하지만, 사실 z가 x로 도달하는 비용 5의 경로는 (z->y)를, 비용 6으로 y가 x에 도달하고자 하는 경로는 (y->z)를 포함하므로 그림 7 시기에 x를 목적지로 하는 패킷이 y, z에 도착한다면 y,z를 무한히 순회하는 라우팅 루프가 발생할 것이다.

 

   - 한마디로 비용이 갑자기 증가한 경우 다른 루트의 중간 과정에 본인 노드가 속하는지를 모르는 상태에서 최소의 거리만을 도출하다가 루프에 빠지는 것이다.

 

Issue :: Count infinity

 

   - 그림 7 상황에서 x 목적지로 향하는 패킷이 우연찮게 도착하지 않아 routing loop를 피할 수 있었다고 하자. y->x의 값이 변경되었으므로 y는 자신의 벡터를 다른 노드에 알려 update 하려 할 것이다.

 

그림 8

   - y는 z가 말하는 비용 5만에 가는 경로를 철썩같이 믿고 있는 상황에서, 반대로 z 역시 y가 말하는 비용 4만에 x에 도착하는 경로를 믿고 있다. 

 

   - y의 cost가 바뀜을 받은 z는 y->?->x 길만 믿고 자신의 z->y->?->x 길의 비용을 7로 수정할 것이다. 역시 이를 업데이트하면 y는 자신의 cost를 8로 수정하고 다시 업데이트하면 z는 9로 수정하는 것을 계속 반복하여 지연만 낳다가 결국에는 y->x의 비용이 50이라는 현실을 받아들일 것이다.

 

   - 이런 문제를 count infinity (무한 계수) 문제라고 한다.

 

Solution :: Poisoned reverse 

 

   - 이런 두가지 이슈는 한마디로 경로 꼬임에 의해 생기는 것이다. y가 x로 가는 경로를 z만 믿고, 또 z 역시 x로 가는 경로를 y에 의존하여 비용을 계산하여 이런 문제가 발생한 것이다.

 

   - 해결 방법은 따라서 간단하다. z가 y를 지나쳐 x를 도달한다면 y에게는 이 루트의 비용을 무한대로 알려주는 것이다. 이 방식을 이용한다면 y는 위와 같은 상황에서 z를 이용할 생각, 또 반대로는 자신을 지나치는 경로를 계산할 생각을 하지 않도록 할 수 있는 것이다.

 

poisoned reverse 사용 시 y->z를 이용하여 x에 도달하는 것을 시도하지 않음