Subject: Re: [Lsr] Fwd: New Version Notification for draft-li-dynamic-flooding-04.txt

From: Peter Psenak <[email-masked]>
Date: Fri, 06 Apr 2018 16:57:41 +0200

Hi Tony,

while I appreciate the flexibility associated with the centralized 
computation of the flooding topology, it has some drawbacks as well:

1. "flooding topology" must be flooded. This makes the flooding 
dependent on the flooded data itself.

2. The extra flooding of "flooding topology" adds some delay in the 
convergence towards the new "flooding topology".

Have you considered the distributed computation of "flooding topology" 
using some standardized algorithm?

Eventually we can support multiple standardized algorithms. A node can 
advertise support for several algorithms and the "active" algorithm is 
selected based on some criteria that would guarantee that all nodes in 
the flooding domain select the same one.

thanks,
Peter

On 27/03/18 18:07 , [email-masked] wrote:
>
> Hi all,
>
> I’ve submitted an updated version of my draft.  Several changes:
>
> - This collapses the two documents into one, so IS-IS is now included.
>   Placeholders are there for OSPF.
> - I’ve expanded the discussion of failure modes.
> - Minor bug fixes.
>
> Your comments are solicited…
>
> Tony
>
>
>> Begin forwarded message:
>>
>> *From: [email-masked] <mailto:[email-masked]>
>> *Subject: **New Version Notification for draft-li-dynamic-flooding-04.txt*
>> *Date: *March 27, 2018 at 9:01:30 AM PDT
>> *To: *"Tony Li" <[email-masked] <mailto:[email-masked]>>
>>
>>
>> A new version of I-D, draft-li-dynamic-flooding-04.txt
>> has been successfully submitted by Tony Li and posted to the
>> IETF repository.
>>
>> Name:draft-li-dynamic-flooding
>> Revision:04
>> Title:Dynamic Flooding on Dense Graphs
>> Document date:2018-03-26
>> Group:Individual Submission
>> Pages:17
>> URL: https://www.ietf.org/internet-drafts/draft-li-dynamic-flooding-04.txt
>> Status: https://datatracker.ietf.org/doc/draft-li-dynamic-flooding/
>> Htmlized: https://tools.ietf.org/html/draft-li-dynamic-flooding-04
>> Htmlized: https://datatracker.ietf.org/doc/html/draft-li-dynamic-flooding
>> Diff: https://www.ietf.org/rfcdiff?url2=draft-li-dynamic-flooding-04
>>
>> Abstract:
>>   Routing with link state protocols in dense network topologies can
>>   result in sub-optimal convergence times due to the overhead
>>   associated with flooding.  This can be addressed by decreasing the
>>   flooding topology so that it is less dense.
>>
>>   This document discusses the problem in some depth and an
>>   architectural solution.  Specific protocol changes for IS-IS, OSPFv2,
>>   and OSPFv3 are described in this document.
>>
>>
>>
>>
>> Please note that it may take a couple of minutes from the time of
>> submission
>> until the htmlized version and diff are available at tools.ietf.org
>> <http://tools.ietf.org>.
>>
>> The IETF Secretariat
>>
>
>
>
> _______________________________________________
> Lsr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lsr
>

---

From: [email-masked]
Date: Fri, 6 Apr 2018 08:19:46 -0700

Hi Peter,

Thank you for your comments.

> while I appreciate the flexibility associated with the centralized computation of the flooding topology, it has some drawbacks as well:
> 
> 1. "flooding topology" must be flooded. This makes the flooding dependent on the flooded data itself.

Absolutely true. If the computation of the topology is incorrect, that would certainly be a bug. 

> 2. The extra flooding of "flooding topology" adds some delay in the convergence towards the new "flooding topology”.

Since we distribute the flooding topology before there are topology failures, it would seem like the latency is not a significant concern.

> Have you considered the distributed computation of "flooding topology" using some standardized algorithm?

Yes, Kireeti raised this in London as well. There are some practical issues with this. How do we ever converge on an algorithm? 

There are many perspectives on what an adequate flooding topology might be. Different administrations have different considerations and risk tolerances. 

