AS Graph

Home

Tutorial

AS Graph

The AS Graph is the start of our BGP simulations. In the diagrams showed in our previous background section, each of those ASes were connected in a directed acyclic graph, using peer-to-peer, and provider-to-customer connections.

In BGPy, we divide an AS Graph into three parts (as can be seen in the bgpy_pkg/bgpy/as_graphs/base folder here)

• ASGraphCollector: Downloads the raw data needed to build the AS Graph
• ASGraphConstructor: Actually builds the ASGraph object
• ASGraph: contains the information related to the AS topology

By default, the simulator uses the CAIDA topology given in it's serial-2 dataset, and you can see the implementation of these three base classes here.

The ASGraph class itself stores the ASes in an as_dict attribute, where the keys are the ASNs, and the values are the as_objects. This is essentially the sole owner of the AS object. If an AS object is deleted out of this dictionary, it will be reclaimed in memory. The AS Graph also has a few AS Groups as attributes, both as sets of ASNs and as sets of AS objects, for convenience. These groups can be changed by modifying the additional_as_group_filters that are passed into the init of this class seen here

Each AS in the graph has a tuple of references to AS objects for peers, customers, and providers, and can be seen here. These references are weak references since they tend to be cyclical, and once the AS graph goes out of scope, we want the memory to be reclaimed immediately due to the large size of the ASGraph. The AS class also contains various useful properties, such as a property for stub, multihomed, transit, input_clique, etc (see them in the class here. Lastly, each AS object contains the routing policy as an attribute.

(for people that are interested in how we manage the memory of the AS graph, see here, otherwise feel free to skip): Python uses reference counting for memory management. Every object has a reference count that goes up when other objects refer to it. If an object is in scope, it's reference count goes up by 1. If the object is placed in the list, the list refers to that object, and it's reference count goes up by 1. When an objects reference count goes down to 0, it gets reclaimed in memory. The issue for our particular graph is that objects __ refer to each other __. This means that their reference count will never go down to 0. Instead - we use weak_proxy for the relationships between ASes to avoid this issue. We also do this later on, with an AS, and it's corresponding routing policy

Next: Routing Policies