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.

People can extract various kinds of information about the Internet from BGP routes tagged with BGP community values with known semantics. In this paper, we conduct a study on the following three issues related to BGP community semantics. First, we design a method to automatically collect self-reported semantics from the Internet and assemble the collected semantics described in natural language into a structured dictionary. The comparison with prior dictionaries shows many community values are exclusively covered by ours and many of them had been used when prior dictionaries were constructed, which confirms the effectiveness of our method. Second, based on this large-size dictionary, we are able to re-evaluate two recent algorithms designed for categorizing community values with unknown semantics, which is a task that, while easier than inferring the detailed semantics, is also very valuable. Our evaluation uncovers some issues within the algorithms that can contribute to their performance improvement. Third, we investigate the fundamental issue in extracting information using community semantics: whether ISPs' behavior is consistent with the published semantics. Our preliminary best-effort investigation reveals the potential risks of using the semantics of some categories of community values.

Researchers have noticed the AS-level Internet topology that can be observed from the current measurement infrastructure is far from complete, which means researchers have to deploy more measurement vantage points (VPs) and conduct measurements for more source/destination pairs to fully understand the whole Internet. Unfortunately, it is known that blindly deploying more points and conducting more measurements to achieve the goal is inefficient, if not infeasible. In this paper, we try to improve the efficiency by predicting where unseen AS links might be located from the observed AS paths to guide the measurements towards a more complete AS-level topology. We formulate the prediction of unseen links as a matrix completion problem. However, the traditional matrix completion methods have limited learning capacities and cannot deal with the complex constraints on the underlying topology. We develop a learning-based matrix completion method specifically for the unseen AS link prediction problem. The method exploits a neural network and utilizes side-information which is carefully chosen from AS attributes based on our understanding on Internet peering practices, therefore our method is able to learn more expressive latent vectors and achieves outstanding prediction performance in our scenario. Experiments performed on a real-world dataset show the prediction results can achieve a high AUC (Area Under the Receiver Operating Characteristic Curve) of 0.834.

Despite researchers have noticed that Looking Glass (LG) vantage points (VPs) are valuable for Internet measurement researches, they can only exploit VPs from well-known LG sites published on several LG portal pages. There should be a lot of LG sites that are not published in these portal pages, namely obscure LG sites, which are not easy to be found and exploited by researchers. In this paper, we design an efficient focused crawler to discover as many LG sites as possible which can avoid unnecessary resource consumption on analyzing irrelevant pages. Our designed focused crawler takes a similarity-guided search that exploits the well-developed search engines and comprehensively mines the common features shared by known LG sites to discover more LG pages. Moreover, the focused crawler takes a two-step PU learning classifier based on carefully selected LG features to efficiently discard irrelevant URLs, thus avoiding a lot of unnecessary resource consumption. As far as we know, we are the first to develop a method to discover obscure LG sites on the web. Experimental results show the effectiveness of our focused crawler. To facilitate practical applications, we further develop an automation tool, which can successfully retrieve 910 obscure automatable LG VPs from relevant pages obtained through our focused crawler. The 910 LG VPs significantly increase the geographic and network coverage of available VPs and we show their potential values in improving the completeness of AS-level Internet topology by a simple case study. Our method and the final VP list are beneficial to the measurement community.