Re: [Lsr] Dynamic flow control for flooding

Tony Przygienda <tonysietf@gmail.com> Wed, 24 July 2019 14:51 UTC

Return-Path: <tonysietf@gmail.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 88E9812011F for <lsr@ietfa.amsl.com>; Wed, 24 Jul 2019 07:51:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Level:
X-Spam-Status: No, score=-1.997 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.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 Z0SmW7AwImc4 for <lsr@ietfa.amsl.com>; Wed, 24 Jul 2019 07:50:58 -0700 (PDT)
Received: from mail-ed1-x52a.google.com (mail-ed1-x52a.google.com [IPv6:2a00:1450:4864:20::52a]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C08801201D5 for <lsr@ietf.org>; Wed, 24 Jul 2019 07:50:57 -0700 (PDT)
Received: by mail-ed1-x52a.google.com with SMTP id k8so47352281edr.11 for <lsr@ietf.org>; Wed, 24 Jul 2019 07:50:57 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=paudBZ+KQRBQdeE9pHmxDbpbBweifdV6YLrALr1I1Gs=; b=aym+n3QSo0keqDzcRc9+nBPaeV3EIs6ZwX+0CbFumpTL+EsluiljBirGbNTVXhzEx4 D1xmxVfgOhbrQ1b+gsvtXXCjyo0pnGJ6YsC57oIabVUS1beWwO1kV6C7HyV7nK+brnFO MQxs5qI37BL5ycICGZGq2ZaDT9DmXWBI2wqqhyaOnlf9l8pgtYNho46np0R+HXt/sFMY 6K2QEUe4nfCpNnNgVt6SJ7yk+x+hqHPH+fBdrcV+6ogSGlrw0VU5sFdgHcf2s1Js1W1+ HhEN65AQYBjpVT5s5B52PMZvdBNBAeKc9V9jIx9F3v0itdkgMlPm3wfQvDANsdaASE8+ ajuA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=paudBZ+KQRBQdeE9pHmxDbpbBweifdV6YLrALr1I1Gs=; b=RiSG/0BcvRmWdGpsod+7gOYfjScKwcDaxWtCjnQXMZI4QJ6XGCWPbx8Ibnc1saZlCK HM5j5CnyI+995jHkuQtI+i/i92UG/0MdWsismihUx0T6qhiL/LwAnuLdEQtwUyFf6/cu 1ce5qqf0r2NmReIt5l/JvdUhwb4CqiYoXAoWPow5/dt0VMgYm5dfCmQX433Mk0P5FsDL JmURq3bgiwlkFeC7LtK5SJGqxg+R9xf2p66ZPrpZlBEnMclHT7asprGrDXPKdzdRPMut QEZyR68UMPyqA3/FUtr0d8M9S8BCrXuQTTCjjgjiXPyc0wtSXuABmnSfcLG+0eBxr/sa 4pFA==
X-Gm-Message-State: APjAAAXE75R2y1JjbByhf+JDintn9YK/O2ezuFiasouphQoDpnAsaSbQ U4dFpFt68/5RUMBNXvXHAylJTkPIjoU4oW+6wj/ggp/2uDo=
X-Google-Smtp-Source: APXvYqwo827mdd8a5o7JJ9tYvwYxGMZoU0FR65vSXZ02WihcFS0VgDQR5hXVWvuvySqQYGfPi8jsvgfMi2j34QrIXkQ=
X-Received: by 2002:a50:9177:: with SMTP id f52mr71947579eda.294.1563979856290; Wed, 24 Jul 2019 07:50:56 -0700 (PDT)
MIME-Version: 1.0
References: <CAMj-N0LdaNBapVNisWs6cbH6RsHiXd-EMg6vRvO_U+UQsYVvXw@mail.gmail.com> <BYAPR11MB36382C89363202D1B5659614C1C70@BYAPR11MB3638.namprd11.prod.outlook.com> <5841_1563943794_5D37E372_5841_105_1_9E32478DFA9976438E7A22F69B08FF924D9C373E@OPEXCAUBMA3.corporate.adroot.infra.ftgroup> <BYAPR11MB363856BB026992DFBB3BB224C1C60@BYAPR11MB3638.namprd11.prod.outlook.com> <8376a87831ffa6f5298c5122907c6e66@xs4all.nl> <CA+b+ER=LOZxoyoonPtC7VKppSNcQohGQdx+n8D3+LndnHdsofQ@mail.gmail.com>
In-Reply-To: <CA+b+ER=LOZxoyoonPtC7VKppSNcQohGQdx+n8D3+LndnHdsofQ@mail.gmail.com>
From: Tony Przygienda <tonysietf@gmail.com>
Date: Wed, 24 Jul 2019 10:50:18 -0400
Message-ID: <CA+wi2hNknyofVfCXzpte5-Jea6tfJH-=XWm3sj9QdRvvZe6O=w@mail.gmail.com>
To: Robert Raszuk <rraszuk@gmail.com>
Cc: Henk Smit <henk.ietf@xs4all.nl>, lsr@ietf.org, "Les Ginsberg (ginsberg)" <ginsberg@cisco.com>, Tony Li <tony.li@tony.li>, "<stephane.litkowski@orange.com>" <stephane.litkowski@orange.com>
Content-Type: multipart/alternative; boundary="000000000000c52923058e6e6fe9"
Archived-At: <https://mailarchive.ietf.org/arch/msg/lsr/sT8qq1T1_z92SONUm5AQOwoUjnk>
Subject: Re: [Lsr] Dynamic flow control for flooding
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: Wed, 24 Jul 2019 14:51:02 -0000

I'm under the impression the whole discussion got triggered by my rather
loose remark during the dinner based on, admittedly, my quite dated
implementation experience (with 2 disjoint distributed SPTs to reduce
flooding). I realized it seems not clearly spelled out on the thread. So to
hopefully clarify a bit: the scenario was not partition really, the
scenario was where I ended up in reduced graphs where rather large
"cliques" ended up being connected by either long'ish think chains (2 links
minimal cuts) which ended up "bottle-necking" the flooding on large changes
like redistribution/restart scenarios causing significant amount of LSPs
needed refresh from "left" to "right" through the bottlenecks. Transients
on the network became longer to the point we ended up (then) scrapping the
attempt after considering how we would bulild two trees _per flooding
source_ to really deal with it which seemed like overkill (and RIFT does
BTW but only because of known topology properties) and then setting
overload for which we couldn't figure out a good dynamic way (too short
dangerous, too long as bad). All that with standard flooding rates (beauty
of having mix-of-implementaitons requirements posed). Controlling the span
in distributed fashion is of course much harder than centralized fashion so
one has to be careful to compare apples-with-oranges here ...

