Re: [Bier] BIER: draft-eckert-bier-cgm2-rbs-01 with performance analysis simulation

Toerless Eckert <tte@cs.fau.de> Mon, 14 February 2022 15:08 UTC

Return-Path: <eckert@i4.informatik.uni-erlangen.de>
X-Original-To: bier@ietfa.amsl.com
Delivered-To: bier@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3D5063A1010 for <bier@ietfa.amsl.com>; Mon, 14 Feb 2022 07:08:47 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.869
X-Spam-Level:
X-Spam-Status: No, score=-5.869 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HEADER_FROM_DIFFERENT_DOMAINS=0.25, RCVD_IN_DNSWL_HI=-5, SPF_HELO_NONE=0.001, SPF_NEUTRAL=0.779, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 1vKE1R3j1xK7 for <bier@ietfa.amsl.com>; Mon, 14 Feb 2022 07:08:42 -0800 (PST)
Received: from faui40.informatik.uni-erlangen.de (faui40.informatik.uni-erlangen.de [IPv6:2001:638:a000:4134::ffff:40]) (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 681AD3A100B for <bier@ietf.org>; Mon, 14 Feb 2022 07:08:39 -0800 (PST)
Received: from faui48e.informatik.uni-erlangen.de (faui48e.informatik.uni-erlangen.de [IPv6:2001:638:a000:4134::ffff:51]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits)) (No client certificate requested) by faui40.informatik.uni-erlangen.de (Postfix) with ESMTPS id 45299549B56; Mon, 14 Feb 2022 16:08:32 +0100 (CET)
Received: by faui48e.informatik.uni-erlangen.de (Postfix, from userid 10463) id 3C2BF4EA658; Mon, 14 Feb 2022 16:08:32 +0100 (CET)
Date: Mon, 14 Feb 2022 16:08:32 +0100
From: Toerless Eckert <tte@cs.fau.de>
To: Aijun Wang <wangaijun@tsinghua.org.cn>
Cc: "'Jeffrey (Zhaohui) Zhang'" <zzhang@juniper.net>, bier@ietf.org, bing.xu@huawei.com
Message-ID: <YgpwcK/VpoHdpSi+@faui48e.informatik.uni-erlangen.de>
References: <YgQTlG4sgMM+cFPG@faui48e.informatik.uni-erlangen.de> <BL0PR05MB5652537CC10FDCE8DACE5B6DD42E9@BL0PR05MB5652.namprd05.prod.outlook.com> <YgU/xfYKvl3be42X@faui48e.informatik.uni-erlangen.de> <017301d82178$0ebb07c0$2c311740$@tsinghua.org.cn>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <017301d82178$0ebb07c0$2c311740$@tsinghua.org.cn>
Archived-At: <https://mailarchive.ietf.org/arch/msg/bier/3RPbl9iRAdOnq5WtBAHDscYHSv0>
Subject: Re: [Bier] BIER: draft-eckert-bier-cgm2-rbs-01 with performance analysis simulation
X-BeenThere: bier@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "\"Bit Indexed Explicit Replication discussion list\"" <bier.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/bier>, <mailto:bier-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/bier/>
List-Post: <mailto:bier@ietf.org>
List-Help: <mailto:bier-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/bier>, <mailto:bier-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 14 Feb 2022 15:08:47 -0000

On Mon, Feb 14, 2022 at 03:54:12PM +0800, Aijun Wang wrote:
> I think another benefit of the CGM2/RBS is the flexible/independent
> assignment of BP for each adjacency on the BFR/BFER in large network. 

Yes, i think thats a restatement of what my second point to Jeffrey was.

> But the drawback is that it can't coexist with the existing BIER forwarding behavior.

Hmm...

- CGM2/RBS could use the existing RFC8296 header, we'd just have
  unused bitstring bits up to the next valid bitstring size of RFC8296
  (64/128/256/...4096). If we optimize the algorithm to break a large
  tree into multiple packets, we should be able to minimize this unused
  bit overhead. But of course, only legacy concerns stop us from also
  defining a newer header and let the market slowly move to that.

- The CGM2/RBS forwarding behavior is really just the most simple
  bit behavior of BIER-TE plus the additional coding to extract the
  bitstring from the header and then for every copy to rewrite the bitstring
  (see pseudocode).  But of course, those two new operations have to be checked
   vs. available vendor NPU coding abilities.

Cheers
    Toerless
