Network Topology Inference: Figuring Out Network Topology from Partial Information

Internet providers are generally unwilling to share information about their networks. The information, such as topology, routing policies and so on, would be very useful to network researchers, but also of great interest to their competitors and intelligence agencies.

The problem

Researchers undertaking network analysis studies need reasonable representations of real networks in order to validate their research, especially in areas such as network management, reliability and resilience. Algorithm performance depends on the type of network and traffic to which it is applied, and so realistic experimental environments are needed.

Reverse engineering of the Internet has been seen as a valuable activity for researchers and various projects internationally have provided datasets that are invaluable to network researchers. It is therefore somewhat surprising that few efforts have been made to validate the methods and results of such projects.

The solution

We have developed and validated a new network topology inference methodology that can be used to obtain shortest path link weights on interior links of networks, in other words, for determining the internal structure of major sub-networks of the Internet.

The difficulty in assessing the accuracy of such inferences is that a non-unique set of link-weights may produce the same routing, and so simple measurements of accuracy, even where ground truth data are available, do not capture the usefulness of a set of inferred weights. We developed a new measure, predictive power, to assess the quality of a specific inference process, and found that the process is reasonably accurate, particularly for networks with low average node degree.