頁籤選單縮合
題 名 | A Valley-Free Shortest Path Algorithm and Its Application in Detecting Critical Links among Autonomous Systems |
---|---|
作 者 | Peng, Wei; Deng, Wenping; Liu, Yujing; Zhao, Feng; Hu, Xiaofeng; | 書刊名 | Journal of Internet Technology |
卷 期 | 15:2 2014.03[民103.03] |
頁 次 | 頁261-271 |
專 輯 | Special Issue on Integration of IoT with Future Internet |
分類號 | 312.76 |
關鍵詞 | Inter-domain routing; Shortest path; Algorithm; Routing policy; Critical link; |
語 文 | 英文(English) |
英文摘要 | 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. |
本系統中英文摘要資訊取自各篇刊載內容。