Hop-by-Hop Forwarding

1. Overview

홉-바이-홉 포워딩(Hop-by-Hop Forwarding)은 목적지가 전 세계 어디든 간에 전체 지도를 볼 필요 없이, 그저 '내 다음 징검다리(Next Hop)'가 누군지만 미친 듯이 빠르게 쳐다보고 패킷을 토스하는 라우터의 릴레이 철학을 해부합니다.

학습자는 하나의 패킷이 라우터를 지날 때마다 IP 주소(최종 목적지)는 변하지 않지만 MAC 주소(징검다리)는 끊임없이 갈아 끼워지는 L2-L3 계층 간 봉투 갈아 끼우기의 본질을 뜯어봅니다. 나아가 수백만 줄의 목적지 리스트 중에서 가장 구체적인 주소 대역을 찾아내는 최장 접두사 일치(Longest Prefix Match) 알고리즘을 장악합니다. 마지막으로, 매 패킷마다 소프트웨어(CPU)가 라우팅 테이블을 뒤지던 원시적인 시대를 벗어나, 하드웨어 반도체(ASIC, TCAM) 수준에서 0.0001초 만에 패킷을 하드웨어로 스위칭(CEF)해 버리는 라우터 고속화의 끝을 확보합니다.

2. Scope & Boundaries

In-Scope

• Forwarding vs Routing: 길을 찾는 '계산(Routing)'과 들어온 패킷을 던지는 '행위(Forwarding)'의 분리.
• Data Plane Mechanics: 라우터 내에서의 패킷 룩업(Lookup)과 스위칭 패브릭(Switching Fabric).
• Longest Prefix Match (LPM): 라우팅 테이블 룩업 시 가장 구체적인 룰을 우선하는 매칭 알고리즘.
• Hardware Forwarding: Process Switching(CPU) vs CEF (Cisco Express Forwarding / FIB, Adjacency Table).

Out-of-Scope

• 라우팅 알고리즘 수학 (Dijkstra, Bellman-Ford): 라우팅 테이블을 "어떻게 채울 것인가?" $\rightarrow$ 08-03-03 OSPF, 08-03-04 BGP 영역으로 분리.
• L4/L7 방화벽 심층 패킷 분석 (DPI): Payload를 까서 악성코드를 잡는 행위 $\rightarrow$ 10-02 Network Security 영역으로 위임.

Boundaries

• Control Plane (Routing) vs Data Plane (Forwarding): 라우터 안에는 2개의 완전히 분리된 뇌가 있습니다. Control Plane은 OSPF나 BGP를 돌리며 주변과 수다를 떨고 천천히 '라우팅 테이블(지도)'을 완성하는 사령관입니다. Data Plane은 사령관이 던져준 지도를 보고 1초에 수백만 개의 패킷을 앞뒤 안 보고 포트 밖으로 던져버리는(Forwarding) 단순 무식한 근육입니다. 이 문서에서는 지도를 그리는 방법이 아니라, 지도를 보고 '얼마나 빨리 패킷을 던지는가(Data Plane)'에만 집중하여 경계를 긋습니다.

3. Counterexample

• 프로세스 스위칭(Process Switching)의 CPU 마비: 10Gbps의 트래픽이 라우터로 쏟아집니다. 초보 관리자가 구형 장비의 하드웨어 스위칭(CEF) 기능을 끄고 모든 패킷을 CPU(소프트웨어)가 라우팅 테이블을 매번 뒤져서 처리하게 만들었습니다(Process Switching). 라우터 CPU 사용률이 즉시 100%를 치고, 모든 네트워크 패킷이 지연되거나 버려지며 뻗어버립니다. Data Plane 트래픽을 하드웨어(ASIC)가 아닌 Control Plane(CPU)으로 밀어 올린 구조적 무지의 대가입니다.
• 롱기스트 프리픽스 매치(LPM)의 오해: 라우터에 두 개의 룰이 있습니다. 1. 10.1.0.0/16은 포트 A로 가라. 2. 10.1.1.0/24는 포트 B로 가라. 패킷의 목적지가 10.1.1.5입니다. 관리자가 "어? 1번 룰에도 속하고 2번 룰에도 속하잖아? 1번 룰이 테이블 위에 있으니까 A로 가겠지!"라고 착각합니다. 라우터는 테이블 순서가 아니라 '비트가 가장 많이 일치하는(가장 구체적인, /24)' 2번 룰을 무조건 우선시하여 B로 던진다는 LPM 원리를 모르는 끔찍한 라우팅 미스입니다.

