[Lsr] Flooding across a network

bruno.decraene@orange.com Tue, 05 May 2020 15:28 UTC

Return-Path: <bruno.decraene@orange.com>
X-Original-To: lsr@ietfa.amsl.com
Delivered-To: lsr@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7168F3A08C0 for <lsr@ietfa.amsl.com>; Tue, 5 May 2020 08:28:02 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, UNPARSEABLE_RELAY=0.001, URIBL_BLOCKED=0.001] autolearn=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=orange.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7V6_X9rhg6YN for <lsr@ietfa.amsl.com>; Tue, 5 May 2020 08:27:59 -0700 (PDT)
Received: from relais-inet.orange.com (relais-inet.orange.com [80.12.70.36]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D14623A0898 for <lsr@ietf.org>; Tue, 5 May 2020 08:27:58 -0700 (PDT)
Received: from opfednr04.francetelecom.fr (unknown [xx.xx.xx.68]) by opfednr25.francetelecom.fr (ESMTP service) with ESMTP id 49GkBP2wwHzCrc1; Tue, 5 May 2020 17:27:57 +0200 (CEST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=orange.com; s=ORANGE001; t=1588692477; bh=q1Q/f6Hba0Spkhv5LVDytz8v+NtiZp6KdaQ/YW2Zq+4=; h=From:To:Subject:Date:Message-ID:Content-Type: Content-Transfer-Encoding:MIME-Version; b=f3GHiyYuzNv7V4QapLbPI5/7eanElmYrD7/UqPdPW0eplPSomDOBXLGjF5Dhn+Xo+ CrQKjKn8qezTSrZmx3yjK9g3u66nQjExamH74H9ccW2nOpaDPFnZs+qhQgyOoQ2R27 4VldZbyBH5GO606+ySLA42/z5P6LOWJCF6riZWpP5stGK9RJgW0CbxyzEcU0sRpojS 7dhcDcbrUOqnPLCZxi/DDsB5nJbXTQodSHwGi+TBKH7uC9KtEeN8OUS4AiqNTDrzO8 st+QIzQlQk4AlDN09zfjgoHF7sgVZOdWDDKjaZyOr8qJult3QpxMosARiq0LE5owu7 V/xUEzEiBWFoQ==
Received: from Exchangemail-eme6.itn.ftgroup (unknown [xx.xx.13.29]) by opfednr04.francetelecom.fr (ESMTP service) with ESMTP id 49GkBP21D2z1xp9; Tue, 5 May 2020 17:27:57 +0200 (CEST)
From: <bruno.decraene@orange.com>
To: "Les Ginsberg (ginsberg)" <ginsberg=40cisco.com@dmarc.ietf.org>, "lsr@ietf.org" <lsr@ietf.org>
Thread-Topic: Flooding across a network
Thread-Index: AdYi7bsxcCpCOCQDSjylEJ0cQECozg==
Date: Tue, 5 May 2020 15:27:56 +0000
Message-ID: <24209_1588692477_5EB185FD_24209_35_1_53C29892C857584299CBF5D05346208A48E3D455@OPEXCAUBM43.corporate.adroot.infra.ftgroup>
Accept-Language: fr-FR, en-US
Content-Language: fr-FR
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.114.13.247]
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/lsr/i596JJVDCDFJFGRSzweNDkntbsE>
Subject: [Lsr] Flooding across a network
X-BeenThere: lsr@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Link State Routing Working Group <lsr.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/lsr>, <mailto:lsr-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/lsr/>
List-Post: <mailto:lsr@ietf.org>
List-Help: <mailto:lsr-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/lsr>, <mailto:lsr-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 05 May 2020 15:28:06 -0000

Les,

> From: Lsr [mailto:lsr-bounces@ietf.org] On Behalf Of Les Ginsberg (ginsberg)
> Sent: Monday, May 4, 2020 4:39 PM
[...]
> when only some nodes in the network support faster flooding the behavior of the whole network may not be "better" when faster flooding is enabled because it prolongs the period of LSDB inconsistency.  

1) Do you have data on this?

