Discovering Millions of New Nodes and Links in the Internet by Challenging the Uniformity Assumption in Multipath Detection
Zhongxu Guan, Shuai Wang, Li Chen, Zhaoteng Yan, Jiaye Lin, Dan Li, Yong Jiang, Yingxin Wang, Ziqian Liu · 2025
Multipath Detection Algorithms (MDAs) are proposed to discover Internet topology in the presence of load balancing (LB). Existing methods assume uniformity in the load-balancing responses (LBR), i.e., responses from the successors of a LB router. However, we reveal that only 20% of the cases exhibit uniformity in the Internet. This finding significantly challenges the completeness of the Internet topology discovered using current MDAs. In this paper, we propose a novel system BayMuDA, that can estimate LBR distributions and calculate the minimum number of probes needed to statistically discover all nodes and links within a given hop. The validation on controlled topologies shows that BayMuDA discovers at least 85%/73% of nodes/links in ~90% of the cases. Our Internet-wide measurement results indicate that BayMuDA can discover millions of Internet nodes and links obscured by the state-of-the-art MDA algorithm, D-Miner, due to uneven responses.