In the last decade, many studies have used the Internetautonomous system (AS)-level topology to perform severalanalyses, from discovering its graph properties to assessing itsimpact on the effectiveness of worm-containment strategies. Yet,the Border Gateway Protocol (BGP) data used to reveal thetopologies are far from complete. Our contribution is threefold.First, we analyze BGP data currently gathered by the most famousroute collector projects, highlighting and explaining the causes oftheir incompleteness. We found that large areas of the Internet arenot properly captured due to the geographical location of routecollector feeders and due to BGP filters, such as export policiesand decision processes. Second, we propose a methodology basedon a new metric, named p2c-distance, which is able to: 1) identifythe minimum number of ASs required to obtain an InternetAS-level topology that is closer to reality; and 2) identify a rankinglist of these ASs to show that it is possible to obtain nonnegligiblecoverage improvements with a limited number of appropriatelychosen feeding ASs. Third, we characterize the ASs that werefound to be part of the solution of the above covering problems.We found that the route collectors are rarely connected to theseASs, thus highlighting that much effort is needed to devise a routecollector infrastructure that ideally would be able to capture acomplete view of the Internet.