Link Prediction-Based Measurement Strategy for Efficient Topology Completeness Improvements

The Autonomous System (AS) level topology observed from current measurement infrastructures is far from complete. Although Looking Glass (LG) vantage points (VPs) that support BGP route queries can provide valuable topology information, the query rate limitations of LG VPs imply that blindly using the VPs to conduct more measurements to improve the topology completeness is inefficient, if not infeasible. In this paper, we try to improve the efficiency by designing a link prediction based measurement strategy, whose basic idea is to first predict where unseen AS links are likely to be located and then use the prediction results to guide the measurements toward a more complete AS-level topology. We formulate the prediction of unseen AS links as a matrix completion problem and develop a side-information assisted learning-based matrix completion method. The method exploits a neural network and utilizes carefully chosen AS attributes based on our understanding on Internet peering practices, thereby learning more expressive latent vectors and achieving outstanding prediction performance in our scenario. We then develop a measurement strategy which takes the link prediction results as guidance to achieve efficient topology completeness improvements. The strategy leverages several heuristics to estimate the utilities of different measurements and takes a greedy algorithm to select the most valuable measurements. Experiments show that our link prediction method can achieve a high AUC (Area Under the Receiver Operating Characteristic Curve) of 0.834 and the link-guided measurement strategy can discover 1.82 times more unseen links than those discovered from non-guided measurement strategies with an equal number of measurements.