Subject: [Bier] End-to-end BIER

From: Caitlin Bestler <[email-masked]>
Date: Wed, 28 Oct 2015 13:26:11 -0700

There is a broad use-case for BIER that has not been properly 
highlighted: explicit application use of bitmaps
to push multicast messages.

Applications specify the subset of a cluster (BIER sub-domain) that is 
to receive a message on a per packet basis.
Sender-determine, or pushed, targeting is natural for many cluster 
applications, especially storage clusters.
Requiring the sender to tell the receivers that they need to join a 
specific group adds latency to any transaction.
When the determination is truly listener based, or the delivery lasts 
long enough, this overhead is insignificant.
But for transactional messages, such as transferring chunks within a 
storage cluster, the extra latency is a killer.

No real changes are required to support this model. At most a few MAY 
clauses would be added.

Each bit position would represent and end-station rather than a BFER. 
The application would map a destination
IP address to a bit position (or bit-positions for BIER-TE). But such an 
implementation would already be allowed
by simply considering the IP stack on each end station to be its own BFER.

It would also be desirable to use Layer 2 multicasting for the final 
delivery hop. The current pseudo-code implies
unicast delivery. Allowing mutlicast L2 delivery only requires adding 
one clause to the forwarding pseudo-code.
We must allow treating an existing L2 multicast address as though it 
were an anonymous virtual BFER that delivered
to a known set of endpoints. An implementation could create a virtual 
BFER under the current wording, but I believe
it would have to allocate a bit position for each virtual group, and 
then explicitly advertise it. Just allowing the actual
BFER to use multicast Layer 2 delivery is more direct. There is no need 
for BFERs to inform BFIRs that multicast delivery
will be used. It makes no difference to the other BFRs. You can even 
make a case that this is already allowed under the
"no harm no foul" rule.

---

From: Tony Przygienda <[email-masked]>
Date: Wed, 28 Oct 2015 21:44:28 -0700

On Wed, Oct 28, 2015 at 1:26 PM, Caitlin Bestler <
[email-masked]> wrote:

> There is a broad use-case for BIER that has not been properly highlighted:
> explicit application use of bitmaps
> Applications specify the subset of a cluster (BIER sub-domain) that is to
> receive a message on a per packet basis.
> When the determination is truly listener based, or the delivery lasts long
> enough, this overhead is insignificant.
> Each bit position would represent and end-station rather than a BFER. The
> application would map a destination

You pretty much describe how BIER works ;-)

> unicast delivery. Allowing mutlicast L2 delivery only requires adding one
> clause to the forwarding pseudo-code.
> We must allow treating an existing L2 multicast address as though it were
> an anonymous virtual BFER that delivered
> to a known set of endpoints. An implementation could create a virtual BFER
> under the current wording, but I believe
> it would have to allocate a bit position for each virtual group, and then
> explicitly advertise it. Just allowing the actual
> will be used. It makes no difference to the other BFRs. You can even make
> a case that this is already allowed under the
> "no harm no foul" rule.
>
>
yes, I agree, such "virtual BFERs" would be possible but are more of an
overlay thing I would say. BIER layer just
delivers the bit to where the bit is announced ;-) No claims are made that
one bit must represent precisely one end-receiver.
In fact for inter-area BIER I think we'll have a bit representing a set of
receivers in possibly a different BIER domain
(I have all that only on paper napkins ;-)

As well, one could even imagine BIER overlay being driven completely by
multicast MAC snooping I think (albeit delivery per IP multicast group
would be not optimal) .

BIER architecture is currently "wide" enough to accomodate all that IMO so
I don't see any changes necessary albeit such a
"use case" description would be interesting given a specific application
(storage in your case I guess).

-- tony

---

From: Eric C Rosen <[email-masked]>
Date: Thu, 29 Oct 2015 13:15:43 -0400

[Caitlin] Each bit position would represent and end-station rather than
a BFER. The application would map a destination IP address to a bit
position (or bit-positions for BIER-TE).

This is really just a control plane issue.

[Caitlin] allowing the actual BFER to use multicast Layer 2 delivery is 
more direct. There is no need for BFERs to inform BFIRs that multicast 
delivery will be used. It makes no difference to the other BFRs. You can 
even make a case that this is already allowed under the "no harm no 
foul" rule.

