네트워크 프로그래밍 - Link State Routing

Link State Routing

위 그림에서 가장 정확한 정보는 각 노드에 direct하게 연결된 노드에 대한 정보이다.

 

Link State 정보는 direct하게 연결된 정보들을 말한다. A의 경우 B,C,D가 된다. 

이와 같은 Link State정보를 모든 노드들에 전달하여

위와 같은 그림을 각각의 모든 노드들이 가지고 있다. 

 

 

Dijkstra Algorithm

최단 경로를 구하기 위해 Dijkstra 알고리즘을 사용한다.

D를 root라고 가정하고 위 그림을 보자.

D로부터 갈 수 있는 노드들을 tentative list 후보목록에 넣는다. 

그 다음에는 tentative list중 cost가 가장 작은 것을 confirmed list로 변경한다. 

 

그리고 C로부터 갈 수 있는 후보를 찾는다. C에서 갈 수 있는 B, A에 대해 D에서 C를 거쳐 가는 cost를 계산하여 next를 C로 tentative list에 넣는다.

위 그림에서는 D에서 C를 거쳐 A, B에 가는 것에 대한 정보 B/5/C, A/12/C 를 tentative list에 추가한다.

B로 가는 두 가지 방법 B/11/B와 B/5/C 중 B/11/B는 cost가 더 높으므로 지우고 B/5/C를 confirmed list에 추가한다.

 

마찬가지 방법으로 B로부터 갈 수 있는 노드를 구하여 D에서 B를 거쳐 가는 cost와 next를 구하여 tentative list에 넣는다. 

위 그림에서는 A/10/C를 tentative list에 추가한다.

A로 가는 두 방법 A/12/C와 A/10/C 중 cost가 높은 A/12/C를 지우고, A/10/C를 confirmed list에 추가한다. 

 

이렇게 구한 confirmed list를 통해 routing table을 만든다. 

 

link state routing은 모든 노드에 연결에 대한 정보가 있는 지도를 각 노드가 가지고, 스스로가 root node가 되어 Dijkstra Algorithm을 실행하는 방법이다. 

 

Forming shortest path three for router A in a graph

A가 root가 되어 direct하게 연결된 노드들을 tentative list에 넣고, cost가 가장 작은 것을 confirmed list에 넣는다.

 

Iteration 1

cost가 작은 B를 confirmed list에 넣고 B의 direct node들을 tentative list에 넣는다. 

이때 root로부터 node까지의 누적 거리를 cost로 한다. 

 

Iteration 2

가장 cost가 적은 D를 confirmed list에 넣고, direct한 E node까지의 경로를 tentative list에 넣는데, A→D→E의 cost는 8로 기존의 B를 경유하는 경로보다 cost가 높으므로 삭제한다.

 

Iteration 3

가장 cost가 적은 E로의 경로를 confirmed list에 넣고, direct node F를 tentative list에 추가한다. 

 

Iteration 4

cost가 가장 적은 C로의 경로를 confirmed list에 넣고, direct noode G를 tentative list에 추가한다.

 

Iteration 5

cost가 적은 F로의 경로를 confirmed list에 넣고, direct node G를 tentative list에 추가하는데, 

이 경우 기존의 A→B→C→G 보다 A→B→E→F→G가 더 cost가 적으므로 F를 통한 G로의 경로를 confirmed list에 추가한다. 

 

이렇게 최단경로를 완성하고 이 정보를 이용하여 routing table을 작성한다. 

 

example

같은 과정으로 위 그림에서 Node A의 routing table을 구하면 다음과 같다. 

 

 

 

이전 포스팅에서 Distance vector에 대해서 알아보았고, 이번 포스팅에서 Link state에 대해서 알아보았다.