An autonomous system is a network under a single administrative control and is identified with an autonomous system number (ASN). Thus, the Internet can be thought of as a network of networks, or more specifically, a network of autonomous systems.
There are separate protocols for routing traffic inside an AS, such as Open Shortest Path First (OSPF). This is known as intradomain routing. There are also protocols for how routing should be done between ASes such as BGP, the border gateway protocol. This is interdomain routing which is the focus of our study.
Although the Autonomous Systems (AS) graph has been studied for years, we still lack tools that can scale up to its size and complexity.We address these limitations in a new tool, called BGPSimPy, which is open source and runs efficiently on commodity hardware with standard tools and packages.
50,000+ routing trees for use with BGPSimPy are available here. The complete dataset is 18.9GB compressed, 49.61GB uncompressed.
Routing TreesThese routing trees can be loaded via SciPy's io mmread and are meant to be used along with BGPSimPy available here:
BGPSimPy on GitHubBGPSimPy creates a unique subgraph for every autonomous system (AS) y, called a routing tree. Paths from any AS x to AS y can then be found using the routing tree for AS y.
Routing trees are represented as sparse adjacency matrices. More specifically, if there is a provider to customer relationship between AS x and AS y where x is the provider and y is the customer, (x,y)=2 and (y,x)=3 in the matrix. If x and y have a peer to peer relationship, (x,y)=(y,x)=1. If no edge exists between x and y, (x,y)=(y,x)=0.
The routing trees are labelled like so: dcompletey.mtx where y is the autonomous system number associated with that tree. Thus, to find a path from ANY AS x to AS y, simply load dcompletey.mtx and use BGPSimPy's find path functions.
This material is based upon work supported partially by the NSF (1314297, 1420716, 1444871, 1518523, and 1518878); DARPA (FA8750-15-C-0118); and AFRL FA8750- 15-2-0075).