Building a scalable network measurement infrastructure: Theory and practice

Today's network applications and services often need to learn the state of the network in terms of latency or bandwidth in order to maximize performance. For example, Internet content providers often place server mirrors throughout the Internet to reduce access latency for clients. Therefore, it is necessary to direct clients to the closest mirrors based on some distance metric in order to realize the benefit of mirroring. However, the complexity of today's Internet infrastructures makes it difficult to learn the necessary network information from the underlying network quickly and efficiently. Internet Distance Map service (IDMaps) proposes a scalable two-tier architecture where IDMaps conducts network measurements and disseminates the network measurements continuously. The network distance service then collects these network measurements to build virtual distance maps of the Internet and provides the network distance information to hosts on the Internet.; We present a study on the placement of measurement hosts in order to build a scalable IDMaps infrastructure to provide end-to-end latency information among Internet hosts. The end-to-end network latency has the additive property that the latency on a path may be estimated by using shorter intermediate latencies. This property allows for the estimation of end-to-end latencies for all hosts in a network based on a scalable infrastructure using a few measurement hosts. The placement problem is modeled as a graph-theoretic placement problem and studied in the context of a service provider's network. A scalable placement algorithm for measurement hosts is designed under the ideal condition that the end-to-end latencies are known. This scalable placement algorithm can estimate end-to-end latencies to within 20 ms while placing measurement hosts on between 2% and 9% of the nodes in the network. The scalability of our placement algorithm gives strong evidence that IDMaps can be realized with a scalable infrastructure inside service providers' networks. A service provider can use this placement algorithm to deploy an IDMaps-like infrastructure to collect network distance information based on static propagation delays.; The placement of measurement hosts under the ideal condition is not suitable for the Internet since the end-to-end latencies are not known. Furthermore, it is nearly impossible to place measurement hosts at desired locations due to financial and administrative constraints. In order for IDMaps to be successful on the Internet, it must be able to provide useful latency information even if measurement hosts are placed inside stub networks. We present two enhancements to the standard IDMaps architecture to mitigate the effect of poor placement. The two enhancements together allow IDMaps to use the minimum number of measurements to obtain a desired level of latency-estimation accuracy.; In order to demonstrate the usefulness of the latency information provided by IDMaps, we study the use of such information in directing clients to the closest server mirrors on the Internet. The study reveals that when latency information is used as the selection metric, there is a rapid diminishing return in deploying more server mirrors throughout the Internet. The availability of latency information can help content distribution networks determine the number of server mirrors to deploy that is cost-effective.