5.2 라우팅 알고리즘

라우팅 알고리즘의 목표는 송신자부터 수신자까지 라우터의 네트워크를 통과하는 좋은 경로를 결정하는 것인데, 일반적으로 ‘좋은’ 경로란 최소 비용 경로를 말한다.

네트워크 제어 평면이 라우터별 제어 방식을 채택하든 논리적 중앙 집중형 방식을 채택하든 상관없이 패킷이 전송 호스트에서 수신 호스트로 이동하기 위한 잘 정의된 일련의 라우터가 항상 존재해야 한다.

라우팅 문제를 나타내는 데는 그래프가 사용되는데, 그래프는 G(N, E)로 나타낸다. N과 E는 각각 노드와 에지의 집합이고, 하나의 에지는 집합 N에 속하는 한 쌍의 노드로 표시된다.

그래프상의 노드는 패킷 전달 결정이 이루어지는 지점인 라우터를 나타내며, 이 노드들을 연결하는 에지는 라우터들 간의 물리 링크를 나타낸다.

에지는 그 비용을 나타내는 값을 갖는다. 이 비용은 해당 링크의 물리적인 거리, 링크 속도, 링크와 관련된 금전 비용 등을 반영한다.

집합 E에 포함된 어떤 에지 (x, y)에 대해 c(x, y)는 노드 x와 y간의 비용을 의미하는데, 만약 노드 쌍 (x, y)가 E에 포함되어 있지 않으면 c(x, y) = INF로 둔다. 모든 에지가 방향성을 갖지 않는 무방향성 그래프만을 고려한다. 에지(x, y)가 집합 E에 속하면, 노드 y는 노드 x의 이웃이라고 한다.

여러 에지들에 비용이 할당되고 나면 라우팅 알고리즘은 출발지와 목적지 간 최소 비용 경로를 찾는 것을 목표로 하게 된다. 만약 그래프의 모든 에지가 같은 비용을 갖는다면 최소 비용 경로가 바로 최단 경로가 된다.

라우팅 알고리즘을 분류하는 일반적인 방법 한 가지는 알고리즘이 중앙 집중형인지 분산형인지이다.

• 중앙 집중형 라우팅 알고리즘
  • 네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산한다.
  • 모든 노드 사이의 연결 상태와 링크 비용을 입력값으로 한다.
  • 계산 자체는 한 장소에서 수행되거나 모든 라우터 각각의 라우팅 모듈로 복사될 수 있다.
  • 해당 알고리즘이 연결과 링크 비용에 대한 완전한 정보를 갖는다는 점이 핵심적인 특징이다.
  • 전체 상태 정보를 갖는 알고리즘을 링크 상태(LS) 알고리즘이라고 하는데, 이는 이 알고리즘이 네트워크 내 각 링크의 비용을 알고 있어야 하기 때문이다.
• 분산 라우팅 알고리즘
  • 최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다.
  • 어떤 노드도 모든 링크의 비용에 대한 완전한 정보를 갖고 있지는 않다.
  • 각 노드는 자신에게 직접 연결된 링크에 대한 비용 정보만을 가지고 시작한다.
  • 분산 라우팅 알고리즘은 거리 벡터(DV) 알고리즘이라고 부르는데, 각 노드가 네트워크 내 다른 모든 노드까지 비용의 추정값을 벡터 형태로 유지하기 때문이다.

라우팅 알고리즘을 분류하는 두 번째 방식은 정적 알고리즘과 동적 알고리즘으로 분류하는 것이다.

• 정적 라우팅 알고리즘
  • 경로는 아주 느리게 변하는데, 종종 사람이 개입한 결과로 그렇게 된다.
• 동적 라우팅 알고리즘
  • 네트워크 트래픽 부하나 토폴로지 변화에 따라 라우팅 경로를 바꾼다.
  • 주기적으로, 혹은 토폴로지나 링크 비용의 변경에 직접적으로 응답하는 방식으로 수행된다.
  • 네트워크 변화에 빠르게 대응한다는 장점도 있지만, 경로의 루프나 경로 진동 같은 문제에 취약하기도 하다.

<aside> 💡 토폴로지(영어: topology, 문화어: 망구성방식)는 컴퓨터 네트워크의 요소들(링크, 노드 등)을 물리적으로 연결해 놓은 것, 또는 그 연결 방식.

</aside>