This seems a bit more problematic to me, as the LAN might attach to 
multiple transit BFRs.  Consider a topology like:

         |----BFR-B---Endpoint-1
BFR-A---|      |
         |----Endpoint-2

That is, BFR-A, BFR-B, and Endpoint-2 are on the LAN, while Endpoint-1 
is downstream of BFR-B.  BFR-B also has another interface that attaches 
to Endpoint-2.  All links are equal cost to the IGP.

Suppose BFR-A receives a packet whose BitString says that the BFERs are 
Endpoint-1 and Endpoint-2.

With existing procedures, BFR-A sends BFR-B the packet with only 
Endpoint-1's bit set, and BFR-A sends Endpoint-2 the packet with only 
Endpoint-2's bit set.

If BFR-A uses layer 2 multicast to send a single packet to both BFR-B 
and Endpoint-2, Endpoint-2's bit will still be set in the packet 
received by BFR-B.  So BFR-B will forward the packet to Endpoint-2, and 
Endpoint-2 will now receive two copies of the packet.

Another problematic scenario:

         |----BFR-B---Endpoint-1
BFR-A---|      |
         |----Endpoint-2
BFR-C---|
         |----Endpoint-3

Here BFR-C and Endpoint-3 are also on the LAN.  Suppose BFR-A receives a 
packet (from one of its other interfaces) whose BitString identifies 
Endpoint-1 and Endpoint-2, while BFR-C receives the same packet (from 
one of its other interfaces), but with a BitString identifying only 
Endpoint-3.  When BFR-A and BFR-C multicast the packet to the LAN, we 
need to make sure that BFR-A and BFR-C don't receive the packet from 
each other, and that BFR-B doesn't receive the packet from BFR-C.  If, 
for example, BFR-C gets the packet from BFR-A, it will conclude from the 
BitString that the packet still needs to be sent to Endpoint-1 and 
Endpoint-2.

It would be an interesting exercise to see if one could state a set of 
enforceable applicability restrictions that eliminate these problems.

The various proposals for MLD/IGMP/PIM overlays address problems like 
this, but the solutions are not at the BIER layer, so I don't think they 
apply directly to the case of end-to-end BIER.

---

From: Caitlin Bestler <[email-masked]>
Date: Thu, 29 Oct 2015 12:56:37 -0700

On 10/29/15 10:15 AM, Eric C Rosen wrote:
> [Caitlin] allowing the actual BFER to use multicast Layer 2 delivery 
> is more direct. There is no need for BFERs to inform BFIRs that 
> multicast delivery will be used. It makes no difference to the other 
> BFRs. You can even make a case that this is already allowed under the 
> "no harm no foul" rule.
>
> is downstream of BFR-B.  BFR-B also has another interface that 
> attaches to Endpoint-2.  All links are equal cost to the IGP.
>
> Suppose BFR-A receives a packet whose BitString says that the BFERs 
> are Endpoint-1 and Endpoint-2.
>
> received by BFR-B.  So BFR-B will forward the packet to Endpoint-2, 
> and Endpoint-2 will now receive two copies of the packet.
>
> Here BFR-C and Endpoint-3 are also on the LAN.  Suppose BFR-A receives 
> a packet (from one of its other interfaces) whose BitString identifies 
> for example, BFR-C gets the packet from BFR-A, it will conclude from 
> the BitString that the packet still needs to be sent to Endpoint-1 and 
> Endpoint-2.
>
> this, but the solutions are not at the BIER layer, so I don't think 
> they apply directly to the case of end-to-end BIER.
>
I'm not certain what the correct phrasing is in routing terminology, but 
going down one layer doing an L2 local-only delivery
is remarkably easy. Each L2 subnet knows its boundaries, and there is 
never an ambiguity about whether a given link is being
used to *forward* and Ethernet frame as opposed to *routing* an IP datagram.

If a BFER does not know how to do a local only L2 multicast then it 
should probably refrain from using that solution.

The fact that a spontaneously appearing MRouter appearing without notice 
would create problems in a WAN environment
is not a reason to avoid using this optimizaton in a datacenter where 
all forwarders and routers are known and the only
question to be determined dynamically is which of them are up.