AS-level end-to-end paths are of great value for ISPs and a variety of network applications. Although tools like traceroute may reveal AS paths, they require the permission to access source hosts and introduce additional probing traffic, which is not feasible in many applications. In contrast, AS path inference based on BGP control plane data and AS relationship information is a more practical and cost-effective approach. However, this approach suffers from a limited accuracy and high traffic, especially when AS paths are long. In this paper, we bring a new angle to the AS path inference problem by exploiting the metrical tree-likeness or low hyperbolicity of the Internet, part of the complex network properties of the Internet. We show that such property can generate a new constraint that narrows down the searching space of possible AS paths to a much smaller size. Based on this observation, we propose two new AS path inference algorithms, namely HyperPath and Valley-free HyperPath. With intensive evaluations on AS paths from real-world BGP Routing Information Bases, we show that the proposed new algorithms can achieve superior performance, in particular, when AS paths are long paths. We demonstrate that our algorithms can significantly reduce inter-AS traffic for P2P applications with an improved AS path prediction accuracy.

This paper investigates the rating of network paths, i.e., acquiring quantized measures of path properties such as round-trip time and available bandwidth. Compared to fine-grained measurements, coarse-grained ratings are appealing in that they are not only informative but also cheap to obtain. Motivated by this insight, we first address the scalable acquisition of path ratings by statistical inference. By observing similarities to recommender systems, we examine the applicability of solutions to a recommender system and show that our inference problem can be solved by a class of matrix factorization techniques. A technical contribution is an active and progressive inference framework that not only improves the accuracy by selectively measuring more informative paths, but also speeds up the convergence for available bandwidth by incorporating its measurement methodology. Then, we investigate the usability of rating-based network measurement and inference in applications. A case study is performed on whether locality awareness can be achieved for overlay networks of Pastry and BitTorrent using inferred ratings. We show that such coarse-grained knowledge can improve the performance of peer selection and that finer granularities do not always lead to larger improvements.