OSPF & Link-State Dynamics

1. Overview

OSPF와 링크 상태 역학(OSPF & Link-State Dynamics)은 낡은 라우터들이 주변 사람 말만 믿고 길을 찾던 멍청한 시대(RIP)를 종식시키고, 네트워크 전체 지도를 완벽하게 그린 후 수학적으로 최적 경로를 도출해 내는 **IGP(내부 게이트웨이 프로토콜)**의 황제 OSPF를 해부합니다.

학습자는 단순히 거리를 재는 것을 넘어, 선로의 대역폭(10Gbps vs 100Mbps)을 비용(Cost)으로 환산하는 링크 상태(Link-State) 철학을 뜯어봅니다. 나아가 수백 대의 라우터가 서로의 상태 정보(LSA)를 퍼뜨려 완벽히 동일한 지도(LSDB)를 복제하는 플러딩(Flooding) 동기화 과정을 장악합니다. 마지막으로, 지도 크기가 너무 커져 라우터가 터지는 것을 막기 위해 전체 네트워크를 구역(Area 0, Area 1)으로 쪼개고, 중추 신경망(Backbone Area 0)을 통해서만 통신을 허용하는 계층적 OSPF 아키텍처 설계 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• Link-State vs Distance-Vector: OSPF(Link-State)와 RIP(Distance-Vector)의 근본적 패러다임 차이.
• LSDB & SPF Algorithm: 링크 상태 데이터베이스(LSDB)의 동기화와 다익스트라(Dijkstra) 알고리즘을 통한 SPF(Shortest Path First) 트리 계산.
• OSPF Hierarchy: Area 0 (Backbone Area)와 일반 Area 간의 계층적 라우팅 통제.
• LSA (Link-State Advertisement): 라우터들이 주변 상태를 브로드캐스트하는 정보 패킷의 본질.

Out-of-Scope

• LSA Type 1~7 비트 레벨 딥 다이브: 각 LSA 타입의 헤더 포맷과 NSSA(Not-So-Stubby Area) 등의 지엽적 예외 처리 $\rightarrow$ CCIE 네트워크 엔지니어링 실습 영역.
• 글로벌 통신사 간 라우팅: 서로 다른 AS 간의 통신 $\rightarrow$ 08-03-04 BGP Path Navigation 영역으로 위임.

Boundaries

• Distance-Vector (RIP) vs Link-State (OSPF): RIP는 "내 옆 라우터가 구글까지 3칸(Hop) 걸린대, 그럼 난 4칸이네" 하고 '남의 말(소문)'에만 의존합니다. 반면 OSPF는 남의 말을 믿지 않습니다. 오직 "A와 B가 1Gbps 선으로 연결되어 있다"는 객관적 사실(Link-State) 팩트 조각들만 수집해서, 자기가 직접 뇌(CPU)에서 전체 지도를 그리고 계산합니다. 남에게 의존하지 않고 주도적으로 경로를 개척하는 이 철학의 차이를 명확히 경계 짓습니다.

3. Counterexample

• 대역폭을 무시한 최단 거리의 함정 (RIP의 맹점): 서울에서 부산으로 가는 길이 두 개 있습니다. A 경로는 라우터를 1개 거치지만 시골 국도(10Mbps)입니다. B 경로는 라우터를 3개 거치지만 KTX 고속철도망(10Gbps)입니다. OSPF가 아닌 구형 RIP(Distance-Vector)를 쓰면 "라우터 개수가 1개인 곳이 더 가깝다!"라며 10Mbps 국도로 모든 트래픽을 밀어 넣어 끔찍한 병목(Bottleneck)이 발생합니다. 대역폭(Bandwidth)을 비용(Cost)으로 역산하는 OSPF의 지능이 결여된 설계입니다.
• 단일 Area 붕괴 (LSDB 폭주): 글로벌 기업망에 OSPF를 도입하며 500대의 라우터를 전부 Area 0에 때려 넣었습니다. 아프리카 지사의 라우터 랜선 하나가 뽑혔다 꽂힐 때마다, 변경된 상태(LSA)가 500대 전체에 브로드캐스트되고, 500대가 동시에 다익스트라 알고리즘을 재계산(SPF Recalculation)합니다. 전체 네트워크 CPU가 100%를 치며 망이 마비됩니다. 500대를 구역(Area)별로 쪼개어, 구역 밖으로는 "선이 뽑혔다"는 자잘한 정보를 숨기고(요약하고) 평온을 유지하는 OSPF 계층화 철학을 무시한 참사입니다.

