ProbInfer: Probability-based AS path inference from multigraph perspective
Abstract Knowing the paths between autonomous systems (ASes) is essential to understanding the behavior of the Internet routing system and contributes to many Internet services. Despite Traceroute being a useful tool that can conveniently reveal AS paths, the accuracy is affected by intermediate techniques, and it is impossible to implement Traceroute between arbitrary hosts. There are also methods that infer the AS path using BGP data, but the accuracy cannot always meet our expectations. The most difficult part of AS path inference is how to find the best path among the candidate paths. In this paper, we proposed ProbInfer: a probability-based AS path inference method that from the perspective of multigraph. The probabilistic method can efficiently solve the problem of finding the best path by scoring each candidate path. The multigraph can conveniently stitch AS paths and provide characters used to improve the accuracy of the method. First, ProbInfer separates the candidate paths into two types: SingleShortest (easy to infer) and MultiShortest (hard to infer and the majority). Second, we design the features used to make decisions from three aspects; especially, the features that come from stitching points and the multigraph show great value. Last, we scored the two types of candidate paths using a machine learning algorithm that trains different models for each situation. The results show that compared with state-of-the-art methods, ProbInfer performs much better.