Bgp Divergence

BGP Divergence Computer Networks Dr. Jorge A. Cobb

Overview 

We will show how BGP diverges



Provide a formal model for the study of this divergence



Show that detecting if BGP will diverge is intractable (probably will not go through this)



We present a sufficient condition to prevent divergence



We present a dynamic solution to prevent divergence at run time

2

Conflicting Policies P u

v

d

Q

Router v prefers P Router u prefers (u v)Q

over over

Q (u v)P

Conflicting policies can cause divergence!

3

Stable Path Problem (SPP)   

Provides a formalization of BGP. Designed by T. Griffin, B. Shepherd, G. Wilfong. Each node represents an entire AS

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0)

4

Stable Path Problem (SPP)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0)

5

Stable Path Problem (SPP)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0)

6

Stable Path Problem (SPP)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0)

7

Stable Path Problem (SPP)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0)

8

Stable Path Problem (SPP)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0)

9

Stable Path Problem (SPP)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0)

10

Stable Path Problem (SPP)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0)

11

Stable Path Problem (SPP)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0)

Possible divergence! 12

Stable Paths Problem (formally) 

An instance S of the stable paths problem is a triple, S = (G, P,Λ)

• • • 

G = network graph P is the set of permitted paths Λ is the ranking of the permitted paths

We overview next each of the components.

13

Graph G 

The network is a graph G = (V, E)

• • •

V = {0, 1, 2, . . . , n} is the set of nodes 0 is the origin (destination) E is the set of undirected edges



Peers(u) = {v | {u,v} ∈ E}



A path is a (possibly empty) sequence of nodes



ε denotes the empty path

14

Permitted Paths  

For each u ∈ V, Pu is the set of permitted paths of u. For each u, u ≠ 0,

• •

  

ε ∈ Pu for each P ∈ Pu,

• the first node in P is u • the last node in P is 0. • P is a simple path

P 0 = { (0) } If P = (u, v, w, . . . , 0) ∈ Pu, then v is the next hop of P P = union over of all u of Pu 15

Ranking Function  

λu is a ranking function over Pu If P ∈ Pu, then

λu (P) represents how desirable P is to u. 

If P1, P2 ∈ Pu and λu(P1) < λu (P2), then

P2 is said to be preferred over P1 

For every u and P ∈ Pu, where P ≠ ε,

λu (ε) = 0 and λu (P) > 0 16

S = (G, P,Λ) (1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0)

17

Stable Path Assignments A path assignment is a function π that gives a path to each node u π (u) ∈ Pu 



Given a path assignment π, choices(π,u) gives the possible new paths of u. choices(π,u) = { (u,v)π(v) | {u,v} ∈ E} ∩ Pu if u ≠ 0 { (0) } if u = 0 note: empty path is always a choice although I did not explicitly include it above 18

Path assignment example  

Let π(u) be the red path at u Choices(0) = { (0) } Choices(4) = { (4,3,0) } Choices(1) = { (1,3,0) (1,0) } Choices(2) = { (2,0) } Choices(3) = { (3,0) } (1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0) 19

Stable Path Assignments (continued ..) 

best(π,u) = best possible choice for u best(π,u) = P iff (∀P′, P′∈ choices(π,u), λu(P) ≥ λu (P′))



A path assignment is stable iff for all u, π(u) = best(π,u)

20



best(0) = { (0) } best(1) = { (1,3,0) } best(2) = { (2,0) } best(3) = { (3,0) } (1 3 0) (1 0)

best(4) = { (4,3,0) }

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0) 21

Solvable SPP 

A SPP S = (G, P,Λ) is solvable iff there is a stable path assignment of S. (This path assignment is known as a “solution”).



Note that some nodes may have an empty path in a given solution. (if choices(π,u) only has empty path then best(π,u) is the empty path)



Note that a solution may not be reachable from all initial states.



Solvable does not imply convergence (convergence: from all initial states, a solution is always reached)



Convergence of course implies solvable 22

Stable Path Assignment Example (2 1 0) (2 0)

5

(5 2 1 0)

2

(1 3 0) (1 0)   

0 1

4

(4 2 0) (4 3 0)

3

(3 0)

Always reaches a stable path assignment (specifically, the one above) Notice node 5 A solution need not represent a shortest path tree, or a spanning tree. 23

Multiple Solutions (1 2 0) (1 0)

(1 2 0) (1 0)

(1 2 0) (1 0)

1

1

1

0

0

2 (2 1 0) (2 0)

DISAGREE

2

0 (2 1 0) (2 0)

(2 1 0) (2 0)

First solution 24

2

Second solution

Multiple solutions can result in “Route Triggering” (1 0) (1 2 3 0)

1

(2 3 0) (2 1 0)

2

(3 2 1 0) (3 0)

1

1

primary link

3

0

2

0

(2 3 0) (2 1 0)

2

(1 0) (1 2 3 0)

0

backup link

3

3

Remove primary link

Restore primary link

25

(3 2 1 0) (3 0)

BAD GADGET : No Solution (1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 2 0) (4 3 0)

0 (3 4 2 0) 3 (3 0)

26

SURPRISE : Beware of Backup Policies (1 3 0) (1 0)

1

2

(2 1 0) (2 0)

0 (3 4 2 0) 3 (3 0)    

4

This is a stable configuration What if link (4, 0) goes down? Bad gadget! (no solution) Not robust to link failures 27

(4 0) (4 2 0) (4 3 0)

PRECARIOUS: Solvable, but may get trapped! (1 5 7 8 0) (1 3 5 7 0) (1 5 7 0) 1

(5 7 8 0) (5 7 0)

(2 5 7 8 0) (2 1 5 7 0) (2 5 7 0) 2

(7 8 0) (7 0) 7

5 3 (3 5 7 8 0) (3 4 2 5 7 0) (3 5 7 0)

0 4

8

(4 2 5 7 8 0) (4 2 5 7 0) (4 3 5 7 0)

This part has a solution only when node 8 is assigned the direct path (8 0).

(8 7 0) (8 0)

As with DISAGREE, this part has two distinct solutions

28

Problem: Find a stable state 

Problem: find a stable system state

• 

i.e., for all u, π(u) = best(π,u)

Two approaches: static and dynamic

•

Static: given S = (G, P,Λ) find a stable path assignment (i.e. write an algorithm whose input is S and output is π)

•

Dynamic: let each AS (i.e. node) continue to execute π(u) := best(π,u) until s table path assignment is found

29

What to do! Static Approach

Dynamic Approach Extend BGP with a dynamic means of detecting and suppressing policy-based oscillations?

Automated Analysis of Routing Policies (This is very hard NP-hard actually).

Inter-AS coordination

These approaches are complementary 30