왜 라우터마다 경로 계산 방식이 다른가

14편에서 동적 라우팅은 라우터들이 서로 정보를 주고받아 라우팅 테이블을 자동으로 만든다는 것을 배웠습니다. 그런데 “서로 정보를 주고받는다”는 방식에는 크게 두 가지 철학이 있습니다. 하나는 이웃에게 “내가 어디까지 얼마나 걸리는지”만 알려주는 방식이고, 다른 하나는 네트워크 전체의 연결 지도를 모든 라우터가 똑같이 갖고 각자 계산하는 방식입니다. 이 두 철학이 바로 거리 벡터(distance vector)와 링크 상태(link state) 라우팅이며, 독학사 시험에서 라우팅 알고리즘 비교 문제로 자주 출제되는 핵심 주제입니다.

1. 거리 벡터 라우팅 — 이웃에게만 소문내기

거리 벡터(distance vector) 라우팅은 각 라우터가 “어떤 목적지까지 거리(비용)가 얼마인지”를 벡터(방향과 값의 목록) 형태로 만들어, 직접 연결된 이웃 라우터에게만 주기적으로 전달하는 방식입니다. 라우터는 이웃에게서 받은 정보에 자신과 이웃 사이의 비용을 더해, 그 목적지까지 자신의 새로운 거리를 갱신합니다. 이 원리를 벨만-포드(Bellman-Ford) 알고리즘이라고 부릅니다.

쉽게 말하면: 거리 벡터 방식은 옆집 사람에게 “이 목적지까지 몇 분 걸리더라”라는 소문만 듣고, 거기에 옆집까지 가는 시간을 더해 자신의 거리를 짐작하는 방식입니다. 전체 지도를 직접 보지는 못합니다.

거리 벡터 방식의 특징은 다음과 같습니다.

• 각 라우터는 네트워크 전체의 구조를 알지 못하고, 이웃이 알려준 거리 값만 신뢰합니다.
• 정보가 이웃에서 이웃으로 퍼지는 데 시간이 걸리므로, 네트워크에 변화가 생겼을 때 모든 라우터가 새 정보를 반영해 안정된 상태(수렴, convergence)에 이르기까지 상대적으로 느립니다.
• 대표 프로토콜은 RIP(Routing Information Protocol)입니다.

2. 링크 상태 라우팅 — 전체 지도를 그린 뒤 최단 경로 계산

링크 상태(link state) 라우팅은 각 라우터가 자신과 직접 연결된 링크의 상태(연결된 이웃과 그 비용)를 네트워크 전체에 flooding(범람, 모든 라우터에게 퍼뜨리는 방식)으로 알립니다. 이렇게 해서 모든 라우터가 네트워크 전체의 연결 지도(링크 상태 데이터베이스)를 똑같이 갖게 되면, 각 라우터는 이 지도를 바탕으로 다익스트라 알고리즘(Dijkstra’s algorithm)을 이용해 자신을 기준으로 한 최단 경로를 스스로 계산합니다.

쉽게 말하면: 링크 상태 방식은 모든 사람이 도시 전체 지도를 나눠 갖고, 각자 자신의 위치에서 목적지까지 가장 빠른 길을 직접 계산하는 방식입니다.

대표 프로토콜은 OSPF(Open Shortest Path First)입니다.

다익스트라 알고리즘 실제 계산

아래와 같은 작은 네트워크 그래프가 있다고 합시다. 노드는 라우터, 간선의 숫자는 링크 비용입니다.

라우터 A를 기준으로 다른 모든 라우터까지의 최단 거리를 다익스트라 알고리즘으로 계산해 보겠습니다. 알고리즘의 규칙은 “아직 방문하지 않은 노드 중 현재까지 계산된 거리가 가장 작은 노드를 방문 확정하고, 그 노드를 거쳐 갈 때 이웃의 거리가 더 짧아지면 갱신한다”입니다.

초기화: A까지의 거리는 0, 나머지는 무한대(아직 모름)로 시작합니다.

1단계 — A 방문. 거리가 가장 작은 A(0)를 확정합니다. A와 연결된 B, C의 거리를 갱신합니다. A→B는 2이므로 B=2, A→C는 5이므로 C=5입니다.

2단계 — B 방문. 미방문 노드 중 가장 작은 값은 B(2)이므로 B를 확정합니다. B를 거쳐 C, D를 갱신합니다. B→C는 1이므로 2+1=3이 기존 C값 5보다 작아 C=3(B경유)로 갱신합니다. B→D는 4이므로 2+4=6, D=6(B경유)으로 갱신합니다.

3단계 — C 방문. 미방문 중 가장 작은 값은 C(3)이므로 C를 확정합니다. C를 거쳐 D, E를 갱신합니다. C→D는 1이므로 3+1=4가 기존 D값 6보다 작아 D=4(C경유)로 갱신합니다. C→E는 7이므로 3+7=10, E=10(C경유)으로 갱신합니다.

4단계 — D 방문. 미방문 중 가장 작은 값은 D(4)이므로 D를 확정합니다. D를 거쳐 E를 갱신합니다. D→E는 3이므로 4+3=7이 기존 E값 10보다 작아 E=7(D경유)로 갱신합니다.

5단계 — E 방문. 남은 노드 E(7)를 확정하면 모든 노드의 최단 거리가 확정됩니다.

C까지 직접 가는 경로(A→C, 비용 5)보다 B를 거쳐 가는 경로(A→B→C, 비용 2+1=3)가 더 짧다는 것이 이번 계산의 핵심 포인트입니다. 다익스트라 알고리즘은 이렇게 직접 경로가 아니라 우회 경로가 더 저렴할 수 있다는 것까지 반영해 진짜 최단 경로를 찾아냅니다.

