Routing Algorithm _ link statement

Routing Algorithm 

 

   forwarding table의 entry를 구성하는 방법

 

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

 

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

 

Link State routing algorithm

 

   - 전체 노드에 broad cast을 통해 각 라우터가 전체 네트워크의 구성과 링크 상황을 다 알고 있는 상황에서 최적의 경로, 최단 경로의 트리를 구성한다. 

 

   - 다익스트라 알고리즘(Dijkstra Algorithm) : 기준 노드에서 시작하여 최단 비용의 경로가 알려진 노드 집합 (N)을 넓힘을 반복한다.

Dijkstra algorithm 그림 1

   - 위 예시에서 처음 기준 노드를 U라고 했을 때, N 집합은 자신 뿐이다. N 집합에서 이웃된 노드(X, W, V) 중에 최소 비용으로 도달할 수 있는 지점은 W이므로, N 집합에 W를 추가한다.

 

 

Dijkstra algorithm 그림 2

   - 그림 2에서 표시된 N 집합에서 이웃된 노드 (X, V, Y) 중 다시 U에서 최소 비용으로 갈 수 있는 노드를 찾으면 경로 (U->X)으로 노드 X이다. 따라서 이 이후에는 U에서 이동할 때, W->X 경로를 이용할 이유가 없어진다.

 

Dijkstra algorithm 그림 3

   - 위와 마찬가지로 N 집합이 U, X, W를 포함한 상태에서 가장 가까운 노드는 V이고 위 X->W 경로와 마찬가지로 V를 도달하기 위해선 U-> V 경로는 의미가 없어질 것이다.

 

Dijkstra algorithm 그림 4

   - 이런 식으로 최단 경로를 아는 노드의 집합을 기준으로 이웃한 노드 중 가장 최소의 경로를 얻을 수 있는 노드를 체크하고 의미없는 경로를 지워나가는 것을 반복하면 위 예시에서 최단 경로 트리는 다음과 같다.

 

Dijkstra algorithm 그림 5

   - 위 최소 경로 트리가 곧 U 노드를 기준으로 해당 네트워크 안에서 최소 비용으로 목적지에 도달 할 수 있도록 하는 노드가 된다. 트리를 찾는 프로세스와 포워딩 테이블은 다음처럼 표로 나타낸다.

 

프로세스 표와 U에서의 forwarding table

   ** 노드 별 forwarding table은 당연히 다르겠지만 다음 목적지를 찾는 프로세스는 동일하다.

 

   ** link statement 방식은 모든 라우터에서 네트워크의 모든 상황을 다 알게해야하므로 네트워크 범위 결정이 중요하다. 보통 한 도메인에 속하는 네트워크를 기준으로 처리한다.

  

Note