Bgp No Divergence

Stable Internet Routing Without Global Coordination Lixin Gao, & Jennifer Rexford,

Computer Networks Dr. Jorge A. Cobb

Dynamic execution model (extended)  



Paper assumes a “shared memory model” as opposed to a message passing model. Assume that each node can “read” the state of its neighbor (i.e. if (u,v) ∈ E, then u can read π(v) and v can read π(u)). Multiple nodes can execute at once

•

Do forever:

• If there is a subset of nodes u , …, u , such that 1

•

•

k

π (ui) ≠ best(π,ui) for 1 ≤ i ≤ k then π(u1), … , π(uk), := best(π,u1), … , best(π,uk)

We assume a “fair” execution that does not ignore some nodes. 2

Problem  



Too much overhead to maintain histories Difficult to gather all policies and check for cycles in dispute graphs Can we select some practical guidelines?

•



If the guidelines are followed, the system is stable (always reaches a steady state)

Their approach: hierarchies

• •

You avoid circular conflicts by introducing hierarchies of nodes Policies are based on the hierarchy

3

BGP Import, Export, Path Selection 

There are three types of policies:

• • •



Import Policy: of the paths offered by my neighbors, which ones will I allow? (i.e. “import” the path) Path Selection: given the paths offered by my neighbors which satisfy my import policy, which one do I like the best? Export Policy: given my current path, will I tell my neighbor of this path or tell my neighbor that I have no path? (i.e., “export” the path)

Note: in the Griffin paper, import/export policy was not explicit, only “list of allowed paths” was given.

•

A path is allowed only if it exists in the export policy of my neighbor and in my import policy 4

Route fields  

Assume an AS A receives a route r from its neighbor B Route r has several fields

• • • •

r.as_path: the list of ASms from B to the destination r.MED: if multiple links between A & B, MED determines which one B prefers that A uses (multi-exit discriminator) r.community: you can organize ASms into “communities”, and mentioned the community to which this path belongs. r.local_pref: how desirable the path is (local preference), and is assigned by A.

5

Path Selection Policy 

If we have multiple BGP speakers per AS then, path selection is as follows: a) From the paths that satisfy the import policies •

Choose those with the greatest local_pref

b) Then, out of the remaining paths from above choose the ones with least # of AS hops to the destination c) Then, for each neighboring AS B, •

Of the paths chosen above, if multiple paths from B (one per BGP border router), choose the one with greatest MED value (we left at most one path per AS neighbor)

d) Choose the path whose internal cost to reach the border router is least. 6

Neighbor Relationships 

For each neighbor B of AS A, we have one of the following relationships:

• • •

B is the service provider of A: in this case, B is the “access point” (or perhaps one of several) over which A accesses the rest of the Internet B is a customer of A: in this case, A is the service provider or B B is a peer of A: neither is a provider or customer of the other. They are simply “peers” who help each other.

7

AS relationship graph

Provider-to-customer edges must form a directed acyclic graph (DAG)

8

Export policy restrictions - providers 

Exporting to a provider: In exchanging routing information with a provider: • An AS can export its routes and the routes of its customers. • However, it can not export routes learned from other providers or peers. • That is, an AS does not provide transit services for its provider.

Provider-tocustomer relationship Exported path to destination

9

Export policy restrictions - peers 

Exporting to a peer: In exchanging routing information with a peer: • An AS can export its routes and the routes of its customers • However, it can not export the routes learned from other providers or peers. • That is, an AS does not provide transit services for its peers.

Provider-tocustomer relationship Exported path to destination

10

Export policy restrictions - customers 

Exporting to a customer: In exchanging routing information with a customer:

•

•

An AS can export its routes, as well as routes learned from its providers and peers. (Routes from other customers?) That is, an AS does provide transit services for its customers. 11

Exported path to destination

Still not good enough 





The following system, even though it satisfies the export policies, is not safe Every node starts directly to zero Then choose the neighbor clockwise

1 (1 3 0) (1 0)

3 (3 2 0) (3 0)

2 (2 1 0) (2 0) 0

12

Additional Policy Requirements Must prefer customer paths over those of peers and providers

13

The end result 



Theorem 1: For a BGP system that has only customer–provider and peer-to-peer relationships (no backup links), if all ASms follow guideline A, then the BGP system is inherently safe (always converges) The proof consists of two steps:

• •

First, show that there exists a steady state (by construction) Second, show that the system always converges to this steady state.

14

