[OSPF] SPF(Shortest Path First) 알고리즘_Dijkstra algorithm

1. SPF 알고리즘 정의

 

최단 경로 알고리즘 (Shortest Path Algorithm, SPF)

  ㅇ 그래프 이론에서, 최단 경로를 찾는 그래프 알고리즘들을 총칭
     - 주로, 단일 출발지로부터 모든 정점까지의 최단 경로를 찾는 탐색 알고리즘

 

Dijkstra’s “Shortest Path First” Algorithm

■  Network topology와 모든 Node 밖의 link cost값을, 모든 Node(라우터)들이 알게 함.
 -위 “Link-state”정보를 Broadcast (flooding)함으로써 모든 라우터에게 전달함
 -모든 라우터들이 동일한 정보를 갖게 됨.


■ 각 노드를 source로 해서, 모든 노드로의 최단경로를 계산함.
 -각 노드(라우터)가 각자의 forwarding table을 갖게 됨.


■ 반복적 계산 방식 : k개의 destination에 대해 최단 경로를 얻으려면, 각 노드로의 경로의 cost 
값을 k번 반복 계산함.
 -한 번의 계산 당 하나의 목적지 node로의 최단 경로가 찾아지며,
 -K번의 계산을 마치면 k개의 목적지 node로의 최단경로가 모두 찾아지게 됨.

 

 

---

 

 

 

2.  SPF 알고리즘 실행 단계

 

OSPF(Open Shortest Path First) 프로토콜은 SPF(Shortest Path First) 알고리즘을 사용하여 최적의 경로를 결정하고 라우팅 테이블을 구축한다. 

1) 라우팅 테이블 초기화
SPF 알고리즘은 라우팅 테이블을 초기화하여 시작한다. 각 라우터는 자신의 라우팅 테이블을 설정하고, 최단 경로 계산을 위해 필요한 초기 매개변수를 준비한다.

2) 네트워크 링크 상태 확인
각 라우터는 자신의 인터페이스를 통해 이웃 라우터와의 링크 상태 정보를 주기적으로 교환한다. 이 정보에는 링크의 가용성, 대역폭, 지연 시간 등의 정보가 포함된다. 이 과정을 통해 각 라우터는 네트워크의 전체 링크 상태를 파악한다.

3) SPF 트리 생성 및 업데이트
라우터는 링크 상태 정보를 사용하여 SPF 트리를 생성하고 업데이트 한다 . SPF 트리는 네트워크의 모든 라우터 간의 최단 경로를 나타내는 구조이다. Dijkstra 알고리즘을 사용하여 각 라우터의 최단 경로를 계산하고, SPF 트리를 구성 한다 . 이 과정에서 각 라우터는 최단 경로를 지속적으로 업데이트하고 테이블에 반영 한다 .

!! For example.
가령, 라우터 A가 네트워크 링크 상태를 확인하여 B, C와의 연결성을 파악 한다 . 이 정보를 바탕으로 SPF 알고리즘이 실행되어 A에서 B와 C로의 최단 경로를 계산하고, 이를 라우팅 테이블에 반영 한다 .

---

 

 

 

3. SPF 알고리즘 예시

 

 

1) 자신을 Root(V1)로 하여 다른 목적지(V2,3,4,5)로 가는 최적의 경로를 찾는 알고리즘.

 

 

 

 

 

 

---

2) 자신을 Root로 하여 계산된 최적의 경로(V1, V2, V3, V4, V5)

 

 

 

 

 

 

 

이상으로 SPF 알고리즘에 대해서 설명을 마치겠습니다.

 

감사합니다.