Dave, Thanks very much for commenting. I’m a bit confused about your column “Receipt Degree” and perhaps how flooding works in your proposal.
Let’s use the example from your section 4.2, where ‘a’ and ‘z’ are the roots and there are only two tiers. Suppose that ‘a’ has an update. It replicates to all lower nodes, except that the link from ‘a’ to ’3’ has failed. Per section 4.4, it seems like this is an update received from an upstream member adjacency. Since this is only a two-tier system, the lower nodes have no downstream nodes, so they do not replicate back to the upstream. How do nodes ‘b’ .. ‘z’ ever get the update? How does ‘3’? If I’m misunderstanding 4.4, and all of ‘i’, …, ‘x’, and ‘1’, …, ’n’ replicate back to ‘z’, then doesn’t it have a receipt degree higher than 2? Or are ‘i’ and ’n’ special cases that do upstream replication, resulting in paths a - i - z - 3 and a - n - z - 3? Very confused, Tony > On Nov 19, 2018, at 1:44 PM, David Allan I <[email protected]> wrote: > > HI Tony: > > Re: draft-allan-lsr-flooding-algorithm…. > > My draft falls under the “bushy” class of solutions, to borrow your > terminology. > > So mapping to your datapoints and translating what I presented in Bangkok to > actual numbers: > > Graph Fault free Single Fault Replication Receipt > Diameter Worst case Degree Degree > Diameter > K4,17 2 3 17 2 > K4,40 2 3 40 2 > K8,80 2 3 80 2 > K8,200 2 3 200 2 > K16,200 2 3 200 2 > K20,400 2 3 400 2 > K40,800 2 3 800 2 > > Worst case occurs when an inter node link fails, as the LSA from one end of > the link needs to loop back via the other root to the node at the other end > of the failed link. > > Rgds > Dave > > From: Lsr <[email protected]> On Behalf Of [email protected] > Sent: Monday, November 19, 2018 10:29 AM > To: [email protected] > Subject: [Lsr] On flooding, diameter, and degree > > > Hi all, > > I’d like to expound a bit more on a point that I made at the mike in Bangkok. > > The figures of merit for a flooding algorithm are the resulting diameter of > the flooding topology and the maximum degree of the nodes in the topology. > > The diameter is important because it says how many hops an link state update > will have to traverse before it covers the topology. This dictates what the > convergence time of the network will be. > > The degree is important because it is the measure of the amount of > replication that a node will have to do during flooding, and, more > importantly, it is also a bound on the number of times that a node can > receive replicas of the same update. If the degree is too high, then the > node can be overwhelmed by an influx of flooding, resulting in instability. > > For a flooding algorithm to be seriously considered, it is important to > characterize these results and understand how they grow under scale. In > particular, I’m concerned about tree based algorithms because they typically > have a large diameter because the tree is tall and spindly, or they end up > with a large degree, because the tree is quite bushy. > > I would very much like to see candidate algorithms present how they perform. > > Here’s a few data points from our algorithm simulations, just for comparison: > > Graph Diameter Degree > K4,17 4 10 > K4,40 4 23 > K8,80 4 22 > K8,200 4 53 > K16,200 6 28 > K20,400 5 45 > K40,800 6 43 > > Thanks, > Tony
_______________________________________________ Lsr mailing list [email protected] https://www.ietf.org/mailman/listinfo/lsr
