Name
Abstract | ||
|---|---|---|
Internet topology discovery consists of inferring the inter-router connectivity ("links") and the mapping from IP addresses to routers ("alias resolution"). Current topology discovery techniques use TTL-limited "traceroute" probes to discover links and use direct router probing to resolve aliases. The often-ignored record route (RR) IP option provides a source of disparate topology data that could augment existing techniques, but it is difficult to properly align with traceroute-based topologies because router RR implementations are under-standardized. Correctly aligned RR and traceroute topologies have fewer false links, include anonymous and hidden routers, and discover aliases for routers that do not respond to direct probing. More accurate and feature-rich topologies benefit overlay construction and network diagnostics, modeling, and measurement. We present DisCarte, a system for aligning and cross-validating RR and traceroute topology data using observed engineering practices DisCarte uses disjunctive logic programming (DLP), a logical inference and constraint solving technique, to intelligently merge RR and traceroute data. We demonstrate that the resultant topology is more accurate and complete than previous techniques by validating its internal consistency and by comparing to publicly-available topologies. We classify irregularities in router implementations and introduce a divide-and-conquer technique used to scale DLP to Internet-sized systems. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1402958.1402993 | SIGCOMM |
Keywords | Field | DocType |
network topology,internet topology,cross validation,divide and conquer | Internet topology,Logical topology,Alias,traceroute,Computer science,Computer network,Network topology,Theoretical computer science,Router,Overlay,The Internet,Distributed computing | Conference |
Volume | Issue | ISSN |
38 | 4 | 0146-4833 |
Citations | PageRank | References |
54 | 2.36 | 32 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rob Sherwood | 1 | 1462 | 128.08 |
| Adam Bender | 2 | 483 | 17.84 |
| neil spring | 3 | 3681 | 276.15 |