컴퓨터공학 300 주제 시리즈의 145번째 글이다. 전체 지도는 여기.

한 줄 요약

라우터는 목적지 IP 를 라우팅 표와 비교해 가장 길게 일치하는 프리픽스(longest prefix match)의 다음 홉으로 패킷을 넘긴다. 그 표를 사람이 채우면 정적 라우팅, 프로토콜이 채우면 동적 라우팅이다.

왜 필요한가

인터넷에는 패킷 하나가 출발지에서 목적지까지 가는 전체 경로를 아는 장비가 없다. 각 라우터는 “이 목적지라면 다음은 저쪽”만 안다. 이 단순한 규칙이 수만 개 네트워크를 엮는다.

라우팅을 모르면 이런 장애를 설명할 수 없다. VPN 을 켰더니 사내망은 되는데 인터넷이 안 된다. 노드를 하나 추가했더니 그 노드에서만 다른 서브넷으로 못 간다. 응답 패킷이 다른 길로 돌아와 방화벽에서 버려진다. 모두 라우팅 표의 한두 줄 문제다.

핵심 개념

라우팅 표

모든 IP 호스트에는 라우팅 표가 있다. 서버 한 대의 표는 대략 이렇게 생겼다(문서용 주소).

목적지            다음 홉          인터페이스
0.0.0.0/0         192.0.2.1        eth0      ← 기본 경로(default route)
192.0.2.0/24      (직접 연결)       eth0
198.51.100.0/24   192.0.2.254      eth0
198.51.100.128/25 192.0.2.253      eth0
  • 직접 연결 경로: 인터페이스에 주소를 붙이면 그 서브넷이 자동으로 들어간다. 다음 홉 없이 ARP 로 바로 보낸다.
  • 기본 경로 0.0.0.0/0: 다른 어떤 줄과도 안 맞을 때 쓰는 마지막 줄이다. 프리픽스 길이가 0 이라 모든 주소와 일치하지만 가장 짧다.

최장 프리픽스 일치

목적지가 198.51.100.200 이면 위 표에서 세 줄이 일치한다. /0, /24, /25. 이 중 가장 긴 /25 를 고른다. 더 구체적인 정보가 이긴다는 원칙이다. CIDR 이후 주소 블록이 크기 제각각으로 쪼개지면서 이 규칙이 필수가 됐다. IPv4 라우터 요구사항을 정리한 RFC 1812 도 이 규칙을 기본으로 둔다.

홉마다 일어나는 일

라우터가 패킷 하나를 넘길 때의 순서다.

  1. 이더넷 프레임을 받고 FCS 를 검사한다.
  2. IP 헤더의 TTL 을 1 줄인다. 0 이 되면 버리고 출발지에 ICMP Time Exceeded 를 보낸다. 라우팅 루프가 생겨도 패킷이 영원히 돌지 않게 하는 장치다. traceroute 는 이 성질을 이용한다(159번 글).
  3. 목적지 IP 로 라우팅 표를 찾는다. 일치하는 경로가 없으면 버리고 ICMP Destination Unreachable 을 보낸다.
  4. 다음 홉의 MAC 을 ARP 로 찾아 새 이더넷 헤더를 쓰고 내보낸다.

IP 주소는 끝까지 그대로고 MAC 주소는 홉마다 바뀐다. NAT 가 끼면 IP 도 바뀐다(146번 글).

정적 라우팅과 동적 라우팅

구분 정적 라우팅 동적 라우팅
표를 채우는 주체 관리자 라우팅 프로토콜
장애 시 사람이 고칠 때까지 그대로 자동으로 우회 경로 계산
적합한 곳 작은 망, 기본 경로 하나 경로가 여럿인 큰 망

동적 라우팅 프로토콜은 범위에 따라 나뉜다.

  • 내부 게이트웨이 프로토콜(IGP): 한 조직 안. 거리 벡터 방식인 RIP(RFC 2453)는 이웃에게 “어디까지 몇 홉”을 주고받는다. 링크 상태 방식인 OSPF(RFC 2328)는 모든 라우터가 망 전체의 링크 지도를 공유하고 각자 다익스트라 최단 경로 알고리즘으로 표를 만든다.
  • 외부 게이트웨이 프로토콜(EGP): 조직(자율 시스템, AS) 사이. 인터넷의 사실상 유일한 EGP 가 BGP(RFC 4271)다. BGP 는 최단 거리보다 정책을 따른다. “이 경로는 어떤 AS 들을 거친다”는 AS 경로 정보를 주고받고, 각 조직이 비용·계약 관계에 따라 고른다.

비대칭 경로

가는 길과 오는 길이 같을 필요는 없다. 각 방향의 라우터가 각자 표를 보고 결정하기 때문이다. 대부분은 문제가 없지만, 연결 상태를 추적하는 방화벽이 한 방향만 보게 되면 응답을 “모르는 연결”로 보고 버린다. 리눅스의 역경로 필터(rp_filter)도 비대칭 경로 패킷을 버릴 수 있다.

직접 해 보기

최장 프리픽스 일치와, 링크 상태 라우팅의 핵심인 다익스트라를 작게 구현해 보자.

import ipaddress as ip
import heapq

