Thanks Tony, good drill down. I see two points here: 1. the point I take here is that in the example resulting prunner framework flooding covers the full graph, i.e. correctness as in "sufficient flooding" is still assured. 2. the solution may be _not_ optimal in terms of constructing a single CDS, i.e. on the boundaries basically full flooding is mandated by the prunner framework. Actually the most extreme case is where _every_ node in the network runs a different algorithm and the prunner framework says "well, flood on all links with different algorithm on the other side". Then it all collapses into full flooding again.
If that's my correct reading then please observe that the -prz- draft does NOT state that in mixed algorithm scenarios _optimal_ flooding in any sense is guaranteed (optimality here seems to mean "CDS with minimal number of links"), it only says that prunner framework will guarantee "sufficient" flooding to build an overall CDS, not less and not more. In fact that's the paragraph that is possibly bits cryptical to most saying that you'd need a "meta-prunner" algorithm for such stuff or synchronization of boundaries of a component (funny enough, the considerations in such design start to be closely related to arbitrary hierarchy principles ;-). There are other considerations but they become even more arcane and AFAIS achieving an "optimal" CDS when components with multiple algorithms are mixed is in pragmatic terms not possible. So, if we agree that prunner framework (i.e. miximing multiple algorithms) does guarantee "sufficient" flooding (i.e. full CDS) but does NOT guarantee any "only necessary" flooding then we're in sync. And it's perfectly fine AFAIS if the WG decides that working on "multiple algorithm mix in the network" is not something to be pursuited, it will be sufficient then to e.g. extend the 97xx to provide leader-based and leaderless signalling as two options (just like there is centralized computed and distributed already) and say that "mixing both modes or multiple algorithms under leaderless is outside the scope of the document". Not every problem under the sun needs to be solved by a WG and practical implications of such scope limitations AFAIS are limited since in practical purposes mixing limits blast radius on migrations and nothing else really AFAIU ;-) So I guess I wasn't specific enough when I said that I don't see a counter example for -prz- framework not being correct. By correctness I always meant "any mix of algorithms being prunners in a network will always deliver _sufficient_ flooding" and not implied any kind of flooding optimality. thanks --- tony On Wed, Nov 20, 2024 at 10:57 PM Tony Li <[email protected]> wrote: > > Hi all, > > Tony P. asked for a counter-example to why neighbor-only algorithm > information is sufficient. This email attempts to articulate just such an > example. > > Suppose that we have a bi-partite network, with two halves, A and B. Part > A contains nodes A1, A2, A3, …. Part B contains nodes B1, B2, B3, …. > > The two halves are connected by three links (A1, B1), (A2, B2), and (A3, > B3). > > The correct flooding topology in this situation is to select exactly two > of the three links. Selecting only one of the links would create a single > point of failure. Selecting all three links leads to unacceptable and > unnecessary flooding. > > Suppose that A1 and B1 are running algorithm X. All other nodes are > running algorithm Y. > > Suppose that under algorithm X, links 2 and 3 are selected. Therefore, A1 > and B1 choose to prune (A1, B1). Further, suppose that under algorithm Y, > links 1 and 2 are selected. Therefore, nodes A3 and B3 choose to prune (A3, > B). Now, only (A2, B2) is selected, creating a single point of failure. > > The key points here are simple: > > - An algorithm makes assumptions about how other nodes in the topology are > going to behave. If multiple algorithms are in play, those assumptions may > not hold. > > - Two concurrent algorithms, while each individually correct, can still > produce a flawed flooding topology if they are asked to interoperate. > > - Full flooding at the boundary between the algorithms is not sufficient > to correct the situation. > > Regards, > Tony > > _______________________________________________ > Lsr mailing list -- [email protected] > To unsubscribe send an email to [email protected] >
_______________________________________________ Lsr mailing list -- [email protected] To unsubscribe send an email to [email protected]
