네트워크 계층 기능 및 라우팅 알고리즘
- 네트워크 제어 평면을 구성하는 두 가지 알고리즘(차이점)
- 라우터별 제어(전통적인 방식)
- 각 라우터별 독립적으로 라우팅 알고리즘을 실행하고 자신이 포워딩 테이블에서 계산하여 스위칭함
- 각 라우터가 자율적으로 작동
- 논리적 중앙 집중형 제어 (SDN) 방식
- 중앙 컨트롤러가 모든 라우터의 포워딩 테이블을 계산하고 전달
- 중앙집중형, SDN에서 사용
- 차이점 : 제어 권한이 라우터에게 있는가, 중앙 컨트롤러에 있는가
- 목표
- 출발지 호스트부터 목적지 호스트까지 라우터의 네트워크를 통과하는 최소 비용 경로 (least-cost path)를 결정
- 중앙 집중형 (링크 상태) 라우팅 vs 분산형 (거리 벡터) 라우팅(차이점)
- 중앙 집중형
- 다익스트라 알고리즘
- 전체 정보를 중앙에서 수집
- 모든 노드가 전체 정보를 알고 있음
- 분산형
- 벨만 포드 알고리즘
- 각 라우터가 이웃 라우터와 정보 교환
- 각자 협력하여 계산
중앙 집중형 (링크 상태) 알고리즘
- 다익스트라 알고리즘
- D(v) = min (D(v), D(w) + c_w,v)
- LSA 메시지
- 이웃 라우터 정보
- 이웃라우터와 직접 연결된 링크의 상태 및 비용 정보
- 과정
- 라우터가 LSA 메시지 생성
- LSA는 네트워크의 모든 라우터로 플러딩
- 다른 다우터들이 전송한 LSA 메시지들을 기반으로, 각 라우터는 네트워크 전체 토폴로지를 구성
- 다익스트라 알고리즘을 통해 두 라우터 사이의 최소 비용 경로 계산
- 다익스트라 알고리즘 특징
- 중앙 집중형
- 모든 노드가 링크 비용을 알고 있음
- 하나의 노드에서 다른 모든 노드까지 최소 비용 경로를 계산
- 반복적 방법을 통해 최소 비용 경로 계산
- 시간 복잡도
- 기본 : O(n^2)
- 우선순위 큐를 힙 데이터 구조로 사용 : O(n log n)
- 경로 진동
- 라우팅 알고리즘이 자주 경로를 변경해서 네트워크가 안정되지 못하고 계속 경로가 변경되는 현상
거리 벡터 알고리즘 (벨만-포드)
- 옆에 있는 노드와만 통신
- D_x(y) = min_v{c_x,v + D_v(y)}
- 과정