6.8.  Prevention of Loops and Duplicates

   The BitString in a BIER-encapsulated packet specifies the set of
   BFERs to which that packet is to be forwarded.  When a
   BIER-encapsulated packet is replicated, no two copies of the packet
   will ever have a BFER in common.  If one of the packet's BFERs
   forwards the packet further, that BFER will first clear the bit that
   identifies itself.  As a result, duplicate delivery of packets is not
   possible with BIER.

   As long as the routing underlay provides a loop-free path between
   each pair of BFRs, BIER-encapsulated packets will not loop.  Since
   the BIER layer does not create any paths of its own, there is no need
   for any BIER-specific loop-prevention techniques beyond the
   forwarding procedures specified in Section 6.5.

   If, at some time, the routing underlay is not providing a loop-free
   path between BFIR-A and BFER-B, then BIER-encapsulated packets may
   loop while traveling from BFIR-A to BFER-B.  However, such loops will
   never result in delivery of duplicate packets to BFER-B.

   These properties of BIER eliminate the need for the "Reverse Path
   Forwarding" (RPF) check that is used in conventional IP multicast
   forwarding.

6.9.  When Some Nodes Do Not Support BIER

   The procedures of Section 6.2 presuppose that, within a given BIER
   domain, all the nodes adjacent to a given BFR in a given routing
   underlay are also BFRs.  However, it is possible to use BIER even
   when this is not the case, as long as the ingress and egress nodes
   are BFRs.  In this section, we describe procedures that can be used
   if the routing underlay is an SPF-based IGP that computes a
   shortest-path 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.

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

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

   3.  BFR-B then continues to look at each of its child nodes,
       including any nodes that have been re-parented to BFR-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, BFR-B's children on the BIER-SPF tree will
   all be BFRs.

   When the BIFT is constructed, BFR-B's child nodes on the BIER-SPF
   tree are considered to be the BFR-NBRs.  The F-BMs must be computed
   appropriately, based on the BFR-NBRs.

   BFR-B may now have BFR-NBRs that are not "directly connected" to
   BFR-B via Layer 2.  To send a packet to one of these BFR-NBRs, BFR-B
   will have to send the packet through a unicast tunnel.  In an MPLS
   network, this may be as simple as finding the IGP unicast next hop to
   the child node and pushing on (above the BIER encapsulation header)
   an MPLS label that the IGP next hop has bound to an address of the
   child node.  (This assumes that the packet is using an MPLS-based
   BIER encapsulation, such as the one specified in Section 2.1 of
   [MPLS_BIER_ENCAPS].)  Of course, the BIFT-id in the BIER
   encapsulation header must be the BIFT-id advertised by the child node
   for the packet's SI, sub-domain, and BitStringLength.

   If for some reason the unicast tunnel cannot be an MPLS tunnel, any
   other kind of tunnel can be used, as long as the encapsulation for
   that tunnel type has a way of indicating that the payload is a
   BIER-encapsulated packet.

   Note that if a BIER-encapsulated packet is not using an MPLS-based
   BIER encapsulation, it will not be possible to send it through an
   MPLS tunnel unless it is known that the tunnel only carries BIER
   packets; this is because MPLS has no "next protocol type" field.
   This is not a problem if an MPLS-based BIER encapsulation is used,
   because in that case the BIER encapsulation begins with an MPLS label
   that identifies the packet as a BIER-encapsulated packet.

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

   While the above description assumes that the routing underlay
   provides an SPF tree, it may also be applicable to other types of
   routing underlays.

   The technique above can also be used to provide "node protection"
   (i.e., to provide fast reroute around nodes that are believed to have
   failed).  If BFR-B has a failed BFR-NBR, BFR-B can remove the failed
   BFR-NBR from the BIER-SPF tree and can then re-parent the child
   BFR-NBRs of the failed BFR-NBR so that they appear to be BFR-B's own
   child nodes on the tree (i.e., so that they appear to be BFR-B's
   BFR-NBRs).  The usual BIER forwarding procedures then apply.
   However, getting the packet from BFR-B to the child nodes of the
   failed BFR-NBR is a bit more complicated, as it may require using a
   unicast bypass tunnel to get around the failed node.

   A simpler variant of step 2 above would be the following:

      If one of the child nodes does not support BIER, BFR-B removes
      that node from the tree.  All BFERs that are reached through that
      child node are then re-parented on the tree, so that BFR-B now
      becomes their parent.

   This variant is simpler because the set of BFERs that are reached
   through a particular child node of BFR-B can be determined from the
   F-BM in the BIFT.  However, if this variant is used, the results are
   less optimal, because packets will be unicast directly from BFR-B to
   the BFERs that are reachable through the non-BIER child node.

   When using a unicast MPLS tunnel to get a packet to a BFR-NBR:

   o  The TTL of the MPLS label entry representing the tunnel SHOULD be
      set to a large value, rather than being copied from the TTL value
      from the BIER encapsulation header, and

   o  When the tunnel labels are popped off, the TTL from the tunnel
      labels SHOULD NOT be copied to the BIER encapsulation header.

   In other words, the TTL processing for the tunnel SHOULD be as
   specified in [RFC3443] for "Pipe Model" and "Short Pipe Model" Label
   Switched Paths (LSPs).  The same principle applies if the tunnels are
   not MPLS tunnels; the BIER packet SHOULD NOT inherit the TTL from the
   tunnel encapsulation.  That way, the TTL of the BIER encapsulation
   header constrains only the number of BFRs that the packet may
   traverse, not the total number of hops.

   If two BIER packets have the same value in the entropy field of their
   respective BIER headers and if both are transmitted through a given
   tunnel, it is desirable for the tunnel encapsulation to preserve the
   fact that the two packets have the same entropy.

   The material in this section presupposes that if a given router is a
   BFR, then it supports BIER on all its interfaces.  It is, however,
   possible that a router will have some line cards that support BIER
   and some that do not.  In such a case, one can think of the router as
   a "partial BFR" that supports BIER only on some of its interfaces.
   If it is desired to deploy such partial BFRs, one can use the
   multi-topology features of the IGP to set up a BIER-specific
   topology.  This topology would exclude all the non-BIER-capable
   interfaces that attach to BFRs.  BIER would then have to be run in a
   sub-domain that is bound to this topology.  If unicast tunnels are
   used to bypass non-BFRs, either (a) the tunnels have to be restricted
   to this topology or (b) the tunnel endpoints have to be BFRs that do
   not have any non-BIER-capable interfaces.

