Hi Tony,
it may be worth to make your algorithm one of the standardized
distributed algorithms. There might be some work to make it
deterministic, like the selection rules mentioned below, but it should
be doable.
What do you think?
thanks,
Peter
On 03/04/2020 01:57, [email protected] wrote:
Hi,
In this morning’s session, Acee asked a question about node selection as part
of path computation. I would like to expound a bit in the spirit of full
transparency.
First off, the selection of nodes is NOT vital to the algorithm. That said, we
found that applying some heuristics helped make the algorithm slightly more
efficient in some cases.
We select the starting node for the first cycle (n0 in the slides) by picking a
node with the highest possible degree in the base topology. Ideally, we’d
really like to pick the node that’s at the center of the graph (and to be very
precise, a node in the centroid or Jordan center), but the computation of this
is somewhat expensive and doesn’t seem worthwhile.
At the end of the first cycle, we now have a set of bi-connected nodes that
each have a degree of 2 in the flooding topology. We could start the next
iteration with any of these nodes, but we already know that n0 has the highest
degree of anything in the topology, so we can always start the next iteration
based off of n0. Note that we do NOT want to continue doing this for
subsequent iterations because the degree of n0 would quickly spiral out of
control. Instead, we want to continue to bound the degree of the nodes in the
flooding topology, so we want to select a node that is on the flooding
topology, but minimizes both degree and diameter. Again, we are not trying for
optimality, so we apply a simple weighting function to aid in this selection.
I hope this makes our approach very clear.
Regards,
Tony
_______________________________________________
Lsr mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/lsr
_______________________________________________
Lsr mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/lsr
