1) Per-Router Control (전통적인 라우팅 알고리즘)
Routing Algorithm Classification (라우팅 알고리즘 분류)
Link State Routing Algorithm: 전체 네트워크의 링크 상태를 파악하여 경로를 결정. 대표적인 예는 Dijkstra's algorithm (다익스트라 알고리즘).
Distance Vector Algorithm: 각 라우터가 주변 라우터와의 거리 정보를 기반으로 경로를 계산. 예로는 Bellman-Ford algorithm (벨만-포드 알고리즘)이 있음.
Hierarchical Routing: 대규모 네트워크를 여러 영역으로 나누어 관리하는 방식.
Routing Protocols (라우팅 프로토콜)
RIP, OSPF (IGP; Interior Gateway Protocol): 내부 네트워크 라우팅을 위해 사용.
BGP (EGP; Exterior Gateway Protocol): 서로 다른 네트워크 사이의 라우팅에 사용.
Data Plane (데이터 평면)과 Control Plane (제어 평면)
FIB (Forwarding Information Base): 데이터 평면에서 패킷을 적절한 출력 포트로 전송.
RIB (Routing Information Base): 제어 평면에서 소스에서 목적지까지의 경로를 결정.
Per-router Control Plane (라우터별 제어 평면)
각 라우터에는 독립적으로 라우팅 알고리즘 구성 요소가 있으며, 이들은 제어 평면에서 서로 상호 작용하여 포워딩 테이블을 계산.
2) Logically Centralized Control: SDN Controllers (논리적 중앙 집중식 제어: SDN 컨트롤러)
OpenFlow Controllers
SDN (Software-Defined Networking) 환경에서 네트워크를 중앙에서 효율적으로 제어할 수 있는 컨트롤러.
Traditional Routing Algorithm (전통적인 라우팅 알고리즘)
Routing Algorithms (라우팅 알고리즘)
라우터 간에 교환되는 메시지의 형식과 순서를 정의하고, 경로 선택 알고리즘을 포함.
목표: 송신 호스트에서 수신 호스트까지 좋은 경로(최소 비용, 가장 빠른, 최소 혼잡 등)를 결정.
Routing Algorithm Classification (라우팅 알고리즘 분류)
Global vs. Decentralized: 전체 네트워크 구조를 알고 있는지 여부에 따라 분류.
Static vs. Dynamic: 경로가 시간에 따라 얼마나 자주 변경되는지에 따라 분류.
Load-sensitive vs. Load-insensitive: 링크 비용이 현재의 혼잡도를 반영하는지 여부에 따라 분류.
Problem of Dijkstra's Algorithm
네트워크 상황에 따라 경로가 반복적으로 변할 수 있으며, 이로 인해 네트워크 성능 저하가 발생할 수 있음.
Distance Vector (DV) Algorithm
Bellman-Ford Equation
최소 비용 경로 계산을 위한 주요 방정식.
DV 알고리즘은 라우터가 직접 연결된 링크만 정확하게 알고 있음.
Count to Infinity Problem
나쁜 뉴스(예: 링크 비용 증가)가 천천히 퍼져서 라우팅 루프 발생 가능.
이를 방지하기 위해 'Split Horizon'과 'Poisoned Reverse' 기법이 사용됨.
LS (Link-State) 라우팅 대비 DV (Distance-Vector) 라우팅
메시지 교환 방식: LS는 전체 네트워크에 걸쳐 작은 메시지를 브로드캐스트하는 반면, DV는 이웃 라우터들 사이에서만 큰 메시지를 교환함.
네트워크 인식 능력: LS는 전체 네트워크의 상태를 인식하는 반면, DV는 오직 국소적인 정보만을 인식함.
경로 계산 방식: LS는 일반적으로 보다 정확하고 효율적인 경로를 계산하지만, 더 많은 연산 자원을 요구함. DV는 계산이 간단하고 자원 사용이 적지만, 때때로 비효율적인 경로를 계산할 수 있음.
동적 반응성: LS는 네트워크 변화에 빠르게 반응하지만, DV는 정보 전파의 지연으로 인해 느린 반응을 보일 수 있음.
(추가 조사)
Link-State (LS) 라우팅
메시지 전송: LS 라우팅에서는 각 라우터가 자신의 직접 연결된 링크의 상태(비용, 속도 등) 정보를 전체 네트워크에 브로드캐스트합니다. 이 정보는 작은 메시지들로 구성되어 전송됩니다.
전체 네트워크 인식: 각 라우터는 전체 네트워크의 링크 상태 정보를 수집하여 로컬 데이터베이스에 저장합니다. 이를 통해 네트워크의 전체 구조를 파악할 수 있습니다.
경로 계산: Dijkstra 알고리즘을 사용하여 소스 라우터로부터 네트워크 내의 모든 다른 라우터까지의 최소 비용 경로를 계산합니다.
동적 반응성: 네트워크 상태 변화에 신속하게 반응하여 라우팅 정보를 업데이트합니다.
복잡도와 부하: 라우터가 많은 정보를 처리해야 하므로 연산 복잡도가 높고, 네트워크에 부하를 줄 수 있습니다.
Distance-Vector (DV) 라우팅
메시지 전송: DV 라우팅에서는 각 라우터가 자신의 이웃 라우터에게만 자신의 최소 비용 추정치를 전송합니다. 이 정보는 일반적으로 더 크고, 전체 네트워크에 걸쳐 전송되지 않습니다.
국소적 인식: 라우터는 오직 직접 연결된 이웃 라우터에 대한 정보만을 알고 있으며, 이웃으로부터 수신한 정보를 통해 전체 네트워크에 대한 추정을 합니다.
경로 계산: Bellman-Ford 알고리즘을 사용하여 최소 비용 경로를 계산합니다. 이 과정은 이웃 라우터 간의 정보 교환을 기반으로 합니다.
반복적인 업데이트: 네트워크 상태의 변화에 따라 라우터들은 지속적으로 정보를 교환하며 라우팅 테이블을 업데이트합니다.
문제점: "Count to Infinity" 문제와 같은 문제가 발생할 수 있습니다. 이는 라우팅 정보의 느린 전파로 인해 발생하며, 네트워크의 불안정성을 초래할 수 있습니다.
LS vs DV
메시지 교환: LS는 전체 네트워크에 걸쳐 작은 메시지를 브로드캐스트합니다. 반면, DV는 이웃 라우터 간에만 큰 메시지를 교환합니다.
네트워크 인식: LS는 네트워크의 전체적인 상태를 인식하지만, DV는 오직 국소적인 정보만을 인식합니다.
경로 계산: LS는 일반적으로 보다 정확하고 효율적인 경로를 계산하지만, 더 많은 연산 자원을 요구합니다. DV는 간단하고 자원 사용이 적지만, 때때로 비효율적인 경로를 계산할 수 있습니다.
동적 반응성: LS는 네트워크 변화에 빠르게 반응하지만, DV는 정보 전파의 지연으로 인해 느린 반응을 보일 수 있습니다.
