4.5 routing algorithms

Routing algorithm

Global

• link state(LS) routing protocol
  • 각 노드가 네트워크에 대한 연결 상태만 전달해서 각자 그래프 형태의 지도를 만들고, 독립적으로 다음 최단 거리를 찾는 방식
  • algorithm: Dijkstra
    • 하나의 노드에서 시작해서 다른 노드에 대해 최단 거리를 계산하는 방식
    • algorithm complexity
      • N’에 포함되지 않은 모든 노드를 체크해야함
      • n(n + 1) / 2: O(n^2)
      • 우선순위 큐를 사용하면 O(nlogn)

Decentralized

• Distance vector routing protocol
  • 각 노드가 Bellman-Ford algorithm을 이용해서 DV(Distance Vector)를 업데이트하고, 이웃들에게 업데이트된 routing table을 공유하면서 최단 거리를 찾는 방식
  • algorithm: Bellman-Ford
    • 이웃을 한번 들렸다가 목적지까지 가는 방법들 중 가장 짧은 것이 최단거리이다.
  • Distance vector

Hierarchical routing

지금까지 routing에 대해 배운 내용은 굉장히 이상적인 내용이다

실제 세상에서는

• 모든 라우터는 똑같지 않고
• 네트워크도 flat하지 않다
• 스케일도 훨씬 크다(routing table에 60억 개의 dest를 저장할 수 없음)

그래서 지방 자치를 도입했다!

autonomous systems(AS): router들을 지역별로 모은다

• intra-AS routing protocol: 같은 AS 안에 있는 라우터들은 같은 routing protocol을 사용한다