348. 링크 상태 (Link State) 라우팅 알고리즘 - 다익스트라(Dijkstra) 기반 (최단경로/SPF)

핵심 인사이트 (3줄 요약)

본질: 링크 상태(Link State) 라우팅은 남의 소문(요약본)을 믿지 않고, 동네 모든 라우터가 각자의 팔다리(링크) 상태 정보를 퍼즐 조각처럼 모아 거대한 3D 지형도를 각자의 뇌 속에 똑같이 그려내는 똑똑하고 독립적인 길 찾기 방식이다.

다익스트라 (Dijkstra / SPF) 알고리즘: 완성된 전체 지도를 펼쳐놓고, 천재 수학자 다익스트라가 만든 SPF(Shortest Path First) 공식을 팽팽 돌려 자기 자신을 뿌리로 삼아 목적지까지의 가장 빠른 나뭇가지 길(SPF 트리)을 수학적으로 완벽하게 깎아낸다.

장점 (속도와 루프 방지): 남이 사기를 쳐도 내 눈으로 전체 지도를 다 꿰뚫어 보고 있으므로 무한 루프(Routing Loop)에 절대 빠지지 않으며, 30초마다 방송을 때리지 않고 **"선이 끊어졌을 때만 즉각 통보(Event-driven)"**하므로 수렴 속도가 번개같이 빠르다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: 각 라우터가 네트워크 전체의 토폴로지(Topology, 연결 상태) 정보를 LSA(Link State Advertisement) 패킷으로 수집해 독자적인 데이터베이스를 구축하고, SPF 알고리즘으로 최적 경로를 계산하는 IGP 프로토콜 계열 (OSPF, IS-IS).
필요성: 구형 거리 벡터(RIP)는 라우터가 15개만 넘어가도 소문이 전달되는 데 몇 분이 걸려 인터넷이 마비되었고, "내 앞이 끊어졌는데 니 앞이 뚫려있다고 뻥치냐?"라며 무한 루프에 빠져 죽어버렸다. 거대해진 대기업 사내망을 버텨내려면, **"라우터 CPU가 연산하느라 좀 고생하더라도, 차라리 찝찝한 소문을 믿지 말고 모든 라우터가 100% 동일한 전체 지도를 공유하게 만들자!"**라는 발상의 전환이 링크 상태의 위대한 탄생 배경이다.
💡 비유: 링크 상태는 1,000피스짜리 **"직소 퍼즐 맞추기"**와 같습니다.
- 거리 벡터가 남이 완성해 놓은 퍼즐 그림을 말로만 전해 듣는 것이라면, 링크 상태는 동네 사람들 1,000명이 자기가 가진 퍼즐 조각(LSA)을 테이블 중앙에 모조리 쏟아붓습니다(Flooding).
- 모든 사람이 각자 조각을 맞춰서 똑같은 '동네 전체 풍경 그림(토폴로지 DB)'을 완성한 뒤, 자기 위치에서 부산까지 가는 최적의 펜 선(다익스트라 알고리즘)을 쭉 그어버립니다.

📢 섹션 요약 비유: 링크 상태는 내 머리 위에 개인용 **"정찰 드론"**을 띄워 도시 전체의 교통 상황을 CCTV로 한눈에 굽어보면서(토폴로지 공유), 막힌 길을 피해 가장 쾌적한 도로를 내 머리로 직접 계산해 내는(SPF) 완벽한 자율 주행 시스템입니다.

Ⅱ. 링크 상태의 3단계 동작과 다익스트라 트리 (Deep Dive)

1. 퍼즐 조각 던지기: LSA Flooding

링크 상태 라우터(OSPF)가 부팅되면 자기 몸에 꽂힌 랜선 상태를 점검한다. "내 1번 팔은 1Gbps 속도고 192.x 망이랑 연결됨."
이 상태 정보가 담긴 엽서를 **LSA (Link State Advertisement)**라고 부른다.
라우터는 이 LSA 엽서를 이웃들에게 무작정 복사해서 뿌려댄다(Flooding). 이웃들도 받으면 또 복사해서 넘긴다. 결과적으로 1초 만에 전국의 모든 라우터가 이 LSA 엽서를 똑같이 수집하게 된다.

2. 지도 완성: LSDB (Link State Database) 구축

모든 라우터는 수집한 100개의 LSA 엽서를 모아 커다란 스케치북에 동네 입체 지도를 완성한다.
이것을 **LSDB (토폴로지 테이블)**라고 부르며, 한 지역(Area) 안에 있는 100대의 라우터는 메모리 속에 100% 토시 하나 안 틀리고 완벽하게 동일한 LSDB 지도를 가지게 된다.

3. 나만의 지름길 파기: 다익스트라(SPF) 알고리즘 가동

지도를 완성했으면 라우터의 두뇌(CPU)가 미친 듯이 회전하기 시작한다.

지도는 똑같지만 라우터마다 자기 서 있는 '위치'가 다르다.
라우터는 자기 자신을 나무의 뿌리(Root)로 삼고, 다익스트라(Dijkstra) 수학 공식을 팽팽 돌려 가장 코스트(대역폭 점수)가 싼 길만 남기고 나머지 잔가지를 다 쳐내 버린다.
이렇게 예쁘게 깎아낸 소나무 모양의 뼈대를 **SPF Tree (Shortest Path First Tree)**라고 부른다. 라우터는 이 트리 정보 중 알맹이만 쏙 빼서 라우팅 테이블(RIB)에 최종 등재한다.

 ┌─────────────────────────────────────────────────────────────┐
 │                링크 상태 (OSPF) 라우터의 3단계 뇌 구조             │
 ├─────────────────────────────────────────────────────────────┤
 │                                                             │
 │   1. 이웃 정보 모음 (Neighbor Table)                           │
 │      "내 옆에 라우터 A, 라우터 B가 살고 있군. (Hello 교환)"          │
 │                                                             │
 │   2. 전체 지도 완성 (LSDB - Topology Table)                   │
 │      "아하, 전국에 라우터 50대가 이런 링크(선로)들로 거미줄처럼         │
 │       다 엮여 있구나! 지형도 100% 파악 완료!"                    │
 │                                                             │
 │   3. 내 입장의 최적 길 깎기 (Routing Table - RIB)                │
 │      "다익스트라 도끼질 퍽! 퍽! 잔가지 다 쳐냄.                     │
 │       결론: Z망 갈 땐 B로 주는 게 대역폭 점수(Cost) 제일 싸네!"      │
 └─────────────────────────────────────────────────────────────┘

4. 이벤트 기반 갱신 (Event-driven Update)의 위력

RIP처럼 30초마다 수첩 전체를 복사해서 뿌리는 미친 짓(대역폭 낭비)을 하지 않는다.
평소엔 조용히 있다가, 포크레인이 2번 선로를 끊어먹는 **이벤트(변화)**가 발생했을 때만, 즉시 해당 라우터가 "삐용! 2번 링크 죽음!"이라는 딱 한 줄짜리 LSA 변경분만 빛의 속도로 뿌린다.
이 소식을 들은 100대의 라우터는 즉시 SPF 공식을 0.1초 만에 다시 돌려서 우회로를 뚫어버린다. (수렴 시간이 기가 막히게 빠르다).

📢 섹션 요약 비유: 다익스트라 알고리즘은 거대한 미로(LSDB)에 갇혔을 때, 하늘에서 헬기를 타고 미로 전체 지도를 쫙 내려다본 다음, 형광펜으로 **"가장 코스트가 적게 드는 탈출구까지의 굵은 선(SPF 트리)"**을 단숨에 그어버리는 천재적인 일필휘지입니다.