Re: [Roll] [Bier] comments on draft-bergmann-bier-ccast

If you have a spanning tree (like a RPL preferred parent tree) or even a DODAG (the traditional structure RPL builds), and then you follow it, the packets will not loop.
The false positive causes a packet to be forwarded down the tree by a grand-parent to a parent that has children that match some of the bits and other children that match some others of the bits; so the parent as an advertiser of the whole set of bits for all its children appears to match all the bits. The false positive makes it so that the parent will get an extraneous copy of the packet. And the packet may be forwarded uselessly down the tree till the parent with the fork, some bits only via one child and some other bits only via another child, so no match. That parent will drop the packet. End of the story.

Pascal

From: Roll [mailto:roll-bounces@ietf.org] On Behalf Of Tony Przygienda
Sent: jeudi 21 juillet 2016 17:07
To: Toerless Eckert (eckert) <eckert@cisco.com>
Cc: Routing Over Low power and Lossy networks <roll@ietf.org>; bier@ietf.org; draft-bergmann-bier-ccast@ietf.org
Subject: Re: [Roll] [Bier] comments on draft-bergmann-bier-ccast

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 ...

On Thu, Jul 21, 2016 at 2:13 AM, Toerless Eckert <eckert@cisco.com<mailto:eckert@cisco.com>> wrote:
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:
> 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.
>
> > As nit I didn't find in 6550 anything talking about "storing mode" so a
> > better reference is needed.
>
> Hmm, I find 81 places in there.  (But Ccast is for non-storing mode.)
>
> Grüße, Carsten
>
> _______________________________________________
> Roll mailing list
> Roll@ietf.org<mailto:Roll@ietf.org>
> https://www.ietf.org/mailman/listinfo/roll

--
---
Toerless Eckert, eckert@cisco.com<mailto:eckert@cisco.com>

--
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