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

"" <> Mon, 14 February 2022 14:50 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id BD0233A0F8D for <>; Mon, 14 Feb 2022 06:50:49 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 1.05
X-Spam-Level: *
X-Spam-Status: No, score=1.05 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, GB_SUMOF=5, HEADER_FROM_DIFFERENT_DOMAINS=0.25, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id h8fGu-7sntan for <>; Mon, 14 Feb 2022 06:50:45 -0800 (PST)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id ADA883A0F44 for <>; Mon, 14 Feb 2022 06:50:44 -0800 (PST)
Received: from ( []) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by (Postfix) with ESMTPS id CE29A549B4C; Mon, 14 Feb 2022 15:50:39 +0100 (CET)
Received: by (Postfix, from userid 10463) id B7EE24EA657; Mon, 14 Feb 2022 15:50:39 +0100 (CET)
Date: Mon, 14 Feb 2022 15:50:39 +0100
From: "" <>
To: "Jeffrey (Zhaohui) Zhang" <>
Cc: "" <>, "" <>
Message-ID: <YgpsP/>
References: <> <> <YgU/> <>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <>
Archived-At: <>
Subject: Re: [Bier] BIER: draft-eckert-bier-cgm2-rbs-01 with performance analysis simulation
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "\"Bit Indexed Explicit Replication discussion list\"" <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 14 Feb 2022 14:50:50 -0000

On Thu, Feb 10, 2022 at 08:29:11PM +0000, Jeffrey (Zhaohui) Zhang wrote:
> Hi Toerless,
> I was indeed comparing RBS with BIER-TE, where both encode the tree.

;-) Sorry that i didn't read that from your email.

> Here is my understanding:
> - To reach N BFERs, you'll need at N bits for sure; to encode K replication points, you need K bits for sure. This does not change with RBS - that's what I meant in the previous email.
> - I do realize that RBS has this advantage: If a packet does not need to go through some replication points that some other packets need to, then this packet does not need all the bits that BIER-TE would need to allocate (but not necessarily set in bitstring). All bits have local significance.
> So, depending on how granular the TE path needs to be, RBS indeed could be very efficient. Is that correct?

Yes. But the efficiency does not only come from not having to have in the bitstring
bits you don't need as you said. That is just one side of the coin.

IMHO the mayor savings come from actually being able to have all the bits you do
want to have (up to the max structured bitstring length supported by HW), and not
being forced to figure out during network configuration:

a) how to split up bitstring space into SI (BIER, BIER-TE), 
b) how to optimize bits (use advanced bits, leacve out "unneded" bits) (BIER-TE).

That's what my thought example was about: What if you want to replicate to N (small)
BFER (whether BIER or BIER-TE), and each bit is in a different SI ?

Of course, if the bitstring would become too large to fit all desired bits into
one packet, you still need to send multiple packets, and there is an interesting
optimization calculation to be done:

  Given a tree described by a set of replication nodes and leaves:
  Determine a minimum number N of sub-trees such that:
  1) Each sub-tree includes a disjoint subset of leave.
  2) The sum of leaves of the sub-trees is the set of leaves of the tree.
  3) The encoded bitstring of each sub-tree fits some max-bitstring limit
  4) The sum of duplicate edges across sub-trees is minimal
     (if an edge occurs N times, it is counted N-1 times as a duplicate edge).

I think this type of "efficiency" metric applies to all of BIER,BIER-TE,CGM2/RBS


> Jeffrey
> Juniper Business Use Only
> -----Original Message-----
> From: <>
> Sent: Thursday, February 10, 2022 11:40 AM
> To: Jeffrey (Zhaohui) Zhang <>
> Cc:;
> Subject: Re: [Bier] BIER: draft-eckert-bier-cgm2-rbs-01 with performance analysis simulation
> [External Email. Be cautious of content]
> 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 <> On Behalf Of
> > Sent: Wednesday, February 9, 2022 2:19 PM
> > To:
> > Cc:
> > 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 (;!!NEt6yMaO-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:
> >
> >
> > 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
> >
> >
> > __;!!NEt6yMaO-gk!WS49OT72vlonSWP3yLtLcW_RQARYP00KEiAWpH592AuDXmrOOJH_b
> > gVzQZXGUd9P$
> --
> ---
> Juniper Business Use Only