4. Prerequisites

• 그래프 이론 (Basic): 다익스트라(Dijkstra) 알고리즘 원리. (04-01-04 Graph Mechanics)
• AS (Autonomous System) 개념 (Basic): 내부망 라우팅(IGP)의 경계. (08-02-03 Routing & GTM)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 거리의 배신과 비용의 승리 (Link-State vs Distance-Vector)

• Why to Learn: 단순히 거쳐 가는 라우터의 개수(Hop)가 적다고 해서 빠른 길이 아님을 통찰하고, 대역폭 기반의 비용(Cost) 계산이 왜 모던 IGP의 표준인지 깨닫기 위함입니다.
• What to Learn:
  • Concepts: Distance-Vector (RIP, 홉 카운트 기반), Link-State (OSPF, 대역폭 기반), Cost (비용), Bandwidth (대역폭).
  • Skills: 주어진 토폴로지에서 100Mbps 선로(Cost 1)와 10Mbps 선로(Cost 10)를 구별하여 OSPF 최적 경로(Shortest Path) 계산하기.
• How to Learn:
  • 1단계: RIP의 맹점: A $\rightarrow$ B(10Mbps) $\rightarrow$ C 가 있습니다. 반대로 A $\rightarrow$ D(1Gbps) $\rightarrow$ E(1Gbps) $\rightarrow$ C 가 있습니다. RIP는 징검다리 개수가 1개인 A $\rightarrow$ B $\rightarrow$ C를 택합니다. 트래픽이 10Mbps 선로에 갇혀 질식합니다.
  • 2단계: OSPF의 비용(Cost): OSPF는 라우터 개수를 안 봅니다. 선로의 대역폭을 10^8 / 대역폭 공식으로 비용(Cost)으로 바꿉니다. 1Gbps 선로는 Cost가 1이고, 10Mbps 선로는 Cost가 10입니다. OSPF는 비용이 훨씬 싼 A $\rightarrow$ D $\rightarrow$ E $\rightarrow$ C (Cost 2)를 선택하는 합리적 계산법을 해부합니다.
• Implement: OSPF Cost 계산기 (파이썬). Reference_Bandwidth = 100Mbps. 링크 A(10Mbps), 링크 B(1Gbps). 로직 연산: Cost_A = 100M / 10M = 10. Cost_B = 100M / 1G = 0.1 -> 1(최소값 보정). 홉 카운트가 많아도 Cost_B 라우팅을 우선하는 매트릭(Metric) 역전 현상 렌더링.

Recommended

Core Topic 02: 지도를 완성하라, LSA 플러딩과 LSDB (LSA Flooding & LSDB)

• Why to Learn: OSPF 라우터가 도대체 어떻게 '자기가 한 번도 가보지 않은' 저 멀리 있는 서브넷까지 지도를 완벽하게 그릴 수 있는지, 그 소문 확산의 메커니즘을 쥐기 위함입니다.
• What to Learn:
  • Concepts: LSA (Link-State Advertisement), Flooding (플러딩), LSDB (Link-State Database), OSPF Hello Packet.
  • Skills: 하나의 라우터에서 발생한 인터페이스 다운(Down) 이벤트가 LSA를 통해 전체 OSPF 네트워크로 전파되어 모든 라우터의 LSDB를 똑같이 동기화하는 과정 추적.
• How to Learn:
  • 1단계: 이웃 탐색 (Hello): 라우터를 켜면, 일단 자기가 꽂혀있는 포트에 Hello 패킷을 쏴서 "내 옆에 누구 있니?"를 파악합니다. 이를 통해 이웃(Neighbor) 목록을 만듭니다.
  • 2단계: 지도 조각 퍼뜨리기 (Flooding): A 라우터가 알아낸 이웃 정보(LSA)를 복사해서 모든 구멍으로 뿜어냅니다(Flooding). B도 뿜어내고 C도 뿜어냅니다. 결국 AS(회사) 안의 모든 라우터는 A, B, C가 뿜어낸 퍼즐 조각(LSA)을 모두 수집하게 됩니다. 이 조각들을 꽉꽉 뭉쳐놓은 완벽한 전체 지도, LSDB(Link-State Database)의 동기화 마법을 뜯어봅니다.
