[네트워크] 라우팅 알고리즘 비교 | Link State 알고리즘, Distance Vector 알고리즘

라우팅 알고리즘

라우팅 알고리즘이란 송신 측에서부터 수신 측 라우터의 네트워크를 통과하는 최적의 경로를 결정하는 알고리즘이다. 그러나 실제로는 여러 가지 이유로 최적의 경로를 결정하지 못할 수 있다.

 

예를 들어 'A기관은 B기관이 소유한 네트워크가 보낸 패킷을 전달해서는 안된다'와 같은 규칙 등이 존재할 수 있다. 그럼에도 불구하고 최대한 최적의 경로를 결정하는 라우팅 알고리즘은 네트워크 분야에서 매우 중요하다.

---

라우팅 알고리즘 분류

라우팅 알고리즘은 중앙 집중형 혹은 분산형인지로 구분할 수 있다.

• 중앙 집중형(global) 라우팅 알고리즘 : 네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산한다. 즉 모든 라우터가 연결 상태와 링크 비용을 알고 있다는 것이다. Link State 알고리즘이 여기에 속하며 주로 다익스트라 알고리즘을 사용한다.
• 분산(decentralized) 라우팅 알고리즘 : 최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다. 어떤 라우터도 모든 링크 비용에 대한 완전한 정보를 갖고 있지 않지만, 각 라우터는 자신에게 연결된 인접 노드에 대한 링크 비용 정보를 알고 있다. 이후 반복된 계산과 인접 노드와의 정보 교환을 통해 목적지까지의 최소 비용 경로를 계산한다. Distance Vector 알고리즘이 여기 속하며 주로 벨만-포드 알고리즘을 사용한다.

 

또한 라우팅 알고리즘은 정적 알고리즘과 동적 알고리즘으로 구분할 수 있다. 

• 정적 라우팅 알고리즘 : 경로의 변경이 느리고 사람이 직접 링크에 대한 비용을 수정해야 한다. 규모가 큰 네트워크에서 일일이 수정하기 불가능하며 사람이 하기에 역부족이다.
• 동적 라우팅 알고리즘 : 네트워크 트래픽 부하나 topology 변화에 따라 라우터가 자체적으로 경로를 바꾼다. 동적 알고리즘은 주기적으로 topology나 링크 비용의 변경에 직접적으로 응답하는 방식으로 수행된다. 동적 알고리즘은 네트워크 변화에 더 빠르게 대응할 수 있지만 경로의 loop나 경로 진동과 같은 문제에 취약하다.

---

Link State 알고리즘(LS알고리즘 : 링크 상태 알고리즘)

LS 알고리즘은 중앙 집중형 알고리즘에 속한다. 즉 모든 라우터(노드)가 모든 링크(간선)의 비용을 알고 있기 때문에 다익스트라 알고리즘을 이용해 최적의 경로를 계산할 수 있다. 한 노드(source node)에서 다른 모든 노드까지의 최적경로를 계산해 routing table에 저장해 놓는다. 

 

 

다익스트라 알고리즘에 대해 잘 모른다면 다음 포스팅을 참고하자.

[알고리즘] 다익스트라(Dijkstra) 알고리즘이란? | c++ 다익스트라 구현

---

Distance Vector 알고리즘(DV알고리즘 : 거리벡터 알고리즘)

DV 알고리즘은 분산형 알고리즘에 속한다. 즉 각 노드는 자신에게 연결된 이웃의 링크의 비용만 알고 있기 때문에 벨만-포드 알고리즘을 이용해 최적의 경로를 계산할 수 있다. DV 알고리즘은 반복적이고 비 동적이며 분산적이다. 이웃끼리 반복해서 정보를 교환해 최적의 경로를 갱신하는 식이다. 

 

DV 알고리즘은 count-to-infinite 문제가 발생할 수 있다. 이 내용은 아래 포스팅을 참고하자.

[네트워크] poisoned reverse란? count to infinity 문제 해결법 | DV 알고리즘

 

벨만-포드 알고리즘에 대해 잘 모른다면 다음 포스팅을 참고하자.

[알고리즘] 벨만 포드(Bellman-Ford) 알고리즘 | c++ 벨만포드 구현

---

Link State 알고리즘과 Distance Vector 알고리즘 비교

 

LS 알고리즘	DV 알고리즘
네트워크 전체 인식	이웃한 라우터의 정보 인식
다익스트라 알고리즘	벨만-포드 알고리즘
링크 상태 정보만을 교환	이웃한 라우터와 라우팅 테이블 교환
이벤트 기반의 갱신 신호 교환	주기적으로 갱신 데이터를 교환