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

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.