Large-scale self -organizing network measurement infrastructure.
Amgad Zeitoun, Sugih Jamin · Deep Blue (University of Michigan) · 2004
Learning network distances, e.g., latency, bandwidth, loss, enhances network applications performance. Internet Distance Map Service (IDMaps) is a measurement infrastructure that enables distance (i.e., latency) estimation between any pair of Internet hosts. The fundamental operation of IDMaps depends on the deployment of several measurement machines, called Tracers , across the Internet. Tracers discover different networks, measure distances to them, and disseminate distance information to higher-level services-IDMaps clients. IDMaps clients collect distance advertisements and build a virtual distance map of the Internet, where the end-to-end distance between any pair of hosts can be estimated. In this dissertation, we design the architecture of a scalable Tracer. More specifically, we develop the main mechanisms used for network discovery, distance measurement, and information dissemination. In addition, we design the protocols used for Tracer-Tracer and Tracer-IDMaps client communications. Due to the Internet's size and the large number of Tracers in the IDMaps infrastructure, the main design principle in our mechanisms is scalability. We develop an efficient and non-intrusive Internet discovery mechanism. The efficiency comes from empirically studying IP address assignment of different hosts. The mechanism exploits the correlation between reachable IP addresses to intelligently probe a small number of IP addresses within each Internet address region. The discovery mechanism utilizes the information revealed by failed probes in a given address region to guide future probes to that region. We also develop a distance measurement mechanism that captures the propagation delay of a path with few probes---8--12 probes. It also detects the condition on the measured path---congestion or route changes---from the delay information revealed by the probes. It determines the accuracy of the measured propagation delay and associates a confidence measure to the captured delay. We also develop a scalable distance advertisement protocol that allows Tracers to self-organize such that each Tracer advertises distances to the proximate Internet address regions. The protocol allows Tracers to detect and transparently recover failures without IDMaps clients intervention. Finally, we study the performance improvement of some network applications. We show, through two examples, that network applications improve their throughput and scalability by augmenting their selection decisions with network distances.