1. 최단 경로 알고리즘 (Shortest Path Algorithm)
ㅇ 그래프 이론에서, 최단 경로를 찾는 그래프 알고리즘
- 주로, 단일 출발지로부터 모든 정점까지의 최단 경로를 차례대로 찾는 탐색 알고리즘
2. [라우팅] 링크상태 라우팅 알고리즘 (Link State Routing Algorithm) 이란?
ㅇ 최소 비용 기준 알고리즘 임
- 링크 상태 데이터베이스를 사용하여,
- 목적지까지의 여러 가능한 경로들 중에서,
- 각 링크 비용 합에 기반하여,
- 최소의 경로 비용을 계산하는 라우팅 알고리즘
3. [라우팅] 링크상태 라우팅 알고리즘 주요 특징
ㅇ 전체 네트워크에 대한 토폴로지와 관련된 모든 정보로써의, LSD(Link State Database)를
- 각각의 라우터가 완벽히 갖고 있게됨.
. 이 LSD를 통해 SPF 트리를 만들고,
. 이를 토대로 최적 경로에 대한 라우팅 테이블을 구축하게 됨
ㅇ 네트워크 토폴로지 및 모든 링크 비용이 알려져 있고, 이들 값이 입력으로 사용됨
- 이에 참여하는 모든 라우터는 항상 전체 네트워크에 대한 맵(지도,그림 등)을 그리고,
- 이를 토대로 최적의 경로를 계산하는 방식을 취함
- 전체 지도는 점차 전 라우터에서 동일하게 그려지도록 빠르게 수렴됨
ㅇ 어떤 링크의 변화가 있는 경우 만 정보를 전달하는 방식을 취함
- 따라서, 라우팅 정보의 교환에 따른 부하는 작은 편임
ㅇ Link State(링크 상태)에 기반하는 최적의 경로 선택을 위한 알고리즘
- 이는 OSPF 등에 적용되어 사용됨
4. [라우팅] 링크상태 알고리즘 입력,출력,변수
※ 임의 노드부터 모든 가능한 목적지까지 최소비용 경로를 계산함
ㅇ 입력 : 연결 가중치 그래프 토폴로지 (전체 노드에 대한 맵)
ㅇ 출력 : L(z) (a에서 z까지 최단 경로 길이)
ㅇ 변수
- D(v) : 출발 노드(a)부터 목적지 노드(v)까지 현재까지의 경로비용
- P(v) : 출발 노드(a)부터 목적지 노드(v)까지 현재 계산에서 이전 노드 (v의 이웃)
- N : 노드의 집합 (링크상태 알고리즘에 의해 현재까지 편입된 노드들의 집합)
ㅇ ... (작성중) ...
5. [라우팅] Link State Intradomain Protocol에 속하는 라우팅 프로토콜의 예
ㅇ 라우팅 프로토콜 : 운반용 프로토콜들 (Routed Protocol)
- OSPF : IP
- DECnet Phase V
- IS-IS, Integrated IS-IS : IP, CLNP
- NLSP : (IPX에 대한 IS-IS 버젼)
- PNNI : ATM