Debugging is going to be more challenging, as inconsistencies between two nodes with different ideas of the topology will be difficult to detect until there is a catastrophic failure.

I’m trying to do something practical, and it seems like doing this in a centralized fashion is the quickest, easiest, and most robust way forward.

> Eventually we can support multiple standardized algorithms. A node can advertise support for several algorithms and the "active" algorithm is selected based on some criteria that would guarantee that all nodes in the flooding domain select the same one.

Seems like that would also require some administrative input.

So, I agree that that’s a technical possibility, but I think that there’s significant problems in making that work. I prefer to focus on something that we can implement more quickly.

Tony

---

From: Peter Psenak <[email-masked]>
Date: Fri, 06 Apr 2018 17:50:24 +0200

Hi Tony,

if we start with a single standardized algorithm, that is easy to 
implement and deploy. We can leave the door open for additional 
algorithms to be defined later together with the selection mechanism.

I have the feeling that the dependency of the "flooding topology" on the 
flooded data is going to bring more complexity, than the selection of 
the distributed algorithm to be used, if we ever need to support more 
then one.

thanks,
Peter

On 06/04/18 17:19 , [email-masked] wrote:
>> convergence towards the new "flooding topology”.
>
>
> Since we distribute the flooding topology before there are topology
> failures, it would seem like the latency is not a significant concern.
>
>
> Yes, Kireeti raised this in London as well. There are some practical
> issues with this. How do we ever converge on an algorithm?
>
> There are many perspectives on what an adequate flooding topology might
> be. Different administrations have different considerations and risk
> tolerances.
>
> Debugging is going to be more challenging, as inconsistencies between
> two nodes with different ideas of the topology will be difficult to
> detect until there is a catastrophic failure.
>
> I’m trying to do something practical, and it seems like doing this in a
> centralized fashion is the quickest, easiest, and most robust way forward.
>
>
> So, I agree that that’s a technical possibility, but I think that
> there’s significant problems in making that work. I prefer to focus on
> something that we can implement more quickly.
>
> Tony
>
>

---

From: Rob Shakir <[email-masked]>
Date: Fri, 06 Apr 2018 16:02:30 +0000

Peter,

How do we transition between algorithms in the approach that you suggest?
Do all non-stub devices need to be upgraded to support the new algorithm
before such time as we can use it? (I think so, because otherwise some
non-stub device cannot be guaranteed to flood to its downstream stub
devices - so we may end up isolating some devices if any device transitions
before all nodes support it).

The advantage of having something advertised is that one can compute it
centrally - and keep the per-node functionality simply obeying the
advertised flooding graph. From an operational perspective, this means that
one can introduce new experimental flooding topology computation approaches
in a manner that is decoupled from needing to do software upgrades across
the whole network. I can also implement non-standard flooding topology
computations based on the network topology which could be only applicable
to that particular network (consider if I wanted to do something like take
into account shared-risk information in the algorithm to allow the
most-SRLG disjoint flooding topology or so).

This is in addition to the points Tony made. I think this
centralised-computation-and-flooded approach is elegant. If the error
handling behaviour for not being able to parse the flooding topology is to
revert to flooding everywhere, then it seems non-destructive too.

Cheers,
r.

---

From: Robert Raszuk <[email-masked]>
Date: Fri, 06 Apr 2018 18:05:42 +0000

I agree with Rob & Tony.

Converging on single algorithm across zoo of vendors is not going to happen
bearing in mind that every single change to such algorithm will require a
massive 1000s nodes software upgrade each time.

Note that even if IETF converges industry may not and that is a practical
aspect.

With current proposal this is just one time upgrade.

Thx,
R.

---

From: "Les Ginsberg (ginsberg)" <[email-masked]>
Date: Fri, 6 Apr 2018 20:06:57 +0000

I think this discussion has already gone much too far in the direction of customized flooding optimizations. Such is the nature of the engineering mind – give us a problem to solve and we’ll come up with a plethora of solutions.

The right perspective (for me anyway) is this:

IGPs have been  popular as distribution mechanisms in part because of the reliability of  their flooding process. This wasn’t easy to achieve – and those of us who have been in the business long enough have seen attempts to create something equivalent fall flat on their face because they couldn’t handle the corner causes. Simple yet robust has been the guiding principle and both IGPs do this well.

