LS 라우팅, DV 라우팅

네트워크의 network layer에서 가장 중요하게 다루는 내용 중 하나인 Routing algorithm에 대해서 보도록 하자.

저번에 control plane과 data plane에 대해서 언급한 적이 있었다. 그 중 control plane에서는 data를 전송할 때의 최적의 path를 찾아주는 Routing을 담당한다고 했다. 그렇다면 구체적으로 어떻게 Routing이 이뤄지는지 알아보자.

전통적 Routing 방식
: Per-Router control plane

• 모든 라우터의 control plane이 서로 상호작용하는 방식이다.

그렇다면 최적의 길이라는 것은 뭐고, 어떻게 그것을 찾을까.

최적의 길은 결국, src 라우터부터 dest 라우터까지 최소비용이 드는 path를 의미한다.
그렇다면 그 최소비용길(least-cost path)는 어떻게 찾을까.

그 해답은 바로 Routing Algorithm이다. 몇 가지 종류의 알고리즘을 기반으로 한 라우팅을 사용하는데, 그 방식과 과정 모두 다르다.

1) Link State(LS) 알고리즘

• Centralized (global)
• neighbor의 정보를 모두에게 전달 - "Broadcasting"
• 모든 라우터들이 전체 네트워크에 대한 정보를 동일하게 갖고 있음
• Link cost 변화시 상대적으로 빠른 수렴
• Dijkstra 알고리즘 기반
• OSPF intra-as 라우팅에 사용 (다음 글에서 소개)

2) Distance Vector(DV) 알고리즘

• Decentralized
• adjacent 라우터들끼리만 정보 교환 (only with neighbor) - "no broadcasting"
• Link cost 변화시 여러번의 iteration 필요(worst case: Count-to-Infinity 발생)
• Bellman-Ford 알고리즘 기반
• RIP intra-as 라우팅에 사용 (다음 글에서 소개)

끝!