[네트워크] 라우팅 알고리즘 - 다익스트라

1. 컨트롤 플레인(Control Plane) vs 데이터 플레인(Data Plane)

네트워크 장비(라우터)의 역할은 크게 두 가지 영역으로 나뉩니다.

• 컨트롤 플레인 (두뇌): 경로를 결정하는 지능적인 영역입니다. 라우팅 알고리즘을 실행하여 "어디로 패킷을 보낼지" 결정하고, 그 결과물인 포워딩 테이블(Forwarding Table)을 생성합니다.
• 데이터 플레인 (일꾼): 실제로 패킷을 전달하는 영역입니다. 컨트롤 플레인이 만든 테이블을 참조하여, 들어오는 패킷의 헤더 정보를 보고 즉시 적절한 출력 인터페이스로 내보내는 포워딩(Forwarding)을 수행합니다.

2. 컨트롤 플레인의 구현 모델

① 라우터별 컨트롤 플레인 (Per-router Control Plane)

• 특징: 각 라우터가 독립적인 라우팅 알고리즘을 실행합니다.
• 동작: 라우터끼리 정보를 교환(수다)하여 각자 자신의 포워딩 테이블을 직접 계산하는 분산형(Distributed) 구조입니다.

② SDN 컨트롤 플레인 (Software-Defined Networking)

• 특징: 원격 컨트롤러(Remote Controller)라는 중앙 서버가 모든 결정을 내립니다.
• 동작: 컨트롤러가 전체 지도를 보고 테이블을 계산한 뒤, 각 라우터 내의 CA(Control Agent)에게 지침을 내립니다. 라우터는 스스로 계산하지 않고 시키는 대로만 움직이는 중앙 집중형(Centralized) 구조입니다.

3. 라우팅 프로토콜과 그래프 추상화

라우팅의 목표

송신지부터 수신지까지 "좋은(Good)" 경로를 찾는 것입니다. 여기서 '좋다'는 기준은 최소 비용(Least Cost), 최단 시간(Fastest), 최소 혼잡(Least Congested) 등을 의미합니다.

그래프 모델링 (G = (N, E))

알고리즘 적용을 위해 네트워크를 수학적으로 추상화합니다.

• N (Nodes): 라우터 집합
• E (Edges): 라우터 간 연결된 링크 집합
• 비용 (c(a,b)): 링크의 가중치. 대역폭에 반비례하거나 혼잡도에 비례하도록 운영자가 설정합니다.

4. 라우팅 알고리즘의 분류

분류 기준	Link State (LS)	Distance Vector (DV)
정보 범위	Global: 모든 라우터가 전체 지도를 가짐	Decentralized: 이웃의 정보만 가짐
핵심 알고리즘	다익스트라 (Dijkstra)	벨만-포드 (Bellman-Ford)
동작 방식	지도를 다 펼쳐놓고 최단 경로 계산	이웃이 준 거리 정보를 바탕으로 내 표 갱신
알고리즘 성격	그리디 (Greedy)	다이나믹 프로그래밍 (DP)

• 방향성: 두 알고리즘 모두 유방향 그래프(Directed Graph)에서 동작 가능합니다. (상/하향 대역폭 차이 반영 가능)

5. 다익스트라(Dijkstra) 알고리즘 심층 분석

주요 기호 (Notation)

• D(v): 출발지부터 목적지 v까지의 현재 최소 비용 추정치
• p(v): 최단 경로상에서 v 바로 직전 노드 (경로 추적용)
• N': 최단 경로가 완전히 확정된 노드들의 집합

노드 확정 순서 (N'에 들어가는 순서)

1. 초기에는 출발 노드(u)만 N'에 포함됩니다.
2. 이후 매 루프마다 N'에 포함되지 않은 노드 중 D(w)가 가장 작은 노드를 선택하여 N'에 추가합니다.
3. 즉, 출발지로부터 거리가 가까운 노드 순서대로 확정됩니다.

연산 복잡도

• 기본 구현: 노드 수 n에 대해 매번 최소값을 찾아야 하므로 약 (n-1) n 번의 연산이 필요하며, 이는 O(n^2)의 복잡도를 가집니다.
• 최적화: 우선순위 큐(Heap)를 사용하면 O(E \log V)로 줄어듭니다.