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

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

HI Tony:

Comments in line:

From: Tony Li <[e-mail]> On Behalf Of [e-mail]
Sent: Monday, November 19, 2018 2:13 PM
To: David Allan I <[e-mail]>
Cc: [e-mail]
Subject: Re: [Lsr] On flooding, diameter, and degree


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.

DA> Repeated here for the time impaired….

                               Spine
               +---+ +---+ +---+ +---+           +---+
               | a | | b | | c | | d | o o o  | z |
               +---+ +---+ +---+ +---+           +---+
                /|\                                           /|\
 \|/                                                                                      \|/
+---+ +---+ +---+       +---+           +---+ +---+ +---+          +---+
| i | |ii | |iii| o o o | x |           | 1 | | 2 | | 3 | o o o | n |
+---+ +---+ +---+       +---+           +---+ +---+ +---+          +---+
/|\                              /|\             /|\                                /|\


DA> And repeated here in a more useful form

[cid:image003.png@01D48016.5B79C5D0]

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

DA> You will have an ambiguous link on each of the diverse paths between the roots where it is upstream on one tree and downstream on the other. In the above example link i-z and link a-n are ambiguous. Hence the LSA from ‘a’ that did not go ‘a’-‘3’ would then go ‘a’-‘n’-‘z’-‘3’. ‘n’ receiving from ‘a’ on an ambiguous link reflects on all member adjacencies except that of origin.

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?
DA> No, only ‘I’ (to ‘a’)  and ‘n’ (to ‘z’) reflect upwards as those are the two links that have both upstream and downstream status.

Or are ‘i’ and ’n’ special cases that do upstream replication, resulting in paths a - i - z - 3 and a - n - z - 3?
DA> I think you have it, as well as why ‘I’ and ‘n’ are special cases.

Very confused,
DA> Hopefully this clears it up

Rgds
Dave







On Nov 19, 2018, at 1:44 PM, David Allan I <[e-mail]<mailto:[e-mail]>> 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 <[e-mail]<mailto:[e-mail]>> On Behalf Of [e-mail]<mailto:[e-mail]>
Sent: Monday, November 19, 2018 10:29 AM
To: [e-mail]<mailto:[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