라우팅과 인터넷 구조 (2) - 라우팅 알고리즘 - soo:bak
작성일 :
라우터는 어떻게 최적 경로를 찾는가
Part 1에서 라우팅 테이블의 구조와 기본 개념을 살펴보았습니다. 동적 라우팅에서 라우터들은 서로 정보를 교환하여 경로를 학습한다고 했는데, 구체적으로 어떤 정보를 어떻게 교환하며 그 정보로 어떻게 최적 경로를 계산할까요?
이 질문에 대한 답으로 두 가지 근본적인 접근법이 존재합니다. 바로 거리 벡터(Distance Vector)와 링크 상태(Link State)입니다.
거리 벡터: 이웃에게 배운다
거리 벡터 알고리즘의 핵심 아이디어는 다음과 같습니다.
“나는 목적지까지의 거리와 방향(다음 홉)만 알고, 전체 경로는 모른다.”
각 라우터는 자신의 라우팅 테이블을 이웃에게 주기적으로 전송하고, 이웃은 받은 정보를 기반으로 자신의 테이블을 업데이트합니다. 이 알고리즘의 수학적 기반은 벨만-포드(Bellman-Ford) 알고리즘입니다.
1
2
3
4
5
6
D(x, y) = min { c(x, v) + D(v, y) }
v∈이웃
D(x, y): x에서 y까지의 최소 비용
c(x, v): x에서 이웃 v까지의 비용
D(v, y): 이웃 v에서 y까지의 최소 비용 (v가 알려줌)
쉽게 말하면 “목적지까지의 최소 비용 = 이웃까지 가는 비용 + 이웃이 알려준 거리 중 최솟값”이 됩니다.
구체적인 예시를 통해 단계별로 살펴보겠습니다.
1
2
3
4
5
6
7
2 1
A ────── B ────── C
│ │
│ 7 │ 3
│ │
└─────── D ───────┘
1 2
각 링크 옆의 숫자는 비용(거리)을 나타냅니다. A-B는 2, B-C는 1, C-D는 3(위쪽)/2(아래쪽), A-D는 7/1입니다.
[초기 상태] - 각 라우터는 직접 연결된 이웃만 알고 있습니다.
1
2
3
4
5
6
7
8
9
라우터 A의 테이블: 라우터 B의 테이블:
목적지 거리 다음홉 목적지 거리 다음홉
B 2 B A 2 A
D 7 D C 1 C
라우터 C의 테이블: 라우터 D의 테이블:
목적지 거리 다음홉 목적지 거리 다음홉
B 1 B A 7 A
D 3 D C 2 C
이 시점에서 A는 C나 D에 어떻게 가는지 모르고, 마찬가지로 다른 라우터들도 직접 연결되지 않은 목적지는 알지 못합니다.
[1라운드] - 각 라우터가 이웃에게 자신의 테이블을 전송합니다.
A는 B와 D에게 테이블을 보내고, B는 A와 C에게, C는 B와 D에게, D는 A와 C에게 보냅니다.
이제 A가 B로부터 받은 정보를 처리하는 과정을 자세히 살펴보겠습니다.
B가 A에게 알려준 정보: “나(B)는 C까지 1이야”
A의 계산:
- C까지 B를 거쳐가면? A→B(2) + B→C(1) = 3
- A는 기존에 C로 가는 경로가 없었으므로 이 경로를 추가합니다.
1
2
3
4
5
A의 업데이트된 테이블:
목적지 거리 다음홉
B 2 B
C 3 B ← 새로 추가됨
D 7 D
마찬가지로 다른 라우터들도 이웃에게서 받은 정보로 테이블을 업데이트합니다.
1
2
3
4
5
6
1라운드 후 각 라우터의 테이블:
라우터 A: B(2), C(3, via B), D(7)
라우터 B: A(2), C(1), D(4, via C) ← C를 통해 D로 가는 경로 학습
라우터 C: A(3, via B), B(1), D(3)
라우터 D: A(7), B(3, via C), C(2) ← C를 통해 B로 가는 경로 학습
[2라운드] - 업데이트된 테이블을 다시 교환합니다.
A가 B로부터 새로운 정보를 받습니다: “나(B)는 D까지 4야” (B→C→D)
A의 계산:
- D까지 B를 거쳐가면? A→B(2) + B→D(4) = 6
- 기존 경로 A→D(7)보다 짧으므로 업데이트!
1
2
3
4
5
A의 업데이트된 테이블:
목적지 거리 다음홉
B 2 B
C 3 B
D 6 B ← 7에서 6으로 개선됨 (경로: A→B→C→D)
[최종 수렴 상태] - 더 이상 변화가 없을 때까지 반복
1
2
3
4
5
6
7
8
라우터 A의 최종 테이블:
목적지 거리 다음홉 경로
B 2 B A→B
C 3 B A→B→C
D 5 D A→D→C? 또는 최적 경로 재계산
(실제로는 A→D(1)→C(2)=3이 A→B(2)→C(1)=3과 같고,
D까지는 A→B(2)→C(1)→D(2)=5 vs A→D(7)에서 5가 선택됨)
이렇게 여러 라운드를 거치면서 각 라우터는 점진적으로 더 나은 경로를 학습하게 되고, 결국 모든 라우터가 최적 경로를 알게 됩니다. 이 상태를 수렴(Convergence)이라 부릅니다.
Count-to-Infinity 문제
거리 벡터 알고리즘에는 치명적인 약점이 존재합니다. 바로 Count-to-Infinity 문제입니다.
간단한 예시로 이 문제를 살펴보겠습니다.
1
2
A ─── B ─── C
1 1
이 상태에서 C가 네트워크에서 분리되었다고 가정합니다 (B-C 링크 단절).
B는 C로의 경로가 사라진 것을 즉시 알지만, A는 아직 이 사실을 모릅니다. A의 테이블에는 여전히 “C까지 거리 2 (A→B→C)”라고 기록되어 있습니다.
이제 문제가 발생합니다. B가 A에게 묻습니다: “C까지 얼마야?”
A가 답합니다: “2야”
B는 생각합니다: “A를 통하면 C까지 갈 수 있네! 1 + 2 = 3”
그래서 B는 새 테이블에 “C까지 거리 3 (B→A→…→C)”이라고 기록합니다. 물론 이 경로는 실제로는 존재하지 않습니다.
다음 라운드에서 역전이 일어납니다.
A가 B에게 묻습니다: “C까지 얼마야?”
B가 답합니다: “3이야”
A는 생각합니다: “음, B를 통하면 1 + 3 = 4네. 기존보다 멀어졌지만 업데이트해야지”
이 과정이 계속 반복됩니다.
1
2
3
4
5
6
7
8
라운드 A의 C거리 B의 C거리
1 2 ∞ → 3
2 4 3
3 4 5
4 6 5
5 6 7
...
∞ ∞ ∞
결국 둘 다 무한대에 도달하긴 하지만, 엄청난 시간이 소요됩니다. RIP의 경우 “무한대”를 16으로 정의하므로 16번의 반복이 필요하며, 30초마다 업데이트한다면 약 8분이 걸립니다.
그동안 C로 향하는 패킷은 A와 B 사이를 무의미하게 왔다갔다 하다가 TTL이 소진되어 폐기됩니다.
거리 벡터의 해결책들
Count-to-Infinity 문제를 완화하기 위해 여러 기법이 개발되었습니다.
Split Horizon (분할 지평선)
핵심 원칙은 “B에게서 배운 경로는 B에게 다시 알려주지 않는다”입니다. 위 예시에서 A는 C로 가는 경로를 B에게서 배웠으므로, A는 B에게 “나도 C까지 갈 수 있어”라고 말하지 않습니다. 그 결과 B는 A를 통한 우회 경로를 애초에 고려하지 않게 됩니다.
Poison Reverse (독 역류)
Split Horizon의 강화 버전입니다. B에게서 배운 경로를 단순히 숨기는 대신, B에게 “무한대”로 적극 알려줍니다. 즉 A가 B에게 “나는 C까지 무한대야 (너를 통하지 않고는 못 가)”라고 명시적으로 전달하는 방식입니다.
Hold-down Timer
경로가 사라지면 일정 시간 동안 해당 목적지에 대한 새로운 경로 정보를 무시합니다. “갑자기 나타난 우회 경로는 의심스러우니 잠시 기다려 보자”라는 전략입니다.
Triggered Updates
주기적 업데이트 시간을 기다리지 않고 변경이 발생하면 즉시 이웃에게 알립니다. 이를 통해 수렴 시간을 단축할 수 있습니다.
이러한 해결책들은 문제를 상당히 완화하지만 완전히 해결하지는 못합니다. 복잡한 토폴로지에서는 여전히 느린 수렴이 발생할 수 있어, 이후 링크 상태 알고리즘이 개발되는 계기가 되었습니다.
RIP: 거리 벡터의 대표
RIP(Routing Information Protocol)는 가장 오래된 동적 라우팅 프로토콜 중 하나로, 1988년 RFC 1058로 표준화되었습니다.
RIP의 주요 특성은 다음과 같습니다.
- 메트릭: 홉 수 (hop count)만 사용
- 최대 홉: 15 (16은 “도달 불가”를 의미)
- 업데이트 주기: 30초마다 전체 테이블 전송
- 전송 방식: UDP 포트 520 사용
그러나 RIP에는 몇 가지 근본적인 한계가 있습니다.
- 15홉 제한으로 인해 대규모 네트워크에는 부적합
- 홉 수만 고려하므로 대역폭이나 지연 같은 품질 요소는 무시됨
- 느린 수렴 속도 (분 단위 소요)
RIPv2에서 몇 가지 개선이 이루어졌습니다.
- CIDR 지원으로 서브넷 마스크 정보 포함
- 인증 기능 추가
- 브로드캐스트 대신 멀티캐스트(224.0.0.9) 사용
그럼에도 불구하고 거리 벡터의 근본적인 한계는 해결되지 않았습니다. 따라서 현대 네트워크에서 RIP는 거의 사용되지 않으며, 학습 목적이나 매우 단순한 환경에서만 볼 수 있습니다.
링크 상태: 전체 지도를 공유하다
거리 벡터의 한계를 극복하기 위해 등장한 것이 링크 상태 알고리즘입니다. 핵심 아이디어는 다음과 같습니다.
“모든 라우터가 전체 네트워크의 토폴로지를 알고, 각자 최적 경로를 계산한다.”
거리 벡터와 링크 상태의 근본적인 차이점을 비교하면:
- 거리 벡터: 이웃이 알려준 “거리” 정보만 알 뿐, 전체 구조는 모름
- 링크 상태: 전체 네트워크의 “지도”를 알고 있음
링크 상태 라우팅은 다음 단계로 진행됩니다.
- 이웃 발견: 인접한 라우터들과 Hello 메시지를 교환하여 서로를 인식
- 링크 비용 측정: 각 링크의 비용(대역폭, 지연 등)을 측정
- LSA 생성: 자신의 링크 정보를 담은 Link State Advertisement를 생성
- LSA 플러딩: 생성한 LSA를 네트워크의 모든 라우터에게 전파
- 데이터베이스 구축: 수신한 LSA들을 모아 전체 토폴로지 데이터베이스를 구축
- SPF 계산: Dijkstra 알고리즘으로 자신을 루트로 하는 최단 경로 트리를 계산
- 라우팅 테이블 생성: SPF 결과를 바탕으로 실제 라우팅 테이블을 구축
핵심은 모든 라우터가 동일한 토폴로지 데이터베이스를 보유한다는 점입니다. 같은 데이터를 가지고 같은 알고리즘을 실행하면 모든 라우터가 일관된 결과를 얻게 됩니다. 덕분에 거리 벡터에서 발생하던 루프 문제가 원천적으로 해결됩니다.
Dijkstra 알고리즘
링크 상태 프로토콜은 다익스트라(Dijkstra) 알고리즘을 사용하여 최단 경로를 계산합니다. 이 알고리즘은 1959년 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger Dijkstra)가 고안했습니다.
알고리즘의 핵심 동작은 세 단계로 요약됩니다.
- 시작점에서 가장 가까운 미확정 노드를 찾아 “확정”한다
- 새로 확정된 노드를 경유하는 경로가 기존보다 짧으면 거리를 업데이트한다
- 모든 노드가 확정될 때까지 1-2를 반복한다
구체적인 예시로 동작 과정을 살펴보겠습니다.
1
2
3
4
5
6
7
10
A ────── B
│╲ │
5│ ╲3 │2
│ ╲ │
D ──── C─┘
2
A에서 출발하여 모든 노드까지의 최단 경로를 찾아보겠습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
[초기 상태]
확정된 노드: {A} (시작점)
A까지 거리: 0
B까지 거리: 10 (직접 연결)
C까지 거리: 3 (직접 연결)
D까지 거리: 5 (직접 연결)
[1단계] 미확정 노드 중 가장 가까운 C(거리 3)를 확정
확정된 노드: {A, C}
C를 경유하는 경로 검토:
- A→C→B: 3 + 2 = 5 < 기존 10 → B 거리를 5로 업데이트!
- A→C→D: 3 + 2 = 5 = 기존 5 → 변화 없음
현재 거리: A=0, B=5, C=3, D=5
[2단계] 미확정 노드 중 가장 가까운 것 선택 (B와 D가 둘 다 5)
B를 먼저 확정 (동점일 경우 임의 선택)
확정된 노드: {A, C, B}
B를 경유하는 경로 검토:
- A→B→... : 이미 확정된 노드로만 연결되어 새로운 개선 없음
[3단계] 남은 D를 확정
확정된 노드: {A, C, B, D}
모든 노드가 확정되어 알고리즘 종료!
최종 결과:
- A→B: 거리 5, 경로 A→C→B
- A→C: 거리 3, 경로 A→C (직접)
- A→D: 거리 5, 경로 A→D (직접)
시간 복잡도는 기본 구현 시 O(n²)이며, 우선순위 큐(힙)를 사용하면 O((n+e)log n)으로 개선됩니다. 여기서 n은 노드 수, e는 엣지 수입니다.
OSPF: 링크 상태의 대표
OSPF(Open Shortest Path First)는 현재 가장 널리 사용되는 IGP로, 1989년에 개발되어 RFC 2328로 표준화되었습니다.
OSPF의 주요 특성은 다음과 같습니다.
- 메트릭: 대역폭 기반의 비용(cost) 사용
- 계층 구조: 영역(Area) 개념으로 대규모 네트워크 지원
- 수렴 속도: 초 단위의 빠른 수렴
- 전송 방식: IP 프로토콜 번호 89 사용 (TCP나 UDP 위에서 동작하지 않음)
OSPF 영역 구조
대규모 네트워크를 효율적으로 관리하기 위해 OSPF는 네트워크를 여러 영역(Area)으로 분할합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Area 1
┌───────┐
│ R1 R2 │
└───┬───┘
│
┌────────┴────────┐
│ Area 0 │ (백본)
│ ABR1 ABR2 │
└────┬───────┬────┘
│ │
┌────┴───┐ ┌─┴────┐
│ Area 2 │ │Area 3│
│ R3 R4 │ │R5 R6 │
└────────┘ └──────┘
- Area 0 (백본 영역): 모든 다른 영역은 반드시 Area 0과 연결되어야 함
- ABR(Area Border Router): 여러 영역의 경계에 위치하여 영역 간 라우팅을 담당
영역 분할의 이점은 다음과 같습니다.
- LSA 플러딩 범위가 영역 내부로 제한되어 트래픽 감소
- SPF 계산 범위가 축소되어 CPU 부하 감소
- 라우팅 테이블 크기가 줄어들어 메모리 효율 향상
OSPF 라우터 유형
OSPF 네트워크에서 라우터는 위치와 역할에 따라 분류됩니다.
- 내부 라우터: 하나의 영역에만 속하는 라우터
- ABR: 여러 영역에 걸쳐 있으며 영역 간 경로 정보를 교환
- ASBR(AS Boundary Router): 다른 AS(자율 시스템)와 연결되어 외부 경로를 주입
- DR(Designated Router): 멀티액세스 네트워크에서 대표 역할 수행
DR/BDR 선출
이더넷처럼 여러 라우터가 같은 네트워크 세그먼트에 연결된 경우를 생각해 보겠습니다. 모든 라우터 쌍이 인접 관계를 맺으면 n(n-1)/2 개의 관계가 필요합니다. 10대의 라우터가 있다면 45개의 인접 관계가 형성되어 관리 부담이 급격히 증가합니다.
이 문제를 해결하기 위해 OSPF는 DR(Designated Router)을 선출합니다. 모든 라우터는 DR과만 LSA를 교환하므로 인접 관계가 크게 단순화됩니다. BDR(Backup DR)은 DR이 장애를 일으킬 경우에 대비한 백업 역할을 합니다.
1
2
3
4
5
6
7
8
DR 없이: DR 있을 때:
R1 ── R2 R1
│╲ ╱│ │
│ ╲╱ │ DR ─┼── R2
│ ╱╲ │ │
R3 ── R4 R3 ── R4
(모두 DR과만 통신)
EIGRP: 하이브리드 접근
EIGRP(Enhanced Interior Gateway Routing Protocol)는 원래 Cisco의 독점 프로토콜이었으나 2013년에 개방되었습니다. 거리 벡터와 링크 상태의 장점을 결합한 하이브리드 방식으로 분류됩니다.
EIGRP의 주요 특성은 다음과 같습니다.
- 복합 메트릭: 대역폭, 지연, 신뢰성, 부하 등 여러 요소를 종합적으로 고려
- DUAL 알고리즘: 빠른 수렴과 루프 방지를 동시에 달성
- 부분 업데이트: 변경된 정보만 전송하여 대역폭 절약
- 비동기 업데이트: 주기적 업데이트 없이 변화 시에만 전송
DUAL 알고리즘
Diffusing Update Algorithm(DUAL)의 핵심은 Feasibility Condition입니다. 이 조건은 루프 방지를 보장합니다.
1
이웃의 Reported Distance < 나의 현재 Feasible Distance
이 조건을 만족하는 이웃만 대체 경로(Feasible Successor)로 미리 인정해 둡니다. 현재 최적 경로(Successor)에 장애가 발생하면 즉시 Feasible Successor로 전환합니다. 재계산 없이 바로 대체 경로를 사용하므로 전환 속도가 매우 빠릅니다.
만약 미리 확보해 둔 Feasible Successor가 없다면, 라우터는 “Active” 상태로 전환하여 이웃들에게 질의를 보냅니다. 모든 응답을 수신하여 새 경로를 결정하면 다시 “Passive” 상태로 돌아갑니다.
알고리즘 비교
지금까지 살펴본 세 가지 접근법을 표로 비교해 보겠습니다.
1
2
3
4
5
6
7
8
9
10
특성 거리 벡터 (RIP) 링크 상태 (OSPF) 하이브리드 (EIGRP)
─────────────────────────────────────────────────────────────────────────
정보 공유 전체 테이블 LSA (링크 정보) 변경분만
공유 대상 이웃에게만 모든 라우터에게 이웃에게만
계산 위치 정보 수신 시 각 라우터에서 개별 정보 수신 시
메모리 사용 낮음 높음 (토폴로지 DB) 중간
CPU 사용 낮음 높음 (SPF 계산) 중간
수렴 속도 느림 (분 단위) 빠름 (초 단위) 매우 빠름 (밀리초)
루프 방지 불완전 완전 완전 (DUAL)
확장성 제한적 (15홉) 높음 (영역 구조) 높음
그렇다면 실제 환경에서는 어떤 것을 선택해야 할까요?
RIP: 현대 네트워크에서는 거의 사용되지 않습니다. 레거시 시스템 유지보수나 매우 작은 테스트 환경에서 간혹 볼 수 있는 정도입니다.
OSPF: 대부분의 기업 네트워크에서 사실상 표준으로 자리 잡았습니다. 개방형 표준이라 특정 벤더에 종속되지 않고, 오랜 기간 검증된 안정성을 갖추고 있습니다.
EIGRP: Cisco 장비로 구성된 환경에서 좋은 선택이 될 수 있습니다. 빠른 수렴 속도와 낮은 오버헤드가 장점이며, 2013년 이후 개방되어 다른 벤더에서도 지원하기 시작했습니다.
IS-IS: 대규모 ISP(인터넷 서비스 제공자)에서 주로 사용됩니다. OSPF와 유사한 링크 상태 프로토콜이지만 IP에 종속되지 않아 다양한 네트워크 계층 프로토콜을 지원합니다.
수렴 속도가 중요한 이유
네트워크 장애가 발생하면 라우팅이 수렴할 때까지 패킷 손실이 불가피합니다. 아래 상황을 살펴보겠습니다.
1
2
3
4
5
6
7
8
9
수렴 전:
A ─X─ B ─── C ─── D
╲ │
╲───────┘
X: 링크 단절
A의 테이블: D로 가려면 B로 (아직 업데이트 안 됨)
→ 패킷 손실 발생
각 프로토콜별 대략적인 수렴 시간:
- RIP: 수 분 소요
- OSPF: 수 초 ~ 수십 초 소요
- EIGRP (Feasible Successor가 있는 경우): 밀리초 단위
음성이나 비디오 같은 실시간 트래픽에서 수 분의 수렴 시간은 치명적인 서비스 중단을 의미합니다. 이것이 현대 네트워크에서 OSPF나 EIGRP처럼 빠른 수렴을 지원하는 프로토콜을 사용하는 이유입니다.
이어지는 Part 3에서는 자율 시스템 간 라우팅을 담당하는 BGP와 인터넷의 전체 구조를 살펴보겠습니다.
관련 글