6.10.  Use of Different BitStringLengths within a Domain

   The procedures of this section apply only when the same encapsulation
   is used throughout the BIER domain.  Consideration of the scenario
   where both multiple encapsulations and multiple BitStringLengths are
   used in a given BIER domain is outside the scope of this document.

   It is possible for different BFRs within a BIER domain to be using
   different Imposition and/or Disposition BitStringLengths.  As stated
   in Section 3:

   "if a particular BFIR is provisioned to use a particular Imposition
   BitStringLength and a particular Imposition sub-domain when imposing
   the encapsulation on a given set of packets, all other BFRs with
   BFR-ids in that sub-domain SHOULD be provisioned to process received
   BIER packets with that BitStringLength (i.e., all other BFRs with
   BFR-ids in that sub-domain SHOULD be provisioned with that
   BitStringLength as a Disposition BitStringLength for that
   sub-domain)."

   Note that mis-provisioning can result in "black holes".  If a BFIR
   creates a BIER packet with a particular BitStringLength and if that
   packet needs to travel through a BFR that cannot process received
   BIER packets with that BitStringLength, then it may be impossible to
   forward the packet to all of the BFERs identified in its BIER header.
   Section 6.10.1 defines a procedure, the "BitStringLength
   Compatibility Check", that can be used to detect the possibility of
   such black holes.

   However, failure of the BitStringLength Compatibility Check does not
   necessarily result in the creation of black holes; Section 6.10.2
   specifies OPTIONAL procedures that allow BIER forwarding to proceed
   without black holes, even if the BitStringLength Compatibility Check
   fails.

   If the procedures of Section 6.10.2 are not deployed but the
   BitStringLength Compatibility Check fails at some BFIR, the BFIR has
   two choices:

   o  Create BIER packets with the provisioned Imposition
      BitStringLength, even though the packets may not be able to reach
      all the BFERs identified in their BitStrings.

   o  Use an Imposition BitStringLength that passes the Compatibility
      Check (assuming that there is one), even if this is not the
      provisioned Imposition BitStringLength.

   Section 6.10.1 discusses the implications of making one or the other
   of these choices.

   There will be times when an operator wishes to change the
   BitStringLengths used in a particular BIER domain.  Section 6.10.3
   specifies a simple procedure that can be used to transition a BIER
   domain from one BitStringLength to another.