It is also useful to remember that bandwidth utilization for IGP flooding is not a problem which we need to solve. It has been demonstrated – even long ago with much less bandwidth than we have today – that IGP flooding bandwidth isn’t a concern. So proposals which suggest we might need to come up with an algorithm that optimizes for bandwidth or SRLGs or whatever criteria one could imagine seem unnecessary – as well as incestuous. And they certainly complicate the problem.

I agree with Peter’s suggestion  that a common decentralized algorithm is desirable. It will simplify problems associated with reconvergence which I think is key.
And I don’t think we really need to support multiple algorithms – it was nice of Peter to allow for that – but as we see now everyone is concerned about the upgrade issues that come with introducing a new algorithm.

Let’s agree on one algorithm and be done.
A variant on https://tools.ietf.org/html/rfc6325#section-4.5.1 is one such candidate.

   Les

From: Lsr <[email-masked]> On Behalf Of Rob Shakir
Sent: Friday, April 06, 2018 9:03 AM
To: Peter Psenak (ppsenak) <[email-masked]>
Cc: [email-masked]; [email-masked]
Subject: Re: [Lsr] Fwd: New Version Notification for draft-li-dynamic-flooding-04.txt

Peter,

How do we transition between algorithms in the approach that you suggest? Do all non-stub devices need to be upgraded to support the new algorithm before such time as we can use it? (I think so, because otherwise some non-stub device cannot be guaranteed to flood to its downstream stub devices - so we may end up isolating some devices if any device transitions before all nodes support it).

The advantage of having something advertised is that one can compute it centrally - and keep the per-node functionality simply obeying the advertised flooding graph. From an operational perspective, this means that one can introduce new experimental flooding topology computation approaches in a manner that is decoupled from needing to do software upgrades across the whole network. I can also implement non-standard flooding topology computations based on the network topology which could be only applicable to that particular network (consider if I wanted to do something like take into account shared-risk information in the algorithm to allow the most-SRLG disjoint flooding topology or so).

This is in addition to the points Tony made. I think this centralised-computation-and-flooded approach is elegant. If the error handling behaviour for not being able to parse the flooding topology is to revert to flooding everywhere, then it seems non-destructive too.

Cheers,
r.

On Fri, 6 Apr 2018 at 08:50 Peter Psenak <[email-masked]<mailto:[email-masked]>> wrote:
Hi Tony,

thanks,
Peter

_______________________________________________
Lsr mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/lsr

---

From: Tony Przygienda <[email-masked]>
Date: Sat, 7 Apr 2018 10:42:39 -0700

Given Les chimed in I can't resist either now ;-)  Individual musings a bit
having done some of the stuff in the past ;-)

On Fri, Apr 6, 2018 at 1:06 PM, Les Ginsberg (ginsberg) <[email-masked]>
wrote:

> I think this discussion has already gone much too far in the direction of
> customized flooding optimizations. Such is the nature of the engineering
> mind – give us a problem to solve and we’ll come up with a plethora of
> solutions.
>
>
>
> IGPs have been  popular as distribution mechanisms in part because of the
> reliability of  their flooding process. This wasn’t easy to achieve – and
> those of us who have been in the business long enough have seen attempts to
> create something equivalent fall flat on their face because they couldn’t
> handle the corner causes. Simple yet robust has been the guiding principle
> and both IGPs do this well.
>

yepp, flooding is hard to get right ;-) However, flooding _is_ a problem in
a highly densed mesh @ scale (which DC fabrics are), bandwidth less so then
the sheer amount of updates generated & necessary CPU power needed IME.
That can be addressed in different ways, flooding DAG optimization variants
being one of them ;-)

>
>
>
>
>
> I agree with Peter’s suggestion  that a common decentralized algorithm is
> desirable. It will simplify problems associated with reconvergence which I
> think is key.
>

