An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network

Download PDF

Abstract

The shortest path computation is a building block of various network applications. Because the real-life networks are evolving as time passes by, Dynamic Shortest Path (DSP) problem has drawn lots of research attention in recent years. However, as DSP has many factors related to network topology, update pattern, and query characteristics, while the existing works only test their algorithms on very limited situations and comparisons, it is still hard to choose the most suitable method during implementation. To this end, we first identify the determinant dimensions and constraint dimensions of DSP problem and create a complete problem space to cover all possible situations. Then we evaluate the state-of-the-art DSP methods under the same implementation standard and test them systematically under a set of synthetic dynamic networks. Furthermore, we propose the dynamic degree to classify the dynamic environments and use throughput evaluate their dynamic performance. These results serve as the guidelines to find the best solution for each situation during system implementation, and also identify the research opportunities. Finally, we validate our findings in the real-life dynamic networks.