Ok, Tony thanks for taking the effort to clarify your example, this is much
more tractable for me. So, if the algorithms are behaving correctly as
prunners as defined in the -prz- draft (so they're not ships in the dark or
start to optimize parts of network that is not running the algorithm or
make assumptions about optimizations occuring there, otherwise there is no
way to interoperate multiple algorithms running at same time AFAIS since
the algorithms basically start to muck with stuff on parts of network they
have no idea semantically about) the following will happen
A1 and B1 will form a component. If A2/B2 are connected to A1/B1 via some
adjacency then A1/B1/A2/B2 will be a single component running X.
Same will happen for nodes A3/B3 and A4/B4 running algo Y.
I assume here in between them in SubA and SubB there is no algorithm (zero
prunner) or another algorithm (which however would end up being two
components since they are separated by the X and Y component). Not
important really.
And here I think I understand now where we have the disconnect and possibly
the definition of the prunner is not precise enough in the draft as it
stands
A prunner MUST build CDS only within its component, i.e. algorithm X will
only optimize the A1/B1/A2/B2 component and cannot start to "decide about
other parts of the network" like assuming what Y will do or tell nodes in Y
what to do. This would amount to give a simile something like "proxy
purging" and cannot work since prunners MUST not have any semantics about
each other (otherwise attempt to build algorithms independently and
interoperate those is impossible).
Y can optimize anything within the A3/B3/A4/B4 component only basically
building a CDS of this part of topology.
Any link, as the prunner definition says, where the algorithm on the other
side doesn't match MUST be flooded (that connect all those CDSes of each
algorithm together in a "sufficient" way although possibly not "optimal" in
some way)
So, the outcome of prunners running will be "X component builds a CDS
within component of nodes signalling to run X", "Y does same for nodes
running Y". Any adjacency in X seeing another algorithm (or no algorithm)
on the other side of adjacency will be flooded, same applies for Y. Whole
thing guarantees total CDS over the network.
Does that kind of framework prevent "leader based distributed algorithms".
Not at all. The only necessary part is actually already there, the
"supported algorithm" signalling. So to interoperate the leader based
distributed algorithm must optimize CDS only within its component as well,
otherwise it assumes something about stuff between them (zero prunner
optimization is allowed in the draft but further leading discussion) and we
end up in the case where multiple algorithms "assuming" stuff about other
algorithms or parts of topology not running the algorithm will cause loss
of total coverage of the graph with the resulting CDS.
For the centralized computation the leader can only compute results for
nodes signalling support for centralized results to interoperate, otherwise
it runs as ship in the dark assuming behavior of the parts that don't
signal (and here is the case again where "no signal" basically indicates
zero-prunner with known behavior) or signal something else as supported. If
the leader starts to optimize across everything disregarding which node
supports what and hence assuming they either take the result or fully flood
then the leader runs basically a ship in the dark and ships in the dark
never interoperate. Observe as well that leader computing centralized
solution must build CDS per component signalling support for the
centralized results.
Hence, the prunner definition is possibly underspecified (or only assumes
from the context in the text and example that CDS is built only within the
component by an algorithm) while your assumption was that any algorithm can
go and somehow magically force parts of topology not running the algorithm
to behave in certain way or assume what another algorithm running on this
part of topology will do in its component. under those assumptions, yes,
algorithms cannot interoperate in building a full CDS over the graph since
they either have to understand each other semantics or are ships in the
night.
I hope that clarifies things a bit better
Practical implications of all this is really that we need an indication of
"supported algorithm" (for leader based) and ideally "running algorithm"
for leaderless case (even with leader, I show example why things will not
work particularly well with distributed without signalling. Both can even
reuse the same signalling if registry distinguishes between "leaderless"
and "leader based" algorithms, even if we choose to have same algorithm in
2 variants)
Example why leader based distributed even now must still always advertise
"supported algorithm" to guarantee CDS if it wants to take advantage of the
zero prunner, i.e. default flooding behavior (assuming that leader
signalling _forces_ the supported algorithm to run, otherwise we always
need a running algorithm signalling)
Let's take a simple triangle
A
/. \
B.--- C
B and C both support an algorithm X signalled by leader but B does not
advertise the "supported algorithm" TLV so C doesn't know it runs X. So in
a sense B ends up running it without advertising it.
here what will happen if C assumes now that B fully floods
B and C will both run the same algorithm deciding that C floods to A
C being unaware that B runs X or anything else due to missing signalling
will assume that B floods fully and hence remove link A-C from the flooding
graph
Result is that A will not be covered at all.
The only other remedy would be for C to not assume that B will flood
(basically declaring it some other funky algorithm it's invisible) and
always flood A-C which will generate a much less "optimal" CDS in terms of
links.
I hope that clarifies things. I'm more than happy to add the "only build
CDS in own component" in the definition of the prunner in the -prz- draft
if that helps to bring the issue to a closure
thanks
-- tony
On Tue, Nov 26, 2024 at 8:17 PM Tony Li <[email protected]> wrote:
>
> Hi all,
>
> Here’s another counter example. As with the previous one, the network has
> two portions: A and B. Subnetwork A has nodes A1, A2, A3, A4, ... and
> subnetwork B has nodes B1, B2, B3, B4, ….
>
> Nodes A1, A2, B1, and B2 are running algorithm X. They collectively
> decide that flooding between the two subnetworks should happen on links
> (A3, B3) and (A4, B4) and they prune (A1, B1) and (A2, B2) from the
> flooding topology.
>
> Nodes A3, A4, B3, and B4 are running algorithm Y. They collectively decide
> that flooding between the two subnetworks should happen on links (A1, B1)
> and (A2, B2) and they prune (A3, B3) and (A4, B4) from the flooding
> topology.
>
> As a result, the flooding topology between subnetwork A and B is
> partitioned.
>
> 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]
