A Fast Algorithm for Inferring AS-Level Path of Internet Topology

Discovering the AS-level path between two end-points is valuable for a wide range of network research like network diagnosis, routing behaviour analysis and protocol optimization. Most existing techniques require direct access to the source, which is difficult for the uncooperative nature of the Internet. For most cases, the routing path between two ASs is the shortest policy path between them. The recently available AS-level connectivity information and AS relationship inference algorithms provide a way for inferring the shortest policy path between any two end-points. Thus it is feasible to determine the AS-level path between two end-points by inferring the shortest policy path between them. The time complexity of the existing algorithm for inferring AS-level path based on this method is O(n\+3), where n is the number of nodes in the graph. Based on the same method, an efficient algorithm for inferring AS-level path of Internet topology is proposed in this paper, which is grounded on the breadth first algorithm for calculating shortest path in undirected graph. The time complexity of the algorithm is O(nm), where n and m is the number of nodes and edges in the graph. Experimental results show that compared with the existing algorithm, this algorithm is much more fast and achieves comparable accuracy.