Merging logical topologies using end-to-end measurements

Knowledge of network topology is useful for understanding the structure of the Internet, for developing and testing new protocols, and as prior information to network tomography algorithms. Building on existing techniques for inferring a single-source tree topology using end-to-end measurements, we address the problem of merging multiple tree topologies. We develop a multiple source active probing methodology and statistical framework for testing whether the paths from two sources to two receivers branch at a common internal node. This information can then be used to determine where portions of the tree topology from one source to a set of receivers overlap with the tree topology from a different source to the same set of receivers. The algorithm uses a novel random probing structure and easily made measurements of packet arrival order. As a result, we do not require precise time synchronization among the participating hosts. Successful experiments performed over a university LAN and over the Internet verify that our methodology is versatile and robust.