• Implement: LSA Flooding 전파 시뮬레이터. Node A, B, C, D가 있음. Node A에 연결된 Link_1이 끊어짐(DOWN). Node A가 LSA(Link_1=Down, Seq=1) 생성 및 주변(B, C)으로 브로드캐스트. B와 C는 수신 후 자신의 LSDB 업데이트 $\rightarrow$ 다시 주변(D)으로 전달. 1초 만에 D의 터미널에 [LSDB UPDATED] A's Link_1 is DOWN이 찍히며 전체 상태가 동기화되는 분산 시스템 데모.

Practical

Core Topic 03: 뇌를 굴려라, 다익스트라 SPF 계산 (The SPF Calculation)

• Why to Learn: 남이 던져준 라우팅 테이블을 맹신하는 게 아니라, 100% 동일한 지도(LSDB)를 펼쳐놓고 각자 스스로의 관점에서 최단 경로를 직접 그려내는 알고리즘의 자립성을 장악하기 위함입니다.
• What to Learn:
  • Concepts: SPF (Shortest Path First) Algorithm, Dijkstra's Algorithm, Root Node, Tree Structure.
  • Skills: LSDB 토폴로지를 기반으로 특정 라우터를 루트(Root)로 하는 다익스트라 트리를 손으로/코드로 직접 그려보고 포워딩 테이블 도출.
• How to Learn:
  • 1단계: 동일한 지도, 다른 시선: 100대의 라우터는 LSA 플러딩을 통해 완전히 똑같은 지도(LSDB)를 가지고 있습니다. 하지만 최종적으로 갈 길(라우팅 테이블)은 다 다릅니다. 왜? 자기 자신의 '위치'가 다르기 때문입니다.
  • 2단계: 내가 중심인 트리 (Dijkstra): A 라우터는 지도를 펼치고, 자기를 뿌리(Root)에 둡니다. 그리고 다익스트라 알고리즘을 돌려 자기 위치에서 뻗어나가는 '비용이 가장 싼 나뭇가지(SPF Tree)'들을 쫙 칩니다. 목적지 Z로 가기 위해 B로 뻗은 가지가 제일 싸다면, 라우팅 테이블에 Z로 갈 땐 B로 던져라라고 딱 1줄 적어놓는 고도의 뇌 작동을 해부합니다.
• Implement: 파이썬 다익스트라(SPF) 트리 생성기. 5개의 노드 간 Cost 매트릭스 [[0, 10, 5, 0, 0], ...] 입력. 엔진이 Node A를 Root로 지정하여 다익스트라 알고리즘(Min-Heap 활용)을 돌려 A->C->B (Cost 15) 최단 경로 트리를 구축함. 최종적으로 A의 Routing Table을 [Dst: B, Next-Hop: C, Cost: 15] 형식으로 추출해 내는 포워딩 룰 생성 과정 렌더링.

Advanced

Core Topic 04: 두뇌 폭발 방지, 백본과 계층화 (Areas & The Backbone)

• Why to Learn: 라우터 500대가 모두 수다를 떨고 매번 다익스트라를 돌리면 CPU가 터지므로, OSPF 네트워크를 여러 구역(Area)으로 쪼개어 소문을 통제하는 대규모 네트워크 아키텍처를 세우기 위함입니다.
• What to Learn:
  • Concepts: OSPF Area 0 (Backbone Area), Non-Backbone Area (Area 1, 2...), ABR (Area Border Router), Route Summarization between Areas.
  • Skills: 글로벌 기업망 설계 시, Area 1(아시아)과 Area 2(유럽)가 반드시 중앙의 Area 0(백본)을 거치도록 강제하는 허브 앤 스포크(Hub-and-Spoke) 토폴로지 설계.
