Re: [Lsr] On flooding, diameter, and degree

[David Allan I <[e-mail]>]

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 <[e-mail]> On Behalf Of [e-mail]
Sent: Monday, November 19, 2018 10:29 AM
To: [e-mail]
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