| 摘要: |
| 准确评估节点的重要性,是增强网络生存性的基础.由于域间路由系统路由策略的复杂性,已有的面向静态拓扑的节点重要性评估方法不能真实反映各个自治系统(autonomous systems,简称AS)在路由中的重要性.首次从动态路由的角度基于AS 之间的最优路径从路由上评估各个AS 的重要性,经过AS 的最优路径数量越多,它就越重要.提出了基于首选路由的AS 重要性评估方法,其时间复杂性为O(l×nm),它与面向静态拓扑的评估方法中最好的时间复杂性相同,并且能够更准确地描述节点的实际重要性.通过真实路由数据进行实验,与两种典型的面向静态拓扑的基于顶点度、强度中心性的评估方法对比,其结果表明,基于首选路由的评估方法可以有效发现AS 网络中连接较少但很重要的节点,并且评估的重要性与实际的重要性更吻合. |
| 关键词: 自治系统 网络生存性 首选路由 重要性评估 |
| DOI：10.3724/SP.J.1001.2012.04233 |
| 分类号: |
| 基金项目:国家自然科学基金(61103189, 61070199); 长江学者和创新团队发展计划(IRT1012); 湖南省自然科学基金(11JJ7003); |
|
| Technique of Evaluating AS Importance Based on Preferred Route |
|
LIU Hong-Jun, HU Xiao-Feng, DENG Wen-Ping, LU Xi-Cheng
|
|
College of Computer, National University of Defense Technology, Changsha 410073, China
|
| Abstract: |
| Evaluating the importance of node is valuable for improving the network survivability. Due to the complexity of inter-domain policy, the existing evaluating methods which are based on static topology can not reflect the real importance of the autonomous systems (ASes) in routing. This paper is the first study to evaluate the AS importance through the best paths between the ASes from the view of dynamic routing. The more the best paths passing through an AS, the more important it is. An evaluation method based on preferred route is proposed, the complexity of which is O(l×nm) and the evaluated importance is more accurate. The time complexity is the same as the best complexity of the evaluating methods based on static topology. To verify the validity, the preferred route method is compared with two representative methods based on static topology under real routing data, which are degree method and stress centrality method respectively. The result shows that the preferred route method can discover the nodes of importance but small connections efficiently. Moreover, the evaluated importance is closer to the real AS importance than the other two methods. |
| Key words: autonomous system network survivability preferred route importance evaluating |
