The cost and complexity of deploying measurement infrastructure in the Internet for the purpose of analyzing its structure and behavior is considerable. Basic questions about the  utility  of increasing the number of measurements and measurement sites have not yet been addressed which has led to a "more is better" approach to wide-area ,measurement studies. In this paper, we step toward a more quantifiable understanding of the marginal utility of performing wide-area ,measurements in the context of Internet topology discovery. We characterize the observable topology in terms of nodes, links, node degree distribution, and distribution of end-to-end flows using statistical and information-theoretic techniques. We classify nodes discovered on the routes between a set of 8 sources and 1277 destinations to differentiate nodes which make up the so called "backbone" from those which border the backbone and those on links between the border nodes and destination nodes. This process includes reducing nodes that advertise multiple interfaces to single IP addresses. We show that the utility of adding sources beyond the second source quickly diminishes from the perspective of interface, node, link and node degree discovery. We also show that the utility of adding destinations is constant for interfaces, nodes, links and node degree indicating that it is more important to add destinations than sources.
['Paul Barford', 'Azer Bestavros', 'John W. Byers', 'Mark Crovella']
On the marginal utility of network topology measurements