“cust_only” route 



I say that a route r is a “cust_only” route if for every pair of adjacent nodes (A,B) in the route, A is a service provider of B Lemma 0 : a node can only export a “cust_only” path to its peers and service providers g h







i





By the export policies, g can only export to its peers/providers a path learned via a customer (e.g. via h) The same for h, h can only export to g paths learned from i. We can continue this argument and notice that only a cust_only path is exported. E.g., assume the path takes a “turn” at a node i By the export policies, i cannot export this path to h, and thus h cannot inform g about it. g cannot export what it does not know 15

Lemma 1(a)  



A stable state always exists Our proof is by construction, the state is constructed by starting from an empty path for all nodes, and then selective executing nodes. Nodes are executed in two phases

•

Phase 1 – “bottom-up” (all customers of u are executed before u)

•

Phase 2 – “top-down” (all service providers of u are executed before u)

16

Invariant 

Level(g) = length of longest path from g to the bottom of the hierarchy (following serv.prov  cust edges)



Execute nodes by level (0, 1, 2 …) We argue that after executing level i, for all nodes g at level j, j ≤ i,



•

If there exists a cust_only path at g in the hierarchy, then g will have chosen such a path and remain with this path always (g is stable)

17

Base case   

Nodes at level 0 These have no customers (level 0) A node g at level 0

• •

If g = d, g chooses (d) as its path and is stable If g ≠ d, then g does not have a cust_only path (irrelevant for the invariant)

18

Induction Step 

Execute level i+1, assume invariant holds for lower levels.  If no cust_only path in hierarchy

a

b

g

f

v



w

at g, then no proof obligation Othewise, • Let v,w have cust_only paths in the hierarchy

•

h

x

y

•

19

By induction, v,w have chosen such a path, and are stable

Let x,y not have cust_only paths (and thus can never chose a cust_only path as their path)

Induction Step (continued)

a

v

v,w are stable (induction hypothesis) and do have a cust_only path



By lemma 0, if x,y ever choose a path, they cannot export it to g



f,h,a, and b are ignored by g, because g prefers a path via a customer, i.e. a path given by v or w, which from above they do have a path



I.e., the set of choices of g is stable



g picks the best from its choices and remains stable

b

g

f



w

h

x

y

20

Phase 2 

 



Depth (g) = max distance from top of the hierarchy to g. Execute by depth: 0, 1, 2, … Invariant: after executing depth i, for any g in depth at most i, g’s path is stable (regardless of future executions) We consider executing only nodes without a cust_only path in the hierarchy

•

If you do have a cust_only path in the hierarchy, you are stable after phase 1.

21

Base case 

g has depth 0: no service provider 

g

f

h 

v

w

x

y



 

v,w,x,y cannot have a cust_only path, since we assume g does not have one By lemma 0, v,w,x,y cannot advertise a path to g By lemma 0, f,h can only advertise cust_only path • If they do have a cust_only path, by Phase 1, it is stable I.e., the choices of g are stable g chooses the best choice and remains stable 22

Induction Step (very similar) a

b



g

f



h 

v

w

x

y



v,w,x,y,f and h same argument as before, either they provide no path or provide a stable path. By induction hypothesis, a and b (with lower depth) already are stable. I.e., the choices of g are again stable g chooses the best choice and remains stable

23

Lemma 1(b)  







A stable state is always reached. How? Let g0, g1, … be the order in which nodes were executed in the two phases of lemma 1 (a) ANY execution if fair, will contain a subsequence where the above nodes are executed I.e., the real execution executes nodes g0, g1, … with multiple nodes executed “in between” u0,0, u0,1, u0,2 … g0, u1,0, u1,1, u1,2 … g1, … The claim (by the authors) is that the same state as in Lemma 1 (a) will be reached.

24

Constrained Peer-to-peer relationships  

  

Thus far, any two pair of nodes may be peers If we restrict this, we can give greater routing flexibility, and allow the routes via a peer to have equal local_pref as routes via customers. We group nodes into “peer equivalent classes” Think of the peer relationship as an ≡ The paper calls these equivalent classes “clusters”

25

Peer clusters and the cluster graph 

Two AS nodes are in the same cluster if there is a path from one to the other via peer edges in the AS graph



A cluster C1 has an edge to cluster C2 if an AS in C1 is a service provider whose customer is in C2



A cluster C has a self-edge if a service provider and its customer are both in C.

26

Clusters and the cluster graph

