Improving the Efficiency of Network Topology Discovery

As wireless and mobile networks are getting more of a commonplace, the discovery and management of dynamic networks has become a serious issue.. Since the topology of wireless and mobile networks always keeps changing, the key issue of topology discovery is how to effectively and efficiently perform the discovery task with minimal impact to normal network traffic. In this paper we analyze the efficiency of some current topology discovery methods used both in wired and wireless networks and show that they are not very efficient. We also analyze the main reason and present a new method called BacktraceTree to improve efficiency of topology discovery. The BacktraceTree first backtraces the topology tree by probing the destination nodes which give response and can find most topology nodes and links, and then it discovers the remainder topology by analyzing the known topology features and probing the unresponding destination nodes. We describe and analyze the BacktraceTree algorithm and compare it with some major current topology discovery methods. Our evaluation shows that BacktraceTree can reduce almost 70% measurement load while maintaining the coverage of router interfaces above 95%. The BacktraceTree algorithm can dramatically improve topology discovery and can thus meet the requirement for fast topology discovery in wireless and mobile networks.