Abstract: 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.

Key words: topology discovery, alias relation, alias filter algorithm