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

 

1. 개요

라우팅 프로토콜은 크게 유니캐스트 방식의 라우팅 프로토콜과 멀티캐스트 방식의 라우팅 프로토콜 등 두 가지로 나눌 수 있다. 유니캐스트 방식의 라우팅 프로토콜에는 RIP, OSPF, BGP 등의 프로토콜이 있고, 멀티캐스트 방식의 라우팅 프로토콜에는 MOSPF, DVMRP, PIM, CBT 등의 프로토콜이 있다. 그림 1은 유니캐스트 방식의 라우팅 프로토콜의 종류를 나타내고 있다.

 

그림 1). Unicast routing protocols

1.1. Intradomain 방식의 라우팅 프로토콜

Intradomain 프로토콜 방식은 AS(Autonomous System) 내에서 이루어지는 라우팅 방식을 말한다. 여기서 AS는 학교 또는 기업 전산망 등과 같은 도메인이라 보면 되겠다. Intradomain 방식에는 크게 두 가지 방식이 있는데 distance vector 라우팅과 link state 라우팅이 있다.

그림 2의 distance vector 방식은 이름에서 의미하듯이 각 노드가 모든 노드로 가기위한 최단거리 벡터를 갖고 있다. 그래서 각 노드의 테이블은 최종목적지로 가기위한 패킷의 다음 목적지를 알려주면서 라우팅을 처리한다. 예를 들어 쉽게 설명하면 각 노드들은 도시가 될 수 있고, 노드들을 잇는 라인은 도시들 간의 도로가 된다. 그리하여 각 노드들에 있는 테이블은 관광객을 다른 도시로 가기 위한 최단거리를 알려주는 것이라 볼 수 있다.

 

그림 2). Distance vector routing tables

그림 3과 같은 link state routing 방식에서는 도메인 내에 있는 각 노드들이 노드와 링크 목록, cost, 링크 상태 등 도메인 전체 토폴로지의 정보를 가지고 라우팅 테이블을 생성하는 데, 이때 사용하는 알고리즘이 다익스트라 알고리즘이다. 초기에는 어떠한 노드도 네트워크 상에 변화가 있을 때까지는 토폴로지에 대한 정보를 알지 못하는 것이 특징이며 자세한 설명은 1.2절에서 하겠다.

 

그림 3). Link state routing

1.2. Dijkstra 알고리즘

다익스트라 알고리즘은 특정 시작점에서 각 목적지까지 이르는 최단 경로를 구하는 알고리즘이다. 이 알고리즘은 각 정점에 이르는 최단 경로를 시작점의 주변에서부터 하나씩 확장지어가면서 서서히 범위를 넓힌 후 최종적으로 모든 정점에 이르는 최단 경로를 구하는 것이다. 이 알고리즘의 순서는 다음과 같다.

① 시작점에 연결되어 있는 정점사이의 거리를 구해서 그 중 최소값을 갖는 정점의 노드를 최단 거리의 노드로 확정지으며 표시한다.

② 시작점에 연결되어 있는 정점들과 연결되어 있는 노드 중 또 다른 정점까지의 거리를 구하고, 계산한 거리 중 최소값을 갖는 정점을 최단 거리의 노드로 확정지으며 표시한다.

③ ②와 같은 과정을 모든 정점에 표시할 때까지 반복하면, 각 정점에서 얻을 수 있는 값이 시작점에서의 최단거리를 뜻하게 된다.

그림 4는 다익스트라 알고리즘을 설명하기 위한 예제를 위해 설정한 토폴로지이다. 하늘색의 원은 노드를 나타내고, 노드 간의 연결된 선은 각 노드 간에 거리를 말한다.

 

그림 4). 전체 토폴로지

다익스트라 알고리즘을 이용하여 a를 시작점으로 하는 각 노드까지의 최단 거리를 검색하는 예를 그림 5를 통해 살펴보겠다. 그림 5에서 원은 각 노드를 나타내고 원 안에 숫자는 노드 a로부터 떨어진 거리를 나타낸 것이다. 그림 5(a)에서 노드 a는 시작점이기에 0으로 시작하며 노드 a로부터 가장 가까운 1만큼 떨어져 있는 노드 b를 최단경로로 확정한다. 이후에 그림 5(b)에서와 같이 노드 a로부터 노드 b 외에 가장 가까운 거리에 있으며 2만큼 떨어져 있는 노드 d를 확정짓고, 그림 5(c)에서와 같이 노드 a로부터 노드 b, d 외에 가장 가까운 거리에 있으며 3만큼 떨어져 있는 노드 e를 최단거리로 확정짓는다. 다음은 그림 5(d)에서와 같이 노드 b, d, e 외에 가장 가까운 거리에 있으며 노드 a로부터 4만큼 떨어져있는 노드 f를 최단 경로로 확정짓는다. 노드 f로 가는 경로 중 노드 e를 거치지 않고 가는 a-b-f 경로는 a-b-e-f보다 거리가 1만큼 더 길기에 a-b-e-f 경로를 최단경로로 선택하게 된다. 그 후, 그림 5(e)에서와 같이 노드 c까지의 최단 경로도 노드 a로부터 거리가 7만큼 떨어진 a-c 경로보다는 노드 a로부터 거리가 6만큼 떨어진 a-b-e-f-c 경로를 최단거리로 확정짓는다. 다음으로는 그림 5(f)와 같이 노드 g까지 가는 경로인 a-d-g를 최단 경로로 확정짓고, 마지막으로 그림 5(g)에서와 같이 노드 a로부터 거리가 10만큼 떨어진 a-b-e-f-h 경로가 아닌 거리가 9만큼 떨어진 a-f-g-h 경로를 선택하면서 모든 노드로 향하는 최단 거리 검색은 완료된다.

그림 5). 다익스트라 알고리즘을 이용한 모든 노드로의 최단거리 검색 (a) ~ (g)

(a)	(b)	(c)
(d)	(e)	(f)
(g)