Technical Report LCCN-2004-01

Title: The Internet Dark Matter – on the Missing Links in the AS Connectivity Map
Authors: Danny Raz and, Rami Cohen
Abstract: The topological structure of the Internet infrastructure is an important and interesting subject that attracted significant research attention in the last few years. Apart from the pure intellectual challenge of understanding a very big, complex, and ever evolving system, built by people and used by many more, knowing the structure of the Internet topology is very important for developing and studying new protocols and algorithms. Starting with the fundamental work of Falostous et. al, a considerable amount of work was done recently in this field, improving our knowledge and understanding of the Internet structure. However, one basic problem is still unanswered: how big is the Internet. In the AS level this means: how many peering relations exist between ASs. Finding this number is hard since there is no direct way to retrieve information from a node regarding its direct neighbors. Thus, it is very difficult to characterize the Internet since it may well be the case that this characterization is a result of the sampling process, and it does not hold for the “real” Internet. In this paper we attack this problem by suggesting a novel usage of the measurements themselves in order to infer information regarding the whole system. In other words, rather than looking at the overall graph that is generated from the union of the data obtained by performing many measurements, we consider the actual different measurements and the amount of new data obtained in each of them with respect to the previous collected data. Using the second moment allows us to reach conclusions regarding the structure of the system we were measuring, and in particular to estimate its total size. We present strong evidence to the fact that a considerable amount (more than 50%) of the links in the AS level are still to be unveiled. Our findings indicate that almost all these missing links are of type peer-peer, and we provide novel insight regarding the structure of the AS connectivity map with respect to the peering type. We also identify a new measure for graphs, the number of spanning trees needed to cover all the edges of a graph, that plays a significant role in the matching of theoretical graph model to the real structure of the revealed portion of the AS connectivity map.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the LCCN technical reports of 2004
To the main CS technical reports page

Computer science department, Technion