TopoScope: Recover AS Relationships From Fragmentary Observations
TopoScope: Recover AS Relationships From Fragmentary Observations
复制标题
DOI：
10.1145/3419394.3423627
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Zitong Jin;Xingang Shi;Yan Yang;Xia Yin;Zhiliang Wang;Jianping Wu
中科院分区：
文献类型：
--
作者：
Zitong Jin;Xingang Shi;Yan Yang;Xia Yin;Zhiliang Wang;Jianping Wu
了解互联网拓扑和自治系统 (AS) 之间的业务关系是研究互联网许多方面的基础。尽管最新的推理算法取得了重大进展，但由于数据有限，其推理结果在一些关键环节上仍然存在错误，从而阻碍了许多依赖于推理关系的应用。我们对数据中固有的挑战进行了深入分析，特别是覆盖范围有限和优势点（VP）的偏集中。其中的某些方面在很大程度上被忽视了，但随着互联网的进一步发展，这些问题将变得更加严重。然后我们开发了 TopoScope，一个用于从此类碎片观测中准确恢复 AS 关系的框架。 TopoScope 使用集成学习和贝叶斯网络来减轻观察偏差，该偏差不仅源于单个 VP，还源于可用 VP 的不均匀分布。它还发现相邻链接组之间的内在相似性，并推断不可直接观察到的隐藏链接上的关系。与最先进的推理算法相比，TopoScope 将推理误差降低了 2.7-4 倍，发现了大约 30,000 个上层隐藏 AS 链接的关系，并且在更不完整或有偏差的观察下仍然更加准确和稳定。
Knowledge of the Internet topology and the business relationships between Autonomous Systems (ASes) is the basis for studying many aspects of the Internet. Despite the significant progress achieved by latest inference algorithms, their inference results still suffer from errors on some critical links due to limited data, thus hindering many applications that rely on the inferred relationships. We take an in-depth analysis on the challenges inherent in the data, especially the limited coverage and biased concentration of the vantage points (VPs). Some aspects of them have been largely overlooked but will become more exacerbated when the Internet further grows. Then we develop TopoScope, a framework for accurately recovering AS relationships from such fragmentary observations. TopoScope uses ensemble learning and Bayesian Network to mitigate the observation bias originating not only from a single VP, but also from the uneven distribution of available VPs. It also discovers the intrinsic similarities between groups of adjacent links, and infers the relationships on hidden links that are not directly observable. Compared to state-of-the-art inference algorithms, TopoScope reduces the inference error by up to 2.7-4 times, discovers the relationships for around 30,000 upper layer hidden AS links, and is still more accurate and stable under more incomplete or biased observations.