4. Prerequisites

• L2 프레임과 L3 패킷 (Basic): MAC 주소와 IP 주소의 분리. (08-01-01, 08-01-02)
• 비트 연산 기초 (Basic): AND 연산을 통한 서브넷 비교. (08-03-01 IP Addressing)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 끝없는 봉투 갈아 끼우기, 릴레이 포워딩 (The Hop-by-Hop Relay)

• Why to Learn: 글로벌 인터넷 통신이 사실은 L3(IP)라는 불변의 편지를 L2(MAC)라는 수십 개의 단거리 택배 상자에 번갈아 담으며 건네주는 과정임을 통찰하기 위함입니다.
• What to Learn:
  • Concepts: Hop-by-Hop (홉 바이 홉), Packet Encapsulation, Decapsulation, L2 MAC Rewrite, TTL Decrement.
  • Skills: 출발지부터 목적지까지 3개의 라우터를 거칠 때, 매 구간(Link)마다 L2 Frame의 Source MAC과 Destination MAC이 어떻게 덮어씌워 지는지(Rewrite) 추적하기.
• How to Learn:
  • 1단계: 내용물(IP)은 불변: 내 노트북(IP A)에서 구글(IP Z)로 편지를 씁니다. 중간에 라우터를 20개 거치더라도, L3 IP 헤더에 적힌 Src: A, Dst: Z는 절대 지워지지 않습니다 (NAT 제외).
  • 2단계: 포장지(MAC)는 소모품: 내 노트북이 1번 라우터에게 던질 때 L2 포장지에 Src: 내 MAC, Dst: 1번 라우터 MAC을 적어 던집니다. 1번 라우터는 이 포장지를 갈기갈기 찢어 버리고(Decapsulation), 2번 라우터에게 던지기 위해 새 포장지에 Src: 1번 라우터 MAC, Dst: 2번 라우터 MAC을 다시 적어(Encapsulation) 던지는 끝없는 포장지 교체 릴레이를 해부합니다.
• Implement: 라우터 L2 Rewrite 시뮬레이터. 패킷 [MAC_A -> MAC_R1 | IP_User -> IP_Google | TTL=64]. 라우터(R1)가 수신.
  1. MAC 포장지 제거
  2. IP TTL 1 감소 (63)
  3. 라우팅 테이블 조회하여 다음 징검다리 R2 확인
  4. ARP 테이블로 R2의 MAC 획득
  5. 새 포장지 조립 [MAC_R1 -> MAC_R2 | IP_User -> IP_Google | TTL=63]. 이 패킷 변형 과정을 터미널에 순차적으로 로그라이크(Log-like) 렌더링.

Recommended

Core Topic 02: 디테일의 승리, 최장 접두사 일치 (Longest Prefix Match)

• Why to Learn: 수십만 개의 복잡하게 얽힌 라우팅 규칙 속에서, 라우터가 충돌 없이 가장 정확한 출구를 골라내는 비트 매칭의 지배 원리를 장악하기 위함입니다.
• What to Learn:
  • Concepts: Routing Table Lookup, Longest Prefix Match (LPM), Prefix Length (/8 vs /24), Default Route (0.0.0.0/0).
  • Skills: 목적지 IP와 라우팅 테이블 룰들의 서브넷 마스크를 각각 AND 연산하여, 가장 1(Match) 비트가 많은 경로를 최종 목적지로 선정하기.
• How to Learn:
  • 1단계: 여러 개의 함정: 목적지 IP 192.168.1.50이 들어왔습니다. 라우팅 테이블에는 192.168.0.0/16 (포트 1), 192.168.1.0/24 (포트 2), 0.0.0.0/0 (포트 3)이 있습니다. 셋 다 일치(Match)합니다. 어디로 보내야 할까요?
  • 2단계: 가장 구체적인 길 (LPM): 라우터는 이 중 비트가 가장 많이 겹치는(Prefix가 가장 긴) /24 룰을 우선합니다. 즉, "아시아로 가라(/16)"는 큰 규칙보다 "한국 서울로 가라(/24)"는 더 디테일한 룰을 따르는 것입니다. 만약 룰이 하나도 안 맞으면 최후의 수단(최단 Prefix 0)인 Default Route로 튕겨내는 영리한 서치 트리(Trie)를 뜯어봅니다.