자주 틀리는 점: 다익스트라 알고리즘에서 매 단계마다 “이미 방문 확정된 노드”의 거리는 이후 단계에서 다시 줄어들지 않는다는 점을 놓치기 쉽습니다. 한 번 방문 확정되면 그 값이 최종 확정 값이며, 이후에는 갱신 대상에서 제외하고 오직 미방문 노드만 갱신 대상으로 삼습니다.

3. RIP vs OSPF 비교

RIP가 홉 수를 최대 15로 제한하는 이유는 아래에서 다룰 무한 카운트 문제를 일정 범위 안에서 끊어내기 위해서입니다. 16이라는 값에 도달하면 “그 목적지는 도달 불가능하다(infinity, 무한대)“고 간주해 문제가 끝없이 이어지는 것을 막습니다.

자주 틀리는 점: “OSPF는 홉 수를 기준으로 최적 경로를 계산한다”는 설명은 틀린 문장으로 자주 나옵니다. 홉 수를 메트릭으로 쓰는 것은 RIP이며, OSPF는 대역폭 기반의 비용을 메트릭으로 사용해 홉 수가 많아도 회선 속도가 빠르면 더 낮은 비용으로 계산될 수 있습니다.

4. 수렴과 루프 문제 — 무한 카운트(count-to-infinity)

거리 벡터 방식은 이웃에게서 들은 정보만 믿기 때문에, 네트워크 구성이 바뀌었을 때(예: 링크 장애) 잘못된 정보가 라우터 사이를 오가며 서서히 커지는 무한 카운트 문제(count-to-infinity problem)가 생길 수 있습니다.

라우터 R1 – R2 – 네트워크 X가 일렬로 연결되어 있고, R2가 네트워크 X에 직접 연결(비용 0)되어 있으며 R1은 R2를 거쳐 X에 도달(비용 1)한다고 합시다. 그런데 R2와 네트워크 X 사이의 링크가 끊어졌다고 가정합니다.

R1과 R2가 서로 상대방에게서 들은(사실은 자신에게서 나온 정보가 되돌아온) 값을 진짜 새로운 경로로 착각해 비용을 1씩 계속 올리는 것이 이 문제의 핵심입니다. 마치 두 사람이 서로 “네가 맞다고 했으니까”라며 잘못된 소문을 부풀려 가는 것과 비슷합니다. RIP는 이 값이 실제로는 무한히 커지지 않도록 16을 “도달 불가”로 정의해 두어, 값이 16에 도달하면 그 이상 세지 않고 경로를 포기하도록 만들었습니다. 이것이 앞서 3절에서 본 “RIP의 최대 홉 수는 15, 16은 무한대(도달 불가)“라는 규칙의 이유입니다.

쉽게 말하면: 무한 카운트 문제는 두 라우터가 서로에게 들은 헛소문을 진짜라고 믿고 되돌려주기를 반복하며 숫자를 계속 부풀리는 현상입니다. RIP는 “16번째 부풀리기부터는 그냥 거짓말로 취급하고 끊어버리자”는 규칙으로 이 문제를 막습니다.

이 문제를 줄이기 위해 실제 거리 벡터 프로토콜은 스플릿 호라이즌(split horizon, 어떤 경로 정보를 배운 인터페이스로는 그 정보를 다시 돌려보내지 않는 규칙)이나 경로 포이즈닝(route poisoning, 도달 불가능해진 경로를 무한대 값으로 즉시 광고하는 규칙) 같은 보완 기법을 함께 사용합니다. 반면 링크 상태 방식(OSPF)은 각 라우터가 이웃의 말이 아니라 네트워크 전체의 실제 연결 지도를 직접 갖고 있어, 이런 식으로 되돌아온 헛소문에 속을 가능성이 근본적으로 낮습니다.

자주 틀리는 점: “링크 상태 방식도 거리 벡터 방식과 동일하게 무한 카운트 문제가 발생한다”는 설명은 틀렸습니다. 무한 카운트 문제는 이웃의 말만 듣고 전체 구조를 모르는 거리 벡터 방식의 구조적 약점이며, 전체 지도를 공유하는 링크 상태 방식에서는 이 문제가 원천적으로 훨씬 적게 발생합니다.

핵심 정리

• 거리 벡터 라우팅(RIP)은 이웃에게만 자신의 거리 정보를 전달하고 벨만-포드 알고리즘으로 갱신하며, 홉 수를 메트릭으로 쓰고 최대 15홉(16은 도달 불가)까지만 허용한다.
• 링크 상태 라우팅(OSPF)은 링크 상태를 네트워크 전체에 flooding해 모든 라우터가 같은 지도를 갖고, 각자 다익스트라 알고리즘으로 최단 경로를 계산하며 대역폭 기반 비용을 메트릭으로 쓴다.
• 다익스트라 알고리즘은 매 단계마다 미방문 노드 중 최소 거리 노드를 확정하고, 그 노드를 거쳐 갈 때 이웃 거리가 더 짧아지면 갱신하는 과정을 반복한다.
• 무한 카운트 문제는 거리 벡터 방식에서 잘못된 정보가 라우터 사이를 오가며 값이 계속 커지는 현상이며, RIP는 16을 도달 불가로 정의해 이를 제한한다.
• 링크 상태 방식은 전체 지도를 직접 공유하므로 무한 카운트 문제에 상대적으로 안전하지만, 계산과 flooding에 필요한 처리 부담은 더 크다.

마무리 복습

참고 자료

• IETF RFC 1058 - RIP 
• IETF RFC 2328 - OSPF