[네트워크] OSPF의 SPF(Shortest Path First) 일반적인 동작 원리

SPF 기본 동작 원리

link-state 라우팅 프로토콜에서 토폴로지안의 각각의 라우터는 다른 모든 라우터에 대한 연결 상태에 대한 정보를 알고 있다. OSPF는 LSAs(Link-State Advertisements), IS-IS는 LSP( Link-State Packets)를 통해서 이러한 정보를 교환하고, IS-IS와 OSPF 모두 SPF알고리즘을 수행하게된다.

라우터가 네트워크의 모든 라우터 그리고 링크의 정보를 알게되면 그들 사이의 가장 빠른 경로를 계산하기 위해 바로 DijkstraShortest Path First 알고리즘 (Edsger W. Dijkstra)을 실행한다.

아래와 같은 네트워가 있다고 가정하고 라우터 A 에서의 SPF가 실행되고 라우팅 테이블이 생성되는 과정을 설명한다.

네트워크의 라우팅 정보가 동기화된 후에는 아래와 같은 link-state 데이터베이스가 생성이 된다.

Router	{neighbor, cost} Pairs
A	{B,5} {C,10}
B	{A,5} {C,3} {D,8}
C	{A,10} {B,3} {D,4}
D	{B,8} {C,4}

- 라우터는 이러한 정보를 이용해서 SPF 알고리즘을 수행하게된다.

- SPF 계산중 각각의 라우터는 PATH list와 TENT list라는 두개의 리스트를 유지하게 된다. PATH list는 경로로 채택된 리스트이고 TENT list는 Tentative의 약자로 LSDB에서 하나씩 꺼내와 비교하기 위해 임시로 넣어두는 리스트라고 보면 되겠다.

- 각각의 리스트는 {router, distance, next-hop} 세개가 하나의 쌍을 이루게된다.

router - 목적지 라우터 ID, 여기선 A,B등 라우터 이름으로 예를 든다.
distance - 목적지까지 걸리는 거리(metric)
next-hop - 목적지까기 가기 위한 다음 라우터의 이름

각각의 라우터에서 실행되는 알고리즘은 다음과 같은 절차로 수행이 된다. 

Step 1.   PATH 리스트에 자기 자신에 대한 노드 self 를 추가한다. 이 노드는 SPF tree의 root가 된다.

Step 2. PATH 리스트에 추가된 노드의 이웃 리스트를 TENT 리스트에 추가한다. 이미 TENT 리스트에 노드가 존재할 경우엔 Cost가 크면 반영하지 않고 cost가 더 작을 경우 교체한다.

[참고] PATH 리스트에 있는 노드를 PATH node, TENT 리스트에 있는 노드를 TENT node라고 부른다.

Step 3. TENT 리스트에서 낮은 코스트에 해당하는 노드를 PATH 리스트로 이동한다. TENT 리스트에 노드가 없을때까지 Step 2부터 반복한다.

라우터 A에서 어떻게 동작하는지 실제로 동장하는 지 살펴보자.

Step 1. 먼자 SPF 트리의 루트로 자신의 노드를 PATH 리스트에 넣는다.

PATH List	TENT List
{A,0,0}	(empty)

Step 2. 조금 전 추가된 PATH 노드의 네이버 노드들을 검색해서 있으면 TENT 리스트에 넣는다. (이미 있을 경우 cost를 비교해서 낮으면 교체 높으면 버린다.)

PATH List	TENT List
{A,0,0}	{B,5,B}
	{C,10,C}

{B,5,B} and {C,10,C} 가 라우터 A의 네이년 노드이므로 TENT 리스트에 추가되었다.

Step 3.  TENT 리스트에서 낮은 cost의 노드를 PATH 리스트로 이동한다. TENT 리스트에 노드가 없다면 SPF가 종료된다.

PATH List	TENT List
{A,0,0}	{C,10,C}
{B,5,B}

{B,5,B} 의 cost가 {C,10,C} 보다 작아서 PATH 리스트로 이동되었다. 라우터 B 로 가기위해 라우터 C를 통한 경로는 B로 직접 가는 것보다 무조건 크다.

Step 4. Step 2를 반복한다. PATh 리스트의 노드의 이웃 노드를 검사해서 이웃노드까지의 경로정보를 TENT 리스트에 추가한다.

PATH List	TENT List
{A,0,0}	{C,10,C}
{B,5,B}	{C,8,B}
	{D,13,B}

{B, 5, B}의 이웃 노드인 {C,8,B} 와 {D,13,B}가 TENT 리스트로 추가되었다. ({C,10,C}노드는 {C,8,B}로 교체됨)

Step 5. TENT 리스트에서 낮은 코스트의 노드를 PATH 리스트로 이동한다.

PATH List	TENT List
{A,0,0}	{D,13,B}
{B,5,B}
{C,8,B}

{C,8,B} 이 PATH리스트로 이동됨.

Step 6. 조금 전 PATH 리스트로 이동안 노느의 이웃 노드를 구해서 같은 룰에 의해서 TENT 리스트에 추가함.

PATH List	TENT List
{A,0,0}	{D,13,B}
{B,5,B}	{D,12,B}
{C,8,B}

계산에 의해서 라우터 D로 가는 경로가 라우터 C를 경유하는 cost 12의 {D,12,B}로 교체가 된다.

Step 7. TENT 리스트의 노드를 검사해서 PATH 리스트로 이동한다.

PATH List	TENT List
{A,0,0}
{B,5,B}
{C,8,B}
{D,12,B}

TENT 리스트에 있는 마지막 노드 {D,12,B} 를 PATH 리스트로 이동한다.

Step 8. TENT 리스트에 노드가 없으므로 종료하고, PATH 리스트의 정보를 라우팅 테이블에 반영된다.

Node	Cost	Next Hop
A	0	Self
B	5	B (directly connected)
C	8	B
D	12	B

SPF 가 수행되고 난 후 예제 토폴로지는 아래와 같은 유효 경로를 가지는 토폴로지가 된다.

라우터 B에서 D로 가는 트래픽은 라우터 A의 트래픽이고, 라우터 A에서 C로 이동하는 트래픽은 발생하지 않는다는 걸 알 수 있다. 라우터 B가 다운되지 않는다면...

실제 SPF는 좀 더 복잡하지만 SPF를 이해하기에는 충분하다.



[참고] Cisco Press - Traffic Engineering with MPLS