인터넷의 네비게이션, 패킷 라우팅(Routing)
지난 포스팅에서 인터넷의 근간인 IP 주소 체계(Addressing)를 다뤘다면, 이번에는 그 주소를 찾아가는 '방법론(Routing)'에 대해 깊게 파고들었다.
흥미로운 점은, 수십억 개의 노드가 연결된 이 거대한 인터넷망에서 패킷이 목적지까지 길을 잃지 않고 찾아가는 과정이 수학적 '그래프 이론(Graph Theory)'과 '최적화 알고리즘'의 집약체라는 것이다. 오늘은 네트워크 계층의 핵심인 라우팅 알고리즘의 진화 과정과, 이를 실제로 구현한 RIP, OSPF, BGP 프로토콜에 대해 엔지니어링 관점에서 정리해 보고자 한다.
인터넷을 바라보는 관점: 그래프와 비용(Graph & Cost)
라우터(Router)의 입장에서 인터넷은 추상화된 가중치 그래프(Weighted Graph)로 보인다.
Node (노드): 라우터 그 자체
Edge (엣지): 라우터를 연결하는 링크 (LAN, WAN 등)
Cost (비용): 해당 링크를 지나가는 데 드는 대가 (지연 시간, 대역폭, 금전적 비용 등)
 |
| Internet as Graph |
결국 라우팅(Routing)이란, 소스(Source) 라우터에서 목적지(Destination) 라우터까지의 '최소 비용(Least Cost)' 경로를 찾아내어 포워딩 테이블(Forwarding Table)을 만드는 최적화 문제로 귀결된다.
아래의 최소 비용 트리(Least-Cost Tree)들은 소스 라우터를 root 노드로 하여 graph를 spanning한 것이다.
 |
| Least-Cost Trees |
최적의 경로를 찾는 세 가지 철학
라우팅 알고리즘은 정보를 얻는 방식과 목적에 따라 크게 Distance Vector, Link State, 그리고 Path Vector 방식으로 나뉜다. 이는 마치 길을 찾을 때 "이정표만 보는 것", "전체 지도를 보는 것"(최소 비용 우선), 그리고 "어떤 길을 피할지 규칙을 정하는 것"(정책 우선)의 차이와 같다.
① Distance Vector (DV) Routing: 이정표를 믿어라
 |
| Distance Vector |
기반 이론: Bellman-Ford Equation
Distance Vector 방식은 라우터가 "오직 인접한 이웃"이 주는 정보에 의존한다.
원리: 각 라우터는 주기적으로 자신의 라우팅 테이블(Vector)을 이웃에게 보낸다. 이웃이 "나를 거치면 목적지까지 비용 5에 갈 수 있어"라고 알려주면, 내 비용을 더해 테이블을 갱신한다.
$$D_{xy} = \min \{ (c_{xz} + D_{zy}) \}$$ (x에서 y로 가는 최소 비용은, 이웃 z까지의 비용 + z에서 y로 가는 비용의 최솟값)
Updating distance vectors 문제점 (Count to Infinity): 이 방식의 치명적인 단점은 '나쁜 소식이 늦게 퍼진다'는 것이다. 링크가 끊어졌을 때(비용
$\infty$ ), 라우터들끼리 서로 갱신된 정보를 무한히 주고받으며 루프(Loop)에 빠질 수 있다.
→ 모든 라우터가 broken link의 cost를 무한대로 설정할 때까지 기다려야 함해결책:
Split Horizon: A에게서 배운 경로는 A에게 다시 알려주지 않는다.
Poison Reverse: A에게서 배운 경로를 A에게 알려줄 때는 비용을 무한대(
$\infty$ )로 설정해 보낸다.
② Link State (LS) Routing: 지도를 그려라
 |
| Link State Database |
기반 이론: Dijkstra Algorithm
Link State 방식은 모든 라우터가 네트워크 전체의 지도(Topology)를 공유한다.
원리:
각 라우터는 자신의 이웃과 링크 비용 정보를 담은 LSP(Link State Packet)를 생성한다.
Flooding: 이 LSP를 네트워크의 모든 라우터에게 뿌린다.
Flooding 모든 라우터가 동일한 LSDB(Link State Database)를 갖게 되면, 각자 자신을 루트(Root)로 하는 다익스트라(Dijkstra) 알고리즘을 돌려 최단 경로 트리를 만든다.
Dijkstra's algorithm
장점: 전체 구조를 알기 때문에 루프가 발생할 확률이 적고, 수렴(Convergence) 속도가 빠르다.
③ Path Vector Routing: 정책(Policy)을 더하다
 |
