Bgp Divergence Cont

BGP Divergence Continued Computer Networks Dr. Jorge A. Cobb

Solving an SPP  

Given an SPP, can we check if it is solvable? Sure,

• •

   

enumerate all possible states For each state, check if it is stable

Exponential complexity!! Can be done for only tiny examples. Can we do better? Solvability of SPP is NP-Complete

•

What does that mean? The best way we know takes exponential time in the size of the input (i.e. the size of S) 2

Network Algorithms for Solving SPP 

Centralized (static):

• • •



All nodes learn the SPP S = (G, P,Λ) Solve SPP locally Exponential worst case

Distributed (dynamic):

• • • •

Pick the best path from the set of your neighbor’s paths, tell your neighbors when you change your mind Can diverge Not guaranteed to find a solution, even when one exists No bound on convergence time

3

Distributed Solution may wander forever = assignment

= solution

4

Another Picture

Can diverge must converge

MAY converge

SPP solvable

5

must diverge

Naughty Gadget 

Has a unique solution (see below) (1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 3 0) (4 2 0)

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

However, it could diverge FOREVER, depending on timing. 6

Naughty Gadget (divergence) Assume we start in this state. The next sequence of slides give you a sequence of steps that diverge forever.

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 3 0) (4 2 0)

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

7

Naughty Gadget (divergence)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 3 0) (4 2 0)

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

8

Naughty Gadget (divergence)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 3 0) (4 2 0)

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

9

Naughty Gadget (divergence)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 3 0) (4 2 0)

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

10

Naughty Gadget (divergence)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 3 0) (4 2 0)

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

11

Naughty Gadget (divergence)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 3 0) (4 2 0)

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

12

Naughty Gadget (divergence)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 3 0) (4 2 0)

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

13

Naughty Gadget (divergence)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 3 0) (4 2 0)

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

14

Naughty Gadget (divergence)

(1 3 0) (1 0)

1

2

(2 1 0) (2 0)

4

(4 3 0) (4 2 0)

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

15

BGP converge problems 

SOLVABILITY

•



REACHABILITY

•



In every stable state, whether AS v has a path to AS w

ASYMMETRY

•



The existence of a stable state

In every stable state, whether the AS path from AS v to w is the reverse path from AS w to v

TRAPPED

•

The existence of a trap (never reach a stable state if you enter the set of trapped states).

16

BGP converge problems (Cont.) 

K-Robust

•



Unique

•



Will solvable set of routing policies remain solvable under any k links failure Uniqueness of final state

Multiple

•

Whether a solvable set of routing policies has more than one final state

17

Complexity results       

REACHABILITY is NP-complete ASYMETRY is NP-complete SOLVABILITY is NP-complete; TRAPPED is NP-hard K- ROBUST is NP-hard UNIQUE is NP-hard MULTIPLE is NP-complete

18

A Sufficient Condition for Sanity 

If an instance of SPP has an acyclic dispute digraph, then Static (SPP)

Dynamic SPP

solvable

safe (can’t diverge)

unique solution

predictable restoration

all sub-problems uniquely solvable

robust with respect to link/node failures

19

Dispute Digraph 



The “nodes” in the graph correspond to paths in the SPP instance. There are two types of arcs (or edges) in the directed dispute graph:

• •





Conflict arcs Transmission arcs.

If this graph is acyclic, then the SPP instance has all the nice properties of the previous slide. If this graph has cycles, we cannot infer anything.

20

Dispute Arc P

v

u … (u v)P … (u v)Q ...

… Q … P ...

Q Note: it is also possible that (u v)Q is not allowed at u

Gives the dispute arc

Q

0

(u v)P 21

Transmission arc u

P

v

… (u,v)P ...

… P ...

Gives the transmission arc

P

(u,v)P 22

0

Dispute Digraph Example 130 10

210 20

1

2 0

20

10

420

210

3420

3

4

3420 30

430 420

CYCLE

430

NAUGHTY GADGET

130 30

23

Dispute Digraph Example cont. 130 10

210 20

1

2 0

3

4

3420 30

420 430

NAUGHTY GADGET

10 210 130 • Consider any node (say 2), think of it as u • Take any path in u, say, 2 1 0 • The next node in the path (i.e. 1) is v • If path 1 0 is in node 1, then there is a transmission arc from 1 0 to 2 1 0. • If there is a path in 1 with higher rank than 1 0, (yes there is, its 1 3 0), and 2 1 3 0 is ranked lower at 2 than 2 1 0 (it is lower ranked, since it is not even allowed at 2) then there is a conflict between 1 3 0 and 2 1 0. 24

Dispute Wheels uk

u0

Rk

Q0

Qk

R0

u1

 u0, u1, … , uk are nodes (not necessarily distinct)

R1

 Ri is a path from ui to u(i+1)

u2

Q1

 Qi is a path from ui to 0

Q2

 Qi and Ri Q(i+1) ∈ Pui  λui(Qi) ≤ λui (Ri Q(i+1))

Q(i+1)

There exists a dispute wheel iff there exists cycle in the dispute digraph

Qi u(i+1)

Ri

ui

25

An Application c is a cost function on edges in SPP. c is coherent if all cycles have positive cost (> 0). An SPP specification is consistent with c if … Q … P ...

v

Q P

implies

c(P) ≥ c(Q)

consistent with coherent c acyclic dispute digraph will always converge 26

Dynamic Execution Model 





For our purposes (to make our life easier) we will consider 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)). Execution is simple

•

Do forever:

•

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

• If there is a node u such that π (u) ≠ best(π,u), then • π(u) := best(π,u)

27

A Dynamic Solution 

Extend SPP with a history attribute



A route’s history contains a path in the dispute digraph that “explains” how the route was obtained,



A route history will contain a dispute cycle if and only if a policy dispute is dynamically realized.



If a route’s history contains a cycle, then suppress it ….



Nodes read their neighbor’s current path and the associated path history of the path.

28

Updating the history 

If your new path is better than your previous path (higher ranked)

•



Add your new path (with a + sign) to the history of your neighbor.

If your new path is worse (lower ranked) than your previous path

•

Add your PREVIOUS path (with a – sign) to the history of your neighbor

29

BAD GADGET 210 20

2 4

420 430

0 3

1

3420 30

130 10 30

path 1 : (1 0) 2 : (2 0) 3 : (3 4 2 0) 4 : (4 2 0)

e e e e

…

…

…

1 : (1 0) 2 : (2 1 0) 3 : (3 0) 4:( )

e (+ 2 1 0) (- 3 4 2 0) (- 4 2 0) (+ 2 1 0) (- 4 2 0) (+ 2 1 0)

1 : (1 3 0) 2 : (2 1 0) 3 : (3 0) 4:( )

(+ 1 3 0) (- 3 4 2 0) (- 4 2 0) (+ 2 1 0) (+ 2 1 0) (- 3 4 2 0) (- 4 2 0) (+ 2 1 0) (- 4 2 0) (+ 2 1 0)

1 : (1 3 0) 2 : (2 0) 3 : (3 0) 4:( )

(+ 1 3 0) (- 3 4 2 0) (- 4 2 0) (+ 2 1 0) (- 2 1 0) (+ 1 3 0) (- 3 4 2 0) (- 4 2 0) (+ 2 1 0) (- 3 4 2 0) (- 4 2 0) (+ 2 1 0) (- 4 2 0) (+ 2 1 0)

…

…

31

TIME

…

event history for path

A CYCLE!

What’s going on ?

Dynamic cycles of event history correspond exactly to static cycles in the dispute digraph.

32