6.10.1.  BitStringLength Compatibility Check

   When a BFIR needs to encapsulate a packet, the BFIR first assigns the
   packet to a sub-domain.  The BFIR then chooses an Imposition
   BitStringLength L for the packet.  The choice of Imposition
   BitStringLength is determined by provisioning.  However, the BFIR
   should also perform the BitStringLength Compatibility Check defined
   below.

   The combination of sub-domain S and Imposition BitStringLength L
   passes the BitStringLength Compatibility Check if and only if the
   following condition holds:

      Every BFR that has advertised its membership in sub-domain S has
      also advertised that it is using Disposition BitStringLength L
      (and possibly other BitStringLengths as well) in that sub-domain.
      (If MPLS encapsulation (Section 2.1 of [MPLS_BIER_ENCAPS]) is
      being used, this means that every BFR that is advertising a label
      for sub-domain S is advertising a label for the combination of
      sub-domain S and Disposition BitStringLength L.)

   If a BFIR has been provisioned to use a particular Imposition
   BitStringLength and a particular sub-domain for some set of packets,
   and if that combination of Imposition BitStringLength and sub-domain
   does not pass the BitStringLength Compatibility Check, the BFIR
   SHOULD log this fact as an error.  It then has the following two
   choices about what to do with the packets:

   1.  The BFIR MAY use the provisioned Imposition BitStringLength
       anyway.  If the procedure of either option 2 or option 3 of
       Section 6.10.2 is deployed, this will not cause black holes and
       may actually be the optimal result.  It should be understood,
       though, that the BFIR cannot determine by signaling whether those
       procedures have been deployed.

   2.  If the BFIR is capable of using an Imposition BitStringLength
       that does pass the BitStringLength Compatibility Check for the
       particular sub-domain, the BFIR MAY use that Imposition
       BitStringLength instead.

   Which of these two choices to make is itself determined by
   provisioning.

   Note that discarding the packets is not one of the allowable choices.
   Suppose, for example, that all the BFIRs are provisioned to use
   Imposition BitStringLength L for a particular sub-domain S but one
   BFR has not been provisioned to use Disposition BitStringLength L for
   sub-domain S.  This will cause the BitStringLength Compatibility
   Check to fail.  If the BFIR sends packets with BitStringLength L and
   sub-domain S, the mis-provisioned BFR will not be able to forward
   those packets, and thus the packets may only be able to reach a
   subset of the BFERs to which they are destined.  However, this is
   still better than having the BFIRs drop the packets; if the BFIRs
   discard the packets, the packets won't reach any of the BFERs to
   which they are destined at all.

   If the procedures of Section 6.10.2 have not been deployed, choice 2
   above might seem like a better option.  However, there might not be
   any Imposition BitStringLength that a given BFIR can use that also
   passes the BitStringLength Compatibility Check.  If it is desired to
   use choice 2 in a particular deployment, then there should be a
   "Fallback Disposition BitStringLength" (call it "F") such that:

   o  Every BFR advertises that it uses BitStringLength F as a
      Disposition BitStringLength for every sub-domain, and

   o  If a BFIR is provisioned to use Imposition BitStringLength X and
      Imposition sub-domain S for a certain class of packets but the
      BitStringLength Compatibility Check fails for the combination of
      BitStringLength X and sub-domain S, then the BFIR will fall back
      to using BitStringLength F as the Imposition BitStringLength
      whenever the Imposition sub-domain is S.

   It is RECOMMENDED that the value of F be the default BitStringLength
   for the encapsulation being used.

