Subject: [Bier] When not all transit nodes support BIER

From: Eric C Rosen <[email-masked]>
Date: Tue, 6 Jan 2015 10:21:51 -0500

The BIER architecture should cover the scenario in which some of the 
transit routers in a BIER domain are not BFRs (i.e., some of the transit 
routers do not support BIER).  I think this scenario can be covered 
fairly easily.  However, we still assume that the ingress and egress 
nodes support BIER; the following only handles the case of transit nodes 
that do not support BIER.  Also, the following only handles the case 
where the "routing underlay" is an SPF-based IGP that computes a tree 
from each node to all other nodes in the domain.

At a given BFR, say BFR B, start with a copy of the IGP-computed 
shortest path tree from BFR B to each router in the domain.  (This tree 
is computed by the SPF algorithm of the IGP.)  Let's call this copy the 
"BIER-SPF tree rooted at BFR B."  BFR B then modifies this BIER-SPF tree 
as follows.

BFR B looks in turn at each of B's child nodes on the BIER-SPF tree.

If one of the child nodes does not support BIER, BFR B will remove that 
node from the tree.  The child nodes of the node that has just been 
removed will be re-parented on the tree, so that BFR B now becomes their 
parent.

BFR B then continues to look at each of its child nodes, including any 
nodes that have been re-parented to B as a result of the previous step.

When all of the child nodes (the original child nodes plus any new ones)
have been examined, B's children on the BIER-SPF tree will all be BFRs.
When the BIFT is constructed, B's child nodes on the BIER-SPF tree will 
be the BFR "adjacencies".  The F-BMs and outgoing BIER-MPLS labels must 
be computed appropriately, based on the BIER adjacency.

B may now have child nodes that are not "directly connected" to B via 
layer 2.  To send a packet to one of these child nodes, B will have to 
send the packet through a unicast tunnel.  This may be as simple as 
finding the IGP unicast next hop to the child node, and pushing on 
(above the BIER-MPLS label advertised by the child) the MPLS label that 
the IGP next hop has bound to an address of the child node.

Of course, the above is not meant as an implementation technique, just 
as a functional description.

A similar technique can be used to provide node protection.  I.e., the 
failed neighbor of BFR B can be removed from B's BIER-SPF tree, and the 
child nodes of the failed node can be re-parented to B.  However, 
getting the packet from B to the child nodes of the failed node is a bit 
more complicated, as it may require using a bypass tunnel to get around 
the failed node.

I think something like this should be incorporated into the architecture
document.

When using a unicast tunnel to get a packet to an "adjacent" BFR, it may 
be advantageous to (a) set the TTL of the MPLS label entry representing 
the "tunnel" to a large value, rather than copying the TTL value from 
the BIER-MPLS label, and (b) when the tunnel labels are popped off, to 
avoid copying the TTL from the tunnel labels to the BIER-MPLS label. 
That way, the TTL of the BIER-MPLS label would only control the number 
of "BFR hops" that the packet may traverse.

Comments?

---

From: Albert Tian <[email-masked]>
Date: Tue, 6 Jan 2015 18:24:17 +0000

Hi Eric,

Yes this is a very good description of the solution. Comments inlined.

Thanks,
Albert

>from each node to all other nodes in the domain.

[Albert] I don¹t see why we can not handle other type of distribution
trees in the same way as SPF trees, if we are using some form of tunneling
technology (such as MPLS) to encapsulate the BIER packet over these
non-BFRs. If the tree building algorithm is not SPF based, it is possible
that a given packet may pass through a given BFR more than once: once
through BIER processing, another time as part of a tunnel. However, there
should be no forwarding loops.

>"BIER-SPF tree rooted at BFR B."  BFR B then modifies this BIER-SPF tree

[Albert] The key change here is the definition of a BFR-NBR and BFR-NH in
section 6.2 of the architecture document. We now allow a BFR-NH to be
non-adjacent in the routing underlay, as long as there is an underlying
tunneling technology to deliver packets to the BFR-NH.

It maybe more convenient to use BFR-NH in our discussions moving forward,
with the knowledge that a BFR-NH may be reachable via a tunnel. In section
6.2 I would suggest we change the section title to BFR Next Hop (BFR-NH).
Here is a proposed new definition of BFR-NH:

³The BFR-NH for a given BFER X from a BFR A, is the first BFR (BIER
capable router) on the path from BFR A to BFER X according to the BIER
distribution tree."

We can also define BFR-NBR as anonymous to BFR-NH and can be non-adjacent
according to routing underlay.

In section 6.4 the derivation of BIFT from BIRT remains unchanged.

In section 6.5 The BIER Forwarding Procedure, we may add to step 4: ³In
case the BFR-NBR is reachable via a tunnel according to the routing
underlay, we may need to encapsulate the BIER packet and send it to the
tunnel associated with the BFR-NBR."

With the above definition of BFR-NH/BFR-NBR, the impact on the rest of the
BIER architecture may be minimized.
[/Albert]

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