Project Octopus:

Backbone Topology Discovery

This is a simple description of the engine. For more detail, please email Rachit.

Design of the Topology Discovery Engine

The circles on the left-hand side are slaves (probe points). They constantly run traceroutes (probes) to various nodes in the network and send the data (via UDP) to the master. The backbone master then compiles the information and occasionally sends feedback to the slaves for more information on a particular node or link.

If information about a particular domain is needed, the Domain Master finds the slave with the fewest hops to a domain and tells it to initiate a domain probe on that particular domain. The results are streamed back to the Domain Master and into the file system. The Domain Master is an independent part of the discovery engine. See this link on how to discover information within a domain.

Backbone topology discovery

The general idea is to traceroute to as many domains as possible and find all the intermediary links and routers.

This method should return most of the routing nodes in the backbone, and all of the important ones. However some intermediary and redundant links may not be found. Consider this case:

The middle node that may be used by Domain A to contact Domain B will not be found. This problem is partially solved if we have multiple probe points. For example, suppose we had a probe point at Domain B, we would have found the link to Domain A. However, we can never guarantee we will find all the nodes and links unless we have a probe point in every domain.

If the probe points are positioned correctly though, we should be able to get all the crucial and important routing nodes and links.

Data

Data has already been gathered from three probe points. Berekeley, Stanford and Cornell. Displaying the backbone topology is difficult, though, because it is huge. We have succesfully displayed a fraction of a fraction of NYSERNET's (a relatively small ISP) backbone, but it is still quite huge. Here is a more visible representation of the backbone. Each column is an ISP. The Y-axis is the number of hops from the Cornell domain. How thick the dots are tell you how many routers are there at that hop. The distance between two columns is exactly 200 routers. You can see that alter.net and MCI have 200 routers at some hops and an ISP can have more than 1000 routers. And this graph was generated when the logging was not complete. We can estimate that the number of backbone routers is in the 50,000 router range.

    This work is part of the new network management research in the CNRG Research Group with Professor S. Keshav.

This page is last modified 10/10/05 02:18:42 PM