2) If not, can you provide an example where increasing the flooding rate on one adjacency prolongs the period of LSDB inconsistency across the network?

3) In the meantime, let's try the theoretical analysis on a simple scenario where a single LSP needs to be flooded across the network.

- Let's call Dij the time needed to flood the LSP from node i to the adjacent node j. Clearly Dij>0.
- Let's call k the node originating this LSP at t0=0s

>From t0, the LSDB is inconsistent across the network as all nodes but k are missing the LSP and hence only know about the 'old' topology.

Let's call  SPT(k) the SPT rooted on k, using Dij as the metric between adjacent nodes i and j. Let's call SP(k,i) the shortest path from k to i; and D(k,i) the shortest distance between k and i.

It seems that the time needed:
- for node j to learn about the LSP, and get in sync with k, is D(k,j)
- for all nodes across the network to learn about the LSP, and get in sync with k, is Max[for all j] D(k,j)

Then how can reducing the flooding delay on one adjacency could prolongs the period of LSDB inconsistency?
It seems to me that it can only improve/decrease it. Otherwise, this would mean that decreasing the cost on a link can increase the cost of the shortest path.

Note: I agree that there are other cases, such as  multiple LSPs originated by the same node, and multiple LSPs originated by multiple nodes, but let's start with the simple case. 

Thanks,
--Bruno

> -----Original Message-----
> From: Lsr [mailto:lsr-bounces@ietf.org] On Behalf Of Les Ginsberg (ginsberg)
> Sent: Monday, May 4, 2020 4:39 PM
> 
> Henk -
> 
> Thanx for your thoughtful posts.
> I have read your later posts on this thread as well - but decided to reply to this one.
> Top posting for better readability.
> 
> There is broad agreement that faster flooding is desirable.
> There are now two proposals as to how to address the issue - neither of which is proposing to use TCP (or equivalent).
> 
> I have commented on why IS-IS flooding requirements are significantly different than that for which TCP is used.
> I think it is also useful to note that even the simple test case which Bruno reported on in last week's interim meeting demonstrated that without any changes to the protocol at all IS-IS was able to flood an order of magnitude faster than it commonly does today.
> This gives me hope that we are looking at the problem correctly and will not need "TCP".
> 
> Introducing a TCP based solution requires:
> 
> a)A major change to the adjacency formation logic
> 
> b)Removal of the independence of the IS-IS protocol from the address families whose reachability advertisements it supports - something which I think is a great strength of the protocol - particularly in environments where multiple address family support is needed
> 
> I really don't want to do either of the above.
> 
> Your comments regarding PSNP response times are quite correct - and both of the draft proposals discuss this - though I agree more detail will be required.
> It is intuitive that if you want to flood faster you also need to ACK faster - and probably even retransmit faster when that is needed.
> The basic relationship between retransmit interval and PSNP interval is expressed in ISO 10589:
> 
> " partialSNPInterval - This is the amount of time between periodic
        > action for transmission of Partial Sequence Number PDUs.
        > It shall be less than minimumLSPTransmission-Interval."
> 
> Of course ISO 10589 recommended values (2 seconds and 5 seconds respectively) associated with a much slower flooding rate and implementations I am aware of use values in this order of magnitude. These numbers need to be reduced if we are to flood faster, but the relationship between the two needs to remain the same.
> 
> It is also true - as you state - that sending ACKs more quickly will result in additional PDUs which need to be received/processed by IS-IS - and this has some impact. But I think it is reasonable to expect that an implementation which can support sending and receiving LSPs at a faster rate should also be able to send/receive PSNPs at a faster rate. But we still need to be smarter than sending one PSNP/one LSP in cases where we have a burst.
> 
> LANs are a more difficult problem than P2P - and thus far draft-ginsberg-lsr-isis-flooding-scale has been silent on this - but not because we aren't aware of this - just have focused on the P2P behavior first.
> What the best behavior on a LAN may be is something I am still considering. Slowing flooding down to the speed at which the slowest IS on the LAN can support may not be the best strategy - as it also slows down the propagation rate for systems downstream from the nodes on the LAN which can handle faster flooding - thereby having an impact on flooding speed throughout the network in a way which may be out of proportion. This is a smaller example of the larger issue that when only some nodes in the network support faster flooding the behavior of the whole network may not be "better" when faster flooding is enabled because it prolongs the period of LSDB inconsistency. More work needs to be done here...
> 
> In summary, I don't expect to have to "reinvent TCP" - but I do think you have provided a useful perspective for us to consider as we progress on this topic,
> 
> Thanx.
> 
    > Les