well, on one hand we have the "telephony networks solution" a.k.a.  a
single node doing all the computation/enforcing state on all. Intoxicating
in its simplicity, unpleasant in its fragility. Plus, what happens if a
_2nd_ node happens to start advertising something else ;-) ?  I think that
e.g. the FlexAlgo currently suggested solution for that problem (i.e.
multiple sources of truth with preference tie-breaking) is a good trade-off
here modulo the necessary convergence time.

On the other hand we have the "fully distributed algorithm" which is
intoxicating in its robustness and frustrating in the time it takes to get
them right if not highly skilled in the art or specs have holes ;-) Well,
for that matter any eventual consistency distributed system is hard (unless
epsilon is inifite ;-)

> And I don’t think we really need to support multiple algorithms – it was
> nice of Peter to allow for that – but as we see now everyone is concerned
> about the upgrade issues that come with introducing a new algorithm.
>

That I would concur with ...

> A variant on https://tools.ietf.org/html/rfc6325#section-4.5.1 is one
And here the dog has more hair than what it initially looks like (from
[however quite dated in case of this problem ;-)] implementation
experience).   First, @ scale a single spanning tree tends to be tad
fragile on failures/convergence, generates "hot-links" on which e'one has
to wait to converge. Doing two max disjoint trees is not easy but doable
from experience @ very non-neglectible complexity. And it's still not fully
"load-balancing" flooding which would be the ideal thing of course. Then,
and I think Tony describes the problem quite well in the draft in its
nature, the problems of diameter and fanout control starts to play a role.
A min-diameter algorithm is (non-distributed) AFAIR a clique problem and
with that NP complete (albeit some good heurestics were around, it's too
long for me to recall).

This of course all having to do with trying to solve a generic graph
problem. If we focus on lattices/Haase/partially ordered graphs (think CLOS
as practical variant or anything that has a north and a south) then the
problem of almost optimal flood reduction while load balancing is quite
tractable in distributed fashion we discovered but we're working on it as
we speak so look for the -06 draft update in another group ;-)

my 2c, rusty and dented but not debased l;-)

--- tony

---

From: Robert Raszuk <[email-masked]>
Date: Sat, 7 Apr 2018 19:43:53 +0200

Les,

Isn't RIFT effectively a new flooding algorithm - while not strictly
designed to be used within current link state protocols - it has the
potential to achieve what you and Peter are proposing isn't it ?

My personal take here would be to progress dynamic flooding *as is* with
the use of DR/DIS as flooding oracles.

If you or anyone however would like to propose a new flooding algorithm to
link state protocols I think nothing stops you to write a separate draft on
that and call it say -optimal-flooding-.

Best,
Robert.

On Fri, Apr 6, 2018 at 10:06 PM, Les Ginsberg (ginsberg) <[email-masked]

> It is also useful to remember that bandwidth utilization for IGP flooding
> is not a problem which we need to solve. It has been demonstrated – even
> long ago with much less bandwidth than we have today – that IGP flooding
> bandwidth isn’t a concern. So proposals which suggest we might need to come
> up with an algorithm that optimizes for bandwidth or SRLGs or whatever
> criteria one could imagine seem unnecessary – as well as incestuous. And
> they certainly complicate the problem.
>
>
>
> *From:* Lsr <[email-masked]> *On Behalf Of *Rob Shakir
> *Sent:* Friday, April 06, 2018 9:03 AM
> *To:* Peter Psenak (ppsenak) <[email-masked]>
> *Cc:* [email-masked]; [email-masked]
> *Subject:* Re: [Lsr] Fwd: New Version Notification for
> draft-li-dynamic-flooding-04.txt
>
>
>
> Peter,
>
>
>

---

From: "Les Ginsberg (ginsberg)" <[email-masked]>
Date: Sat, 7 Apr 2018 19:47:30 +0000

Robert –

I think discussion of RIFT belongs in the appropriate WG – not here.

Flooding “as is” isn’t relevant here – since “as is” would mean as the IGPs do it today.
Whether the flooding topology is calculated/advertised by a designated node or is calculated in a distributed fashion clearly a different flooding topology from the one IGPs use today is required or we will have accomplished nothing.

   Les

