네트워크 토폴로지의 일부분에 변화가 생겼을 때, 효율적으로 최단경로를 설정 할 수 있는 대표적인 알고리즘으로 DSPT(Dynamic Shortest Path Tree)가 있다. 그러나 링크 비용이 증가하는 경우 DSPT 증가 알고리즘은 잘못된 최단경로를 계산한다. 따라서 본 논문에서는 DSPT 증가 알고리즘을 개선하여 신뢰성 있는 최단경로를 계산하는 P-DSPT(Precise-Dynamic Shortest Path Tree) 알고리즘과 RDSP(Reliable Dynamic Shortest Path) 알고리즘을 제안한다. 제안된 알고리즘의 성능을 평가하기 위해서 DSPT, 다익스트라 알고리즘 등과 성능을 비교하였으며, 최대 17%의 성능 향상이 있었다.
DSPT algorithm is well known for searching altered SPT efficiently as a cost of link is changed. But DSPT algorithm is wrong for some cases. So we will show this with an example, and propose P-DSPT(Precise-Dynamic Shortest Path Tree) and RDSP(Reliable Dynamic Shortest Path) that is a new DSPT algorithm. The result of an evaluation shows that overall performance of the proposed algorithm is improved a maximum of 17% compared with DSPT and well-known Dijkstra algorithm.
