A novel router level topology discovery algorithm

Router level topology could be discovered from IP level topology based on alias resolution, while current alias resolution technique has low efficiency. In order to discover router level topology efficiently, a novel router level topology discovery algorithm was proposed, which has adopted the idea of alias filter. First, the characteristics of alias in IP addresses were explored theoretically, and three propositions were proposed based on the characteristics. Then an alias filter algorithm called AF and an alias relation verification algorithm called ARV were put forward. Finally, both algorithms were verified via the IP level topologies covering China, Japan, and Korea, which were discovered by Skitter of CAIDA. The results proved that the concept of alias filtering is very important and the algorithms proposed in this paper are valid and efficient, and the router level topology could be discovered efficiently.