Heuristics for internet map discovery

Abstruct-Mematar is a program that uses hoplimited probes-the same primitive used in traceroute-to infer an Internet map. It uses in-formed random d r e s s probing to farefully exploring the IP address space when determining router adjacencies, uses sourceroute capable routers wherever possible to enhance the fidelity of the resulting map, and em-ploys novel mechanisms for resolving a h c s (iteffaces belonging to the same router). This paper describes the design of these heuristics and our experiences with Mercator, and pments some prelfmiinrvy analysis of the resulting Internet map. I