> 
> 
> > -----Original Message-----
> > From: Lsr <lsr-bounces@ietf.org> On Behalf Of Henk Smit
> > Sent: Thursday, April 30, 2020 6:58 AM
> > To: lsr@ietf.org
> > Subject: [Lsr] Why only a congestion-avoidance algorithm on the sender isn't
> > enough
> > 
> > 
> > Hello all,
> > 
> > Two years ago, Gunter Van de Velde and myself published this draft:
> > https://tools.ietf.org/html/draft-hsmit-lsr-isis-flooding-over-tcp-00
> > That started this discussion about flow/congestion control and ISIS
> > flooding.
> > 
> > My thoughts were that once we start implementing new algorithms to
> > optimize ISIS flooding speed, we'll end up with our own version of TCP.
> > I think most people here have a good general understanding of TCP.
> > But if not, this is a good overview how TCP does it:
> > https://en.wikipedia.org/wiki/TCP_congestion_control
> > 
> > 
> > What does TCP do:
> > ====
> > TCP does 2 things: flow control and congestion control.
> > 
> > 1) Flow control is: the receiver trying to prevent itself from being
> > overloaded. The receiver indicates, through the receiver-window-size
> > in the TCP acks, how much data it can or wants to receive.
> > 2) Congestion control is: the sender trying to prevent the links between
> > sender and receiver from being overloaded. The sender makes an educated
> > guess at what speed it can send.
> > 
> > 
> > The part we seem to be missing:
> > ====
> > For the sender to make a guess at what speed it can send, it looks at
> > how the transmission is behaving. Are there drops ? What is the RTT ?
> > Do drop-percentage and RTT change ? Do acks come in at the same rate
> > as the sender sends segments ? Are there duplicate acks ? To be able
> > to do this, the sender must know what to expect. How acks behave.
> > 
> > If you want an ISIS sender to make a guess at what speed it can send,
> > without changing the protocol, the only thing the sender can do is look
> > at the PSNPs that come back from the receiver. But the RTT of PSNPs can
> > not be predicted. Because a good ISIS implementation does not
> > immediately
> > send a PSNP when it receives a LSP. 1) the receiver should jitter the
> > PSNP,
> > like it should jitter all packets. And 2) the receiver should wait a
> > little
> > to see if it can combine multiple acks into a single PSNP packet.
> > 
> > In TCP, if a single segment gets lost, each new segment will cause the
> > receiver to send an ack with the seqnr of the last received byte. This
> > is called "duplicate acks". This triggers the sender to do
> > fast-retransmission. In ISIS, this can't be be done. The information
> > a sender can get from looking at incoming PSNPs is a lot less than what
> > TCP can learn from incoming acks.
> > 
> > 
> > The problem with sender-side congestion control:
> > ====
> > In ISIS, all we know is that the default retransmit-interval is 5
> > seconds.
> > And I think most implementations use that as the default. This means
> > that
> > the receiver of an LSP has one requirement: send a PSNP within 5
> > seconds.
> > For the rest, implementations are free to send PSNPs however and
> > whenever
> > they want. This means a sender can not really make conclusions about
> > flooding speed, dropped LSPs, capacity of the receiver, etc.
> > There is no ordering when flooding LSPs, or sending PSNPs. This makes
> > a sender-side algorithm for ISIS a lot harder.
> > 
> > When you think about it, you realize that a sender should wait the
> > full 5 seconds before it can make any real conclusions about dropped
> > LSPs.
> > If a sender looks at PSNPs to determine its flooding speed, it will
> > probably
> > not be able to react without a delay of a few seconds. A sender might
> > send
> > hunderds or thousands of LSPs in those 5 seconds, which might all or
> > partially be dropped, complicating matters even further.
> > 
> > 
> > A sender-sider algorithm should specify how to do PSNPs.
> > ====
> > So imho a sender-side only algorithm can't work just like that in a
> > multi-vendor environment. We must not only specify a congestion-control
> > algorithm for the sender. We must also specify for the receiver a more
> > specific algorithm how and when to send PSNPs. At least how to do PSNPs
> > under load.
> > 
> > Note that this might result in the receiver sending more (and smaller)
> > PSNPs.
> > More packets might mean more congestion (inside routers).
> > 
> > 
> > Will receiver-side flow-control work ?
> > ====
> > I don't know if that's enough. It will certainly help.
> > 
> > I think to tackle this problem, we need 3 parts:
> > 1) sender-side congestion-control algorithm
> > 2) more detailed algorithm on receiver when and how to send PSNPs
> > 3) receiver-side flow-control mechanism
> > 
> > As discussed at length, I don't know if the ISIS process on the
> > receiving
> > router can actually know if its running out of resources (buffers on
> > interfaces, linecards, etc). That's implementation dependent. A receiver
> > can definitely advertise a fixed value. So the sender has an upper bound
> > to use when doing congestion-control. Just like TCP has both a
> > flow-control
> > window and a congestion-control window, and a sender uses both. Maybe
> > the
> > receiver can even advertise a dynamic value. Maybe now, maybe only in
> > the
> > future. An advertised upper limit seems useful to me today.
> > 
> > 
> > What I didn't like about our own proposal (flooding over TCP):
> > ====
> > The problem I saw with flooding over TCP concerns multi-point networks
> > (LANs).
> > 
> > When flooding over a multi-point network, setting up TCP connections
> > introduces serious challenges. Who are the endpoints of the TCP
> > connections ?
> > Full mesh ? Or do all ISes on a LAN create a TCP-connection to the DIS ?
> > There is no backup DIS in ISIS (unlike OSPF). Things get messy quickly.
> > 
> > However, the other two proposals do not solve this problem either.
> > How will a sender-side congestion-avoidence algorithm determine whether
> > there were drops ? There are no acks (PSNPs) on a LAN. We assume most
> > LSPs
> > that are broadcasted are received by all other ISes on the LAN. There
> > are
> > no acks. Only after the DIS has sent its periodic CSNPs, ISes can send
> > PSNPs to request retransmissions. It seems impossible (or very hard) to
> > me for all ISes on a LAN to keep track of dropped LSPs and adjust their
> > sending speed accordingly.
> > 
> > When flooding on a LAN, the receiver-side algorithm seems best. Because
> > all ISes can see what the lowest advertised sending-speed is. And make
> > sure they send slow enough to not overload the slowest IS. I'm not sure
> > this is a good solution, but is seems easier and more realistic than
> > ISIS-flooding-over-TCP or sender-side congestion-avoidance.
> > 
> > 
> > My conclusion:
> > ====
> > Sender-side congestion-control won't work without specifying in more
> > detail how and when to send PSNPs.
> > Receiver-side flow-control will certainly help. I dont' know if it's
> > good enough. I don't know if advertising a static value is good enough.
> > But it's a start.
> > 
> > I still think we'll end up re-implementing a new (and weaker) TCP.
> > 
> > 
> > henk.
> > 
> > _______________________________________________
> > Lsr mailing list
> > Lsr@ietf.org
> > https://www.ietf.org/mailman/listinfo/lsr
> 
> _______________________________________________
> Lsr mailing list
> Lsr@ietf.org
> https://www.ietf.org/mailman/listinfo/lsr

_________________________________________________________________________________________________________________________

Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc
pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler
a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,
Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.

This message and its attachments may contain confidential or privileged information that may be protected by law;
they should not be distributed, used or copied without authorisation.
If you have received this email in error, please notify the sender and delete this message and its attachments.
As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.
Thank you.