6.10.2.  Handling BitStringLength Mismatches

   Suppose that a packet has been BIER-encapsulated with a
   BitStringLength value of X and that the packet has arrived at BFR-A.
   Now suppose that according to the routing underlay the next hop is
   BFR-B, but BFR-B is not using X as one of its Disposition
   BitStringLengths.  What should BFR-A do with the packet?  BFR-A has
   three options.  It MUST do one of the three, but the choice of which
   procedure to follow is a local matter.  The three options are:

   1.  BFR-A MAY discard the packet.

   2.  BFR-A MAY re-encapsulate the packet, using a BIER header whose
       BitStringLength value is supported by BFR-B.

       Note that if BFR-B only uses Disposition BitStringLength values
       that are smaller than the BitStringLength value of the packet,
       this may require creating additional copies of the packet.
       Whether additional copies actually have to be created depends
       upon the bits that are actually set in the original packet's
       BitString.

   3.  BFR-A MAY treat BFR-B as if BFR-B did not support BIER at all,
       in which case BFR-A applies the rules of Section 6.9.

   Note that there is no signaling that enables a BFR to advertise which
   of the three options it will use.

   Option 2 can be useful if there is a region of the BIER domain where
   the BFRs are capable of using a long BitStringLength as well as a
   region where the BFRs are only capable of using a shorter
   BitStringLength.

6.10.3.  Transitioning from One BitStringLength to Another

   Suppose one wants to migrate the BitStringLength used in a particular
   BIER domain from one value (X) to another value (Y).  The following
   migration procedure can be used.  This procedure allows the BFRs to
   be reprovisioned one at a time and does not require a "flag day".

   1.  Upgrade all the BFRs in the domain so that they use both value X
       and value Y as their Disposition BitStringLengths.

   2.  Reprovision the BFIRs so that they use BitStringLength value Y as
       the Imposition BitStringLength.

   3.  One may then optionally reprovision all the BFRs so that they no
       longer use Disposition BitStringLength X.

7.  Operational Considerations

   BIER offers a radical simplification over current IP multicast
   operations: no tree-building control plane, no per-flow forwarding
   state, no Reverse Path Forwarding (RPF), no Rendezvous Point (RP),
   etc.  BIER packet forwarding/replication is along the unicast paths
   to each bit position set in the packet, ensuring that the
   encapsulated multicast packets follow the same path as unicast to
   each set bit in the header.  The BIER FIB can be derived from the
   SPF-calculated unicast FIB or from any other forwarding-path
   calculation in or out of band.  Each bit will follow this unicast
   path from the entry point of the BIER domain to the edge device with
   that assigned bit.

   Due to these differences, operational expectations from traditional
   multicast solutions do not apply to a BIER domain.  There is no
   granular per-flow state at each node defining a tree.  Monitoring
   flows at the forwarding-plane level ((S,G) entries) is not provided
   in a BIER node.  BIER FIB packet counters may be maintained for
   BFR-ids or next-hop neighbors.  Any flow-based metrics will require
   deeper packet inspection; this topic is outside the scope of this
   document.  In this way, BIER is again more like unicast.

   It is this reduction in state that allows for one of the key
   operational benefits of BIER: deterministic convergence.  The BIER
   FIB can converge immediately after the unicast FIB regardless of how
   many multicast flows are transiting the links.  Careful monitoring of
   (S,G) utilization is not required within a BIER domain.

