Hi Xuesong,
> Thank you for your work about Flooding Reduction mechanism. I think it is > very useful for IGP scalability. Thank you, we very much appreciate that. > When Sarah giving presentation for > draft-chen-lsr-dynamic-flooding-algorithm-00 in LSR interim meeting, I raised > a question about how to handle multipoint failure in the flooding topology. I > remembered that draft-ietf-lsr-dynamic-flooding-04 was mentioned. I have read > this draft, especially section 6.8.11 and temporary flooding relevant > content. I think it is a valid method logically. (We have tried to raise some > examples to challenge this method, but in all these cases, this method works) > Considering that reliability of IGP is crucial for deployment, we are still > wondering whether some mathematical proof is necessary (or possible) to > guarantee that, in all the possible scenarios, proper convergence could be > achieved when using flooding reduction algorithm, just as traditional IGP > mechanism. The proof may be case by case depending on the flooding reduction > algorithm, but we think even some example or clue about how to do this will > be very helpful. A proof? Ok, I can try to be rigorous, but it’s been a very long time. I apologize in advance to Kireeti, Mr. Myers, Mr. Douglas, and Prof. Greever for what follows. Definition: Let G=(V, E) be a finite graph. F=(V, E’) is a ‘flooding topology’ on G if E’ is a subset of E and F is connected. We normally have other properties for flooding topologies, such as being bi-connected, relatively sparse, minimal diameter, and minimal degree, but those properties are not relevant for this proof. Definition: Let C=(V*, E*), V* a subset of V, E* a subset of E, be the ‘cut’ of G. This represents the failures in the topology. Let G’ = G - C, the topology after failure, and let F’ = F - C, be the flooding topology after failure. Definition: Let R = E - E* - E’. This is the set of 'recovery edges': edges that have not failed and are not part of the flooding topology. Corollary: R is finite. Proof: G is finite, by definition. Therefore E is finite, E* must be finite, and E’ is finite. Lemma 1: If G’ is connected, then F’ + R is connected. Proof: G’ = G - C = (V, E) - (V*, E*) = (V - V*, E - E*). F’ + R = (F - C) + (E - E* - E’) = (V, E’) - (V*, E*) + (E - E* - E’) = ( V - V*, E’ - E* ) + ( E - E* - E’) = ( V - V*, E’ - E* + E - E* - E’ ) = ( V - V*, E - E* - E* ) = ( V - V*, E - E* ) = G’. Q.E.D. Lemma 2: If G’ is connected, then incrementally adding edges from R to F’ will yield a connected flooding topology. Proof: By induction. Let R’ be a subset of R. Induction property: Either F' + R’ is connected, or R’ is a proper subset of R. Base case: R’ is the empty set. If F’ is connected, then F’ + R’ is connected and the property is satisfied. If F’ + R’ is not connected, R’ is empty, which is a proper subset of R. Induction case: Let r be a recovery edge in R - R’ (i.e., a new edge to add). If F’ + R’ is connected, then the property is satisfied already. If F’ + R’ + r is connected, the property is satisfied. If R’ + r = R, then by Lemma 1, the property is satisfied. Otherwise, R’ + r != R, and the property is satisfied. By our corollary, the induction must terminate. Q.E.D. Bugs, questions, and comments are welcome. Regards, Tony
_______________________________________________ Lsr mailing list [email protected] https://www.ietf.org/mailman/listinfo/lsr
