Discarte
Authors:
Open Access
- 17 August 2008
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 38 (4) , 303-314
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.Keywords
This publication has 31 references indexed in Scilit:
- The DLV system for knowledge representation and reasoningACM Transactions on Computational Logic, 2006
- Towards an accurate AS-level traceroute tool2003
- The causes of path inflation2003
- A routing underlay for overlay networks2003
- Measuring ISP topologies with rocketfuel2002
- Inferring link weights using end-to-end measurements2002
- Passive network tomography using Bayesian inference2002
- Resilient overlay networks2001
- On routes and multicast trees in the InternetACM SIGCOMM Computer Communication Review, 1998
- End-to-end routing behavior in the InternetIEEE/ACM Transactions on Networking, 1997