Requirement: the cluster graph must be acyclic (violated above) 27

Additional (more relaxed) policy requirements 

Paths via peers can have the same local_pref as customer paths (no greater than the “lowest” customer path)

28

Bad example     





This system diverges (cyclic cluster graph) Initially none of the ASms have a route. Activate AS 5 and AS 4. Assume ASms 1, 2, and 3 are always activated together. The first activation leads ASms 1, 2, and 3 to (1 0), (2 0), and (3 4 5 0), respectively. On the next activation, they switch to (1 2 0), (2 3 4 5 0), and (3 1, 0) The process may repeat indefinitely. The order of paths reflects the local_pref value not the overall ranking of the path 29

The end result 



Theorem 2: For a BGP system that has only customer–provider and peer-to-peer relationships (no backup links) and the cluster graph is acyclic, then, if all ASms follow guideline B, then the BGP system is inherently safe (always converges) The proof consists of two steps:

• •

First, show that there exists a steady state (by construction) Second, show that the system always converges to this steady state.

30

Lemma 2a    

A stable state exists Phase 1 – same as before (top down) This implies that a cluster is executed only after all its clusters “below” it are executed. Note, in Phase 1 of Lemma 1, the elements of a cluster could be executed in any order.

31

Additional restriction on Phase 1 





Order the peers in a cluster as follows candidate(g) = shortest(paths exported by customers of g with highest local_pref at g) If length(candidate(g)) < length(candidate(h))

•



Execute g first 

32

All customers executed before any member of the cluster I.e., candidate(g) fixed (see invariant next page)

Invariant 

After execution, a node will satisfy one of the following:

• •



Its path is a cust_only path, and this holds forever The node will never have a cust_only path, even if one exists in the hierarchy

Base case

• • •

Lowest cluster (no element has customers) If g = d, then g’s cust_only path is (d) and this is stable If g ≠ d, then since no customers, g will never have a cust_only path

33

Induction step 

a

b 

g

f

h 

v

w

x

y 



By induction hyp, all of v,w,x,y either have a fixed cust_only path, or have no cust_only path By Lemma 0, v,w,x,y advertize only cust_only paths to their providers I.e., v,w,x,y (from the view of their providers) are fixed, and are either empty or have a cust_only path. Hence, cadidate(f), candidate(g), candidate(h) are all fixed (perhaps empty) If candidate(g) is empty, then g will never have a cust_only path (satisfies the invariant)

34

Induction step (continued) 

a

b 

g

f

h 

v

w

x

y 

Assume candidate(g) and candidate(f) not empty, and candidate(h) empty. By Guideline B, any path from a or b is ignored by g (because candidate(g) not empty) Note that f will advertise (f,candidate(f)) to g or nothing (Lemma 0) If local_pref(candidate(g)) > local_pref(f,candidate(f)) then

•



g always picks candidate(g) and remains stable Otherwise, from Guideline B,

local_pref(candidate(g)) = local_pref(f,candidate(f))

35

Induction step (continued) a

If length(candidate(g)) < length(f,candidate(f)) • g chooses always candidate(g) and is stable



length(candidate(g)) ≥ length(f,candidate(f))



If length(candidate(g)) > length(f,candidate(f))

b

g

f

v



w

h

x

y

• • •

36

f executes first, and by induction (and Lemma 0), f always offers an empty path or (f,candidate(f)) to g. If f offers empty, g chooses its path and stays stable. else g chooses the one via f (shorter) and stays stable (since both input paths are stable)

Induction step (continued) 

a

b

g

f

v

w

h

x

y

If length(candidate(g)) = length(f,candidate(f)) • Again, f executes first, and by induction (and Lemma 0), f always offers an empty path or (f,candidate(f)) to g. • If offers empty, g chooses its path, and stay stable (since all input paths are stable) • If f offers (f,candidate(f)), then g has two equal choices • BGP always break ties in a deterministic way (e.g. IP address) • I.e., g will always choose the same from these two paths, and be stable. 37

Phase 2 of Lemma 2(a) 

Same as before.

38

Lemma 2(b)  

From any starting state, we reach a stable state Proof is the same as in Lemma 1(b)

39

Backup links   

The paper also deals with backup links Please read it on your own Yes, you are responsible for it 

40

Remarks 



If links and or nodes are added/deleted, or if the policies change, as long as they satisfy the given requirements the system will remain stable. Can we argue that these systems will have an acyclic dispute graph?

41