Subject: [Lsr] Dynamic flooding path computation

From: [email-masked]
Date: Thu, 2 Apr 2020 16:57:00 -0700

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

---

From: Peter Psenak <[email-masked]>
Date: Fri, 3 Apr 2020 10:11:46 +0200

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-masked] wrote:
> _______________________________________________
> Lsr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lsr
> 
>

---

From: [email-masked]
Date: Fri, 3 Apr 2020 08:58:58 -0700

Hi Peter,

> 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?

I will certainly stipulate the possibility.

However, as I’ve said from the start, I have some grave concerns about debugging this and making it inter-operable. Every node choice, every edge selection, from the selection of the initial node, through DFS, through BFS, needs to be identical. The weighting between degree and diameter needs to deterministic and fixed.

We would have to have extensive deployment experience before I would feel comfortable pouring concrete on this.

So, if someone would like to make a distributed version, we will support it.  But we aren’t in a place where we’re ready to drive that effort. Please feel free.

Tony