• Implement: LPM 룩업 엔진 모사 (파이썬). Routing Table Array [{subnet: '10.0.0.0/8', port: 'A'}, {subnet: '10.1.0.0/16', port: 'B'}]. 들어온 패킷 10.1.5.5. 엔진이 패킷을 2진수로 변환하고 룰들과 비트 매칭. /8 룰은 8비트 매치. /16 룰은 16비트 매치. 엔진이 Max Match Length = 16을 찾아내어 [Result] Forwarding to Port B (LPM matched 16 bits)를 출력하는 논리 렌더링.

Practical

Core Topic 03: 뇌와 근육의 분리, 컨트롤 플레인 vs 데이터 플레인 (Control vs Data Plane)

• Why to Learn: 라우터를 단일 컴퓨터로 보는 초보적 시각을 버리고, 초당 수억 개의 패킷을 던지기 위해 '지도를 그리는 뇌'와 '짐을 나르는 근육'을 완벽히 분리한 SDN 아키텍처의 근본을 쥐기 위함입니다.
• What to Learn:
  • Concepts: Control Plane (컨트롤 플레인), Data Plane / Forwarding Plane (데이터 플레인), Routing Protocol (OSPF/BGP), CPU vs ASIC.
  • Skills: 라우터 장애 시, 라우팅 테이블이 안 그려지는 것인지(OSPF/BGP 장애) 패킷이 안 날아가는 것인지(라인 카드/칩셋 장애) 계층 분리하여 디버깅.
• How to Learn:
  • 1단계: 사령관 (Control Plane): CPU에서 소프트웨어로 돌아갑니다. OSPF와 BGP 프로토콜을 이용해 다른 라우터와 10초마다 수다를 떨며 글로벌 '네트워크 지도(RIB)'를 천천히, 그리고 완벽하게 그려냅니다. 패킷을 직접 나르지는 않습니다.
  • 2단계: 짐꾼 (Data Plane): 사령관이 다 그린 지도를 바탕으로 요약본(FIB)을 만들어 짐꾼들에게 넘겨줍니다. 짐꾼들은 소프트웨어가 아닌 깡통 하드웨어(ASIC) 칩셋입니다. 요약 지도를 칩셋에 구워 넣고, 패킷이 들어오는 순간 뇌를 거치지 않고 반사 신경(0.001ms)으로 포트 밖으로 쳐냅니다. 이 완벽한 뇌와 근육의 분업을 뜯어봅니다.
• Implement: Control / Data Plane 과부하 분리 시뮬레이터. 패킷이 1초에 1,000만 개 쏟아짐. 만약 구조가 엉성해서 모든 패킷이 Control Plane의 CPU로 간다면 [CRASH] CPU 100% - BGP Sessions Dropped. 정상적인 아키텍처라면 사령관(CPU) 사용률은 1%로 평온하게 BGP 세션을 유지하고, 패킷은 라인 카드의 Data Plane (ASIC)에서 99% 스위칭되어 무정지 통신이 이루어지는 아키텍처 비교 렌더링.

Advanced

Core Topic 04: 반도체에 구워진 지도, 하드웨어 스위칭 (Hardware Forwarding & CEF)

• Why to Learn: 소프트웨어로 라우팅 테이블을 뒤지는(Process Switching) 원시 시대를 종식시키고, TCAM 메모리와 CEF(Cisco Express Forwarding)를 통해 라우터를 기가비트 하드웨어 스위치처럼 미친 속도로 동작하게 만드는 마법을 장악하기 위함입니다.
• What to Learn:
  • Concepts: Process Switching (CPU 기반), Fast Switching (캐시 기반), CEF / Topology-driven Switching (FIB + Adjacency Table), TCAM (Ternary Content Addressable Memory).
  • Skills: 라우팅 테이블(RIB)이 Data Plane용 하드웨어 테이블(FIB)과 MAC 정보 테이블(Adjacency)로 사전 결합(Pre-computed)되어 내려가는 최적화 파이프라인 이해.
