Report

Part IV BGP Modeling BGP Is Not Guaranteed to Converge! BGP is not guaranteed to converge to a stable routing. Policy inconsistencies can lead to “livelock” protocol oscillations. Goal: Design a simple, tractable and complete model of BGP modeling Example application: sufficient condition to guarantee convergence. 2 BGP is Solving What Problem? Underlying problem Distributed means of computing a solution. Shortest Paths RIP, OSPF, IS-IS X? BGP X can aid in the design of policy analysis algorithms and heuristics, aid in the analysis and design of BGP and extensions, help explain some BGP routing anomalies, provide a fun way of thinking about the protocol3 Separate Dynamic and Static Semantics Static semantics: BGP policies Stable Paths Problem Dynamic semantics: BGP SPVP SPVP: Simple Path Vector Protocol A distributed algorithm for solving Stable Paths Problem 4 What is Stable Paths Problem? Example: A graph of nodes and edges, Node 0, called the origin, For each non-zero node, a set or permitted paths to the origin. This set always contains the “null path”. A ranking of permitted paths at each node. Null path is always least preferred. 222 10 0 5 5210 2 4 420 430 3 30 0 1 130 10 most preferred … least preferred (not 5null) A Solution to SPP A solution is an assignment of permitted paths to each node such that node u’s assigned path is either the null path or is a path uwP, where wP is assigned to node w and {u,w} is an edge in the graph, each node is assigned the highest ranked path among those consistent with the paths assigned to its neighbors 6 A Solution to SPP A solution need not represent a shortest path tree or a spanning tree 210 20 5 5210 2 4 420 430 3 30 0 1 130 10 7 There can be Multiple Solutions to an SPP 120 10 120 10 1 120 10 1 0 0 2 210 20 DISAGREE 1 2 210 20 First solution 0 2 210 20 Second solution 8 Multiple Solutions Can Occur Due to Recovery: 10 1230 1 230 210 2 1 primary link 0 2 0 1 10 1230 2 230 310 0 backup link 3210 30 3 Remove primary link 3 3 3210 30 Restore primary link 9 Ranking BGP Paths Highest local Preference Shortest AS path Length Origin: IGP<EGP<INCOMPLETE Lowest MED value IBGP preferred over EBGP Lowest IGP cost Tie breaking 10 Bad Gadget: No Solution Stage 1: 1: [10] 2: [210] 3: [30] Stage 2: 1:[130] 2:[20] 3:[320] Back to stage 1 2 210 20 4 0 1 130 10 3 320 30 11 Bad Gadget: No Solution Stage 1: 1: [10] 2: [20] 3: [320] Stage 2: 1:[130] 2:[210] 3:[30] Back to stage 1 2 210 20 4 0 1 130 10 3 320 30 12 Has A Solution, But Can Get Trapped: 4 310 3120 5 5310 563120 53120 4310 453120 43120 1 3 120 10 0 6 2 6310 643120 63120 This part has a solution only when node 1 is assigned the direct path (1 0). 210 20 As with DISAGREE, this part has two distinct solutions 13 Has A Solution, But Can Get Trapped: 4 310 3120 5 5310 563120 53120 4310 453120 43120 1 3 120 10 0 6 2 6310 643120 63120 This part has a solution only when node 1 is assigned the direct path (1 0). 210 20 As with DISAGREE, this part has two distinct solutions 14 How To Solve An SPP? Exponential complexity Just enumerate all path assignments, And check stability of each…. NP-complete 3-SAT can be reduced to SPP 15 Distributed Algorithms to Solve SPP OSPF-like Distributed topology, path ranks Solve SPP locally Exponential worst case How to avoid loops if multiple solutions exist? RIP-like: Pick the best path form neighbors’ paths Tell neighbors about changes Can diverge Not guaranteed to find a solution even if it exists No bound on convergence time 16 SPVP Protocol Pick the best path available at any time process spvp[u] { receive P from w { rib-in(uw) := u P if rib(u) != best(u) { rib(u) := best(u) foreach v in peers(u) { send rib(u) to v } } } } 17 SPVP and SPP SPVP wanders around assignment space SPP Solvable must converge SPVP Can Diverge must diverge 18 A sufficient condition for sanity If an instance of SPP has an acyclic dispute digraph, then Static (SPP) Dynamic (SPVP) solvable safe (can’t diverge) unique solution predictable restoration all sub-problems uniquely solvable robust with respect to link/node failures 19 Dispute Digraph Example 130 10 210 20 1 2 0 20 10 420 210 3420 3 4 3420 30 420 430 BAD GADGET II CYCLE 430 130 30 20 Dispute Wheels R_k u_0 u_k Q_0 Q_k •At u_i, rank of Q_i u_1 R_1 is less than or equal u_2to rank of R_iQ_(i+1) Q_1 R_0 Q_2 Q_(I+1) Q_i u_(i+1) R_i u_i •There exists a dispute wheel iff there exists cycle in the dispute digraph 21 Dispute Wheel Example 1230 120 10 2310 230 20 1 2 3 1 1 2 0 0 3 3 2 3120 310 30 22 A Dynamic Solution Extend SPVP 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 …. 23