Evaluating the Topology Coverage of BGP monitors

BGP monitors are currently the main data resource of AS-level topology measurement, and the integrity of measurement result is limited to the location of such BGP monitors. However, there is currently no work to conduct a comprehensive study of the range of measurement results for a single BGP monitor. In this paper, we take the first step to describe the observed topology of each BGP monitor. To that end, we first investigate the construction and theoretical up-limit of the measured topology of a BGP monitor based on the valley-free model, then we evaluate the individual parts of the measured topology by comparing such theoretical results with the actually observed data. We find that: 1) for more than 90% of the monitors, the actually observed peer-peer links merely takes a small part of all theoretical visible links; 2) increasing the BGP monitors in the same AS may improve the measurement result, but with limited improvement; and 3) deploying multiple BGP monitors in different ASs can significantly improve the measurement results, but non-local BGP monitors can hardly replace the local AS BGP monitors. We also propose a metric for monitor selection optimization, and prove its effectiveness with experiment evaluation.