• How to Learn:
  • 1단계: 플러딩 지옥: 라우터 1대가 꺼지면 전체 500대가 즉시 다익스트라 계산을 다시 합니다(SPF Recalculation). 서울에서 라우터 1대가 흔들리는데, 미국에 있는 라우터 CPU가 100%를 치는 나비효과가 발생합니다.
  • 2단계: 계층적 단절 (Area): 전체를 백본(Area 0)과 지사(Area 1, Area 2)로 쪼갭니다. Area 1 내부에서 라우터가 꺼진 소문은 Area 1 안에서만 플러딩됩니다. Area 1과 0을 걸치고 있는 경계 라우터(ABR)는 백본 쪽에 "Area 1 내부 사정은 알 거 없고, 그냥 10.1.0.0/16으로 가려면 나한테 보내"라고 경로를 뭉뚱그려 요약(Summarize)해 버립니다. 타 구역의 자잘한 변화에 내 CPU가 흔들리지 않게 방어막을 치는 OSPF 스케일링의 끝판왕을 뜯어봅니다.
• Implement: OSPF ABR(Area Border Router) 요약 시뮬레이터. Area 1 내부 라우터들이 192.168.1.0/24, 192.168.2.0/24 링크 변동 이벤트를 미친 듯이 뿜어냄. 하지만 경계에 있는 ABR_Router가 이를 Area 0(Backbone)로 플러딩할 때는 자잘한 이벤트를 모두 Drop하고, 오직 1시간 주기로 요약된 192.168.0.0/16 LSA 1장만 던져서 Area 0 라우터들의 CPU(다익스트라 연산)를 평온하게 0%로 유지시키는 인프라 격리 애니메이션.

7. Terminology

8. References

Primary

• [P1] CS2023 - Networking and Communication (NC) - Routing and Forwarding (Link-State Algorithms)
• [P5] SFIA - Network Design (NTDS) - Dynamic Routing Protocol Architectures

Secondary

• [Computer Networking: A Top-Down Approach] Kurose & Ross - Intra-AS Routing in the Internet: OSPF
• [TCP/IP Illustrated, Volume 1] Kevin R. Fall - OSPF: Open Shortest Path First

Industry

• [Cisco Networking Academy] - Single-Area and Multiarea OSPF
• [IETF RFC 2328] - OSPF Version 2

9. Final Checklist

Primary

• 징검다리 개수(Hop Count)만 따지는 RIP 프로토콜의 대역폭 무시 맹점을 지적하고, 10Gbps와 100Mbps의 차이를 비용(Cost)으로 환산하여 최적 경로를 찾는 OSPF의 링크 상태(Link-State) 패러다임 우위를 설명할 수 있는가?
• OSPF 라우터가 주변 상태 변화를 감지했을 때 LSA(Link-State Advertisement) 패킷을 플러딩(Flooding)하여, AS 내부의 모든 라우터가 100% 동일한 LSDB(Link-State Database) 지도를 완성하는 동기화 메커니즘을 증명할 수 있는가?

Secondary

• 완벽하게 동기화된 LSDB 위에서, 각 라우터가 자신을 루트(Root)로 삼아 다익스트라(Dijkstra)의 SPF(Shortest Path First) 알고리즘을 독자적으로 구동하여 최종 라우팅 포워딩 룰을 도출하는 단계를 해부할 수 있는가?
• 500대의 라우터가 단일 Area에 묶여있을 때, 링크 하나가 깜빡거리는 이벤트(Flapping)가 전체 500대의 CPU 다익스트라 재계산을 유발하여 네트워크를 마비시키는 'SPF Recalculation 폭풍'의 위험을 식별할 수 있는가?

Industry

• 위와 같은 연산 폭풍(CPU 오버헤드)을 격리하기 위해, OSPF 네트워크를 백본(Area 0)과 일반 Area(1, 2)로 분할하고 모든 타 구역 간 통신이 백본을 관통하도록 강제하는 계층적 2-Tier 아키텍처를 설계할 수 있는가?
• 두 Area의 경계에 서 있는 ABR(Area Border Router)가 타 Area에서 발생한 자잘한 LSA 변동을 백본으로 넘기지 않고, 거대한 하나의 서브넷으로 경로 요약(Route Summarization)하여 차단하는 트래픽 댐(Dam)의 가치를 논증할 수 있는가?