[Bier] comments on draft-ietf-roll-ccast

[Tony Przygienda <[e-mail]>]

Read with interest. Intriguing and something that was rattling in the back
of my skull already for a while having dealt with Blooms in other venues
;-)

Generally, I think I would encourage enquiries into a flavor of BIER
bitmasks being BLOOM filters (especially seeing it was
draft-bergmann-bier-ccast
first ;-), i.e. we don't consider the bitmask something being a perfect
hash of <SD,SI> but rather a BLOOM for a set of <SD,SI>s or maybe even
total SD.  In principle the mask signifies all possible destinations
addressed (incl. false positives) and on forwarding the fastpath has to
hash all possible outgoing destinations on an interface and see whether
they match incoming BLOOM.

--- tony


Footnote: How computationally expensive is that? Well, depends on bunch
variables of course and how much unnecessary replications are we willing to
live with. And of course how many destinations we address on average, the
higher N on bloom the worse the performance unless we are willing to go
high m or accept high p (I use standard BLOOM variable notation here). As
the draft astutely observes, lots of that stuff can be pre-computed on
outgoing interfaces already (in fact just for the BFR-ids that are seen in
the signalling and not all 16K) ...

Simple sample with an intriguing number:

a) assuming 16K BFRs & 1% being addressed on average (N=160) and
b) allowing for p=20% false positives (i.e. 190 BFRs would get it)  and

we could fit with k=2 hash functions e.thing into m=~512 bits mask size.

Of course the false positives go up dramatically if N grows.

Another interesting observation is that using blooms would liberate us from
the 16K BFR-id scaling of technology which in itself maybe an interesting
angle.

There are variations like attenuaned filters but I won't go there further
...

As a quick thought we could even imagine distributing in parallel

MPLS label = <SI,SD,BML>
MPLS label = BLOOM on <SI 1-4, SD, BML>

whereas the BLOOM can be used by the source if e.g. a group is addressed
that only flips a bunch of bits spread across the SIs 1-4 which would be
far more bandwitdth efficient than sending 4 copies.  in 256 bits we can
address up to 26 destinations with p=0.01 albeit k>6