348. 링크 상태 (Link State) 라우팅 알고리즘

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

본질: 링크 상태 라우팅 알고리즘은 라우팅과 경로 제어에서 핵심 동작과 제약을 이해하게 해 주는 개념이다.

가치: 링크 상태 라우팅 알고리즘을 이해하면 수렴 속도과 확장성 사이의 균형을 더 정확히 볼 수 있다.

판단 포인트: 설계 시에는 개념 자체보다 적용 조건, 운영 복잡도, 인접 기술과의 경계를 함께 판단해야 한다.

Ⅰ. 개요 및 필요성

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

[거리 벡터 라우팅 알고리즘]
    │
    ▼
[링크 상태 라우팅 알고리즘]
    │
    └──▶ [거리 벡터 라우팅 루프 방지]

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

Ⅱ. 아키텍처 및 핵심 원리

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 트리)"**을 단숨에 그어버리는 천재적인 일필휘지입니다.

Ⅲ. 비교 및 연결

링크 상태 라우팅 알고리즘을 볼 때는 앞뒤 개념과의 경계를 함께 봐야 전체 흐름이 선명해진다. 거리 벡터 라우팅 알고리즘이 기반 조건을 만든다면, 링크 상태 라우팅 알고리즘은 그 위에서 핵심 메커니즘을 구현하고, 거리 벡터 라우팅 루프 방지는 이를 더 확장된 적용 단계로 연결한다. 따라서 단일 정의보다 수렴 속도과 확장성에 어떤 차이를 만드는지 비교하는 것이 중요하다.

관점	선행 개념	현재 개념	확장 개념
초점	거리 벡터 라우팅 알고리즘의 기반 정리	링크 상태 라우팅 알고리즘의 핵심 동작	거리 벡터 라우팅 루프 방지의 확장 적용
자원 관점	기본 조건 확보	수렴 속도 최적화	규모와 범위 확대
판단 포인트	도입 가능성 확인	현재 메커니즘의 적합성 판단	운영·확장 전략 연결

📢 섹션 요약 비유: 링크 상태 라우팅 알고리즘은 비슷한 기술들 사이의 차선을 구분하는 분기점과 같다. 어디서 갈라지는지 알아야 헷갈리지 않는다.

Ⅳ. 실무 적용 및 기술사 판단

실무에서는 링크 상태 라우팅 알고리즘을 단독 개념으로 외우기보다 어떤 병목을 줄이기 위한 선택인지 먼저 따져야 한다. 특히 거리 벡터 라우팅 알고리즘 수준의 기본 대책으로 충분한지, 아니면 링크 상태 라우팅 알고리즘이 제공하는 메커니즘이 실제로 필요한지 구분해야 한다. 이후 확장 단계에서는 거리 벡터 라우팅 루프 방지와 같은 후속 기술, 자동화 체계, 표준 호환성까지 함께 검토해야 한다.

실무 체크리스트

현재 문제의 핵심이 수렴 속도 부족인지, 확장성 악화인지 먼저 분리한다.
링크 상태 라우팅 알고리즘가 추가하는 복잡도와 운영 이득이 균형을 이루는지 확인한다.
도입 후에는 인접 기술인 거리 벡터 라우팅 루프 방지와의 연계 방식을 함께 검증한다.

안티패턴

링크 상태 라우팅 알고리즘의 장점만 보고 트래픽 패턴이나 운영 비용을 무시한 채 과도 도입하는 설계
거리 벡터 라우팅 알고리즘와의 경계를 정리하지 않아 중복 투자나 정책 충돌을 만드는 설계
📢 섹션 요약 비유: 링크 상태 라우팅 알고리즘을 실제로 쓰는 판단은 도구 상자를 고르는 일과 비슷하다. 좋아 보이는 도구보다 지금 문제에 맞는 도구가 중요하다.

Ⅴ. 기대효과 및 결론

링크 상태 라우팅 알고리즘은 라우팅과 경로 제어를 이해할 때 핵심 축을 잡아 주는 개념이다. 올바르게 적용하면 수렴 속도 개선과 구조적 단순화에 기여하지만, 조건을 잘못 잡으면 오히려 복잡도와 운영 부담이 커질 수 있다. 앞으로는 거리 벡터 라우팅 루프 방지, 의도 기반 라우팅, 자동화 운영과의 결합을 통해 더 정교하게 발전할 가능성이 크다. 따라서 이 개념은 정의 자체보다 “언제 쓰고 언제 다른 방법으로 넘길 것인가”의 관점으로 기억하는 것이 좋다. 향후에는 의도 기반 라우팅 같은 자동화 흐름과 결합되어 더 정교한 형태로 확장될 가능성이 크다.

📢 섹션 요약 비유: 링크 상태 라우팅 알고리즘은 큰 흐름 속에서 기억해야 오래 남는다. 지금의 장점과 다음 확장 방향을 같이 보면 전체 그림이 선명해진다.

📌 관련 개념 맵

개념	연결 포인트
거리 벡터 라우팅 알고리즘	현재 개념이 등장하기 전에 갖춰야 할 배경이나 인접 선행 개념이다.
라우팅 테이블 (Routing Table)	패킷 전달 의사결정의 기준이 된다.
메트릭 (Metric)	최적 경로를 선택하는 비교 척도다.
거리 벡터 라우팅 루프 방지	현재 개념이 확장되거나 적용 단계로 이어질 때 자주 함께 언급된다.

📈 관련 키워드 및 발전 흐름도

[선행 개념: 거리 벡터 라우팅 알고리즘]
    │
    ▼
[현재 개념: 링크 상태 라우팅 알고리즘]
    │
    ├──▶ [확장 A: 거리 벡터 라우팅 루프 방지]
    └──▶ [확장 B: 의도 기반 라우팅]

링크 상태 라우팅 알고리즘는 거리 벡터 라우팅 알고리즘에서 출발해 현재 메커니즘을 정교화하고, 이후 거리 벡터 라우팅 루프 방지와 의도 기반 라우팅 같은 확장 흐름으로 이어진다고 보면 기억이 오래간다.

👶 어린이를 위한 3줄 비유 설명

여러 갈림길이 있는 미로에서 가장 좋은 길을 고르는 게임과 같아요.
이 개념은 길이 막히면 다른 길로 빨리 바꾸는 규칙도 알려줘요.
그래서 인터넷 길찾기가 덜 헤매고 더 똑똑해져요.