From: Lsr <[email-masked]> On Behalf Of Robert Raszuk
Sent: Saturday, April 07, 2018 10:44 AM
To: Les Ginsberg (ginsberg) <[email-masked]>
Cc: [email-masked]; Rob Shakir <[email-masked]>; [email-masked]; Peter Psenak (ppsenak) <[email-masked]>
Subject: Re: [Lsr] Fwd: New Version Notification for draft-li-dynamic-flooding-04.txt

Les,

Isn't RIFT effectively a new flooding algorithm - while not strictly designed to be used within current link state protocols - it has the potential to achieve what you and Peter are proposing isn't it ?

My personal take here would be to progress dynamic flooding *as is* with the use of DR/DIS as flooding oracles.

If you or anyone however would like to propose a new flooding algorithm to link state protocols I think nothing stops you to write a separate draft on that and call it say -optimal-flooding-.

Best,
Robert.

On Fri, Apr 6, 2018 at 10:06 PM, Les Ginsberg (ginsberg) <[email-masked]<mailto:[email-masked]>> wrote:
I think this discussion has already gone much too far in the direction of customized flooding optimizations. Such is the nature of the engineering mind – give us a problem to solve and we’ll come up with a plethora of solutions.

   Les

From: Lsr <[email-masked]<mailto:[email-masked]>> On Behalf Of Rob Shakir
Sent: Friday, April 06, 2018 9:03 AM
To: Peter Psenak (ppsenak) <[email-masked]<mailto:[email-masked]>>
Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: Re: [Lsr] Fwd: New Version Notification for draft-li-dynamic-flooding-04.txt

Peter,

Cheers,
r.

thanks,
Peter

---

From: Robert Raszuk <[email-masked]>
Date: Sat, 7 Apr 2018 21:52:17 +0200

Hi Les,

Just to clarify ..

*as is* - was meant to indicated as described in draft-li-dynamic-flooding
proposal. Not *as is* today in IGPs.

Thx,
R.

On Sat, Apr 7, 2018 at 9:47 PM, Les Ginsberg (ginsberg) <[email-masked]>
wrote:

> Whether the flooding topology is calculated/advertised by a designated
> node or is calculated in a distributed fashion clearly a different flooding
> topology from the one IGPs use today is required or we will have
> accomplished nothing.
>
>
>
>    Les
>
>
>
>
>
> *From:* Lsr <[email-masked]> *On Behalf Of *Robert Raszuk
> *Sent:* Saturday, April 07, 2018 10:44 AM
> *To:* Les Ginsberg (ginsberg) <[email-masked]>
> *Cc:* [email-masked]; Rob Shakir <[email-masked]>; [email-masked]; Peter
> Psenak (ppsenak) <[email-masked]>
>
> On Fri, Apr 6, 2018 at 10:06 PM, Les Ginsberg (ginsberg) <
> [email-masked]> wrote:
>

---

From: Uma Chunduri <[email-masked]>
Date: Mon, 16 Apr 2018 22:20:33 +0000

Hi Peter,

> I have the feeling that the dependency of the "flooding topology" on the flooded data is going to bring more complexity, than the selection of the distributed algorithm to be used, if we ever need to support more then one.

I see

https://datatracker.ietf.org/doc/draft-hegdeppsenak-isis-sr-flex-algo/?include_text=1 proposes flexible algorithms for route computation. 

Here, you are saying similar to flexible algorithms for route computation - flexible algorithms can be used for computing "flooding topology" in a distributed fashion ; is that correct?

Else I don't see any connection to different algorithms in the flooding topology context; please clarify?
--
Uma C.

-----Original Message-----
From: Lsr [mailto:[email-masked]] On Behalf Of Peter Psenak
Sent: Friday, April 06, 2018 8:50 AM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [Lsr] Fwd: New Version Notification for draft-li-dynamic-flooding-04.txt

Hi Tony,

if we start with a single standardized algorithm, that is easy to implement and deploy. We can leave the door open for additional algorithms to be defined later together with the selection mechanism.

I have the feeling that the dependency of the "flooding topology" on the flooded data is going to bring more complexity, than the selection of the distributed algorithm to be used, if we ever need to support more then one.

thanks,
Peter

