Network Discovery

Status
With Haye Chan (haye@cs.cornell.edu) Walter Chang (wcc3@cornell.edu) and Cristian Estan (estan@cs.cornell.edu)

The goal of this work is to automatically discover network topology both within a domain and in the Internet backbone. Past work in this area is here. A paper describing this work can be found here. Current work on this topic is described here.The new areas in this topic are:

Exploiting history: We think that it would be interesting and insightful to periodically run intra-domain and backbone discovery algorithms and analyze how topologies change over time. This would allow us to track growth patterns, particularly in the backbone, where ISPs rarely reveal topology information.

Evaluating ISP goodness: Hop contour maps display backbone topologies in a way rather different from a normal graph layout. In future work, we would like to correlate metrics on hop contour maps, such as the ratio of the maximal width to the height, with the `goodness' of an ISP's topology. This would allow customers to quickly and objectively evaluate the relative merits of competing ISPs.

Correlation: Currently, the backbone discovery algorithm discovers a tree of links and nodes rooted at a single source point. While it is possible to generate multiple rooted trees by choosing multiple probe points, correlating this information to form a single topology is a complex task. Our current approach to collating this information is semi-automatic and requires both skill and many hours of painstaking work. In future work, we would like to automate this process.

Analysis: While we have evaluated the performance of our algorithms in a couple of domains, we have yet to carry out a formal asymptotic analysis of their complexity. We would like to do so in the future, because we think that this will allow us to gain insight into their behavior, and perhaps suggest variations that have better performance.

Link characteristics: Currently, we do not discover link characteristics such as capacity and mean delay. Existing tools such as pathchar [Jacobson 97] and PBM [Paxson 97] can discover these automatically. In future work, we plan to integrate these tools with ours.

Exploit other sources of information: At the moment, our tools do not exploit routing information within a domain. If a topology discovery tool were allowed to extract information from a routing daemon running RIP or OSPF, it would be possible to quickly get subnet information within a domain. Similarly, we could extract network-specific information from a Microsoft WINS server, a Novell Directory Server, or an Appletalk network. In future work, we plan to integrate these sources of information with our tools.