라우팅과 인터넷 구조 (2) - 라우팅 알고리즘 - soo:bak
작성일 :
라우터는 어떻게 최적 경로를 찾는가
Part 1에서 라우팅 테이블의 구조와 기본 개념을 살펴보았습니다. 동적 라우팅에서 라우터들은 서로 정보를 교환하여 경로를 학습합니다. 어떤 정보를 교환하고, 그 정보로 어떻게 최적 경로를 계산할까요?
두 가지 접근법이 있습니다. 거리 벡터(Distance Vector)와 링크 상태(Link State)입니다.
거리 벡터: 이웃에게 배운다
거리 벡터(Distance Vector) 알고리즘에서 각 라우터는 목적지까지의 거리와 방향(다음 홉)만 알고, 전체 경로는 모릅니다.
각 라우터는 자신의 라우팅 테이블을 이웃에게 주기적으로 전송합니다. 이웃은 받은 정보를 기반으로 자신의 테이블을 업데이트합니다.
수학적으로는 벨만-포드(Bellman-Ford) 알고리즘에 기반합니다.
라우팅에서 비용(cost)은 링크를 지나는 데 드는 대가입니다. 홉 수, 대역폭, 지연 등으로 측정합니다. 목적지까지의 최소 비용 = 이웃까지의 비용 + 이웃이 알려준 비용 중 최솟값입니다.
예시로 살펴보겠습니다.
1
2
3
4
5
6
2 1
A ─────── B ─────── C
│ │
│7 │2
│ │
└──────── D ────────┘
링크 옆의 숫자는 비용입니다. A-B는 2, B-C는 1, A-D는 7, C-D는 2입니다.
[초기 상태] - 각 라우터는 직접 연결된 이웃만 알고 있습니다.
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 2 D C 2 C
이 시점에서 A는 C에 어떻게 가는지 모릅니다. 다른 라우터들도 직접 연결되지 않은 목적지는 모릅니다.
이제 라우터들이 테이블을 교환합니다. 모든 라우터가 한 번씩 테이블을 보내고 업데이트하는 주기를 라운드라고 합니다.
[1라운드] 각 라우터가 이웃에게 자신의 테이블을 전송합니다.
A는 B와 D에게 테이블을 보내고, B는 A와 C에게, C는 B와 D에게, D는 A와 C에게 보냅니다.
A가 B로부터 받은 정보를 처리하는 과정을 보겠습니다.
B가 A에게 알려줍니다: “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(3, via C)
라우터 C: A(3, via B), B(1), D(2)
라우터 D: A(7), B(3, via C), C(2)
B는 C를 통해 D로 가는 경로를, D는 C를 통해 B로 가는 경로를 학습했습니다.
[2라운드] 1라운드에서 B는 C를 통해 D로 가는 경로(비용 3)를 학습했습니다. 이 새로운 정보를 이웃에게 알려줘야 합니다.
B가 A에게 알려줍니다: “D까지 비용 3”
A는 계산합니다: D까지 B를 거쳐가면? A→B(비용 2) + B→D(비용 3) = 5
A는 이미 D로 가는 경로가 있습니다(직접 연결, 비용 7). 새로 계산한 5가 더 작으므로 테이블을 업데이트합니다.
1
2
3
4
5
A의 업데이트된 테이블:
목적지 비용 다음홉
B 2 B
C 3 B
D 5 B ← 7에서 5로 개선
[수렴] 이 과정을 반복하면 어느 시점에서 테이블이 더 이상 변하지 않습니다. 모든 라우터가 최적 경로를 알게 된 상태입니다. 이를 수렴(Convergence)이라 합니다.
1
2
3
4
5
라우터 A의 최종 테이블:
목적지 비용 다음홉 경로
B 2 B A→B
C 3 B A→B→C
D 5 B A→B→C→D
RIP: 거리 벡터의 대표
거리 벡터 알고리즘을 사용하는 대표적인 프로토콜이 RIP(Routing Information Protocol)입니다. 1988년 RFC 1058로 표준화되었습니다.
RIP의 특성:
- 메트릭: 홉 수(hop count)만 사용
- 최대 홉: 15 (16은 “도달 불가”를 의미)
- 업데이트 주기: 30초마다 전체 테이블 전송
- 전송 방식: UDP 포트 520 사용
하지만 RIP에는 한계가 있습니다.
- 15홉 제한으로 대규모 네트워크에는 부적합
- 홉 수만 고려하므로 대역폭이나 지연 같은 품질 요소는 무시
- 느린 수렴 속도 (분 단위 소요)
RIPv2에서 개선이 이루어졌습니다.
- CIDR 지원으로 서브넷 마스크 정보 포함
- 인증 기능 추가
- 브로드캐스트 대신 멀티캐스트(224.0.0.9) 사용
하지만 거리 벡터의 근본적인 한계는 해결되지 않았습니다. 그 한계가 무엇인지 살펴보겠습니다.
Count-to-Infinity 문제
거리 벡터 알고리즘에는 약점이 있습니다. Count-to-Infinity 문제입니다.
1
2
A ─── B ─── C
1 1
B-C 링크가 단절되었다고 가정합니다.
B는 C로의 경로가 사라진 것을 즉시 압니다. 하지만 A는 모릅니다. A의 테이블에는 여전히 “C까지 비용 2”라고 기록되어 있습니다.
다음 라운드에서 A가 B에게 테이블을 보냅니다: “C까지 비용 2”
B는 계산합니다: A를 거쳐 C로 가면? B→A(비용 1) + A→C(비용 2) = 3
B는 테이블에 “C까지 비용 3”이라고 기록합니다. 하지만 이 경로는 실제로 존재하지 않습니다. A가 알고 있는 C로의 경로도 B를 거치기 때문입니다.
다음 라운드에서 역전이 일어납니다.
B가 A에게 테이블을 보냅니다: “C까지 비용 3”
A는 계산합니다: 기존 경로(비용 2)가 사라졌으니 B를 거쳐야 합니다. A→B(비용 1) + B→C(비용 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에게서 배웠으므로, B에게 테이블을 보낼 때 C 정보를 제외합니다. B는 A를 통한 우회 경로를 고려하지 않게 됩니다.
Poison Reverse (독 역류)
Split Horizon의 강화 버전입니다. B에게서 배운 경로를 숨기는 대신, B에게 “C까지 비용 무한대”라고 알려줍니다. B는 A를 통해 C로 갈 수 없다는 것을 명확히 알게 됩니다.
Hold-down Timer
경로가 사라지면 일정 시간 동안 해당 목적지에 대한 새로운 경로 정보를 무시합니다. 장애 직후 들어오는 잘못된 우회 경로 정보를 걸러냅니다.
Triggered Updates
주기적 업데이트 시간을 기다리지 않고, 변경이 발생하면 즉시 이웃에게 알립니다. 수렴 시간을 단축합니다.
이 해결책들은 거리 벡터 방식을 유지하면서 문제를 완화합니다. 하지만 완전히 해결하지는 못합니다. 복잡한 토폴로지(네트워크 구조)에서는 여전히 느린 수렴이 발생할 수 있습니다.
이러한 한계 때문에 완전히 다른 접근 방식인 링크 상태 알고리즘이 개발되었습니다.
링크 상태: 전체 지도를 공유하다
링크 상태(Link State) 알고리즘에서 모든 라우터는 전체 네트워크의 토폴로지를 알고, 각자 최적 경로를 계산합니다.
거리 벡터와 링크 상태의 차이점:
- 거리 벡터: 이웃이 알려준 비용 정보만 알고, 전체 구조는 모름
- 링크 상태: 전체 네트워크의 지도를 알고 있음
링크 상태 라우팅의 동작 단계:
- 이웃 발견: 인접한 라우터들과 Hello 메시지를 교환하여 서로를 인식
- 링크 비용 측정: 각 링크의 비용(대역폭, 지연 등)을 측정
- LSA 생성 및 전파: 자신의 링크 정보를 담은 LSA(Link State Advertisement)를 생성하고 네트워크의 모든 라우터에게 전파
- 토폴로지 데이터베이스 구축: 수신한 LSA들을 모아 전체 네트워크 구조를 파악
- 최단 경로 계산: Dijkstra 알고리즘으로 자신을 루트로 하는 최단 경로 트리를 계산
- 라우팅 테이블 생성: 계산 결과를 바탕으로 라우팅 테이블 구축
모든 라우터가 동일한 토폴로지 데이터베이스를 보유합니다. 거리 벡터에서는 A가 “B를 통해 C로 갈 수 있다”고 믿고, B가 “A를 통해 C로 갈 수 있다”고 믿는 상황이 발생했습니다. 링크 상태에서는 모든 라우터가 같은 지도를 보고 있으므로 이런 모순이 생기지 않습니다.
Dijkstra 알고리즘
링크 상태 프로토콜은 다익스트라(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
[초기 상태]
확정: {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를 경유하는 경로 검토:
- 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)입니다.
OSPF의 특성:
- 메트릭: 대역폭 기반의 비용 사용
- 계층 구조: 영역(Area) 개념으로 대규모 네트워크 지원
- 수렴 속도: 초 단위
- 전송 방식: IP 위에서 직접 동작 (프로토콜 번호 89). RIP는 UDP를 사용하지만, OSPF는 TCP나 UDP 없이 IP 바로 위에서 동작하며 신뢰성을 자체적으로 처리함
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 전파 범위가 영역 내부로 제한되어 트래픽 감소
- 최단 경로 계산 범위가 축소되어 CPU 부하 감소
- 라우팅 테이블 크기가 줄어들어 메모리 효율 향상
OSPF 라우터 유형
OSPF 네트워크에서 라우터는 역할에 따라 분류됩니다.
- 내부 라우터: 하나의 영역에만 속함
- ABR: 여러 영역에 걸쳐 있으며 영역 간 경로 정보 교환
- ASBR(AS Boundary Router): 다른 자율 시스템(AS)과 연결되어 외부 경로 주입
- DR(Designated Router): 멀티액세스 네트워크에서 대표 역할 수행
DR/BDR 선출
여러 라우터가 같은 네트워크에 연결된 경우, 모든 라우터 쌍이 인접 관계를 맺으면 관계 수가 많아집니다. 10대의 라우터가 있다면 45개의 인접 관계가 필요합니다.
OSPF는 DR(Designated Router)을 선출하여 이 문제를 해결합니다. 모든 라우터는 DR과만 LSA를 교환합니다. 인접 관계가 10개에서 9개로 줄어듭니다. 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 알고리즘
DUAL(Diffusing Update Algorithm)은 대체 경로를 미리 계산해 둡니다. 현재 경로에 장애가 발생하면 재계산 없이 즉시 대체 경로로 전환합니다.
대체 경로로 인정받으려면 조건이 있습니다. 이웃이 알려준 목적지까지의 비용이 나의 현재 비용보다 작아야 합니다. 이 조건이 루프를 방지합니다.
이 조건을 만족하는 이웃을 대체 경로(Feasible Successor)로 미리 지정해 둡니다. 현재 경로(Successor)에 장애가 발생하면 재계산 없이 대체 경로로 전환합니다.
대체 경로가 없는 경우에는 새 경로를 찾아야 합니다. 라우터는 Active 상태로 전환하여 이웃들에게 질의를 보냅니다. 모든 응답을 받아 새 경로를 결정하면 Passive 상태로 돌아갑니다. 평상시에는 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(Intermediate System to Intermediate System): OSPF와 함께 대표적인 링크 상태 프로토콜입니다. 대규모 ISP(인터넷 서비스 제공자)에서 주로 사용됩니다. IP에 종속되지 않아 다양한 네트워크 계층 프로토콜을 지원합니다.
수렴 속도가 중요한 이유
네트워크 장애가 발생하면 라우팅이 수렴할 때까지 패킷 손실이 불가피합니다.
1
2
3
4
5
6
7
8
9
수렴 전:
A ─X─ B ─── C ─── D
╲ │
╲───────┘
X: 링크 단절
A의 테이블: D로 가려면 B로 (아직 업데이트 안 됨)
→ 패킷 손실 발생
각 프로토콜별 수렴 시간:
- RIP: 분 단위
- OSPF: 초 단위
- EIGRP (대체 경로가 있는 경우): 밀리초 단위
음성이나 비디오 같은 실시간 트래픽에서 분 단위 수렴은 서비스 중단을 의미합니다. 현대 네트워크에서 OSPF나 EIGRP를 사용하는 이유입니다.
마무리
이 글에서 살펴본 내용을 정리하면:
- 거리 벡터: 이웃에게서 배운 거리 정보만으로 경로 결정. 단순하지만 수렴이 느리고 Count-to-Infinity 문제 발생
- 링크 상태: 전체 네트워크 토폴로지를 공유하고 Dijkstra 알고리즘으로 최단 경로 계산. 빠른 수렴과 루프 방지
- RIP: 거리 벡터의 대표. 15홉 제한, 느린 수렴으로 현대 네트워크에서 거의 사용 안 함
- OSPF: 링크 상태의 대표. 영역 구조로 확장성 확보, 현재 가장 널리 사용되는 IGP
- EIGRP: 하이브리드 방식. DUAL 알고리즘으로 빠른 수렴과 루프 방지 달성
Part 3에서는 자율 시스템 간 라우팅을 담당하는 BGP(Border Gateway Protocol)와 인터넷의 전체 구조를 다룹니다.
관련 글