> 
> Best Regards
> 
> Aijun Wang
> China Telecom
> 
> -----Original Message-----
> From: bier-bounces@ietf.org <bier-bounces@ietf.org> On Behalf Of
> tte@cs.fau.de
> Sent: Friday, February 11, 2022 12:40 AM
> To: Jeffrey (Zhaohui) Zhang <zzhang@juniper.net>
> Cc: bier@ietf.org; bing.xu@huawei.com
> Subject: Re: [Bier] BIER: draft-eckert-bier-cgm2-rbs-01 with performance
> analysis simulation
> 
> Jeff,
> 
> It is indeed initially somewhat counterintuitive to think that the CGM2/RBS
> bitstring encoding could be more efficient (less copies) than BIER - given
> how BIER does not even need to encode the tree but just the leaves. Whereas
> CGM2/RBS does encode the tree.
> 
> The reason becomes IMHO more obvious, when one considers that BIER needs to
> send a separate packet copy even if just ONE BFER in the bitstring needs a
> copy. If we have a BSL of 256 bits, it means we encoded 255 "dead-weight"
> bits. And if we want to replicate a packet to N% out of a large number of
> BFER one can imagine how we get to the points where where the bitstring of
> every packet copy will have only a few bits set.
> 
> With the compressed tree model, the length of each bitstring of interest is
> just the total number of direct adjacencies (BFER or BFR), so the efficiency
> of each such bitstring is never as low as 1/256, but maybe just 1/20 - if
> the BFR has
> 20 neighbors (other BFR or BFER). So within a max of 256 bits of "variable
> length encoded tree", there is maybe better than 10% of bits to which a copy
> is made.
> 
> Meaning: I wouldn't want to bet a large amount of money on how exactly the
> comparison would play out when we increase the BSL size for both BIER and
> CGM2/RBS (as you suggested), because then the efficiency of a BSL=512
> bitstring in BIER could be as low as 1/512 if only one bit is set there.
> Whereas the percentace "replication efficiency per bit of addressing" in
> CGM2/RBS would probably stay the same.
> 
> Cheers
>     Toerless
> 
> 
> On Wed, Feb 09, 2022 at 08:49:26PM +0000, Jeffrey (Zhaohui) Zhang wrote:
> > Hi Toerless,
> > 
> > Not sure if my understanding is correct, but it seems that RBS does not
> reduce the number of bits that are needed to encode the tree. Rather, it
> increases the number of bits (to encode the recursive structure).
> > I agree that it reduces the size of BIFTs, but even current BIER-TE can
> reduce the number of copies if you use a longer bitstring?
> > 
> > Jeffrey
> > 
> > 
> > Juniper Business Use Only
> > 
> > -----Original Message-----
> > From: BIER <bier-bounces@ietf.org> On Behalf Of tte@cs.fau.de
> > Sent: Wednesday, February 9, 2022 2:19 PM
> > To: bier@ietf.org
> > Cc: bing.xu@huawei.com
> > Subject: [Bier] BIER: draft-eckert-bier-cgm2-rbs-01 with performance 
> > analysis simulation
> > 
> > [External Email. Be cautious of content]
> > 
> > 
> > Dear BIER-TE WG:
> > 
> > Robin did add a section (6.3) describing an initial performance gain
> analysis of CGM2/RBS to the github source
> (https://urldefense.com/v3/__https://github.com/toerless/bier-cgm2-rbs__;!!N
> Et6yMaO-gk!WS49OT72vlonSWP3yLtLcW_RQARYP00KEiAWpH592AuDXmrOOJH_bgVzQZyfK9En$
> ), and i just did a bit of editorial fixup and posted it as -01 of the
> draft.
> > 
> > This actually is the first time i actually like the HTML'ized version of a
> draft, because the topology picture is so large it doesn't fit a single
> page:
> > 
> > https://urldefense.com/v3/__https://www.ietf.org/archive/id/draft-ecke
> > rt-bier-cgm2-rbs-01.html__;!!NEt6yMaO-gk!WS49OT72vlonSWP3yLtLcW_RQARYP
> > 00KEiAWpH592AuDXmrOOJH_bgVzQaBIgBPC$
> > 
> > The interesting piece about the comparison is that it is actually
> comparing CGM2/RBS to BIER, and not BIER-TE. Because BIER itself should be
> requiring less copies than BIER-TE, so the gain of CGM2/RBS over BIER-TE
> should be even higher, but the fact alone that you get away with fewer
> packet copies to large receiver sets even though the bitstring also needs to
> encode the path/tree towards the receivers is really cool.
> > 
> > Robin, two Q:
> > 
> > 1. The new text mentions "in our graphs", but the text does not include
> any such graphs (yet).
> > I guess such a graph would be even worse to convert to ASCII than the
> topology.
> > Maybe post whatever format you have those results in to github (PDF,
> png...) and then we actually may want to see if/how a PDF version of the
> draft could include better than just ASCII art. Certainly a good reason to
> finally try it out.
> > And short term we can just add references to such visuals to the draft.
> > 
> > 2; Is it correct to assume that the hops through the topology that you
> simulated are "just" shortest-path, maybe with some ECMP choice - aka: the
> same paths that also BIER would choose given some "default" IGP routing
> setup ?
> > 
> > Cheers
> >     Toerless
> > 
> > _______________________________________________
> > BIER mailing list
> > BIER@ietf.org
> > https://urldefense.com/v3/__https://www.ietf.org/mailman/listinfo/bier
> > __;!!NEt6yMaO-gk!WS49OT72vlonSWP3yLtLcW_RQARYP00KEiAWpH592AuDXmrOOJH_b
> > gVzQZXGUd9P$
> 
> --
> ---
> tte@cs.fau.de
> 
> _______________________________________________
> BIER mailing list
> BIER@ietf.org
> https://www.ietf.org/mailman/listinfo/bier

-- 
---
tte@cs.fau.de