[컴퓨터 네트워크] 13. 라우팅 알고리즘: Link-State와 Distance-Vector

네트워크 그래프 예시
=====================

        2
  (u) -------> (v)
  |  \          |
 1|   \5        |3
  |    \        |
  v     v       v
 (x)---(w)---->(y)---->(z)
    3      1        2

c(u,v) = 2, c(u,x) = 1, c(u,w) = 5
c(v,y) = 3, c(x,w) = 3, c(w,y) = 1
c(y,z) = 2

라우팅 알고리즘 분류
======================

1. 정보 범위에 따라:
   - 전역적 (Global): 모든 노드의 정보를 알고 계산 --> Link-State
   - 분산적 (Decentralized): 이웃 정보만으로 반복 계산 --> Distance-Vector

2. 동작 방식에 따라:
   - 정적 (Static): 경로가 거의 변하지 않음
   - 동적 (Dynamic): 네트워크 변화에 따라 주기적으로 재계산

3. 부하 민감도에 따라:
   - 부하 민감 (Load-Sensitive): 링크 혼잡도를 비용에 반영
   - 부하 비민감 (Load-Insensitive): 현재 인터넷 라우팅 방식

다익스트라 알고리즘 (Dijkstra's Algorithm)
===========================================

초기화:
  N' = 출발 노드 u
  D(v) = c(u,v) (직접 연결된 이웃의 비용)
         무한대 (직접 연결되지 않은 노드)

반복:
  1. N'에 포함되지 않은 노드 중 D(w)가 최소인 노드 w를 선택
  2. w를 N'에 추가
  3. w의 이웃 v에 대해:
     D(v) = min(D(v), D(w) + c(w,v))
  4. 모든 노드가 N'에 포함될 때까지 반복

다익스트라 실행 과정 (출발: u)
===============================

단계 | N'        | D(v) | D(w) | D(x) | D(y) | D(z)
-----+-----------+------+------+------+------+------
  0  | u         |  2   |  5   |  1   |  inf |  inf
  1  | u,x       |  2   |  4   |  1   |  inf |  inf
  2  | u,x,v     |  2   |  4   |  1   |  5   |  inf
  3  | u,x,v,w   |  2   |  4   |  1   |  5   |  inf
  4  | u,x,v,w,y |  2   |  4   |  1   |  5   |  7
  5  | 모든 노드  |  2   |  4   |  1   |  5   |  7

최단 경로 트리:
  u -> v: 비용 2 (직접)
  u -> x: 비용 1 (직접)
  u -> w: 비용 4 (u -> x -> w)
  u -> y: 비용 5 (u -> v -> y 또는 u -> x -> w -> y)
  u -> z: 비용 7 (u -> ... -> y -> z)

LS 진동 문제 예시
==================

시점 1: A -> B 경로로 대부분의 트래픽이 흐름
  --> A -> B 링크 비용 증가

시점 2: 모든 노드가 A -> C -> D -> B 경로로 전환
  --> A -> C 링크 비용 증가

시점 3: 다시 A -> B 경로로 전환 (진동 반복)

해결책: 라우팅 업데이트 시점을 랜덤화

벨만-포드 방정식
=================

d(x, y) = min { c(x, v) + d(v, y) }
           v

여기서 v는 x의 모든 이웃 노드

의미: x에서 y까지의 최소 비용은
  = x에서 이웃 v까지의 비용 + v에서 y까지의 최소 비용
  이 값이 최소인 이웃 v를 통해 이동

DV 알고리즘 동작
==================

각 노드 x는 다음을 유지:
  - c(x,v): 이웃 v까지의 링크 비용
  - Dx: x의 거리 벡터 (모든 목적지까지의 추정 비용)
  - Dv: 각 이웃 v의 거리 벡터

동작:
  1. 초기화: 직접 연결된 이웃은 링크 비용, 나머지는 무한대
  2. 이웃으로부터 거리 벡터를 수신하면:
     Dx(y) = min { c(x,v) + Dv(y) } (모든 이웃 v에 대해)
  3. 자신의 거리 벡터가 변경되면 모든 이웃에게 전송
  4. 변화가 없을 때까지 반복

DV 알고리즘 실행 (3노드 예시)
===============================

토폴로지:
  x ---7--- y
  |       / |
  1     /   1
  |   2     |
  z --------+

초기 거리 벡터:
  Dx = [0, 7, 1]  (x->x, x->y, x->z)
  Dy = [7, 0, 1]  (y->x, y->y, y->z)
  Dz = [1, 1, 0]  (z->x, z->y, z->z)

1단계: 각 노드가 이웃의 DV를 수신하고 갱신

  노드 x 갱신:
    Dx(y) = min(c(x,y)+Dy(y), c(x,z)+Dz(y))
          = min(7+0, 1+1) = 2
    Dx(z) = min(c(x,y)+Dy(z), c(x,z)+Dz(z))
          = min(7+1, 1+0) = 1

  갱신 후 Dx = [0, 2, 1]  (x->y가 7에서 2로 변경)

2단계: 변경된 DV를 이웃에게 전파, 더 이상 변화 없으면 종료

Count-to-Infinity 예시
========================

토폴로지: x ---4--- y ---1--- z

초기 거리 벡터:
  Dy(x) = 4, Dz(x) = 5 (z -> y -> x)

링크 변경: c(x,y) = 4 --> 60

y 갱신: Dy(x) = min(60, 1+Dz(x)) = min(60, 1+5) = 6
  (z를 경유하면 6이라고 생각, 하지만 z도 y를 경유!)

z 갱신: Dz(x) = min(1+Dy(x)) = 1+6 = 7

y 갱신: Dy(x) = min(60, 1+7) = 8

z 갱신: Dz(x) = 1+8 = 9

... 계속 1씩 증가하면서 44번 반복 후에야 수렴!

Poisoned Reverse 동작
======================

z는 y를 통해 x에 도달 (z -> y -> x)

z가 y에게 알리는 정보:
  Dz(x) = 무한대  (실제로는 5이지만 y에게는 무한대로 알림)

이유: z가 y를 경유하므로, y가 z를 경유하는 루프 방지

링크 변경 c(x,y) = 60 발생 시:
  y 갱신: Dy(x) = min(60, 1+무한대) = 60
  y가 z에게 Dy(x)=60 전달
  z 갱신: Dz(x) = min(1+60) = 61

  --> 즉시 올바른 값으로 수렴!

Link-State vs Distance-Vector
================================

항목              | Link-State (LS)      | Distance-Vector (DV)
------------------+----------------------+----------------------
정보 범위         | 전체 네트워크 토폴로지 | 이웃의 거리 벡터만
메시지 복잡도     | O(N x E) 메시지       | 수렴까지 가변적
수렴 속도         | O(N^2) 빠름          | 느림 (루프 가능)
견고성            | 각 노드 독립 계산     | 오류가 전파될 수 있음
                  | (오류 영향 제한적)    | (잘못된 DV 전파)
메모리 요구       | 전체 토폴로지 저장    | 이웃 DV만 저장
실제 사용         | OSPF, IS-IS          | RIP, BGP (경로 벡터)

실제 프로토콜과 알고리즘
==========================

라우팅 프로토콜   | 기반 알고리즘  | 사용 범위
-----------------+--------------+------------------
RIP              | DV           | 소규모 AS 내부
OSPF             | LS           | 대규모 AS 내부
IS-IS            | LS           | ISP 네트워크
BGP              | 경로 벡터     | AS 간 (인터넷 전체)
EIGRP            | DV 개선      | Cisco 네트워크