Large-scale testing of the Internet's Border Gateway Protocol (BGP) via topological scale-down

The Internet is a critical communication infrastructure servicing billions of end-users world-wide. Ongoing studies of the Internet's operations show that data loss and increased latency are occurring due to weaknesses in its interdomain routing protocol, BGP. Many solutions have been proposed, but few have experienced widespread adoption. Both the delayed discovery of the protocol's shortcomings, and apathy for its proposed solutions, are partially due to inadequate testing practices. Internet interdomain routing technologies are not evaluated at appropriate scale. Better testing is suggested, which incorporates the specification of large-scale experimental topologies. This is necessary, as BGP performs the distributed operation of interdomain routing across the thousands of networks composing the Internet. However, only small to moderately sized topologies can be currently accommodated by today's testing platforms. A modeling methodology based on path preserving scale-down is proposed to extend the topological scale of interdomain routing experimentation. A given Internet topology is reduced in terms of its autonomous systems (ASes) using a combination of Gaussian elimination and several graphical heuristics. The interdomain routing paths generated by BGP on this reduced topology are also preserved. Path preservation keeps the length, composition, and ordering of these routing paths unchanged. When the routing paths guiding Internet traffic among ASes are preserved across the size reduction, the large-scale traffic engineering induced by BGP can be estimated at much lower scales. Internet data losses due to certain inappropriate interdomain routing behaviors can be identified. As an example, a persistent multiple origin autonomous system (MOAS) conflict is characterized over a topology containing 8826 ASes. It is shown that this problem's large-scale characterization can be obtained using scale-down models that are 70% smaller, and thus more accommodating to common testing platforms (e.g., simulation and networking testbeds).