Open Access Open Access  Restricted Access Subscription Access

A Valley-Free Shortest Path Algorithm and Its Application in Detecting Critical Links among Autonomous Systems

Wei Peng,
Wen-Ping Deng,
Yu-Jing Liu,
Feng Zhao,
Xiao-Feng Hu,

Abstract


The no-valley and prefer-customer policies are two important routing policies to guarantee the safety and robustness of the inter-domain routing system. Given an AS (Autonomous System) topology, the calculation of shortest paths must consider the two routing policies concurrently. In this paper, we propose a valley-free shortest path algorithm using the classic Dijkstra's algorithm framework. The algorithm finds shortest policy paths from other nodes to a specified destination in order to accommodate the routing policies. It is further applied in the problem of detecting critical AS links. A genetic algorithm is designed to find the optimal link set. Using real topology data sets from CAIDA, we evaluate the performance of the proposed algorithms. It turns out that although the routing policies give rise to the complexity in calculating, the time complexity of the algorithm is approximate to the classic algorithm. Additionally, we found that the differences of shortest path lengths with/without the policy constraints are decreasing with the evolution of the Internet. On detecting critical AS links, the genetic algorithm finds critical link sets for AS topologies of four countries. The results have revealed the different robustness of AS topologies for different countries.

Keywords


Inter-domain routing; Shortest path; Algorithm; Routing policy; Critical link

Citation Format:
Wei Peng, Wen-Ping Deng, Yu-Jing Liu, Feng Zhao, Xiao-Feng Hu, "A Valley-Free Shortest Path Algorithm and Its Application in Detecting Critical Links among Autonomous Systems," Journal of Internet Technology, vol. 15, no. 2 , pp. 261-271, Mar. 2014.

Full Text:

PDF

Refbacks

  • There are currently no refbacks.





Published by Executive Committee, Taiwan Academic Network, Ministry of Education, Taipei, Taiwan, R.O.C
JIT Editorial Office, Office of Library and Information Services, National Dong Hwa University
No. 1, Sec. 2, Da Hsueh Rd., Shoufeng, Hualien 974301, Taiwan, R.O.C.
Tel: +886-3-931-7314  E-mail: jit.editorial@gmail.com