라우팅 알고리즘 - 벨만포드 (Bellman-Ford), 다익스트라 (Dijkstra)

라우팅 알고리즘

동적 라우팅 프로토콜에서 목적지까지 최적경로를 산출하여 라우팅 테이블을 유지, 관리하기 위해 사용되며 두 분류로 나뉜다.

 

분산 라우팅 알고리즘

• 이웃 노드와 정보를 교환하여 반복적이고 분산된 방식으로 수행.
• 거리 벡터 알고리즘 (Bellman-Ford)

글로벌 라우팅 알고리즘

• 네트워크 전체에 대한 완벽한 정보가 필요.
• 링크 상태 알고리즘 (Dijkstra)

벨만포드 알고리즘 (Bellman-Ford Algorithm)

한 노드에서 다른 노드까지 최단거리를 구하기 위해 사용된다. 다익스트라 알고리즘과는 다르게 가중치가 음수인 경우에도 사용이 가능하다는 장점을 지니지만 시간 복잡도가 크기 때문에 가중치가 양수인 경우엔 사용될 이유가 없다.

 

네트워크에서는 간선의 비용이 음수가 될 수 없으나 라우팅 테이블의 크기가 적고 간단하기 때문에 소규모 네트워크에서 사용되는 거리 벡터 라우팅 프로토콜에 사용되는 알고리즘이다.

 

우선 시작 노드를 결정하여 시작 노드는 0으로, 다른 노드는 무한대와 가까운 높은 값으로 초기화한 후 현재 노드에서 인접한 노드를 탐색하며 값을 비교하고, 비교값이 낮다면 갱신한다.

 

R1의 인접 노드를 모두 확인했으니 링크가 연결된 다른 인접노드로 넘어가서 탐색을 시작한다. 순서는 무관하지만 우선 R2로 넘어가보자, R3로 가는 경로의 값이 5 > 2 + (-2) 이므로 최단경로를 갱신하고, R5로 향하는 경로값(2 + 4)을 갱신한다. 다음으로는 R3로 넘어가서 인접노드를 탐색하고, 다음으로는 R4로 넘어가서 인접노드를 탐색하게 된다.

다음으로 시작 노드를 R2로 바꿔서 또 같은 과정을 반복하고, 인접 노드 탐색이 끝나면 다시 시작 노드를 R3로 바꿔가며 모든 노드의 탐색이 완료될 때까지 이 과정을 반복한다, 그래서 R1의 입장에서 네트워크를 바라보았을 때, R5 방향으로 가려면 R2를 거친다는 정보와 cost가 6이라는 정보만 인지할 뿐, 네트워크 구성이 어떻게 되어있는지를 파악할 수 없다. 이렇듯 각 노드는 이웃이 주는 정보들을 계산하고 이웃에게 계산 결과를 알린다는 점에서 분산적이고, 모든 과정이 완료되어 더이상 정보를 교환하지 않을 때까지 반복된다는 점에서 반복적이며, 모든 노드가 톱니바퀴처럼 동작할 필요가 없다는 점에서 비동기적인 특성을 지니지만 여기서 이상한 점을 하나 찾을 수 있다. 경로값이 음수인 R2, R3의 링크를 보자.

 

R2, R3의 경로값은 음수값인데 이건 마치 어떤 톨게이트에서 고객 감사 행사로 100원을 받는 대신에 100원을 준다고 하는것과 같다. 톨게이트에서 나오자마자 다시 돌아가서 반복적으로 이 돈을 받을 수 있다면 무한히 돌아서 창조경제가 가능해진다.

이러한 사이클은 네트워크에서 치명적인 루핑이 발생하게 되고 최저 비용 거리를 구할 수 없게 된다. 최단 경로에서는 같은 노드를 두번 지날 일이 없기 때문에 거치는 노드의 수를 V라고 하면 (V-1)번 까지 반복하여 경로값을 확정했음에도 불구하고 최저비용이 갱신될 수 있을 때 음수 사이클이 있다고 판단할 수 있게 된다.

다익스트라 알고리즘 (Dijkstra Algorithm)

음의 가중치가 없는 그래프를 가정하고 모든 노드까지의 최단거리를 구하는 알고리즘이다. 인공위성 GPS 소프트웨어 등에서 자주 사용되는만큼 라우팅 프로토콜에서도 아주 중요하다.

다익스트라 알고리즘에서 최단 거리는 여러 개의 최단 거리로 구성된다, 하나의 최단 거리를 구할 때, 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징을 가진다. 이러한 점에서 벨만포드 알고리즘과 동작방식에 차이가 있다.

 

R1을 출발지로 가정하면 다른 모든 노드의 경로값은 무한대로 초기화하고, 인접노드의 경로값을 갱신한다. 이후에 R2의 경로값이 가장 낮으므로 우선 방문한다.

 

R2를 방문하고 인접노드의 경로값을 계산한다. R5, R6로 가는 경로값을 갱신하고, 방문하지 않은 노드 중 가중치가 가장 적은 노드는 R3이므로 R3를 방문하고 가중치를 비교한다. 이 경우 기존의 경로값보다 작은 경로값이 없기에 갱신되지 않는다.

 

다음으로 가중치가 적은 R5를 방문하고, R7의 경로값을 갱신한다. 이후 같은 과정을 반복하며 테이블에서 가중치가 적은 노드들을 차례로 모두 방문하게 되면 갱신이 끝나게 된다.

여기서 만약 목적지가 R7이라고 가정한다면 우선 R7과 연결된 R5로 가야하고, R5로 가는 경로는 가중치를 기반으로 R2를 경유해야 한다는 것을 파악할 수 있다. R1의 입장에서 모든 노드를 방문하였으니 전체 구성이 어떻게 되어있는지를 파악할 수 있게 되며 최단경로의 조합으로 목적지를 찾을 수 있게 된다.

 

가중치가 음수일 때 차이점

출발지가 R1이고 목적지가 R4라고 가정한다면 R3을 경유하는것이 더 좋다. 다만 다익스트라 알고리즘은 기본적으로 탐욕 알고리즘 (Greedy) 방식이므로 R3을 경유하여 비용이 감소하는 경우를 고려하지 못한다

 

다익스트라 알고리즘은 R2에서 R3로 갈지, R4로 갈지 판단할 때 음수가 없다고 가정하면 다익스트라 알고리즘의 Greedy 한 탐색방식이 좋은 결과를 가져올 수 있으나 음수가 있을 경우에는 되려 손해를 보게 된다.

반면 벨만포드 알고리즘의 경우에는 R3가 R2에게 가중치가 -200이라는 것을 알려줄 수 있기 때문에 자신을 경유하는 경로를 알려줄 수 있다. 물론 네트워크에서 회선비용이 음수가 될 일은 없다.

 

https://daengsik.tistory.com/45