that said pretty much out this thread

--- tony



On Wed, Jul 24, 2019 at 9:34 AM Robert Raszuk <rraszuk@gmail.com> wrote:

> Hey Henk & all,
>
> If acks for 1000 LSPs take 16 PSNPs (max 66 per PSNP) or even as long as
> Tony mentioned the full flooding as Tony said may take 33 sec - is this
> really a problem ?
>
> Remember we are not talking about protocol convergence after link flap or
> node going down. We are talking about serious network partitioning which
> itself may have lasted for minutes, hours or days. While just considering
> absolute numbers yelds desire to go faster and faster, if we put things in
> the overall perspective is there really a problem to be solved in the first
> place ?
>
> Would there still be a problem if LSR WG recommends faster acking maybe
> not for each LSP but for say 20 or 30 max ?
>
> Thx,
> R.
>
>
>
>
>
>
>
>
> On Wed, Jul 24, 2019 at 3:18 PM Henk Smit <henk.ietf@xs4all.nl> wrote:
>
>>
>> Hello Les,
>>
>> Les Ginsberg (ginsberg) wrote on 2019-07-24 07:17:
>>
>> > If you accept that, then it makes sense to look for the simplest way
>> > to do flow control and that is decidedly not from the RX side. (I
>> > expect Tony Li to disagree with that 😊 – but I have already
>> > outlined why it is more complex to do it from the Rx side.)
>>
>> In your talk on Monday you called the idea in
>> draft-decraene-lsr-isis-flooding-speed-01 "receiver driven flow
>> control".
>> You don't like that. You want "transmit based flow control".
>> You argued that you can do "transmit based flow control" on the sender
>> only.
>> Therefor your algorithm is merely a "local trick".
>> And "local tricks" don't need RFCs. I agree with that.
>> But I don't agree that your algorithm is just a "local trick"..
>>
>>
>> In your algorithm, a "sender" sends a number of LSPs to a receiver.
>> Without waiting for acks (PNSPs). Like in any sliding window protocol.
>> The sending router keeps an eye on the number of unacked LSPs.
>> And it determines how fast it can send more LSPs based on the current
>> number of unacked LSPs. Every time the sender receives a PSNP, it
>> knows the receiver got a number of LSPs, so it can increase its
>> send-window again, and then send more LSPs.
>> Correct ?
>>
>> I agree that the core idea of this algorithm makes sense.
>> After all, it looks a lot like TCP.
>> I believe the authors of draft-decraene-lsr-isis-flooding-speed were
>> planning something like that for the next version of their draft.
>>
>>
>> However, I do not agree with the name "tx driven flow control".
>> I also do not agree that this algorithm is "a local trick".
>> Therefor I also do not think this algorithm doesn't need to be
>> documented (in an RFC).
>>
>> In your "tx based flow control", the sender (tx) sends LSPs at a rate
>> that is derived from the rate at which it receives PSNPs. Therefor
>> it is the sender of the PSNPs that sets the speed of transmission !
>> So it is still the receiver (of LSPs) that controls the flow control.
>> The name "tx based flow control" is a little misleading, imho.
>>
>>
>> It is important to realize that the success of your algorithm actually
>> depends on the behaviour of the receiver. How does it send PSNPs ?
>> Does it send one PSNP per received LSP ? Or does it pack multiple acks
>> in one PSNP ? Does it send a PSNP immediatly, or does it wait a short
>> time ? Does it try to fill a PSNP to the max (putting ~90 acks in one
>> PSNP) ? Does the receiver does something in between ? I don't think
>> the behaviour is specified exactly anywhere.
>>
>> I know about an IS-IS implementation from the nineties. When a router
>> would receive an LSP, it would a) set the SSN bit (for that
>> LSP/interface),
>> and b) start the psnp-timer for that interface (if not already running).
>> The psnp-timer would expire 2 seconds later. The router would then walk
>> the LSPDB, find all LSPs with the SSN-bit set for that interface. And
>> then build a PSNP with acks for all those LSPs. The result would be
>> that: a) the first PSNP would be send 2 seconds (+/- jitter) after
>> receiving the first LSP, and b) the PSNP would include ~66 acks. (As
>> a router receiving at full speed would have received 66 LSPs in 2
>> seconds).
>>
>> For your "tx based flow control" algorithm to work properly, this has
>> to change. The receiving router must send PSNPs more quickly and more
>> aggressively. The result would be that there will be less acks in each
>> PSNP. And thus more PSNPs will be sent.
>>
>> This makes us realize: in the current situation, if a router receives
>> a 1000 LSPs, and sends those LSPs to 64 neighbors, it would receive:
>> - the 1000 LSPs from an upstream neighbor, plus
>> - 1000/66 = 16 PSNPs from each downstream neighbor = 64 * 16 = 1024
>> PSNPs.
>> This makes a total of ~2000K PDUs received.
>>
>> If routers would send one PSNP per LSP (to have faster flow control),
>> then the router in this example would receive:
>> - the 1000 LSPs from an upstream neighbor, plus
>> - 1000 PSNPs from each downstream neighbor * 16 = 1600 PSNPs.
>> This makes a total of ~17000 PDUs received.
>>
>> The total number of PDUs received on this router would go from 2K PDUs
>> to 17K PDUs.
>>
>> Remember that the problem we're trying to solve here is to make sure
>> that routers do not get overrun on the receipt side with too many
>> packets too quickly. It seems an aggressive PSNP-scheme, to achieve
>> faster flow-control, is actually very counter-productive.
>>
>> Of course the algorithm can be tweaked. E.g. TCP sends one ack per
>> every 2 received segments (if I'm not mistaken). If we do that here,
>> the number of PDUs would go down from 17K to 9K PDUs. What do you
>> propose ? How do you want the feedback of PSNPs to be quick, while
>> maintaining an efficient packing of multiple acks per PSNP ?
>>
>>
>> In any case, the points I'm trying to make here:
>> *) Your algorithm is not sender-driven, but still receiver-driven.
>> *) Your algorithm changes/dictates behaviour both on sender and
>> receiver.
>> *) Interaction between a sender and a receiver is what we call a
>> protocol.
>>     If you want to make this work, especially in multi-vendor
>> environments,
>>     we need to document these algorithms. Aka in an RFC.
>>
>> Kind regards,
>>
>> 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
>