7.1.  Configuration

   A BIER domain requires that each edge node (BFER) be given a unique
   bit position in the BIER mask (BFR-id).  The BFR-id must be
   configured on each BFER and associated with a unique IP address of
   that BFER.  Any existing manual or automated configuration tools must
   provide access to BIER-specific configuration.  The association of
   the BFR-id with a unique address of the BFER to which it is assigned
   must also be advertised into the IGP of the BIER domain.  This may be
   implied from the BIER configuration or require IGP-specific
   configuration.  This document does not dictate any specific
   configuration methodology.

8.  IANA Considerations

   This document does not require any IANA actions.

9.  Security Considerations

   When BIER is paired with a particular multicast flow overlay, it
   inherits the security considerations of that layer.  Similarly, when
   BIER is paired with a particular routing underlay, it inherits the
   security considerations of that layer.

   If the BIER encapsulation of a particular packet specifies an SI or a
   BitString other than the one intended by the BFIR, the packet is
   likely to be misdelivered.  If the BIER encapsulation of a packet is
   modified (through error or malfeasance) in a way other than that
   specified in this document, the packet may be misdelivered.  Some
   modifications of the BIER encapsulation, e.g., setting every bit in
   the BitString, may result in (intentional or unintentional)
   denial-of-service (DoS) attacks.

   If a BFIR is compromised, it may impose a BIER encapsulation with all
   the bits in the BitString set; this would also result in a DoS
   attack.

   Every BFR MUST be provisioned to know which of its interfaces lead to
   a BIER domain and which do not.  BIER-encapsulated packets MUST NOT
   be accepted from outside the BIER domain.  (Reception of
   BIER-encapsulated packets from outside the BIER domain would create
   an attack vector for DoS attacks, as an attacker might set all the
   bits in the BitString.)

   If two interfaces lead to different BIER domains, the BFR MUST be
   provisioned to know that those two interfaces lead to different BIER
   domains.  If the provisioning is not correct, BIER-encapsulated
   packets from one BIER domain may "leak" into another; this is likely
   to result in misdelivery of packets.

   DoS attacks may also result from incorrect provisioning (through
   error or malfeasance) of the BFRs.

   If the procedures used for advertising BFR-ids and BFR-prefixes are
   not secure, an attack on those procedures may result in incorrect
   delivery of BIER-encapsulated packets.

10.  References

10.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/info/rfc2119>.

   [RFC3443]  Agarwal, P. and B. Akyol, "Time To Live (TTL) Processing
              in Multi-Protocol Label Switching (MPLS) Networks",
              RFC 3443, DOI 10.17487/RFC3443, January 2003,
              <https://www.rfc-editor.org/info/rfc3443>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in
              RFC 2119 Key Words", BCP 14, RFC 8174,
              DOI 10.17487/RFC8174, May 2017,
              <https://www.rfc-editor.org/info/rfc8174>.

10.2.  Informative References

   [BGP_BIER_EXTENSIONS]
              Xu, X., Ed., Chen, M., Patel, K., Wijnands, IJ., and A.
              Przygienda, "BGP Extensions for BIER", Work in Progress,
              draft-ietf-bier-idr-extensions-03, August 2017.

   [BIER_MVPN]
              Rosen, E., Ed., Sivakumar, M., Aldrin, S., Dolganow, A.,
              and T. Przygienda, "Multicast VPN Using BIER", Work in
              Progress, draft-ietf-bier-mvpn-09, November 2017.

   [Boivie_Feldman]
              Boivie, R. and N. Feldman, "Small Group Multicast", Work
              in Progress, draft-boivie-sgm-02, February 2001.

   [ISIS_BIER_EXTENSIONS]
              Ginsberg, L., Ed., Przygienda, A., Aldrin, S., and J.
              Zhang, "BIER Support via ISIS", Work in Progress,
              draft-ietf-bier-isis-extensions-06, October 2017.

   [MPLS_BIER_ENCAPS]
              Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A.,
              Tantsura, J., Aldrin, S., and I. Meilik, "Encapsulation
              for Bit Index Explicit Replication in MPLS and non-MPLS
              Networks", Work in Progress, draft-ietf-bier-mpls-
              encapsulation-12, October 2017.

   [OSPF_BIER_EXTENSIONS]
              Psenak, P., Ed., Kumar, N., Wijnands, IJ., Dolganow, A.,
              Przygienda, T., Zhang, J., and S. Aldrin, "OSPF Extensions
              for BIER", Work in Progress, draft-ietf-bier-ospf-bier-
              extensions-09, October 2017.

   [RFC6513]  Rosen, E., Ed., and R. Aggarwal, Ed., "Multicast in
              MPLS/BGP IP VPNs", RFC 6513, DOI 10.17487/RFC6513,
              February 2012, <https://www.rfc-editor.org/info/rfc6513>.

   [RFC6514]  Aggarwal, R., Rosen, E., Morin, T., and Y. Rekhter, "BGP
              Encodings and Procedures for Multicast in MPLS/BGP IP
              VPNs", RFC 6514, DOI 10.17487/RFC6514, February 2012,
              <https://www.rfc-editor.org/info/rfc6514>.

