[Router] SPF(Shortest Path First) 최단 경로 우선 알고리즘

 

SPF는 Dynamic Routing 프로토콜의 Link State방식에 OSPF가 사용하는 알고리즘입니다.

이번 시간에는 SPF에 대해서 자세하게 알아볼까요?

 

 

관련된 링크 = Dynamic Routing ( http://bosungs2y.tistory.com/entry/Router-Dynamic-Routing )

 

▶ SPF(Shortest Path First)란?

SPF는 Distance Vector알고리즘보다 복잡하기 때문에 메모리와 CPU에 부담을 더주지만 링크 변동에 따른 인식이 빠르고 라우팅 테이블
교환시 트래픽이 작은 장점이 있습니다.

 

▶ SPF 네트워크 구성도

쉽게 설명을 위해 예제의 네트워크를 통해 설명하겠습니다.

구성 >> 라우터 A는 Network 2에도 cost 0으로 접속되며, 라우터 B에는 cost 20으로 접속 된다.
             라우터 B는 Network 2와 Network 3에 cost 0으로 접속되며, 라우터 A에는 cost 20으로, 라우터 C에는 cost30으로 접속 된다.
             라우터 C는 Network 3과 Network 4에 cost 0으로 접속되고, 라우터 B에는 cost 30으로 접속된다.

 

A Router

* 용어 설명 *

- Destination = 목적지 네트워크

- Next Hop = 목적지 네트워크까지 가기위한 다음 라우터 경로

- Metric = 목적지 네트워크까지 거쳐가야 할 라우터 수

 

 

B Router 

 

 

 

C Router 

 

결론

1. Link Satae Database로부터 각 라우터는 자신을 Root하는 SPF(shortest path tree)를 만듬.
2. 자신을 Root로 하는 각각의 tree로 부터 routing table을 생성
3. SPF와 이 결과로 만들어진 routing table들을 보면서 목적지까지 경로를 구성