Re: [Lsr] Dynamic flooding path computation

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, tony.li@tony.li 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
> Lsr@ietf.org
> https://www.ietf.org/mailman/listinfo/lsr
> 
> 