一种计算因特网AS拓扑的最短路径的快速算法

最短路径是因特网AS(autonomous system)拓扑的一个重要特征,AS间的路由路径一般是AS之间的最短路径.因特网服务提供商之间复杂的商业关系导致AS之间存在复杂的路由关系,从而影响AS路由路径的选择,因此在计算AS拓扑中最短路径时需要考虑AS间的路由关系.提出了一种计算AS拓扑中最短路径的算法,算法基于无向图的宽度优先最短路径算法,时间复杂度为O(nm),这里n和m分别为拓扑图中节点和边的个数.通过实验发现,与现有的计算AS拓扑最短路径的时间复杂度为O(n3)的算法相比,该算法在实现同样精确度的前提下大幅缩短了计算时间.

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.