Re: [Lsr] Flooding across a network

[Jeff Tantsura <[e-mail]>]

Robert,

Assuming C and E provide access to the same set of destinations, that are closer of further away from C and E.
B (which is fast), after it notifies A that it can’t reach C directly will cause A to send traffic to D. D - dependent on total cost would start happily sending some traffic towards destinations behind C to B so LFA on B wouldn’t really help.

Cheers,
Jeff
On May 5, 2020, 5:04 PM -0700, Robert Raszuk <[e-mail]>, wrote:
> Hi Les,
>
> A side comment but your example shows another - one may say even much more serious issue.
>
> Assume we have LFA/TI-LFA enabled in the network and precomputed on B which get's activated and shifts traffic to E when detects that C is down. Detection is fast .. 10s-100s of milliseconds.
>
> Now if B converges fast and recomputes topology much faster then D it may remove protection and send packets to D natively. Well clearly as we established D is slow and will loop it back.
>
> That is why I mentioned the other day that a fast control plane is not always a good thing (I am sure many will say the opposite - but it is ok ;).
>
> But this proves that consistent convergence time in a domain is rather a good thing regardless if it takes 2 sec or 50 sec on all nodes.
>
> Best,
> Robert.
>
>
>
> > On Wed, May 6, 2020 at 1:35 AM Les Ginsberg (ginsberg) <ginsberg=[e-mail]> wrote:
> > > Bruno -
> > >
> > > Seems like it was not too long ago that we were discussing this in person.  Ahhh...the good old days...
> > >
> > > First, let's agree that the interesting case does not involve 1 or even a small number of LSPs. For those cases flooding speed does not matter.
> > > The interesting cases involve a large number of LSPs (hundreds or thousands). And in such cases LFA/microloop avoidance techniques are not applicable.
> > >
> > > Take the following simple topology:
> > >
> > >    |  | ... |            |
> > >      +---+             +---+
> > >      | C |             | E |
> > >      +---+             +---+
> > >        |                 | 1000
> > >      +---+             +---+
> > >      | B |-------------| D |
> > >      +---+   1000      +---+
> > >        |                 |
> > >        |                 |
> > >         \               /
> > >          \            /
> > >           \         /
> > >            \      /
> > >              +---+
> > >              | A |
> > >              +---+
> > >
> > > There is a topology northbound of C and E (not shown) and a topology southbound of A (not shown).
> > > Cost on all links is 10 except B-D and D-E where cost is high.
> > >
> > > C is a node with 1000 neighbors.
> > > When all links are up, shortest path for all northbound destinations is via C.
> > > All nodes in the network support fast flooding except for Node D.
> > > Let’s say fast flooding is 500 LSPs/second and slow flooding (Node D) is 20 LSPs/seconds.
> > > If  Node C fails we have 1000 LSPs to flood.
> > > All nodes except for D can receive these in 2 seconds (plus internode delay time).
> > > D can receive LSPs in 50 seconds.
> > >
> > > When A and B and all southbound nodes receive/process the LSP updates they will start sending traffic to Northbound destinations via D.
> > > But for the better part of 50 seconds, Node D has yet to receive all LSP updates and still believes that shortest path is via B-C. It will loop traffic.
> > >
> > > Had all nodes used slow flooding, it still would have taken 50 seconds to converge, but there would be significantly less looping. There could be a good amount of blackholing, but this is preferable to looping.
> > >
> > > One can always come up with examples – based on a specific topology and a specific failure - where things might be better/worse/unchanged in the face of inconsistent flooding speed support.
> > > But I hope this simple example illustrates the pitfalls.
> > >
> > >     Les
> > >
> > > > -----Original Message-----
> > > > From: [e-mail] <[e-mail]>
> > > > Sent: Tuesday, May 05, 2020 8:28 AM
> > > > To: Les Ginsberg (ginsberg) <[e-mail]>; [e-mail]
> > > > Subject: Flooding across a network
> > > >
> > > > Les,
> > > >
> > > > > From: Lsr [mailto:[e-mail]] 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:[e-mail]] 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 <[e-mail]> On Behalf Of Henk Smit
> > > > > > Sent: Thursday, April 30, 2020 6:58 AM
> > > > > > To: [e-mail]
> > > > > > 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
> > > > > > [e-mail]
> > > > > > https://www.ietf.org/mailman/listinfo/lsr
> > > > >
> > > > > _______________________________________________
> > > > > Lsr mailing list
> > > > > [e-mail]
> > > > > 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.
> > >
> > > _______________________________________________
> > > Lsr mailing list
> > > [e-mail]
> > > https://www.ietf.org/mailman/listinfo/lsr
> _______________________________________________
> Lsr mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/lsr