table = [
    ("0.0.0.0/0",         "192.0.2.1"),
    ("192.0.2.0/24",      "직접 연결"),
    ("198.51.100.0/24",   "192.0.2.254"),
    ("198.51.100.128/25", "192.0.2.253"),
]
table = [(ip.ip_network(p), nh) for p, nh in table]

def lookup(dst):
    d = ip.ip_address(dst)
    matches = [(net, nh) for net, nh in table if d in net]
    net, nh = max(matches, key=lambda m: m[0].prefixlen)
    return net, nh

for dst in ["192.0.2.77", "198.51.100.5", "198.51.100.200", "203.0.113.9"]:
    net, nh = lookup(dst)
    print(f"{dst:15s} -> {str(net):18s} 다음 홉 {nh}")

# OSPF 처럼 링크 비용 지도를 공유했다고 치고 R1 기준 최단 경로 계산
links = {("R1","R2"):10, ("R1","R3"):1, ("R3","R2"):1, ("R2","R4"):1, ("R3","R4"):10}
graph = {}
for (a, b), c in links.items():
    graph.setdefault(a, []).append((b, c)); graph.setdefault(b, []).append((a, c))

def dijkstra(src):
    dist, first_hop, pq = {src: 0}, {}, [(0, src, None)]
    while pq:
        d, u, hop = heapq.heappop(pq)
        if d > dist.get(u, float("inf")): continue
        if hop: first_hop.setdefault(u, hop)
        for v, c in graph[u]:
            nd = d + c
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v, hop or v))
    return dist, first_hop

dist, hop = dijkstra("R1")
for r in sorted(dist):
    if r != "R1":
        print(f"R1 -> {r}: 비용 {dist[r]}, 다음 홉 {hop[r]}")

192.0.2.77      -> 192.0.2.0/24       다음 홉 직접 연결
198.51.100.5    -> 198.51.100.0/24    다음 홉 192.0.2.254
198.51.100.200  -> 198.51.100.128/25  다음 홉 192.0.2.253
203.0.113.9     -> 0.0.0.0/0          다음 홉 192.0.2.1
R1 -> R2: 비용 2, 다음 홉 R3
R1 -> R3: 비용 1, 다음 홉 R3
R1 -> R4: 비용 3, 다음 홉 R3

R1 과 R2 는 직접 연결돼 있지만 비용이 10 이라, R3 를 거치는 비용 2 경로가 선택됐다. 라우팅 표에 들어가는 건 전체 경로가 아니라 “다음 홉 R3” 하나뿐이라는 점을 보라. 실제 라우터는 수십만 개 경로에서 이 검색을 초당 수백만 번 해야 하므로 선형 탐색 대신 트라이(trie)나 전용 하드웨어(TCAM)를 쓴다.

현업에서는

  • 리눅스에서 ip route 로 표를 보고, ip route get <목적지> 로 “이 주소면 실제로 어느 경로를 타는지”를 바로 물을 수 있다. 장애 조사 첫 명령으로 좋다.
  • VPN 클라이언트가 0.0.0.0/0 을 자기 인터페이스로 바꾸면 모든 트래픽이 터널로 간다(full tunnel). 사내 대역만 보내려면 해당 프리픽스만 터널 경로로 넣는다(split tunnel).
  • 쿠버네티스 CNI 중 일부(Calico 의 BGP 모드 등)는 노드끼리 BGP 로 파드 대역 경로를 주고받는다. 오버레이 없이 라우팅만으로 파드 간 통신을 만드는 방식이다.
  • 인터넷 규모에서는 BGP 설정 실수 하나가 큰 사업자의 접속 장애로 번진 사례가 반복돼 왔다. 그래서 경로 출처 검증(RPKI) 같은 보호 장치가 확산되고 있다.

확인 문제

  1. 라우팅 표에 10.0.0.0/8, 10.1.0.0/16, 10.1.2.0/24 가 있을 때 10.1.3.4 는 어느 줄을 타는가?
  2. TTL 필드가 없다면 라우팅 루프에서 어떤 일이 생기는가?
  3. 거리 벡터와 링크 상태 방식의 가장 큰 차이는 무엇인가?
  4. BGP 가 단순 최단 경로가 아니라 “정책”으로 경로를 고르는 이유는?
  5. 비대칭 경로가 상태 추적 방화벽에서 문제를 일으키는 이유는?

풀이

  1. 10.1.2.0/24 는 일치하지 않는다(10.1.3.x 이므로). 일치하는 /8 과 /16 중 더 긴 10.1.0.0/16 을 탄다.
  2. 패킷이 루프를 끝없이 돌며 대역폭을 소모한다. TTL 이 있으면 정해진 홉 수 뒤에 버려진다.
  3. 거리 벡터는 이웃에게 목적지별 거리만 전달하고, 링크 상태는 모든 라우터가 전체 망 지도를 공유한 뒤 각자 최단 경로를 계산한다.
  4. AS 들은 서로 다른 조직이고, 어떤 경로로 트래픽을 받고 보낼지는 비용·계약·보안 같은 사업 판단이기 때문이다.
  5. 방화벽이 연결의 한 방향만 보게 되어, 반대 방향 패킷을 상태 표에 없는 연결로 판단하고 버리기 때문이다.

더 읽을거리 (References)