Subject: [Bier] comments on draft-bergmann-bier-ccast

From: Tony Przygienda <[email-masked]>
Date: Sun, 17 Jul 2016 04:08:24 -0700

Read the draft with interest.

Generally, not sure how it touches BIER specifically. It seems to specify
RPL extensions. Yes, one could reuse the BIER bit mask to propagate a BLOOM
filter instead of a perfect mask @ the benefit of 'set bit mask
compression' vs. the cost of spurious transmissions as the draft
acknowledges where the degenerate case is a full broadcast. The according
BIER procedures/approach is nowhere to be found in the draft though ...

As nit I didn't find in 6550 anything talking about "storing mode" so a
better reference is needed.

--- tony

---

From: Toerless Eckert <[email-masked]>
Date: Wed, 20 Jul 2016 19:04:33 -0700

Yes, quite inteesting. Listened to Carstens preso and had a chat
with him afterwards.  Read my comment on roll mailing list,
i was mostly surprised about the target use case. Really an excellent
use case for BIER-TE.  Just throw IP multicast away ;-)

Wrt to the logic:

The basic concept is not RPL specific but could be applied elsewhere:

Bloom-filter: Take eg: 256 bits, compress into 64 bits: Each of the 
256 bits becomes eg: a randomn set of 4 of those 64 bits. You consider
a bit set if all those 4 bits in the compressed 64 bit are set. So
you match against a bitmask instead of a single bit in forwarding.

You can effectively only use this if the trees are sparse (few bits set)
else the number of false positives is getting too high. The exact
stochastics still escapes me. And you could send to a denser group by
just sending differrent copies. But how more efficient that is than
doing thre same thing to BIER/BIER-TE - that type of comparison also escapes me.

RPL storing mode means that the intermediate RPL routers have a routing table,
non-storing mode means they don't - and the root sends packet with effectively
a source route. 

BIER requires intermediate nodes to have BFER routes to build the BIFT.
So you need storing mode. Most lightweight intermediate RPL router implementations
don't seem to implement this (we implement it in IOS, but yeah... not lightweight ;-).
So the draft describes the most simple BIER-TE like forwrding logic where every
link/outgoing-interface is a "bit". 

If you don't need bitstring compression in a RPL network just use
uncompressed bitstring, and you've got a very simple version of BIER-TE.
And with storing routers, you could equally run BIER in these RPL networks.

The 100,000$ problem to apply bloom filters to "normal" (non-RPL) BIER/BIER-TE
environments are the false positives: In BIER-TE they can cause loops.
And the bits can't be reset due to the bloom filter logic. If i remember
BIER (no TE) well enough, we would at least get duplicates if we can not
reset bits (not quite sure about loops). In RPL there is only a spanning
tree from the root, so no alternative path / loops == false positives
are only a little bit wasted bandwidth.

The name BIER-TE for a RPL or any other spanning tree network is of course
somewhat irritating. There's no real "TE" choise - there's only one path
towards every receiver. Maybe call it BIER-HB2 (Hop-By-Hop-Bits).

Cheers
    Toerless

Free Cultural Education Program: If you order a Bit-Burger beer here in
Germany, please do not expect patties or buns. Burger is just from
Burg = castle. Alas, they also serve the beer without the castle.

> _______________________________________________
> BIER mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/bier

-- 
---
Toerless Eckert, [email-masked]

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 21 Jul 2016 07:09:12 +0200

Hi Tony,

thanks for taking note of this draft.

> Generally, not sure how it touches BIER specifically. It seems to
> specify RPL extensions. 

Indeed. We used the "WG name" BIER in the draft at the time we submitted
the first version because the BIER BOF was just happening and we weren't
sure where this would end up.  By now it is pretty clear this will end
up in ROLL (if at all), but resubmitting the draft to create a new -00
just for a WG name change is confusing.

> Yes, one could reuse the BIER bit mask to
> propagate a BLOOM filter instead of a perfect mask @ the benefit of 'set
> bit mask compression' vs. the cost of spurious transmissions as the
> draft acknowledges where the degenerate case is a full broadcast. The
> according BIER procedures/approach is nowhere to be found in the draft
> though ... 

No, as we are indeed focusing on RPL.

One very important thing we get from RPL is the rank, which allows us to
avoid forwarding loops even though the individual routers are pretty
much oblivious about the structure of the network (non-storing mode is
based on source routes from the root of the destination-oriented
directed acyclic graph, DODAG).  So I wouldn't immediately know how to
generalize the current approach to other underlying unicast routing
protocols.  But the use of bloom filters (instead of bitmaps) to
identify a set of outgoing interfaces is probably extractable, if that
is useful somewhere else.

> better reference is needed. 

Hmm, I find 81 places in there.  (But Ccast is for non-storing mode.)

Grüße, Carsten

---

From: Toerless Eckert <[email-masked]>
Date: Thu, 21 Jul 2016 02:13:18 -0700

Thinking more of it (fun to analyse ;-):

Without having done the math, i'd suspect this might be very efficient in
very large networks for small-receiver-sets. Aka: 2048 NFER/receivers, 64
bits bitstring, max normal number of receivers ca. 16 for a packet.

This could be very efficient in very large networks for "small-receiver-set".
Aka: 2048 BFER/receivers. Maybe typically 16 receivers.

This is not 100% tied to RPL. Consider a data-center with 100,000 VMs,
with thousands of 'vlans', each hosting a typically a quite limited
number of VMs. Instead of creating per-VLAN flood-state across the DC
(which AFAIK gets complicated with all the overlay options involved),
you could simply use maybe hmm... 256 ? bits bitstring. 

You need spanning tree forwarding (no redundancy). And you need some
logic figuring out the intermediate  interfaces in the bitstring. In
RPL, the root does this. In a DC this could be more tricky.

On Thu, Jul 21, 2016 at 07:09:12AM +0200, Carsten Bormann wrote:
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Tony Przygienda <[email-masked]>
Date: Thu, 21 Jul 2016 08:06:40 -0700

yep, all good discussion. Of all, I missed the possible looping for BIER of
false positives. That needs treatment before the whole idea is feasible I
think ...

-- 
*We’ve heard that a million monkeys at a million keyboards could produce
the complete works of Shakespeare; now, thanks to the Internet, we know
that is not true.*
—Robert Wilensky