Distance information protocol (DIP) for Internet distance map service (IDMaps)

To enable distributed applications to quickly and efficiently discover network distances to other participants without doing measurement themselves, the Internet Distance Map Service (IDMaps) provides distance estimates between any two hosts on the Internet. Example applications that can benefit from IDMaps service include Web caching where user requests can be guided to the nearest cache server and application-level multicast where member hosts can build efficient multicast trees among themselves based on their relative distances.; IDMaps design is made up of a 2-layer architecture, IDMaps Tracers and IDMaps servers. Tracers are autonomous processes deployed at various places on the Internet. They continuously measure the distances among themselves and between IP address prefixes, and report the measurement results to IDMaps servers. IDMaps servers collect the distance reports from Tracers and build topology databases. User applications query IDMaps servers for distance information, and the servers in turn estimate the requested distance using their topology databases.; A fundamental challenge in IDMaps is to design a scalable and efficient information dissemination protocol that can deliver distance information from Tracers to IDMaps servers, which is the focus of this dissertation research. From our research, we provide important knowledge on how large the Internet is in terms of network distance. We also estimate that thousands of Tracers are needed to accurately portrait Internet distance map. In addition to Jamin's work (JJJ00], we give a simple and effective algorithm to further reduce the size of distance map.; Most importantly, we design a feedback-controlled information advertisement protocol - Distance Information Protocol (DIP) to efficiently deliver distance information from Tracers to IDMaps servers. We have verified DIP design with extensive simulations which show promising results on DIP's scalability and robustness. Its overhead grows sub-linearly with the system size, esp. the number of Tracers. We also design a novel, unicast-based feedback suppression scheme that has great scalability to keep the system overhead low. We believe that DIP design has presented not only a scalable and robust solution to IDMaps, but also a valuable insight into the design principles for scalable information dissemination protocols in general.