An Efficient Method for Router Alias Identification with Active-Passive Collaboration

doi:10.3969/j.issn.1671-1122.2025.12.003

Abstract

Abstract:

Router alias identification is one of the key technologies for accurately analyzing the network topology. Aiming at the problems of low efficiency and weak anti-interference ability of router alias identification in large-scale networks, this paper proposed an efficient router alias identification method with active-passive collaboration. First, a collaborative framework was constructed that integrated four types of active probing protocols (ICMP/TCP/UDP/SYN) and BGP/SNMP passive monitoring. The geographical scheduling was optimized through a quadtree index to reduce the cross-regional probing delay. Then, a dynamic task allocation model was designed. The calculation complexity was optimized from O(n2) to O(n) by using the load variance threshold control. Furthermore, an IPBH anti-interference algorithm was proposed. The noise interference was suppressed through a sliding window mechanism and dynamic threshold adjustment. A large number of experiments were carried out based on the commonly used CAIDA2023 dataset. The results show that the proposed method has obvious advantages in terms of identification efficiency and anti-interference compared with the original MBT typical router alias identification method. The speed of identifying every 10,000 routers was reduced from 42.3 seconds to 4.1 seconds. Through the local smoothing with a sliding window and dynamic threshold adjustment using the Kalman filter, the randomization noise of the IP identification and the interference of equal-cost multi-path are suppressed. An alias identification accuracy rate of 90.1% is achieved in a 25% noise environment, which is 7% to 25% higher than methods such as RadarGun, Hybrid Alias, and NoiseShield, etc.

Key words: active-passive collaborative detection, router alias identification, IPBH algorithm, dynamic task allocation

CLC Number:

TP309

HU Dan, YANG Jilong. An Efficient Method for Router Alias Identification with Active-Passive Collaboration[J]. Netinfo Security, 2025, 25(12): 1863-1877.

Figures/Tables 22

References 29

[1]	SPRING N, MAHAJAN R, WETHERALL D. Measuring ISP Topologies with Rocketfuel[J]. ACM SIGCOMM Computer Communication Review, 2002, 32(4): 133-145. doi: 10.1145/964725.633039 URL
[2]	KUMAR A, LEE T, KATTA N, et al. ECMP Load Balancing in the Wild: A Measurement Study of Path Instability in SDN[C]// ACM.The 2020 Conference on Emerging Networking Experiments and Technologies (CoNEXT). New York: ACM, 2020: 1-14.
[3]	FELDMANN A, LUCKIE M, REXFORD J, et al. The Economic Cost of Internet Infrastructure Misconfigurations: A Global ISP Perspective[J]. ACM SIGCOMM Computer Communication Review, 2019, 49(4): 2-10.
[4]	BRENNER-BARR A, BEN-ARTZI A, RAMI G, et al. Detecting and Mapping Routers with Monotonic Bounds Test[C]// USENIX. The 2011 ACM SIGCOMM Conference on Internet Measurement. Berkeley: USENIX, 2011: 387-400.
[5]	BEVERLY R, BERGER A. Leveraging IP Identifier for Coarse Router Classification[C]// Springer. Passive and Active Measurement Conference. Heidelberg: Springer, 2015: 183-192.
[6]	SHERWOOD R, SPRING N. Touring the Internet in a TCP Sidecar[C]// ACM. The 6th ACM SIGCOMM Conference on Internet Measurement. New York: ACM, 2006: 339-344.
[7]	KEYS K, HYUN Y, LUCKIE M, et al. Internet-Scale IPv4 Alias Resolution with MIDAR[J]. IEEE/ACM Transactions on Networking, 2013, 21(2): 383-399. doi: 10.1109/TNET.2012.2198887 URL
[8]	ZHOU Jun, ZHANG Jian, YANG Shunfeng. Stochastic Modeling and Convergence Analysis of Internet Routers[J]. Applied Mathematics and Mechanics, 2022, 43(2): 207-214.
[9]	YUAN Fuxiang. Analysis of Network Characteristics for IP Positioning[D]. Zhengzhou: Information Engineering University, 2020.
	袁福祥. 面向IP定位的网络特性分析[D]. 郑州: 战略支援部队信息工程大学, 2020.