Acknowledgements

   The authors wish to thank Rajiv Asati, Alia Atlas, John Bettink, Ross
   Callon (who contributed much of the text on deterministic ECMP),
   Nagendra Kumar, Christian Martin, Neale Ranns, Albert Tian, Ramji
   Vaithianathan, Xiaohu Xu, and Jeffrey Zhang for their ideas and
   contributions to this work.

   The authors also wish to thank Sue Hares, Victor Kuarsingh, and Dan
   Romascanu for their reviews of this document.

Contributors

   The following people contributed significantly to the content of this
   document and should be considered co-authors:

   Gregory Cauchie
   Bouygues Telecom
   Email: gcauchie@bouyguestelecom.fr

   Mach(Guoyi) Chen
   Huawei
   Email: mach.chen@huawei.com

   Arkadiy Gulko
   Thomson Reuters
   195 Broadway
   New York, NY  10007
   United States of America
   Email: arkadiy.gulko@thomsonreuters.com

   Wim Henderickx
   Nokia
   Copernicuslaan 50
   Antwerp  2018
   Belgium
   Email: wim.henderickx@nokia.com

   Martin Horneffer
   Deutsche Telekom
   Hammer Str. 216-226
   Muenster  48153
   Germany
   Email: Martin.Horneffer@telekom.de

   Luay Jalil
   Verizon
   1201 East Arapaho Rd.
   Richardson, TX  75081
   United States of America
   Email: luay.jalil@verizon.com

   Uwe Joorde
   Deutsche Telekom
   Hammer Str. 216-226
   Muenster  D-48153
   Germany
   Email: Uwe.Joorde@telekom.de

   Greg Shepherd
   Cisco Systems
   170 West Tasman Drive
   San Jose, CA  95134
   United States of America
   Email: shep@cisco.com

   Jeff Tantsura
   Email: jefftant.ietf@gmail.com

Authors' Addresses

   IJsbrand Wijnands (editor)
   Cisco Systems, Inc.
   De Kleetlaan 6a
   Diegem  1831
   Belgium

   Email: ice@cisco.com


   Eric C. Rosen (editor)
   Juniper Networks, Inc.
   10 Technology Park Drive
   Westford, Massachusetts  01886
   United States of America

   Email: erosen@juniper.net


   Andrew Dolganow
   Nokia
   438B Alexandra Rd #08-07/10
   Alexandra Technopark
   Singapore  119968
   Singapore

   Email: andrew.dolganow@nokia.com


   Tony Przygienda
   Juniper Networks, Inc.
   1194 N. Mathilda Ave.
   Sunnyvale, California  94089
   United States of America

   Email: prz@juniper.net


   Sam K. Aldrin
   Google, Inc.
   1600 Amphitheatre Parkway
   Mountain View, California  94043
   United States of America

   Email: aldrin.ietf@gmail.com