BGP DivergenceComputer NetworksDr. Jorge A. CobbOverview We will show how BGP diverges Provide a formal model for the study of this divergence Detecting if BGP will diverge is intractable (probably will not go through this)2will not go through this) We present a sufficient condition to prevent divergence There are dynamic solution to prevent divergence at run time, at the expense of efficiency (probably will not go through this)Conflicting Policiesu v dPQ3Router v prefers P over QRouter u prefers (u v)Q over (u v)PConflicting policies can cause divergence!Stable Path Problem (SPP) Provides a formalization of BGP. Designed by T. Griffin, B. Shepherd, G. Wilfong. Each node represents an entire AS12(1 3 0)(2 1 0)410432(1 3 0)(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 1 0)(2 0)Stable Paths Problem (formally) An instance S of the stable paths problem is a triple, S = (G, PPPP,Λ)• G = network graph•PPPPis the set of 102(1 3 0)(1 0)(2 1 0)(2 0)5•PPPPis the set of permitted paths• Λ is the ranking of the permitted paths We overview next each of the components.043(3 4 2 0)(3 0)(4 2 0)(4 3 0)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 edges6•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 pathPermitted Paths For each u ∈ V, PPPPuis the set of permitted paths of u. PPPP0= { (0) } (always, by definition, 0 can reach 0 ☺) PPPP1= { (1, 3, 0), (1, 0), ε } PPPP2={ (2, 1, 0), (2, 0), ε }PPPP3= { (3, 4, 2, 0), (3, 0), ε}7PPPP= { (3, 4, 2, 0), (3, 0), ε}10432(1 3 0)(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 1 0)(2 0)Permitted Paths: details PPPP0= { (0) } For each u, u ≠ 0,• ε ∈ PPPPu• for each P ∈ PPPPu, •the first node in P is u8•the first node in P is u•the last node in P is 0.•P is a simple path If P = (u, v, w, . . . , 0) ∈ PPPPu, then v is the next hop of P PPPP = union over of all u of PPPPuRanking Function λuis a ranking function over PPPPu λu (P) represents how desirable P is to u.If P1, P2∈PPPPuand 10432(1 3 0)(1 0)(3 4 2 0)(4 2 0)(2 1 0)(2 0)9If P1, P2∈PPPPand λu(P1) < λu(P2), then • P2is said to be preferred over P1 For every u and P ∈ PPPPu, where P ≠ ε,• λu (ε) < λu (P) 43(3 4 2 0)(3 0)(4 2 0)(4 3 0) λ(3, 0) < λ(3 ,4, 2, 0)• λ(ε) < λ(3, 0) λ(1, 0) < λ(1, 3, 0)• λ(ε) < λ(1, 0)Path Assignments A path assignment is a function π that gives a path to each node u (think of it as the “state” of the system) π(u) ∈ PPPPu Below:• π(2) = (2 1 0), obviously this is a problem since 1 is nottaking path (1 0) at this moment10taking path (1 0) at this moment10432(1 3 0)(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 1 0)(2 0)Path Assignments Given a path assignment π, choices(π,u) lists the possible new paths of u.choices(π,u) = { (u ; π(v)) | {u,v} ∈ E } ∩ PPPPu if u ≠ 0{ (0) } if u = 0note: empty path is always a choice although I did not explicitly 11note: empty path is always a choice although I did not explicitly include it above10432(1 3 0)(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 1 0)(2 0)choices(1) = {ε, (1, 3, 0), (1, 0)}choices(2) = {ε, (2, 0)}choices(3)? choices(4)?Stable Path Assignments best(π,u) = best possible choice for u, given a path assignment πbest(π,u) = P iff P∈choices(π,u) ∧12P∈choices(π,u) ∧(∀ P′, P′∈ choices(π,u), λu(P) ≥ λu(P′)) A path assignment is stable iff for all u,π(u) = best(π,u)• Stable, NOT optimal! • Nodes may not end up with their highest ranking pathExample best(0) = { (0) } best(4) = { (4,3,0) }best(1) = { (1,3,0) }best(2) = { (2,0) }best(3) = { (3,0) } Choices(0) = { (0) }Choices(1) = { (1,3,0), (1,0), εεεε}Choices(2) = { (2,0), εεεε }Choices(3) = { (3,0), εεεε }Choices(4) = { (4,3,0), εεεε}1310432(1 3 0)(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 1 0)(2 0)Choices(4) = { (4,3,0), εεεε}SPP Examples 10432(1 3 0)(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 1 0)(2 0)Bad gadget: this SPP instance has no stable path assignment14(3 0)(4 3 0)10432(1 3 0)(1 0)(3 0)(4 3 0)(4 2 0)(2 1 0)(2 0)Good gadget: this SPP instance has a stable path assignment (in red)Note: 2 is not taking its highest ranked pathExecuting The System An execution step of the system consists of the following• Pick any node u arbitrarily (with some fairness, of course, don’t ignore some nodes forever)•Compute best(π,u), where π is the current path 15•assignment• π(u) := best(π,u) Repeat forever until can’t do another step (i.e. a stable path assignment is found)Executing Bad Gadget12(1 3 0)(1 0)(2 1 0)(2 0)1610432(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 0)12(1 3 0)(1 0)(2 1 0)(2 0)Executing Bad Gadget1710432(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 0)12(1 3 0)(1 0)(2 1 0)(2 0)Executing Bad Gadget1810432(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 0)12(1 3 0)(1 0)(2 1 0)(2 0)Executing Bad Gadget1910432(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 0)12(1 3 0)(1 0)(2 1 0)(2 0)Executing Bad Gadget2010432(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 0)12(1 3 0)(1 0)(2 1 0)(2 0)Executing Bad Gadget2110432(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 0)12(1 3 0)(1 0)(2 1 0)(2 0)Executing Bad Gadget2210432(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 0)12(1 3 0)(1 0)(2 1 0)(2 0)Executing Bad Gadget2310432(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 0)12(1 3 0)(1 0)(2 1 0)(2 0)Executing Bad Gadget2410432(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 0)Possible divergence!Solvable SPP A SPP S = (G, PPPP,Λ) 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 pathin a 25Note that some nodes may have an empty pathin a given solution. • if choices(π,u) only has empty path then best(π,u) is the empty path Some SPP instances may have more than one solutionExample of SPP solutions10432(1 3 0)(1 0)(3 4 2 0)(3 0)(4 2 0)(4 3 0)(2 1 0)(2 0)Bad gadget: has no solution26(3 0)(4 3 0)10432(1 3 0)(1 0)(3 0)(4 3 0)(4 2 0)(2 1 0)(2 0)Good gadget: has a single solution (in red)Note: 2 is not taking its highest ranked pathSingle Solution Example5(5 2 1 0)0(2 1 0)(2 0)(4 2 0)(4 3 0)4227 Has a single solution (in red above) Notice node 5 (empty path) A solution need not represent a shortest path tree, or a spanning tree. 0(1 3 0)(1
View Full Document
Unlocking...