Link-State 라우팅 프로토콜은 Best-Path를 선출하기 위하여 Dijkstra’s SPF 알고리즘을 사용한다. SPF 알고리즘은 네덜란드 과학자 에츠허르 다익스트라(Edsger Wybe Dijkstra)에 의해 고안된 알고리즘으로 그래프에서 하나의 Node를 기준으로 다른 모든 노드까지 최단거리를 구하기 위하여 만들어졌다.

  동일한 방식이기는 하지만, OSPF가 SPF 알고리즘을 사용하여 각각의 네트워크에 대해서 Best-Path를 선출하는 방법은 다음 장에서 학습하기로 하고, 여기서는SPF 알고리즘이 최단거리를 계산하는 기본 원리에 대하여 다음 토폴로지를 통해 알아보기로 하자.

  Node A ~ Node F 까지 총 6개의 Node가 있고, 각 Node들의 Link 정보들을 데이터베이스에 저장을 하였다. 그리고, Best-Path를 찾기 위해서는 각 Node에 대하여 가장 작은 Total Cost(총 거리)을 가진 경로를 계산하여야 하는데, 그림에서 ‘Best-Path’ 표를 보면 Node의 위치를 모르는 경우에는 Node 까지 Total Cost 값을 무한대로 설정해 놓은 것을 확인할 수 있다.

  자 이제 Node A에서 각 Node에 대한 Best-Path를 하나씩 구해 보도록 하겠다. 먼저, 자신의 Node에서 각 Node까지 최단거리를 계산하여야 하기 때문에 Node A를 가장 먼저 가지고 온다. 당연히 Node A에서 Node A까지의 거리는 ‘0’일 것이다.

  그리고, Node A의 Link정보를 기반으로 그림을 그리면 다음과 같이 그림이 그려질 수 있을 것이다.

  Node A의 Link 정보를 확인해 보면 Node B(Cost = 3), Node C(Cost = 1), Node D(Cost = 3)와 연결되어 있다. 그래서, Node A의 Link 정보를 기반으로 Node B, Node C, Node D 까지 TENT Path(임시 Best-Path)를 선출을 한다.

  다음으로 TENT Path 중에서 Best-Path가 될 수 있는 경로를 선출한다. Node B의 경우는 Cost가 ‘3’인데, 만일 Node C와 Node B 사이의 Cost가 ‘1’인 경우 Best-Path가 될 수 없다. Node D의 경우도 Cost가 ‘5’이기 때문에 Node B나 Node C를 통해서 갈 수 있는 다른 경로의 Cost가 낮은 경우 Best-Path가 될 수 없다. 이런 경우는 Best-Path로 선출되지 못하고 다른 경로와 비교를 위해 TENT Path에 남아 있게 된다.

  하지만, Node C는 Cost가 ‘1’로 가장 작은 Cost 값을 가지고 있기 때문에 Node B나 Node D를 통해서 가는 경로가 Best-Path가 될 수 없다. 그러므로, 지금 경로가 Node C에 대한 Best-Path로 선출된다.

  그리고 Node A와 Node C에 대해 Best-Path가 선출되었으니 데이터베이스에서 Node A와 Node C로 가는 경로는 다 삭제를 해도 될 것이다. 그런 경우 다음과 같이 데이터베이스의 양이 줄어들게 된다.

  다음으로 Node C에 대해 Best-Path를 선출하였으니 Node C의 Link 정보를 가져온다.

  Node C는 Node B, Node D, Node E와 연결이 되어 있다. 그 정보를 TENT Path에 넣어서 비교해 보니, Node B와 Node C는 TENT Path 내에서 Cost가 ‘3’으로 가장 값을 가지고 있다. 그러므로, Node D나  Node E를 통해 가는 다른 경로가 있다고 하더라도 현재 최단 Cost인 ‘3’보다 작을 수 없다. Node D도 마찬가지이다. 그러므로, 지금 경로가 Node B와 Node D에 대한 Best-Path로 선출된다.  하지만, Node E는 Node B나 Node D를 통하여 더 좋은 경로가 있을 수 있으므로 아직 Best-Path가 될 수 없다.

  그리고, Node B와 Node D에 대하여 Best-Path가 선출되었으니 데이터베이스에서 Node B와 Node D로 가는 Link를 삭제하면 다음과 같이 Link 정보가 3개 밖에 남지 않은 것을 확인할 수 있다.

  그리고, Best-Path가 선출된 Node B와 Node D의 Link 정보를 가져와야 하는데 Node B는 더이상 남아 있는 Link 정보가 없으니 끝이 난 것이고, Node D의 Link 정보를 기반으로 그림을 그리면 다음과 같다.

  Node D 아래에 Node F를 구성한 다음 계산해 보니 Node F까지 Cost가 ‘8’이 되었다. 이런 경우 Node E를 통하여 Node F로 가는 더 좋은 경로가 있을 수 있으므로 해당 경로는 Best-Path가 될 수 있다. 하지만, Node E는 TENT Path에서 가장 작은 경로를 가지고 있으므로 다른 경로를 통해 더 좋은 경로가 나올 수 없다. 그러므로, 현재의 경로가 Best-Path가 된다.

  다음으로 Node E에 대한 Best-Path가 선출되었으니 Node E로 가는 다른 Link를 지우고 Node E의 Link 정보를 기반으로 그림을 그리면 다음과 같다.

  마지막으로 Node F의 Link 정보를 가져와야 하는데 더이상 남은 Link 정보가 없다. 이렇게 데이터베이스에 있는 모든 Link 정보를 다 사용하고 나면 SPF 알고리즘을 통해 각 Node에 대한 Best-Path를 선출하는 과정이 끝나게 되는 것이다. 처음에는 어려울 수 있으나 빈 종이에 임의대로 토폴로지를 그리고 Cost 값을 적용한 후 SPF 알고리즘에 의해 하나씩 그려나가는 연습을 몇 번 해 보면 쉽게 계산이 되는 것을 확인할 수 있다.

1 COMMENT

Comments are closed.