Discarte: a disjunctive internet cartographer
Discarte: a disjunctive internet cartographer
复制标题
DOI：
10.1145/1402958.1402993
复制
发表时间：
2008-08
期刊：
影响因子：
--
通讯作者：
Rob Sherwood;Adam Bender;N. Spring
中科院分区：
文献类型：
--
作者：
Rob Sherwood;Adam Bender;N. Spring
互联网拓扑发现包括推断路由器间的连通性（“链路”）和从IP地址到路由器的映射（“别名解析”）。当前的拓扑发现技术使用TTL限制的“跟踪路由”探测来发现链路，并使用直接路由器探测来解析别名。经常被忽略的记录路由（RR）IP选项提供了一个可以增强现有技术的不同拓扑数据源，但由于路由器RR实现标准化不足，因此很难与基于跟踪路由的拓扑正确对齐。正确对齐的RR和traceroute拓扑具有更少的错误链接，包括匿名和隐藏路由器，并发现不响应直接探测的路由器的别名。更精确和功能更丰富的拓扑有利于覆盖构建和网络诊断、建模和测量。我们提出了Discarte，一个系统，用于对齐和交叉验证RR和traceroute拓扑数据使用观察到的工程实践Discarte使用析取逻辑编程（DLP），逻辑推理和约束求解技术，智能地合并RR和traceroute数据。我们证明，由此产生的拓扑结构是更准确和完整的比以前的技术，通过验证其内部的一致性，并通过比较公开可用的拓扑结构。我们对路由器实现中的不规则性进行分类，并介绍了一种用于将DLP扩展到Internet大小的系统的分而治之技术。
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.