Computer Networks Dr. Jorge A. Cobb BGP Divergence Continued2 Statically Solving an SPP l Given an SPP, can we check if it is solvable? l Sure, a) enumerate all possible states b) For each state, check if it is stable l Checking for safety is even worse (check all sub-instances) l Solvability of SPP is NP-Complete a) Exponential complexity!! (that we know of)3 A Sufficient Condition for Sanity l If an instance of SPP has no dispute wheel, then Static (SPP) solvable Dynamic SPP unique solution converges predictable restoration all sub-problems uniquely solvable robust with respect to link/node failures (safe)4 Dispute Wheels u0 § u0, u1, … , uk are nodes (not necessarily distinct) § Ri is a path from ui to u(i+1) § Qi is a path from ui to 0 § Qi and Ri Q(i+1) ∈ Pui § λui(Qi) < λui (Ri Q(i+1)) u1 u2 ui u(i+1) uk Q0 Q1 Q2 Qk Q(i+1) Qi R0 R1 Ri Rk 0Example of Dispute Wheel “Bad Triangle” Its “dispute wheel” 5 2 1 0 3 (1 2 0) (1 0) (2 3 0) (2 0) (3 1 0) (3 0) 2 1 0 3 “Bad Gadget” A “dispute wheel” 2 1 0 4 3 (1 3 0) (1 0) (2 1 0) (2 0) (3 4 2 0) (3 0) (4 3 0) (4 2 0) R1 R2 R3 Q2 Q1 Q3Sufficient Condition for a Solution l Theorem: if an SPP instance does not have a dispute wheel, then it has a solution l Note: this is a sufficient but not necessary condition a) A dispute wheel could exist and still we have a solution (can you add nodes to bad triangle and make it converge while still having a dispute wheel???) l We will build a spanning tree such that: a) If we complete the construction then there is a solution b) If we “get stuck”, then there is a dispute wheel • Equivalently (contrapositive): no dispute wheel è spanning tree built à solution exists 6Ensuring solution IS a spanning tree l Some solutions have some nodes with an empty path (not a spanning tree). l We modify the SPP instance by adding an additional node x, and adding for each node u, the path (u x 0), that is ranked lowest among all paths at u. l You can show the solutions are the same as before, except no one has an empty path. 7 5 (5 2 1 0) 0 (2 1 0) (2 0) (1 3 0) (1 0) (3 0) (4 2 0) (4 3 0) 3 4 2 1 5 (5 2 1 0) (5 x 0) 0 (2 1 0) (2 0) (2 x 0) (1 3 0) (1 0) (1 x 0) (3 0) (3 x 0) (4 2 0) (4 3 0) (4 x 0) 3 4 2 1 x (x 0)Tree construction l For a tree T (not necessarily spanning), define V(T) to be the vertices (nodes) of T l Let S be our SPP instance. l You can show the following (show it on your own) • After each step of our construction, the sub-instance S’ obtained from S by removing all nodes not in V(T) and all paths with nodes not in V(T) is stable. 8 5 (5 2 1 0) (5 x 0) 0 (2 1 0) (2 0) (2 x 0) (1 3 0) (1 0) (1 x 0) (3 0) (3 x 0) (4 2 0) (4 3 0) (4 x 0) 3 4 2 1 x (x 0) 0 (1 3 0) (1 0) (3 0) 3 1 T T is stable Note that (1 0) remains since both 1 and 0 are in TAdding a node to the tree l A path P is said to be consistent with tree T if once P encounters a node in T, the rest of P is along T • I.e., once in T you remain in T l Notation: for a node v in tree T, let T(v) be the path from v to 0 along T. 9Adding a node to the tree (continued) l Consider any node u not in T such that: a) It has a neighbor v in T, and (u, v)T(v) is allowed at u. (notation: v is the first node in T(v)) b) Of all the paths P in Pu that are “consistent with T” path (u, v)T(v) (i.e. directly into T) is the highest ranked of these paths. l If such u is found, add u to T • Note: such u may not exist. • In this case, we are “stuck”, and T does not become spanning. 10Example: build the tree l First: T = {0, x} (x satisfies both (a) and (b) above) l Note that, because of this, now ALL nodes u always have at least one path consistent with T, i.e., (u, x, 0) 11 5 0 (2 1 0) (2 0) (2 x 0) (1 3 0) (1 0) (1 x 0) (3 0) (3 x 0) (4 2 0) (4 3 0) (4 x 0) 3 4 2 1 x (x 0) (5 2 1 0) (5 x 0) 0 xExample: build the tree l Next candidates: a) Because the tree is still small, all paths in all nodes are consistent with T. b) E.g., 1 has three consistent paths: (1 3 0), (1 0), (1 x 0) c) However, in only node 3, the highest ranked one, i.e. (3 0), has its next hop in T d) We thus add 3 to the tree. 12 5 0 (2 1 0) (2 0) (2 x 0) (1 3 0) (1 0) (1 x 0) (3 0) (3 x 0) (4 2 0) (4 3 0) (4 x 0) 3 4 2 1 x (x 0) (5 2 1 0) (5 x 0) 0 xExample continued … 13 0 x 3 5 0 (2 1 0) (2 0) (2 x 0) (1 3 0) (1 0) (1 x 0) (3 0) (3 x 0) (4 2 0) (4 3 0) (4 x 0) 3 4 2 1 x (x 0) (5 2 1 0) (5 x 0) l Next candidates: a) Again, because the tree is still small, all paths in every node not in T, i.e., all paths in nodes 1, 2, 4, and 5, are consistent with T. b) E.g., 1 has three consistent paths: (1 3 0), (1 0), (1 x 0) c) However, of these nodes, only node 1, the highest ranked one, i.e. (1 3 0), has its next hop in T d) We thus add 1 to the tree.Example continued … 14 0 x 3 5 0 (2 1 0) (2 0) (2 x 0) (1 3 0) (1 0) (1 x 0) (3 0) (3 x 0) (4 2 0) (4 3 0) (4 x 0) 3 4 2 1 x (x 0) (5 2 1 0) (5 x 0) l Next candidates: a) All nodes not in T have a consistent path, but, not all paths in all nodes not in T (in nodes 2, 4, and 5) are consistent with T. E.g., (5 2 1 0) …
View Full Document
Unlocking...