| Spanning Trees |
목적: Policy-Based Routing (Not just Least Cost)
Distance Vector와 Link State가 "어떻게 하면 가장 빨리 갈까?"(효율성)에 집중했다면, Path Vector는 "어떤 길로 가는 것이 우리의 이익에 부합하는가?"(정책)를 고민한다. ISP(인터넷 서비스 제공자) 간의 통신에서는 단순히 짧은 경로보다 상업적, 정치적 이유로 특정 경로를 선호하거나 배제해야 할 때가 많기 때문이다.
원리: Distance Vector와 비슷하지만, 단순히 '거리(Distance)'만 보내는 것이 아니라 목적지까지 거쳐가는 '경로 전체(Path)'를 보낸다.
예: "목적지 X로 가려면 [AS1, AS5, AS3]를 거쳐야 해."
장점:
Loop Prevention: 경로 정보에 '내 이름(AS 번호)'이 이미 포함되어 있다면, 루프가 형성된 것이므로 해당 경로를 즉시 폐기한다. (Count to Infinity 문제의 근본적 해결)
Policy Enforcement: 경로 리스트를 보고 "경쟁사 망인 AS5는 거치지 않겠다"와 같은 정책을 적용할 수 있다.
실제 인터넷을 움직이는 프로토콜 (Implementation)
이론은 현실에서 프로토콜로 구현된다. 우리는 AS(Autonomous System, 자율 시스템) 내부에서 쓰이는 IGP와 외부에서 쓰이는 EGP를 구분해야 한다.
① RIP (Routing Information Protocol) - 구관이 명관?
 |
| RIP |
분류: IGP / Distance Vector 기반
특징:
Metric: 오직 Hop Count(거쳐가는 라우터 수)만 따진다. (속도는 무시하고 거리만 봄)
제약: 최대 홉이 15로 제한된다. (16은 무한대/도달 불가로 간주). 따라서 소규모 네트워크에 적합하다.
구현: UDP 포트 520번을 사용하며, 30초마다 주기적으로 라우팅 정보를 브로드캐스트한다.
엔지니어링 관점: 단순해서 구현이 쉽고 오버헤드가 적지만, 링크 속도나 혼잡도를 반영하지 못해 최신 대규모 망에는 부적합하다.
 |
| RIP example |
② OSPF (Open Shortest Path First) - 엔터프라이즈의 표준
 |
| OSPF |
분류: IGP / Link State 기반
특징:
Metric: 대역폭(Throughput), 지연시간 등을 종합적으로 고려한 Cost를 사용한다.
계층적 구조 (Hierarchy): 네트워크가 커지면 Flooding 트래픽이 감당이 안 된다. OSPF는 이를 해결하기 위해 Area 개념을 도입했다.
Backbone Area (Area 0): 모든 Area 연결의 중심.
일반 Area는 내부 디테일을 숨기고 요약된 정보만 백본으로 보낸다. 이를 통해 확장성(Scalability)을 확보했다.
 |
| Areas |
③ BGP (Border Gateway Protocol) - 인터넷의 접착제
분류: EGP / Path Vector 기반
필요성: 서로 다른 ISP(예: SKT와 KT, 또는 국가 간) 사이의 라우팅은 단순히 '최단 거리'가 정답이 아니다. 여기엔 '정책(Policy)'이 개입한다. (예: "내 트래픽은 경쟁사 망을 통과시키지 마라")
특징:
Distance Vector와 비슷하지만, 단순히 비용만 따지는 게 아니라 전체 경로(Path)의 속성(AS 리스트)을 함께 전달한다.
Loop Prevention: 경로(Path)에 자신의 AS 번호가 있으면 루프로 간주하고 버린다.
TCP 연결: 신뢰성이 매우 중요하므로 UDP가 아닌 TCP 연결 위에서 동작한다.
| Feature | Distance Vector (DV) | Link State (LS) | Path Vector (PV) |
| 핵심 알고리즘 | Bellman-Ford | Dijkstra | Policy-based Bellman-Ford |
| 정보 범위 | Local (이웃의 지식) | Global (전체 토폴로지) | Path Information (경로 + 정책) |
| 주요 프로토콜 | RIP, EIGRP | OSPF, IS-IS | BGP |
| 장점 | 구현이 간단함 | 수렴 속도 빠름, 루프 없음 | 정책 적용 가능, 루프 방지 용이 |
| 단점 | Count to Infinity, 느린 수렴 | 많은 계산 리소스, 복잡성 | 설정이 복잡함 |
마무리
이번에 네트워크 스택을 깊게 파보면서 느낀 점은, 우리가 단순히 "인터넷이 연결되었다"라고 말하는 상태 뒤에는 수많은 라우터들이 끊임없이 대화하고, 지도를 그리고, 최적의 경로를 계산하는 치열한 제어 평면(Control Plane)의 활동이 있다는 것이다.
RIP는 작고 단순한 조직에,
OSPF는 성능과 확장이 필요한 기업 내부에,
BGP는 정책과 비즈니스 관계가 얽힌 전 세계 인터넷 연결에 사용된다.
엔지니어로서 네트워크를 설계한다면, 단순히 "통신이 되느냐"를 넘어 트래픽의 규모, 망의 안정성, 그리고 관리 정책에 따라 적절한 라우팅 프로토콜을 선택하는 안목이 필수적일 것이다. 다음 포스팅에서는 이러한 라우팅 위에서 호스트를 찾았을 때 데이터가 어떻게 요청한 프로세스로 전달되는지 Transport Layer에 관해 다뤄보겠다.
추천글
[컴퓨터 네트워크] 데이터 통신의 기본 요소와 TCP/IP 5계층
[컴퓨터 네트워크] Data-link layer | Frameing, Error Control methods, MAC Protocols
[컴퓨터 네트워크] Physical Layer | 데이터 전송 속도의 한계, 아날로그의 디지털화 & 디지털의 아날로그화
[컴퓨터네트워크] Network Layer: Data transfer | IPv4 datagram, Fragmentation, ICMP, Mobile IP, IPv6
