[Network] Longest Prefix Match (LPM) 알고리즘

네트워크에서 패킷이 전송될 때, “이 패킷을 어디로 보낼까?” 를 결정하는 핵심은 라우팅 테이블 조회(Routing Table Lookup) 입니다.
이때 가장 중요한 개념 중 하나가 바로 Longest Prefix Match, 즉 가장 긴 접두사 일치입니다.

---

🧠 1. Longest Prefix Match란?

**Longest Prefix Match (LPM)**는 IP 라우팅에서 사용되는 기본 규칙으로,
패킷의 목적지 IP 주소와 라우팅 테이블의 네트워크 주소를 비교하여, 가장 길게 일치하는 네트워크(프리픽스)를 선택하는 알고리즘입니다.

👉 즉, 여러 경로가 일치하더라도 더 구체적인(서브넷 마스크가 긴) 경로를 우선 선택합니다.

---

🌐 2. 예시로 이해하기

다음과 같은 라우팅 테이블이 있다고 해봅시다:

네트워크넷마스크Next Hop

10.0.0.0	/8	A
10.10.0.0	/16	B
10.10.1.0	/24	C

패킷의 목적지 IP가 10.10.1.25일 때, 세 개의 네트워크 모두와 일치합니다.

네트워크일치 여부프리픽스 길이

10.0.0.0/8	✅	8
10.10.0.0/16	✅	16
10.10.1.0/24	✅	24

결과: /24 프리픽스가 가장 구체적이므로 Next Hop C가 선택됩니다.
이것이 바로 Longest Prefix Match입니다.

---

⚙️ 3. 왜 필요한가?

만약 LPM이 없다면 단순히 “처음 일치하는 항목”을 선택하게 됩니다.
이 경우, 세분화된 라우팅 정책(예: 특정 서브넷은 방화벽을 거쳐야 함)을 적용할 수 없습니다.

따라서 LPM은 다음과 같은 이유로 필수적입니다:

• 세분화된 네트워크 제어 가능
• 대규모 라우팅 테이블의 효율적 탐색
• 기본 경로(default route)와 특정 경로의 공존 지원

---

🧩 4. 알고리즘 동작 방식

Longest Prefix Match를 구현하는 방법에는 여러 가지가 있습니다.
대표적인 세 가지 방식은 다음과 같습니다.

(1) Linear Search (선형 탐색)

• 모든 라우팅 엔트리를 순차적으로 비교
• 가장 긴 일치 프리픽스를 선택
• 구현은 간단하지만 성능이 느림 (O(N))

 

best_match = null max_prefix_length = -1 for route in routing_table: if packet.dest_ip matches route.network: if route.prefix_length > max_prefix_length: best_match = route max_prefix_length = route.prefix_length return best_match

---

(2) Trie (Prefix Tree)

• IP 주소를 비트 단위로 트리 형태로 저장
• 각 노드는 0 또는 1로 분기
• 검색 시 최장 일치 경로를 따라 내려감

예시:

 

10.10.1.25 → 00001010.00001010.00000001.00011001

• 트리를 따라 내려가며 존재하는 가장 깊은 일치 노드가 LPM 결과
• 시간 복잡도는 O(W), W는 주소 길이(IPv4는 32)

✅ 실제로 Cisco, Juniper 등 라우터는 대부분 Trie 기반 LPM을 사용

---

(3) Compressed Trie (Patricia Trie)

• 연속된 비트를 하나의 경로로 압축
• 메모리 절약 + 탐색 속도 향상
• 상용 라우터에서 자주 사용되는 최적화된 LPM 구조

---

🧮 5. 실제 동작 예시 (Cisco 스타일)

 

Router# show ip route ... O 10.0.0.0/8 [110/2] via 192.168.1.1 O 10.10.0.0/16 [110/3] via 192.168.1.2 O 10.10.1.0/24 [110/4] via 192.168.1.3 ... Router# ping 10.10.1.25 # 패킷은 /24 경로를 따라 192.168.1.3으로 전달됨

---

📊 6. IPv6에서도 동일한 개념

IPv6 주소는 128비트이지만 LPM 원리는 완전히 동일합니다.

예:

• 2001:db8::/32 → 전체 네트워크
• 2001:db8:1234::/48 → 특정 서브넷

2001:db8:1234::abcd 목적지는 /48 프리픽스를 가진 경로로 라우팅됩니다.

---

🚀 7. 성능 최적화

대규모 ISP 라우터는 수십만 개의 라우팅 엔트리를 LPM으로 탐색해야 합니다.
이를 위해 다음 기술들이 함께 사용됩니다.

기술설명

TCAM (Ternary Content-Addressable Memory)	하드웨어에서 병렬 비교 수행
FIB (Forwarding Information Base)	실제 패킷 전송 시 빠른 조회용 캐시
Route Aggregation	불필요한 세분화 줄이기 (예: /24 → /16 병합)

---

💬 8. 정리

항목설명

개념	가장 긴 네트워크 프리픽스를 선택하는 알고리즘
목적	더 구체적인 경로를 우선 선택
구현	Linear Search, Trie, Patricia Trie
핵심 포인트	“더 긴 서브넷 마스크가 더 구체적이다”
실제 적용	IP 라우팅, 방화벽 정책, NAT 규칙 등

---

🧭 9. 한 줄 요약

“Longest Prefix Match는 라우터가 패킷을 가장 구체적인 목적지로 보낼 수 있게 해주는 핵심 알고리즘이다.”

---

📚 참고 자료

• RFC 1812 – Requirements for IP Version 4 Routers
• Cisco – Understanding IP Routing Lookup Process
• Juniper Tech Library – LPM in Routing Engine

---

원하신다면