On 06/04/18 17:19 , [email-masked] wrote:
> There are many perspectives on what an adequate flooding topology 
> might be. Different administrations have different considerations and 
> risk tolerances.
>
> I’m trying to do something practical, and it seems like doing this in 
> a centralized fashion is the quickest, easiest, and most robust way forward.
>
>
>> Eventually we can support multiple standardized algorithms. A node 
>> can advertise support for several algorithms and the "active" 
>> algorithm is selected based on some criteria that would guarantee 
>> that all nodes in the flooding domain select the same one.
>
>

---

From: Peter Psenak <[email-masked]>
Date: Tue, 17 Apr 2018 11:39:02 +0200

Hi Uma,

please see inline:

> Here, you are saying similar to flexible algorithms for route computation - flexible algorithms can be used for computing "flooding topology" in a distributed fashion ; is that correct?

that's not what we are proposing. At least not at this point.

> Else I don't see any connection to different algorithms in the flooding topology context; please clarify?

the discussion we are having in the context of the
draft-li-dynamic-flooding is whether to use the centralized or 
distributed approach to compute the flooding topology.

Current text in the draft mandates the centralized approach and requires 
flooding of the data to describe the "flooding topology" itself.

We are proposing to also support distributed version of it with either a 
single standardized algorithm or possibly multiple distributed 
algorithms, which would require some agreement between all devices in 
the flooded domain.

thanks,
Peter

---

From: "Acee Lindem (acee)" <[email-masked]>
Date: Tue, 17 Apr 2018 20:00:52 +0000

Speaking as a WG member:

I think a distributed flooding algorithm is more robust and will converge faster when there more than one concurrent failure in the flooding topology. Additionally, if there is a node failure of the flooding leader and that node is a node is on flooding topology, there could be greater delays.

The same solution suggested for the centralized approach of flooding on the union of the old and new topologies could be used for transitions. However, prune to the newer topology could be quicker since it should be easier to assure downstream neighbors have converged on the new topology than the whole domain.

Thanks,
Acee

From: Lsr <[email-masked]> on behalf of "Les Ginsberg (ginsberg)" <[email-masked]>
Date: Saturday, April 7, 2018 at 3:47 PM
To: Robert Raszuk <[email-masked]>
Cc: "[email-masked]" <[email-masked]>, Rob Shakir <[email-masked]>, Tony Li <[email-masked]>, "Peter Psenak (ppsenak)" <[email-masked]>
Subject: Re: [Lsr] Fwd: New Version Notification for draft-li-dynamic-flooding-04.txt

Robert –

   Les

Les,

Best,
Robert.

   Les

Peter,

Cheers,
r.

thanks,
Peter

---

From: [email-masked]
Date: Tue, 17 Apr 2018 13:24:16 -0700

Acee,

> I think a distributed flooding algorithm is more robust and will converge faster when there more than one concurrent failure in the flooding topology.

No doubt. However, we do not normally attempt to protect against multiple concurrent failures. Regardless of how the flooding topology is computed, multiple failures can partition it and convergence will become seriously problematic.  In the face of multiple failures, no node could have a complete and consistent database and even with a distributed algorithm, you may have multiple iterations of computing a new topology, flooding, and computing.

Let’s not kid ourselves: distributed is no panacea. 

We do not design our redundant hardware systems to deal with multiple concurrent failures, simply because the complexity of such failures is so high. It’s paid off as these things simply don’t happen with significant frequency.  What is important is that we have eventual consistency.

> Additionally, if there is a node failure of the flooding leader and that node is a node is on flooding topology, there could be greater delays.

All nodes are on the flooding topology, necessarily.

If the leader fails, then it’s similar to any other node failure.  Flooding happens around the failed node. Assuming the flooding topology was bi-connected, flooding is not interrupted and the network should converge in a single flood/SPF cycle.

If the old leader returns to the topology quickly, then there is no issue.

If the old leader does not return, then there is a leader election/computation/flooding sequence, but that happens while there is a functioning flooding topology. NBD.

> The same solution suggested for the centralized approach of flooding on the union of the old and new topologies could be used for transitions. However, prune to the newer topology could be quicker…

You can’t assume that you had complete information when computing the distributed version.

Tony