[10]	DONNET B, FRIEDMAN T. Internet Topology Discovery: A Survey[J]. IEEE Communications Surveys & Tutorials, 2007, 9(4): 56-69.
[11]	KOUNTOURIS A, KINTIS P, CHEN P, et al. Exposed! A Large-Scale Analysis of Cloud Service Misconfigurations[C]// USENIX.The 29th USENIX Security Symposium. Berkeley: USENIX, 2020: 2545-2562.
[12]	YUAN Fuxiang, LIU Fenlin, LIU Chong, et al. MLAR: Large-Scale Network Alias Resolution for IP Positioning[J]. Chinese Journal of Network and Information Security, 2020, 6(4): 77-94.
	袁福祥, 刘粉林, 刘翀, 等. MLAR:面向IP定位的大规模网络别名解析[J]. 网络与信息安全学报, 2020, 6(4):77-94.
[13]	MUHLBAUER W, FELDMANN A, MAENNEL O, et al. Building an AS-Topology Model that Captures Route Diversity and Its Applications[C]// ACM. The 2007 ACM SIGCOMM Conference on Internet Measurement. New York: ACM, 2007: 1-14.
[14]	LIU Zheng, ZHANG Yang, WU Qiang, et al. AutoTopo: SNMP-Based Topology Discovery with Active Learning[C]// ACM. The SIGCOMM Workshop on Network Data Analytics (NDA’22). New York: ACM, 2022: 1-8.
[15]	WANG Zhanfeng, CHENG Guang, HU Chao, et al. Research Progress of Alias Resolution Technology[J]. Journal on Communications, 2019, 40(7): 169-185. doi: 10.11959/j.issn.1000-436x.2019134
	王占丰, 程光, 胡超, 等. 别名解析技术研究进展[J]. 通信学报, 2019, 40(7):169-185. doi: 10.11959/j.issn.1000-436x.2019134
[16]	ALI S, QURESHI K N, RANA L, et al. Simple Network Management Protocol (SNMP) and Its Challenges: A Survey[J]. IEEE Communications Surveys & Tutorials, 2020, 22(3): 1559-1587.
[17]	HE Heng, CHEN Kai, JIN Hai, et al. HybridAlias: A Hybrid Active-Passive Approach for Scalable Router Alias Resolution[C]// ACM. The ACM SIGCOMM Conference. New York: ACM, 2022: 456-470.
[18]	LIU Yang, ZHANG Ming, LI Dong, et al. DynaMap: Dynamic IP Alias Mapping with High Accuracy and Efficiency[J]. IEEE/ACM Transactions on Networking, 2019, 27(3): 1024-1037.
[19]	LIU Xiaobo, GUO Li, CHENG Guang, et al. APAR: Adaptive Path Probing for Fast and Accurate Router Alias Resolution[J]. IEEE/ACM Transactions on Networking, 2023, 31(2): 812-827.
[20]	LIU Xiangyang, JIN Yier, VAN DER MERWE J, et al. Towards a Lightweight Solution for Low-Rate DoS Attack Detection[J]. IEEE/ACM Transactions on Networking, 2022, 30(4): 1789-1802.
[21]	CHEN Min, LIU Yong, LIU Zimu, et al. GAP: A General Framework for Graph Alignment in Network Topology Inference[C]// IEEE. IEEE Conference on Computer Communications(INFOCOM 2022). New York: IEEE, 2022: 270-279.
[22]	CHENG Guang, WANG Zhanfeng, HU Chao, et al. FedAlias: A Federated Learning Framework for Privacy-Preserving and Collaborative Router Alias Resolution[J]. IEEE Transactions on Information Forensics and Security, 2023, 18: 1526-1540.
[23]	WANG Zihao, LIU Yang, CHEN Min, et al. APAR: Adaptive Path Selection for Alias Resolution with Attention Mechanism[J]. IEEE Transactions on Network and Service Management, 2023, 20(1): 512-525.
[24]	ZHOU Xuan, CHEN Min, LIU Yang, et al. Scalable Internet-Wide Alias Resolution with Global-Local Analysis[J]. IEEE/ACM Transactions on Networking, 2023, 31(5): 2101-2114. doi: 10.1109/TNET.2022.3233908 URL
[25]	BEVERLY R, BERGER A. Leveraging IP Identifier for Coarse Router Classification[C]// IFIP. The 15th International Conference on Passive and Active Measurement. Heidelberg: Springer, 2015: 183-192.
[26]	SHERRY J, KATZ-BASSETT E. A Survey of Router Aliasing and a New Approach Using Geographic Diversity[C]// ACM.The 2012 ACM SIGCOMM Conference on Internet Measurement. New York: ACM, 2012: 1-14.
[27]	ZHANG Wei, LI Hang, WANG Zhi. An Active Probing-Based Detection Method for Anomalous Nodes in Internet Topology[J]. Netinfo Security, 2023, 23(3): 45-53.
	张伟, 李航, 王智. 基于主动探测的互联网拓扑异常节点检测方法[J]. 信息网络安全, 2023, 23(3):45-53.
