-
Notifications
You must be signed in to change notification settings - Fork 7
BGP
To start with, we'll go over the BGP. Almost all routing policies inherit from this class.
This policy (and most policies) have a few data structures.
The first is a weak reference to the AS class that contains it, which can be useful for information regarding the AS information (like the ASN). For some policies, the AS information is necessary for the defenses against attacks.
The second is the localRIB at the AS. The LocalRIB class stores the best announcement (i.e. the path) to each prefix. It is a subclass of AnnContainer along with the other announcement containers, and can be seen here.
The third main data structure is the recv_queue, which can be seen here. This is how the AS stores the announcements it is receiving from a particular relationship. After storing all of the announcements for a particular relationship, the AS will then process these announcements, and add the best ones (potentially) to their localRIB.
Beyond the data structures, BGP's import and export policies are split up into three main files:
The propagation functions are in line with business economic incentives. In other words, announcements that have been received from peers or providers are only sent to customers, and customer announcements are sent to every relationship. Every time an announcement is propagated, it first attempts to propagate it using the _policy_propagate function, a hook for policies to define their own export policy based on specific conditions. If the hook does nothing, then it falls back on the _process_outgoing_ann function, which by default just calls the neighbor's receive_ann function.
The process incoming anns functions are a bit tricker. The main function here is the process_incoming_anns function. This function does the following:
- For each announcement in the recv_queue
- Check if the announcement is valid using _valid_ann, which is by default just checking if the ASN is in the AS Path to prevent loops (for but policies like ROV, it also checks if the announcement is invalid by ROA)
- Compare this announcement to the current best announcement in the local RIB using GaoRexford (to follow)
- If the new announcement is better, add it to the local RIB
The gao rexford functions define valley free routing behavior. Normally in a graph if you want to go from one node to another, you want to find the shortest path. However, in BGP, you want to find the path that makes you the most money. This algorithm is Gao Rexford. It's quite simple:
- Prefer announcements from customers (paying) over peers (free) over providers (costs money)
- Prefer announcements with the shorter AS path
- Tiebreak by lowest ASN
It's important to note that in normal BGP in the real world, tiebreaking strategies can be quite different, but since ground truth data for these tiebreaking strategies is scarce, we default to just tiebreaking by the lowest ASN.