路由器级拓扑发现中的别名过滤算法  

Alias filter algorithm in router level topology discovery

作　　者：赵洪华[1] 白华利[1] 陈鸣[1] 魏镇韩[1] 

机构地区：[1]解放军理工大学指挥自动化学院,江苏南京210007

出　　处：《西安电子科技大学学报》2009年第1期177-182,188,共7页Journal of Xidian University

基　　金：国家自然科学基金重大研究计划资助(90304016);国家863计划资助(2007AA01Z418)

摘　　要：通过别名解析可以在IP级拓扑的基础上获得路由器级拓扑.为了提高路由器级拓扑发现的效率,首先根据网络的结构特征归纳了IP级拓扑中不存在别名关系的条件,提出了处理别名关系的3条定理.其次在此基础上提出了别名过滤的思想并设计了别名过滤算法,通过哈希技术在IP级拓扑中排除不可能存在别名的情况,找出IP级拓扑中所有可能具有别名关系的情况.最后用CAIDA项目中的中日韩3国因特网IP级拓扑数据对别名过滤算法进行了验证分析,结果表明别名过滤算法能够有效减少别名解析的数量,提高路由器级拓扑发现的效率.Router level topology could be discovered from IP level topology based on alias resolution. In order to improve the efficiency of the router level topology discovery algorithm, the instances where there are alias relations are summarized. First, the conditions where there are not alias relations are concluded based on the characteristics of the network structure, and three theorems are brought forward when dealing with alias relations. Then, an alias filer algorithm called AF（Alias Filter） is put forward based on the instances and theorems, which could be used to find all of the conditions of alias relation possible by the Hash technique. Finally, the AF algorithm is verified via the IP level topologies from the Internet covering China, Japan, and Korea, which were discovered by Skitter of CAIDA. The results prove that the algorithm of AF could reduce IP addresses of alias resolution and improve the efficiency of router level topology discovery greatly.

关 键 词：拓扑发现 别名关系 别名过滤算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]