Researchers investigating topics such as performance, stability, and growth of the Internet often turn to BGP routing tables to obtain Internet topology. BGP routing tables provide a mapping from address prefixes to autonomous system (AS) paths. Our study, based on hundreds of thousands of traceroutes from three locations worldwide, categorizes differences between AS paths obtained from BGP routing tables and AS paths derived from traceroute paths. We find much of the disparity results from exchange points ASes (which rarely appear in BGP paths) and by groups of ASes under the same ownership. We introduce a new AS relationship, common ownership, that reflects the complexities of real-world business relationships and practices. Yet another potential cause of incongruity, that of third-party addresses, is not a significant source of discrepancy between BGP and traceroute paths, as we showed in a separate study published in PAM2003. In traceroute paths that differ for reasons other than the above causes, the traceroute AS path is usually longer than the BGP AS path and the difference is typically caused by the introduction of additional ASes in the traceroute path.

We conjecture that the observed difference in size between the cores (the sets of nodes that can reach directed cycles) of an AS graph derived from BGP and an AS graph derived from traceroute is due to the visibility of peering at exchange points in traceroute paths and alternation of ASes which is often present at the ends of traceroute paths.