[28]	CHEN Gang, LIU Yang, ZHOU Yue. Construction Technology of Network Device Fingerprint Library Based on Multi-Source Data Fusion[J]. Netinfo Security, 2022, 22(7): 12-20.
	陈刚, 刘洋, 周悦. 多源数据融合的网络设备指纹库构建技术[J]. 信息网络安全, 2022, 22(7):12-20.
[29]	XU Zhen, WANG Xiaofeng, LI Ning. Router Alias Resolution Algorithm Based on Probabilistic Graphical Model[J]. Journal of Computer Research and Development, 2023, 60(2): 334-345.
	徐震, 王晓峰, 李宁. 基于概率图模型的路由器别名解析算法[J]. 计算机研究与发展, 2023, 60(2):334-345.

类型	核心原理	优势	局限性	代表方法	假阳率	复杂度
主动探测法	发送定制探测包分析IPID/TTL等特征	接口覆盖率高(大于85%)	受ECMP干扰假阳率高	MBT^[4], Ally ^[5]	1.8%~ 3.5%	O(n2)
被动监测法	解析BGP/SNMP日志构建别名关系	无需主动流量注入	数据碎片化 (覆盖率小于60%)	BGP-Miner^[13]	—	O(n)
混合方法	融合主被动数据互补验证,动态阈值调整/自适应路径探测	抗路径跳变干扰,噪声鲁棒性提升	任务调度低(负载方差大于等于0.65),实时性不足(延迟大于等于15ms)	Hybrid Alias^[17], NoiseShield^[20]	1.20%	O(n2)

协议	覆盖率	抗ECMP跳变率	适用场景
ICMP	76.30%	35%	基础连通性验证
TCP	85.40%	28%	防火墙穿透
UDP	68.90%	22%	无状态设备探测
SYN	79.10%	31%	负载均衡路径追踪

权重类型	基准值	调整范围	边界约束
地理密度	0.58	±0.05	0.53~0.63
连接状态	0.30	±0.05	0.25~0.35
任务负载	0.12	±0.05	0.07~0.17

分类	具体内容
硬件平台	集群配置:8台Intel Xeon Platinum 8375C服务器（32核/64线程，主频3.6 GHz）；内存:512 GB DDR4（ECC校验）；网络:10 Gbps双网卡（RDMA支持）；存储:NVMe SSD阵列（200 TB，IOPS 1M）
软件工具	主动探测:Python 3.10 + Scapy 2.4.5（四协议探测包定制）；被动监测:BGPStream 2.0（BGP更新解析）+ Net-SNMP 5.9（SNMPv3加密查询）；数据处理:PostgreSQL 14（拓扑关系存储）+ Redis 6.2（实时任务队列）+ Spark 3.3（分布式计算）
数据集与基准真值	数据集:CAIDA2023公开数据集（120万路由器接口，IPv4占比92%），注入25%均匀分布IPID噪声（模拟Linux RFC7739）；基准真值:RIPE Atlas平台（10,000+全球探针）主动探测 + IRR数据库（路由前缀聚合性验证） + 人工标注5%高置信度别名对
噪声与干扰模拟	动态负载均衡:配置3条ECMP等价路径，每5 min修改哈希种子强制路径切换； IPID随机化:在25%接口响应中随机替换IPID值（δ=???，均匀分布U(-δ,δ)）；突发流量:基线1 Gbps + 瞬时3 Gbps DDoS流量（持续10 min）

指标	优质阈值	合格阈值	测量误差范围
任务耗时	≤ 5 s	≤ 15 s	±0.3s
负载均衡度	≤ 0.3	≤ 0.6	±0.02
准确率	≥ 90%	≥ 75%	±0.5%
假阳率	≤ 1%	≤ 3%	±0.1%