Report

STABLE PATH PROBLEM Based on The Stable Path Problem and Interdomain Routing Timothy G. Griffin, Bruce Shepherd, Gordon Wilfong Presented by: Sangeetha A. J. Overview BGP basics Simple Path Vector Protocol Stable Path Problem Dispute Wheels 2 Border Gateway Protocol The only interdomain routing protocol used in the internet today. Not based on shortest path. Path vector protocol. 3 How is BGP different from shortest path algorithms? Policy based metrics Independent routing policies at each AS These policies could be conflicting BGP can be considered a distributed algorithm to solve the Stable Path Problem. 4 BGP route selection Order of preference 1. Highest local preference 2. Shortest AS path 3. Lowest IP address for next hop 5 Peering transformation Composition of three transformations 1. Export policies r1 = export (u w, r) 2. Path vector transformation r2 = PVT (u w, r1) 3. Import policies r3 = import (u w, r2) 6 Peering transformation pt (u w, r) = import (u w, PVT(u w, export(u w, r))) Suppose u0 is originating AS P = uk uk-1 …..u1 u0 Route record received is pt( uk uk-1, pt( uk-1 Ranking function λ uk uk-2, ……..pt ( u1 u0 )))..)) (P) 7 Simple Path Vector Protocol process spvp(u) { receive P from w { rib-in(uw) := P if rib(u) != best(u) { rib(u) := best(u) for each v in peers(u) { send rib(u) to v } } } } 8 Stable path problem Mathematical formulation that captures the semantics of any path vector protocol. Does every node have a stable route to one destination node? Node 0 is assumed to be origin or destination of all routes. 9 SHORTEST - 1 1 2 0 4 3 10 SHORTEST 1- Path assignment Node Time 1 2 1 2 3 4 10 20 30 - 10 20 30 430 11 SHORTEST 1 1 2 0 4 3 12 Stable path problem Undirected graph G = (V, E) V- set of nodes , E - set of edges Path is either empty path or a sequence of nodes (vk vk -1…..v1 v0 ) Pv - set of permitted paths from v to origin If P1 , P2 ϵ Pv and λ v (P1) < λ v (P2) then P2 is preferred over P1. 13 Stable path problem An instance of stable path problem, S = (G,P,Λ) Graph together with permitted paths and ranking function for each node. Some properties P0 = {(0)} for all v ϵ V – {0} ◦ ϵ ϵ Pv (null path is always present in the set) ◦ λ v (ϵ) =0 , λ v (P) > 0 for P ≠ ϵ (null path has lowest preference) ◦ P ϵ Pv then P is a simple path (no repeated nodes). 14 Stable path problem A path assignment is a function π function that maps a node to a permitted path. π(u) ϵ Pu All possible permitted paths at u , choices (π, u) = { (u v) π(v) | {u,v} ϵ E } ∩ Pu (u ≠ 0) { (0)} otherwise 15 Stable path problem W is subset of Pu such that each path in W has a distinct next hop. Best path in W, best(W, u) {P ϵ W with maximal λ u (P) ϵ W≠Φ otherwise } Path assignment π is stable at node u if π(u) = best (choices (π, u) ,u) 16 Stable path problem π is stable, if it is stable at each node u Path assignment vector (P1 , P2 ,….., Pn ) where π(u)=Pu If π is stable and π(u)= (u w) P, then π(w)= P. Thus stable path implies tree rooted at the origin. The stable path problem, S = (G,P,Λ) is solvable if there is a stable path assignment for S. 17 SHORTEST 2 1 2 0 4 3 18 SHORTEST 2 1 2 0 4 3 19 Good Gadget 1 2 0 4 3 20 Good Gadget Node Time 1 2 3 4 1 10 20 30 - 2 130 210 30 430 3 130 20 30 430 21 Good Gadget 1 2 0 4 3 22 Bad Gadget 1 2 0 4 3 23 Bad Gadget Node Time 1 2 3 4 1 10 20 30 - 2 130 210 30 420 3 130 20 3420 430 4 10 20 30 420 5 130 210 30 420 24 Naughty Gadget 1 2 0 4 3 25 Naughty Gadget Node Time 1 2 3 4 1 10 20 30 - 2 130 210 30 420 3 130 20 3420 430 4 10 20 30 420 5 130 210 3420 430 6 10 20 30 26 Multiple solutions possible 1 2 0 1 2 0 1 2 0 27 Observations about SPP A stable path problem is safe if SPVP always converges. SPP solvability does not imply safety. ◦ Naughty gadget has single solution but SPVP may diverge. Oscillations are possible. It always diverges if there is no solution. Multiple stable solutions are possible for a SPP. 28 Dispute Wheels A sequence of nodes , ui . A sequence of non-empty paths, Qi and Ri. R k-1 u k-1 u0 R0 u1 Q0 Qk-1 Q1 R1 Q2 Qi+1 u2 v Qi u i+1 Ri ui 29 Dispute Wheels A circular set of dependencies between routing policies that cannot be simultaneously satisfied. Ri is a path from ui to ui+1 Qi ϵ Pui Ri Qi+1 ϵ Pui λ ui (Qi) < λ ui (Ri Qi+1 ) Preferred path for every node goes around the wheel instead of following the spoke. 30 Dispute Wheel of Bad Gadget u2 u0 R2 1 2 Q0 Q2 0 R0 Q1 3 4 R1 u1 31 Dispute Wheel of Naughty Gadget R0 u0 3 Q0 0 2 4 u1 Q1 R1 32 Properties of dispute wheel No dispute wheel implies Solvability Unique solution Safety Robustness 33 Dispute wheel Construct a sequence of subsets of V, V0 , V1… Corresponding path assignments π0, π1…. Direct path P = (u1 u2) P2 P2= π(u2) Add nodes to the set, if its highest rank consistent with πi is direct path. If you are unable to find nodes whose paths are consistent with existing path assignments, you get a dispute wheel. 34 Good Gadget 1 2 0 4 3 35 Good Gadget 0 1 2 3 4 Node Time 1 (0) - - - - 2 (0) - - 30 - 3 (0) 130 - 30 430 4 (0) 130 210 30 430 36 Bad Gadget 1 2 0 4 3 37 Bad Gadget Node Time 1 0 1 2 3 4 (0) - - - - 38 Solvability R0 u1 u0 Q0 v1 R1 u2 39 Unique solution R0 u1 u0 R3 R1 u3 R2 u2 40 Robustness If stable path problem, S, has no dispute wheel then S is robust. S is fragile if S is solvable but there exist some E’ (subset of E) such that S/E’ is not solvable. 41 Bad Backup- Fragile 1 2 0 4 3 42 Conclusion A network with unique solution can have a dispute wheel, if transient oscillations are present. This is a rigid condition. Even in networks with multiple stable states, we get dispute wheels. 43 Complementary approaches Operational guidelines Static analysis of routing policies Dynamic detection 44 45