• How to Learn:
  • 1단계: 소프트웨어의 끔찍한 병목: 패킷이 들어올 때마다 CPU가 1. 라우팅 테이블을 뒤져 다음 홉(IP)을 찾고, 2. ARP 테이블을 뒤져 다음 홉의 MAC을 찾아 포장지를 씌웁니다. 패킷 수천만 개를 매번 이렇게 계산하면 라우터가 터집니다 (Process Switching).
  • 2단계: CEF의 하드웨어 마법 (FIB): 똑똑한 라우터는 패킷이 오기도 전에 미리 CPU가 라우팅 테이블(IP)과 ARP 테이블(MAC)을 합쳐버립니다. "192.168.1.0/24로 가는 건 무조건 포트 2번이고 씌워야 할 MAC 주소는 00:AA...다"라는 결론 덩어리(FIB + Adjacency Table)를 만들어 반도체(TCAM) 메모리에 구워버립니다. 패킷이 들어오면 하드웨어가 단 1 클럭(O(1) 시간)만에 답을 찾고 튕겨내는 기가비트 라우팅의 끝을 해부합니다.
• Implement: CPU 룩업 vs TCAM(CEF) 룩업 벤치마크 모사. CPU 로직: for route in RoutingTable: 선형 탐색($O(N)$) -> ARP 테이블 탐색. 소요 시간 100us. TCAM 로직: 들어온 IP를 Hash Key로 사용하여 결합된 딕셔너리(FIB)에서 O(1)로 즉시 Next-Hop MAC까지 한 방에 추출. 소요 시간 1us. 1,000만 개의 패킷 처리 시 100배 차이나는 성능(Throughput) 비교 차트 렌더링.

7. Terminology

8. References

Primary

• [P1] CS2023 - Networking and Communication (NC) - Routing and Forwarding
• [P5] SFIA - Network Design (NTDS) - Forwarding Architectures and Hardware

Secondary

• [Computer Networking: A Top-Down Approach] Kurose & Ross - The Network Layer: Data Plane (Inside a Router)
• [TCP/IP Illustrated, Volume 1] Kevin R. Fall - IP Forwarding

Industry

• [Cisco Technical Documentation] - Understanding Cisco Express Forwarding (CEF)
• [Juniper Networks] - Packet Forwarding Architecture

9. Final Checklist

Primary

• 내 노트북(PC)에서 구글 서버로 통신할 때, L3의 출발지/목적지 IP 주소는 불변인 반면 L2의 출발지/목적지 MAC 주소는 라우터를 거칠(Hop) 때마다 어떻게 덮어씌워지는지(Rewrite) 메커니즘을 증명할 수 있는가?
• 하나의 라우터에 10.1.0.0/16 규칙과 10.1.1.0/24 규칙이 동시에 존재할 때, 목적지 IP가 10.1.1.50인 패킷이 롱기스트 프리픽스 매치(LPM) 알고리즘에 의해 어디로 포워딩될지 논증할 수 있는가?

Secondary

• 통신사 백본 라우터에서 복잡한 BGP 지도를 연산하는 '컨트롤 플레인(Control Plane)'의 CPU와, 실제 10Gbps의 트래픽을 처리하는 '데이터 플레인(Data Plane)' 칩셋을 아키텍처적으로 분리해야 하는 뇌/근육 분산 이유를 설명할 수 있는가?
• 패킷의 목적지 서브넷과 일치하는 규칙이 라우팅 테이블에 단 하나도 없을 경우, 최후의 보루(LPM 길이 0)인 기본 게이트웨이(Default Route, 0.0.0.0/0)를 통해 외부 망으로 트래픽을 넘겨버리는 포워딩 백스톱(Backstop) 원리를 해부할 수 있는가?

Industry

• 패킷이 들어올 때마다 매번 라우팅 테이블과 ARP 테이블을 순차 조회하는 프로세스 스위칭(Process Switching)의 CPU 병목을 식별할 수 있는가?
• 위 병목을 제거하기 위해, 컨트롤 플레인(RIB) 정보를 미리 포워딩 정보 기지(FIB)와 Adjacency 테이블로 결합한 뒤 하드웨어 메모리(TCAM)에 밀어 넣어 $O(1)$ 속도로 패킷을 쳐내는 CEF (Topology-driven Switching) 파이프라인을 설계할 수 있는가?