Routing Algorithm

목적 : 출발지 라우터 - 목적지 라우터까지 최적의 경로 찾기

• 최적의 경로 : 최소의 비용(congestion, bandwidth, distance 등)을 고려하여 가장 빠르게 목적지까지 도달할 수 있는 경로

종류

Link State Algorithm

모든 라우터들의 정보(link cost)를 알고 있는 경우

• 어디서 사용되나? : OSPF
• 어떻게 경로를 찾는가?
  • Dijkstra's Algorithm (다익스트라) 사용
    • 한 노드에서 주위의 모든 노드까지 가는 최단경로를 구하는 알고리즘

Notation

Pseudo Code

Example

Distance Vector

자신과 이웃한 라우터의 정보(distance vector)만 알고 있는 경우

• 어디서 사용되나?
  • RIP, BGP
• 어떻게 경로를 찾는가?
  • Bellman-Ford Algorithm (벨만 포드) 사용
    • DP 방식을 통해