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

Alias filter algorithm in router level topology discovery

通过别名解析可以在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.