summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc8279.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/rfc/rfc8279.txt')
-rw-r--r--doc/rfc/rfc8279.txt2411
1 files changed, 2411 insertions, 0 deletions
diff --git a/doc/rfc/rfc8279.txt b/doc/rfc/rfc8279.txt
new file mode 100644
index 0000000..4337d28
--- /dev/null
+++ b/doc/rfc/rfc8279.txt
@@ -0,0 +1,2411 @@
+
+
+
+
+
+
+Internet Engineering Task Force (IETF) IJ. Wijnands, Ed.
+Request for Comments: 8279 Cisco Systems, Inc.
+Category: Experimental E. Rosen, Ed.
+ISSN: 2070-1721 Juniper Networks, Inc.
+ A. Dolganow
+ Nokia
+ T. Przygienda
+ Juniper Networks, Inc.
+ S. Aldrin
+ Google, Inc.
+ November 2017
+
+
+ Multicast Using Bit Index Explicit Replication (BIER)
+
+Abstract
+
+ This document specifies a new architecture for the forwarding of
+ multicast data packets. It provides optimal forwarding of multicast
+ packets through a "multicast domain". However, it does not require a
+ protocol for explicitly building multicast distribution trees, nor
+ does it require intermediate nodes to maintain any per-flow state.
+ This architecture is known as "Bit Index Explicit Replication"
+ (BIER). When a multicast data packet enters the domain, the ingress
+ router determines the set of egress routers to which the packet needs
+ to be sent. The ingress router then encapsulates the packet in a
+ BIER header. The BIER header contains a bit string in which each bit
+ represents exactly one egress router in the domain; to forward the
+ packet to a given set of egress routers, the bits corresponding to
+ those routers are set in the BIER header. The procedures for
+ forwarding a packet based on its BIER header are specified in this
+ document. Elimination of the per-flow state and the explicit tree-
+ building protocols results in a considerable simplification.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 1]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+Status of This Memo
+
+ This document is not an Internet Standards Track specification; it is
+ published for examination, experimental implementation, and
+ evaluation.
+
+ This document defines an Experimental Protocol for the Internet
+ community. This document is a product of the Internet Engineering
+ Task Force (IETF). It represents the consensus of the IETF
+ community. It has received public review and has been approved for
+ publication by the Internet Engineering Steering Group (IESG). Not
+ all documents approved by the IESG are a candidate for any level of
+ Internet Standard; see Section 2 of RFC 7841.
+
+ Information about the current status of this document, any errata,
+ and how to provide feedback on it may be obtained at
+ https://www.rfc-editor.org/info/rfc8279.
+
+Copyright Notice
+
+ Copyright (c) 2017 IETF Trust and the persons identified as the
+ document authors. All rights reserved.
+
+ This document is subject to BCP 78 and the IETF Trust's Legal
+ Provisions Relating to IETF Documents
+ (https://trustee.ietf.org/license-info) in effect on the date of
+ publication of this document. Please review these documents
+ carefully, as they describe your rights and restrictions with respect
+ to this document. Code Components extracted from this document must
+ include Simplified BSD License text as described in Section 4.e of
+ the Trust Legal Provisions and are provided without warranty as
+ described in the Simplified BSD License.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 2]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+Table of Contents
+
+ 1. Introduction ....................................................4
+ 2. The BFR Identifier and BFR-Prefix ...............................7
+ 3. Encoding BFR Identifiers in BitStrings ..........................8
+ 4. Layering .......................................................11
+ 4.1. The Routing Underlay ......................................11
+ 4.2. The BIER Layer ............................................12
+ 4.3. The Multicast Flow Overlay ................................13
+ 5. Advertising BFR-ids and BFR-Prefixes ...........................13
+ 6. BIER Intra-Domain Forwarding Procedures ........................15
+ 6.1. Overview ..................................................15
+ 6.2. BFR Neighbors .............................................17
+ 6.3. The Bit Index Routing Table ...............................18
+ 6.4. The Bit Index Forwarding Table ............................19
+ 6.5. The BIER Forwarding Procedure .............................20
+ 6.6. Examples of BIER Forwarding ...............................23
+ 6.6.1. Example 1 ..........................................23
+ 6.6.2. Example 2 ..........................................24
+ 6.7. Equal-Cost Multipath Forwarding ...........................26
+ 6.7.1. Non-deterministic ECMP .............................27
+ 6.7.2. Deterministic ECMP .................................28
+ 6.8. Prevention of Loops and Duplicates ........................29
+ 6.9. When Some Nodes Do Not Support BIER .......................30
+ 6.10. Use of Different BitStringLengths within a Domain ........33
+ 6.10.1. BitStringLength Compatibility Check ...............34
+ 6.10.2. Handling BitStringLength Mismatches ...............36
+ 6.10.3. Transitioning from One BitStringLength to
+ Another ...........................................36
+ 7. Operational Considerations .....................................37
+ 7.1. Configuration .............................................37
+ 8. IANA Considerations ............................................37
+ 9. Security Considerations ........................................38
+ 10. References ....................................................39
+ 10.1. Normative References .....................................39
+ 10.2. Informative References ...................................39
+ Acknowledgements ..................................................40
+ Contributors ......................................................41
+ Authors' Addresses ................................................43
+
+
+
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 3]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+1. Introduction
+
+ This document specifies a new architecture for the forwarding of
+ multicast data packets. The architecture provides optimal forwarding
+ of multicast data packets through a "multicast domain". However, it
+ does not require the use of a protocol for explicitly building
+ multicast distribution trees, and it does not require intermediate
+ nodes to maintain any per-flow state. This architecture is known as
+ "Bit Index Explicit Replication" (BIER).
+
+ A router that supports BIER is known as a "Bit-Forwarding Router"
+ (BFR). The BIER control-plane protocols (see Section 4.2) run within
+ a "BIER domain", allowing the BFRs within that domain to exchange the
+ information needed for them to forward packets to each other
+ using BIER.
+
+ A multicast data packet enters a BIER domain at a "Bit-Forwarding
+ Ingress Router" (BFIR), and leaves the BIER domain at one or more
+ "Bit-Forwarding Egress Routers" (BFERs). A BFR that receives a
+ multicast data packet from another BFR in the same BIER domain, and
+ forwards the packet to another BFR in the same BIER domain, will be
+ known as a "transit BFR" for that packet. A single BFR may be a BFIR
+ for some multicast traffic while also being a BFER for some multicast
+ traffic and a transit BFR for some multicast traffic. In fact, for a
+ given packet, a BFR may be a BFIR and/or a transit BFR and/or (one
+ of) the BFER(s) for that packet.
+
+ A BIER domain may contain one or more sub-domains. Each BIER domain
+ MUST contain at least one sub-domain, the "default sub-domain" (also
+ denoted "sub-domain 0"). If a BIER domain contains more than one
+ sub-domain, each BFR in the domain MUST be provisioned to know the
+ set of sub-domains to which it belongs. Each sub-domain is
+ identified by a sub-domain-id in the range [0,255].
+
+ For each sub-domain to which a given BFR belongs, if the BFR is
+ capable of acting as a BFIR or a BFER, it MUST be provisioned with a
+ "BFR-id" that is unique within the sub-domain. A BFR-id is a small
+ unstructured positive integer. For instance, if a particular BIER
+ sub-domain contains 1,374 BFRs, each one could be given a BFR-id in
+ the range [1,1374].
+
+ If a given BFR belongs to more than one sub-domain, it may (though it
+ need not) have a different BFR-id for each sub-domain.
+
+ When a multicast packet arrives from outside the domain at a BFIR,
+ the BFIR determines the set of BFERs to which the packet will be
+ sent. The BFIR also determines the sub-domain in which the packet
+ will be sent. Determining the sub-domain in which a given packet
+
+
+
+Wijnands, et al. Experimental [Page 4]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ will be sent is known as "assigning the packet to a sub-domain".
+ Procedures for choosing the sub-domain to which a particular packet
+ is assigned are outside the scope of this document. However, once a
+ particular packet has been assigned to a particular sub-domain, it
+ remains assigned to that sub-domain until it leaves the BIER domain.
+ That is, the sub-domain to which a packet is assigned MUST NOT be
+ changed while the packet is in flight through the BIER domain.
+
+ Once the BFIR determines the sub-domain and the set of BFERs for a
+ given packet, the BFIR encapsulates the packet in a "BIER header".
+ The BIER header contains a bit string in which each bit represents a
+ single BFR-id. To indicate that a particular BFER is to receive a
+ given packet, the BFIR sets the bit corresponding to that BFER's
+ BFR-id in the sub-domain to which the packet has been assigned. We
+ will use the term "BitString" to refer to the bit string field in the
+ BIER header. We will use the term "payload" to refer to the packet
+ that has been encapsulated. Thus, a "BIER-encapsulated" packet
+ consists of a "BIER header" followed by a "payload".
+
+ The number of BFERs to which a given packet can be forwarded is
+ limited only by the length of the BitString in the BIER header.
+ Different deployments can use different BitString lengths. We will
+ use the term "BitStringLength" to refer to the number of bits in the
+ BitString. It is possible that some deployments will have more BFERs
+ in a given sub-domain than there are bits in the BitString. To
+ accommodate this case, the BIER encapsulation includes both the
+ BitString and a "Set Identifier" (SI). It is the BitString and the
+ SI together that determine the set of BFERs to which a given packet
+ will be delivered:
+
+ o By convention, the least significant (rightmost) bit in the
+ BitString is "bit 1", and the most significant (leftmost) bit is
+ "bit BitStringLength".
+
+ o If a BIER-encapsulated packet has an SI of n and a BitString with
+ bit k set, then the packet must be delivered to the BFER whose
+ BFR-id (in the sub-domain to which the packet has been assigned)
+ is n*BitStringLength+k.
+
+ For example, suppose the BIER encapsulation uses a BitStringLength of
+ 256 bits. By convention, the least significant (rightmost) bit is
+ bit 1, and the most significant (leftmost) bit is bit 256. Suppose
+ that a given packet has been assigned to sub-domain 0 and needs to be
+ delivered to three BFERs, where those BFERs have BFR-ids in
+ sub-domain 0 of 13, 126, and 235, respectively. The BFIR would
+ create a BIER encapsulation with the SI set to zero and with bits 13,
+ 126, and 235 of the BitString set. (All other bits of the BitString
+ would be clear.) If the packet also needs to be sent to a BFER whose
+
+
+
+Wijnands, et al. Experimental [Page 5]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ BFR-id is 257, the BFIR would have to create a second copy of the
+ packet, and the BIER encapsulation would specify an SI of 1, and a
+ BitString with bit 1 set and all the other bits clear.
+
+ It is generally advantageous to assign the BFR-ids of a given
+ sub-domain so that as many BFERs as possible can be represented in a
+ single bit string.
+
+ Suppose a BFR (call it "BFR-A") receives a packet whose BIER
+ encapsulation specifies an SI of 0 and a BitString with bits 13, 26,
+ and 235 set. Suppose BFR-A has two BFR neighbors, BFR-B and BFR-C,
+ such that the best path to BFERs 13 and 26 is via BFR-B, but the best
+ path to BFER 235 is via BFR-C. BFR-A will then replicate the packet,
+ sending one copy to BFR-B and one copy to BFR-C. However, BFR-A will
+ clear bit 235 in the BitString of the packet copy it sends to BFR-B
+ and will clear bits 13 and 26 in the BitString of the packet copy it
+ sends to BFR-C. As a result, BFR-B will forward the packet only
+ towards BFERs 13 and 26, and BFR-C will forward the packet only
+ towards BFER 235. This ensures that each BFER receives only one copy
+ of the packet.
+
+ Detailed procedures for forwarding a BIER-encapsulated packet through
+ a BIER domain can be found in Section 6.
+
+ With this forwarding procedure, a multicast data packet can follow an
+ optimal path from its BFIR to each of its BFERs. Further, since the
+ set of BFERs for a given packet is explicitly encoded into the BIER
+ header, the packet is not sent to any BFER that does not need to
+ receive it. This allows for optimal forwarding of multicast traffic.
+ This optimal forwarding is achieved without any need for transit BFRs
+ to maintain per-flow state or to run a multicast tree-building
+ protocol.
+
+ The idea of encoding the set of egress nodes into the header of a
+ multicast packet is not new. For example, [Boivie_Feldman] proposes
+ to encode the set of egress nodes as a set of IP addresses, and
+ proposes mechanisms and procedures that are in some ways similar to
+ those described in the current document. However, since BIER encodes
+ each BFR-id as a single bit in a bit string, it can represent up to
+ 128 BFERs in the same number of bits that it would take to carry the
+ IPv6 address of a single BFER. Thus, BIER scales to a much larger
+ number of egress nodes per packet.
+
+ BIER does not require that each transit BFR look up the best path to
+ each BFER that is identified in the BIER header; the number of
+ lookups required in the forwarding path for a single packet can be
+
+
+
+
+
+Wijnands, et al. Experimental [Page 6]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ limited to the number of neighboring BFRs; this can be much smaller
+ than the number of BFERs. See Section 6 (especially Section 6.5) for
+ details.
+
+ The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
+ "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
+ "OPTIONAL" in this document are to be interpreted as described in
+ BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
+ capitals, as shown here.
+
+2. The BFR Identifier and BFR-Prefix
+
+ Each BFR MUST be assigned a single "BFR-prefix" for each sub-domain
+ to which it belongs. A BFR's BFR-prefix MUST be an IP address
+ (either IPv4 or IPv6) of the BFR. It is RECOMMENDED that the
+ BFR-prefix be a loopback address of the BFR.
+
+ If a BFR belongs to more than one sub-domain, it may (though it need
+ not) have a different BFR-prefix in each sub-domain.
+
+ All BFR-prefixes used within a given sub-domain MUST belong to the
+ same address family (either IPv4 or IPv6).
+
+ The BFR-prefix of a given BFR in a given sub-domain MUST be routable
+ in that sub-domain. Whether a particular BFR-prefix is routable in a
+ given sub-domain depends on the "routing underlay" associated with
+ that sub-domain. The notion of "routing underlay" is described in
+ Section 4.1.
+
+ A "BFR Identifier" (BFR-id) is a number in the range [1,65535].
+ Within a given sub-domain, every BFR that may need to function as a
+ BFIR or BFER MUST have a single BFR-id, which identifies it uniquely
+ within that sub-domain. A BFR that does not need to function as a
+ BFIR or BFER in a given sub-domain does not need to have a BFR-id in
+ that sub-domain.
+
+ The value 0 is not a legal BFR-id.
+
+ The procedure for assigning a particular BFR-id to a particular BFR
+ is outside the scope of this document. However, it is RECOMMENDED
+ that the BFR-ids for each sub-domain be assigned "densely" from the
+ numbering space, as this will result in a more efficient encoding
+ (see Section 3). That is, if there are 256 or fewer BFERs, it is
+ RECOMMENDED to assign all the BFR-ids from the range [1,256]. If
+ there are more than 256 BFERs but less than 512, it is RECOMMENDED to
+ assign all the BFR-ids from the range [1,512], with as few "holes" as
+
+
+
+
+
+Wijnands, et al. Experimental [Page 7]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ possible in the earlier range. However, in some deployments, it may
+ be advantageous to depart from this recommendation; this is discussed
+ further in Section 3.
+
+ In some deployments, it may not be possible to support (in a given
+ sub-domain) the full range of 65,535 BFR-ids. For example, if the
+ BFRs in a given sub-domain only support 16 SIs and if they only
+ support BitStringLengths of 256 or less, then only 16*256=4,096
+ BFR-ids can be supported in that sub-domain.
+
+3. Encoding BFR Identifiers in BitStrings
+
+ To encode a BFR-id in a BIER data packet, one must convert the BFR-id
+ to an SI and a BitString. This conversion depends upon the parameter
+ we are calling "BitStringLength". The conversion is done as follows.
+ If the BFR-id is N, then
+
+ o SI is the integer part of the quotient (N-1)/BitStringLength.
+
+ o The BitString has one bit position set. If the low-order bit is
+ bit 1 and the high-order bit is bit BitStringLength, the bit
+ position that represents BFR-id N is
+ ((N-1) modulo BitStringLength)+1.
+
+ If several different BFR-ids all resolve to the same SI, then all of
+ those BFR-ids can be represented in a single BitString. The
+ BitStrings for all of those BFR-ids are combined using a bitwise
+ logical OR operation.
+
+ Within a given BIER domain (or even within a given BIER sub-domain),
+ different values of BitStringLength may be used. Each BFR MUST be
+ provisioned to know the following:
+
+ o The BitStringLength ("Imposition BitStringLength") and sub-domain
+ ("Imposition sub-domain") to use when it imposes (as a BFIR) a
+ BIER encapsulation on a particular set of packets, and
+
+ o The BitStringLengths ("Disposition BitStringLengths") that it will
+ process when (as a BFR or BFER) it receives packets from a
+ particular sub-domain.
+
+ It is not required that a BFIR use the same Imposition
+ BitStringLength or the same Imposition sub-domain for all packets on
+ which it imposes the BIER encapsulation. However, 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
+
+
+
+Wijnands, et al. Experimental [Page 8]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ 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). Exceptions to
+ this rule MAY be made under certain conditions; this is discussed in
+ Section 6.10.
+
+ When a BIER encapsulation is specified, the specification MUST define
+ a default BitStringLength for the encapsulation. Every BFIR
+ supporting that encapsulation MUST be capable of being provisioned
+ with that default BitStringLength as its Imposition BitStringLength.
+ Every BFR and BFER supporting that encapsulation MUST be capable of
+ being provisioned with that default BitStringLength as a Disposition
+ BitStringLength.
+
+ The specification of a BIER encapsulation MAY also allow the use of
+ other BitStringLengths.
+
+ If a BFR is capable of being provisioned with a given value of
+ BitStringLength as an Imposition BitStringLength, it MUST also be
+ capable of being provisioned with that same value as one of its
+ Disposition BitStringLengths. It SHOULD be capable of being
+ provisioned with each legal smaller value of BitStringLength as (a)
+ its Imposition BitStringLength, and (b) one of its Disposition
+ BitStringLengths.
+
+ In order to support transition from one BitStringLength to another,
+ every BFR MUST be capable of being provisioned to simultaneously use
+ two different Disposition BitStringLengths.
+
+ A BFR MUST support SI values in the range [0,15] and MAY support SI
+ values in the range [0,255]. ("Supporting the values in a given
+ range" means, in this context, that any value in the given range is
+ legal and will be properly interpreted.) Note that for a given
+ BitStringLength, the total number of BFR-ids that can be represented
+ is the product of the BitStringLength and the number of supported
+ SIs. For example, if a deployment uses (in a given sub-domain) a
+ BitStringLength of 64 and supports 256 SIs, that deployment can only
+ support 16384 BFR-ids in that sub-domain. Even a deployment that
+ supports 256 SIs will not be able to support 65,535 BFR-ids unless it
+ uses a BitStringLength of at least 256.
+
+ When a BFIR determines that a multicast data packet, assigned to a
+ given sub-domain, needs to be forwarded to a particular set of
+ destination BFERs, the BFIR partitions that set of BFERs into
+ subsets, where each subset contains the target BFERs whose BFR-ids in
+ the given sub-domain all resolve to the same SI. Call these the
+ "SI-subsets" for the packet. Each SI-subset can be represented by a
+ single BitString. The BFIR creates a copy of the packet for each
+
+
+
+Wijnands, et al. Experimental [Page 9]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ SI-subset. The BIER encapsulation is then applied to each packet.
+ The encapsulation specifies a single SI for each packet and contains
+ the BitString that represents all the BFR-ids in the corresponding
+ SI-subset. Of course, in order to properly interpret the BitString,
+ it must be possible to infer the sub-domain-id from the encapsulation
+ as well.
+
+ Suppose, for example, that a BFIR determines that a given packet
+ needs to be forwarded to three BFERs, whose BFR-ids (in the
+ appropriate sub-domain) are 27, 235, and 497. The BFIR will have to
+ forward two copies of the packet. One copy, associated with SI=0,
+ will have a BitString with bits 27 and 235 set. The other copy,
+ associated with SI=1, will have a BitString with bit 241 set.
+
+ In order to minimize the number of copies that must be made of a
+ given multicast packet, it is RECOMMENDED that the BFR-ids used in a
+ given sub-domain be assigned "densely" (see Section 2) from the
+ numbering space. This will minimize the number of SIs that have to
+ be used in that sub-domain. However, depending upon the details of a
+ particular deployment, other assignment methods may be more
+ advantageous. Suppose, for example, that in a certain deployment,
+ every multicast flow is intended either for the "east coast" or for
+ the "west coast", but not for both coasts. In such a deployment, it
+ would be advantageous to assign BFR-ids so that all the "west coast"
+ BFR-ids fall into the same SI-subset and so that all the "east coast"
+ BFR-ids fall into the same SI-subset.
+
+ When a BFR receives a BIER data packet, it will infer the SI from the
+ encapsulation. The set of BFERs to which the packet needs to be
+ forwarded can then be inferred from the SI and the BitString.
+
+ In some of the examples given later in this document, we will use a
+ BitStringLength of 4 and will represent a BFR-id in the form
+ "SI:xyzw", where SI is the Set Identifier of the BFR-id (assuming a
+ BitStringLength of 4) and xyzw is a string of 4 bits. A
+ BitStringLength of 4 is used only in the examples; we would not
+ expect actual deployments to have such a small BitStringLength.
+
+ It is possible that several different forms of BIER encapsulation
+ will be developed. If so, the particular encapsulation that is used
+ in a given deployment will depend on the type of network
+ infrastructure that is used to realize the BIER domain. Details of
+ the BIER encapsulation(s) will be given in companion documents. An
+ encapsulation for use in MPLS networks is described in
+ [MPLS_BIER_ENCAPS]; that document also describes a very similar
+ encapsulation that can be used in non-MPLS networks.
+
+
+
+
+
+Wijnands, et al. Experimental [Page 10]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+4. Layering
+
+ It is helpful to think of the BIER architecture as consisting of
+ three layers: the "routing underlay", the "BIER layer", and the
+ "multicast flow overlay".
+
+4.1. The Routing Underlay
+
+ The "routing underlay" establishes "adjacencies" between pairs of
+ BFRs and determines one or more "best paths" from a given BFR to a
+ given set of BFRs. Each such path is a sequence of BFRs
+ <BFR(k), BFR(k+1), ..., BFR(k+n)> such that BFR(k+j) is "adjacent" to
+ BFR(k+j+1) (for 0<=j<n).
+
+ At a given BFR, say BFR-A, for every IP address that is the address
+ of a BFR in the BIER domain, the routing underlay will map that IP
+ address into a set of one or more "equal-cost" adjacencies. If a
+ BIER data packet has to be forwarded by BFR-A to a given BFER, say
+ BFER-B, the packet will follow the path from BFR-A to BFER-B that is
+ determined by the routing underlay.
+
+ It is expected that in a typical deployment, the routing underlay
+ will be the default topology that the Interior Gateway Protocol
+ (IGP), e.g., OSPF, uses for unicast routing. In that case, the
+ underlay adjacencies are just the OSPF adjacencies. A BIER data
+ packet traveling from BFR-A to BFER-B will follow the path that OSPF
+ has selected for unicast traffic from BFR-A to BFER-B.
+
+ If one wants to have multicast traffic from BFR-A to BFER-B travel a
+ path that is different from the path used by the unicast traffic from
+ BFR-A to BFER-B, one can use a different underlay. For example, if
+ multi-topology OSPF is being used, one OSPF topology could be used
+ for unicast traffic and the other for multicast traffic. (Each
+ topology would be considered to be a different underlay.)
+ Alternatively, one could deploy a routing underlay that creates a
+ multicast-specific tree of some sort. BIER could then be used to
+ forward multicast data packets along the multicast-specific tree,
+ while unicast packets follow the "ordinary" OSPF best path. (In a
+ case like this, many multicast flows could be traveling along a
+ single tree, and the BitString carried by a particular packet would
+ identify those nodes of the tree that need to receive that packet.)
+ It is even possible to have multiple routing underlays used by BIER,
+ as long as one can infer from a data packet's BIER encapsulation
+ which underlay is being used for that packet.
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 11]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ If multiple routing underlays are used in a single BIER domain, each
+ BIER sub-domain MUST be associated with a single routing underlay
+ (though multiple sub-domains may be associated with the same routing
+ underlay). A BFR that belongs to multiple sub-domains MUST be
+ provisioned to know which routing underlay is used by each
+ sub-domain. By default (i.e., in the absence of any provisioning to
+ the contrary), each sub-domain uses the default topology of the
+ unicast IGP as the routing underlay.
+
+ In scenarios where External BGP (EBGP) is used as the IGP, the
+ underlay adjacencies, by default, are the BGP adjacencies.
+
+ Specification of the protocols and procedures of the routing underlay
+ is outside the scope of this document.
+
+4.2. The BIER Layer
+
+ The BIER layer consists of the protocols and procedures that are used
+ in order to transmit a multicast data packet across a BIER domain,
+ from its BFIR to its BFERs. This includes the following components:
+
+ o Protocols and procedures that a given BFR uses to advertise, to
+ all other BFRs in the same BIER domain:
+
+ * its BFR-prefix;
+
+ * its BFR-id in each sub-domain for which it has been provisioned
+ with a BFR-id;
+
+ * the set of Disposition BitStringLengths it has been provisioned
+ to use for each sub-domain;
+
+ * optionally, information about the routing underlay associated
+ with each sub-domain.
+
+ o The procedures used by a BFIR to impose a BIER header on a
+ multicast data packet.
+
+ o The procedures for forwarding BIER-encapsulated packets and for
+ modifying the BIER header during transit.
+
+ o The procedures used by a BFER to decapsulate a BIER packet and
+ properly dispatch it.
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 12]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+4.3. The Multicast Flow Overlay
+
+ The "multicast flow overlay" consists of the set of protocols and
+ procedures that enable the following set of functions.
+
+ o When a BFIR receives a multicast data packet from outside the BIER
+ domain, the BFIR must determine the set of BFERs for that packet.
+ This information is provided by the multicast flow overlay.
+
+ o When a BFER receives a BIER-encapsulated packet from inside the
+ BIER domain, the BFER must determine how to further forward the
+ packet. This information is provided by the multicast flow
+ overlay.
+
+ For example, suppose the BFIR and BFERs are Provider Edge (PE)
+ routers providing Multicast Virtual Private Network (MVPN) service.
+ The multicast flow overlay consists of the protocols and procedures
+ described in [RFC6513] and [RFC6514]. The MVPN signaling described
+ in those RFCs enables an ingress PE to determine the set of egress
+ PEs for a given multicast flow (or set of flows); it also enables an
+ egress PE to determine the "Virtual Routing and Forwarding Tables"
+ (VRFs) to which multicast packets from the backbone network should be
+ sent. MVPN signaling also has several components that depend on the
+ type of "tunneling technology" used to carry multicast data through
+ the network. Since BIER is, in effect, a new type of "tunneling
+ technology", some extensions to the MVPN signaling are needed in
+ order to properly interface the multicast flow overlay with the BIER
+ layer. These are specified in [BIER_MVPN].
+
+ MVPN is just one example of a multicast flow overlay. Protocols and
+ procedures for other overlays will be provided in companion
+ documents. It is also possible to implement the multicast flow
+ overlay by means of a "Software-Defined Network" (SDN) controller.
+ Specification of the protocols and procedures of the multicast flow
+ overlay is outside the scope of this document.
+
+5. Advertising BFR-ids and BFR-Prefixes
+
+ As stated in Section 2, each BFER is assigned (by provisioning) a
+ BFR-id (for a given BIER sub-domain). Each BFER must advertise these
+ assignments to all the other BFRs in the domain. Similarly, each BFR
+ is assigned (by provisioning) a BFR-prefix (for a given BIER domain)
+ and must advertise this assignment to all the other BFRs in the
+ domain. Finally, each BFR has been provisioned to use a certain set
+ of Disposition BitStringLengths for each sub-domain and must
+ advertise these to all other BFRs in the domain.
+
+
+
+
+
+Wijnands, et al. Experimental [Page 13]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ If the BIER domain is also a link-state routing IGP domain (i.e., an
+ OSPF or IS-IS domain), the advertisement of the BFR-prefix,
+ <sub-domain-id, BFR-id>, and BitStringLength can be done using the
+ advertisement capabilities of the IGP. For example, if a BIER domain
+ is also an OSPF domain, these advertisements can be done using the
+ OSPF "Opaque Link State Advertisement" (Opaque LSA) mechanism.
+ Details of the necessary extensions to OSPF and IS-IS will be
+ provided in companion documents. (See [OSPF_BIER_EXTENSIONS] and
+ [ISIS_BIER_EXTENSIONS].)
+
+ If, in a particular deployment, the BIER domain is not an OSPF or
+ IS-IS domain, procedures suitable to the deployment must be used to
+ advertise this information. Details of the necessary procedures will
+ be provided in companion documents. For example, if BGP is the only
+ routing algorithm used in the BIER domain, the procedures of
+ [BGP_BIER_EXTENSIONS] may be used.
+
+ These advertisements enable each BFR to associate a given
+ <sub-domain-id, BFR-id> with a given BFR-prefix. As will be seen in
+ subsequent sections of this document, knowledge of this association
+ is an important part of the forwarding process.
+
+ Since each BFR needs to have a unique (in each sub-domain) BFR-id,
+ two different BFRs will not advertise ownership of the same
+ <sub-domain-id, BFR-id> unless there has been a provisioning error.
+
+ o If BFR-A determines that BFR-B and BFR-C have both advertised the
+ same BFR-id for the same sub-domain, BFR-A MUST log an error.
+ Suppose that the duplicate BFR-id is "N". When BFR-A is
+ functioning as a BFIR, it MUST NOT encode the BFR-id value N in
+ the BIER encapsulation of any packet that has been assigned to the
+ given sub-domain, even if it has determined that the packet needs
+ to be received by BFR-B and/or BFR-C.
+
+ This will mean that BFR-B and BFR-C cannot receive multicast
+ traffic at all in the given sub-domain until the provisioning
+ error is fixed. However, that is preferable to having them
+ receive each other's traffic.
+
+ o Suppose that BFR-A has been provisioned with BFR-id N for a
+ particular sub-domain but that it has not yet advertised its
+ ownership of BFR-id N for that sub-domain. Suppose also that it
+ has received an advertisement from a different BFR (say BFR-B)
+ that is advertising ownership of BFR-id N for the same sub-domain.
+ In such a case, BFR-A SHOULD log an error and MUST NOT advertise
+ its own ownership of BFR-id N for that sub-domain as long as the
+ advertisement from BFR-B is extant.
+
+
+
+
+Wijnands, et al. Experimental [Page 14]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ This procedure may prevent the accidental misconfiguration of a
+ new BFR from impacting an existing BFR.
+
+ If a BFR advertises that it has a BFR-id of 0 in a particular
+ sub-domain, other BFRs receiving the advertisement MUST interpret
+ that advertisement as meaning that the advertising BFR does not have
+ a BFR-id in that sub-domain.
+
+6. BIER Intra-Domain Forwarding Procedures
+
+ This section specifies the rules for forwarding a BIER-encapsulated
+ data packet within a BIER domain. These rules are not intended to
+ specify an implementation strategy; to conform to this specification,
+ an implementation need only produce the same results that these rules
+ produce.
+
+6.1. Overview
+
+ This section provides a brief overview of the BIER forwarding
+ procedures. Subsequent subsections specify the procedures in more
+ detail.
+
+ To forward a BIER-encapsulated packet:
+
+ 1. Determine the packet's sub-domain.
+
+ 2. Determine the packet's BitStringLength and BitString.
+
+ 3. Determine the packet's SI.
+
+ 4. From the sub-domain, the SI, and the BitString, determine the set
+ of destination BFERs for the packet.
+
+ 5. Using information provided by the routing underlay associated
+ with the packet's sub-domain, determine the next-hop adjacency
+ for each of the destination BFERs.
+
+ 6. It is possible that the packet's BitString will have one or more
+ bits that correspond to BFR-ids that are not in use. It is also
+ possible that the packet's BitString will have one or more bits
+ that correspond to BFERs that are unreachable, i.e., that have no
+ next-hop adjacency. In the following, we will consider the
+ "next-hop adjacency" for all such bit positions to be the "null"
+ next hop.
+
+ 7. Partition the set of destination BFERs such that all the BFERs in
+ a single partition have the same next hop. We will say that each
+ partition is associated with a next hop.
+
+
+
+Wijnands, et al. Experimental [Page 15]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ 8. For each partition:
+
+ a. Make a copy of the packet.
+
+ b. Clear any bit in the packet's BitString that identifies a
+ BFER that is not in the partition.
+
+ c. Transmit the packet to the associated next hop. (If the
+ next hop is the null next hop, the packet is discarded.)
+
+ If a BFR receives a BIER-encapsulated packet whose <sub-domain, SI,
+ BitString> triple identifies that BFR itself, then the BFR is also a
+ BFER for that packet. As a BFER, it must pass the payload to the
+ multicast flow overlay. If the BitString has bits set for other
+ BFRs, the packet also needs to be forwarded further within the BIER
+ domain. If the BF(E)R also forwards one or more copies of the packet
+ within the BIER domain, the bit representing the BFR's own BFR-id
+ MUST be clear in all the copies.
+
+ When BIER on a BFER is to pass a packet to the multicast flow
+ overlay, it of course decapsulates the packet by removing the BIER
+ header. However, it may be necessary to provide the multicast flow
+ overlay with contextual information obtained from the BIER
+ encapsulation. The information that needs to pass between the BIER
+ layer and the multicast flow overlay is specific to the multicast
+ flow overlay. Specification of the interaction between the BIER
+ layer and the multicast flow overlay is outside the scope of this
+ specification.
+
+ If the BIER encapsulation contains a "Time to Live" (TTL) value, this
+ value is not, by default, inherited by the payload. If a particular
+ multicast flow overlay needs to know the TTL value, this needs to be
+ specified in whatever specification defines the interaction between
+ BIER and that multicast flow overlay.
+
+ If the BIER encapsulation contains a Traffic Class field, a
+ Type of Service field, a Differentiated Services field, or any field
+ of that sort, the value of that field is not, by default, passed to
+ the multicast flow overlay. If a particular multicast flow overlay
+ needs to know the values of such fields, this fact needs to be
+ specified in whatever specification defines the interaction between
+ BIER and that multicast flow overlay.
+
+ When BIER on a BFER passes a packet to the multicast flow overlay,
+ the overlay will determine how to further dispatch the packet. If
+ the packet needs to be forwarded into another BIER domain, then the
+ BFR will act as a BFER in one BIER domain and as a BFIR in another.
+
+
+
+
+Wijnands, et al. Experimental [Page 16]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ A BIER-encapsulated packet cannot pass directly from one BIER domain
+ to another; at the boundary between BIER domains, the packet must be
+ decapsulated and passed to the multicast flow overlay.
+
+ Note that when a BFR transmits multiple copies of a packet within a
+ BIER domain, only one copy will be destined to any given BFER.
+ Therefore, it is not possible for any BIER-encapsulated packet to be
+ delivered more than once to any BFER.
+
+6.2. BFR Neighbors
+
+ The "BFR Neighbors" (BFR-NBRs) of a given BFR, say BFR-A, are those
+ BFRs that, according to the routing underlay, are adjacencies of
+ BFR-A. Each BFR-NBR will have a BFR-prefix.
+
+ Suppose a BIER-encapsulated packet arrives at BFR-A. From the
+ packet's encapsulation, BFR-A learns (a) the sub-domain of the packet
+ and (b) the BFR-ids (in that sub-domain) of the BFERs to which the
+ packet is destined. Then, using the information advertised per
+ Section 5, BFR-A can find the BFR-prefix of each destination BFER.
+ Given the BFR-prefix of a particular destination BFER, say BFER-D,
+ BFR-A learns from the routing underlay (associated with the packet's
+ sub-domain) an IP address of the BFR that is the next hop on the path
+ from BFR-A to BFER-D. Let's call this next hop "BFR-B". BFR-A must
+ then determine the BFR-prefix of BFR-B. (This determination can be
+ made from the information advertised per Section 5.) This BFR-prefix
+ is the BFR-NBR of BFR-A on the path from BFR-A to BFER-D.
+
+ Note that if the routing underlay provides multiple equal-cost paths
+ from BFR-A to BFER-D, BFR-A may have multiple BFR-NBRs for BFER-D.
+
+ Under certain circumstances, a BFR may have adjacencies (in a
+ particular routing underlay) that are not BFRs. Please see
+ Section 6.9 for a discussion of how to handle those circumstances.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 17]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+6.3. The Bit Index Routing Table
+
+ The "Bit Index Routing Table" (BIRT) is a table that maps from the
+ BFR-id (in a particular sub-domain) of a BFER to the BFR-prefix of
+ that BFER, and to the BFR-NBR on the path to that BFER. As an
+ example, consider the topology shown in Figure 1. In this diagram,
+ we represent the BFR-id of each BFR in the SI:xyzw form discussed in
+ Section 3.
+
+ ( A ) ------------ ( B ) ------------ ( C ) ------------ ( D )
+ 4 (0:1000) \ \ 1 (0:0001)
+ \ \
+ ( E ) ( F )
+ 3 (0:0100) 2 (0:0010)
+
+ Figure 1: BIER Topology 1
+
+ This topology will result in the BIRT of Figure 2 at BFR-B. The
+ first column shows the BFR-id as a number and also (in parentheses)
+ in the SI:BitString format that corresponds to a BitStringLength
+ of 4. (The actual minimum BitStringLength is 64, but we use 4 in the
+ examples.)
+
+ Note that a BIRT is specific to a particular BIER sub-domain.
+
+ --------------------------------------------
+ | BFR-id | BFR-Prefix | BFR-NBR |
+ | (SI:BitString) | of Dest BFER | |
+ ============================================
+ | 4 (0:1000) | A | A |
+ --------------------------------------------
+ | 1 (0:0001) | D | C |
+ --------------------------------------------
+ | 3 (0:0100) | E | E |
+ --------------------------------------------
+ | 2 (0:0010) | F | C |
+ --------------------------------------------
+
+ Figure 2: Bit Index Routing Table at BFR-B
+
+
+
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 18]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+6.4. The Bit Index Forwarding Table
+
+ The "Bit Index Forwarding Table" (BIFT) is derived from the BIRT as
+ follows. (Note that a BIFT is specific to a particular sub-domain.)
+
+ Suppose that several rows in the BIRT have the same SI and the same
+ BFR-NBR. By taking the logical OR of the BitStrings of those rows,
+ we obtain a bit mask that corresponds to that combination of SI and
+ BFR-NBR. We will refer to this bit mask as the "Forwarding Bit Mask"
+ (F-BM) for that <SI, BFR-NBR> combination.
+
+ For example, in Figure 2, we see that two of the rows have the same
+ SI (0) and same BFR-NBR (C). The bit mask that corresponds to
+ <SI=0, BFR-NBR-C> is 0011 ("0001" OR'd with "0010").
+
+ The BIFT is used to map from the BFR-id of a BFER to the
+ corresponding F-BM and BFR-NBR. For example, Figure 3 shows the BIFT
+ that is derived from the BIRT of Figure 2. Note that BFR-ids 1 and 2
+ have the same SI and the same BFR-NBR; hence, they have the
+ same F-BM.
+
+ -------------------------------------
+ | BFR-id | F-BM | BFR-NBR |
+ | (SI:BitString) | | |
+ =====================================
+ | 1 (0:0001) | 0011 | C |
+ -------------------------------------
+ | 2 (0:0010) | 0011 | C |
+ -------------------------------------
+ | 3 (0:0100) | 0100 | E |
+ -------------------------------------
+ | 4 (0:1000) | 1000 | A |
+ -------------------------------------
+
+ Figure 3: Bit Index Forwarding Table
+
+ This BIFT is programmed into the data plane and used to forward
+ packets, applying the rules specified below in Section 6.5.
+
+
+
+
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 19]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+6.5. The BIER Forwarding Procedure
+
+ Below is the procedure that a BFR uses for forwarding a
+ BIER-encapsulated packet.
+
+ 1. Determine the packet's SI, BitStringLength, and sub-domain.
+
+ 2. If the BitString consists entirely of zeroes, discard the packet;
+ the forwarding process has been completed. Otherwise, proceed to
+ step 3.
+
+ 3. Find the position (call it "k") of the least significant (i.e.,
+ of the rightmost) bit that is set in the packet's BitString.
+ (Remember, bits are numbered from 1, starting with the least
+ significant bit.)
+
+ 4. If bit k identifies the BFR itself, copy the packet, and send the
+ copy to the multicast flow overlay. Then clear bit k in the
+ original packet, and go to step 2. Otherwise, proceed to step 5.
+
+ 5. Use the value k, together with the SI, sub-domain, and
+ BitStringLength, as the "index" into the BIFT.
+
+ 6. Extract from the BIFT the F-BM and the BFR-NBR.
+
+ 7. Copy the packet. Update the copy's BitString by AND'ing it with
+ the F-BM (i.e., PacketCopy->BitString &= F-BM). Then forward the
+ copy to the BFR-NBR. (If the BFR-NBR is null, the copy is just
+ discarded.) Note that when a packet is forwarded to a particular
+ BFR-NBR, its BitString identifies only those BFERs that are to be
+ reached via that BFR-NBR.
+
+ 8. Now update the original packet's BitString by AND'ing it with the
+ INVERSE of the F-BM (i.e., Packet->BitString &= ~F-BM). (This
+ clears the bits that identify the BFERs to which a copy of the
+ packet has just been forwarded.) Go to step 2.
+
+ This procedure causes the packet to be forwarded to a particular
+ BFR-NBR only once. The number of lookups in the BIFT is the same as
+ the number of BFR-NBRs to which the packet must be forwarded; it is
+ not necessary to do a separate lookup for each destination BFER.
+
+ When a packet is sent to a particular BFR-NBR, the BitString is not
+ the only part of the BIER header that needs to be modified. If there
+ is a TTL field in the BIER header, it will need to be decremented.
+ In addition, when either of the encapsulations of [MPLS_BIER_ENCAPS]
+ is used, the BIFT-id field is likely to require modification, based
+ on signaling from the BFR-NBR to which the packet is being sent. The
+
+
+
+Wijnands, et al. Experimental [Page 20]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ BIFT-id field of an incoming BIER packet implicitly identifies an SI,
+ a sub-domain, and a BitStringLength. If the packet is sent to a
+ particular BFR-NBR, the BIFT-id field must be changed to whatever
+ value that BFR-NBR has advertised for the same SI, sub-domain, and
+ BitStringLength. (If the encapsulation of Section 2.1 of
+ [MPLS_BIER_ENCAPS] is used, this is essentially an MPLS label swap
+ operation.)
+
+ Suppose it has been decided (by the above rules) to send a packet to
+ a particular BFR-NBR. If that BFR-NBR is connected via multiple
+ parallel interfaces, it may be desirable to apply some form of load
+ balancing. Load-balancing algorithms are outside the scope of this
+ document. However, if the packet's encapsulation contains an entropy
+ field, the entropy field SHOULD be respected; two packets with the
+ same value of the entropy field SHOULD be sent on the same interface
+ (if possible).
+
+ In some cases, the routing underlay may provide multiple equal-cost
+ paths (through different BFR-NBRs) to a given BFER. This is known as
+ "Equal-Cost Multipath" (ECMP). The procedures described in this
+ section must be augmented in order to support load balancing over
+ ECMP. The necessary augmentations can be found in Section 6.7.
+
+ In the event that unicast traffic to the BFR-NBR is being sent via a
+ "bypass tunnel" of some sort, the BIER-encapsulated multicast traffic
+ sent to the BFR-NBR SHOULD also be sent via that tunnel. This allows
+ any existing "fast reroute" schemes to be applied to multicast
+ traffic as well as to unicast traffic.
+
+ Some examples of these forwarding procedures can be found in
+ Section 6.6.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 21]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ The rules given in this section can be represented by the following
+ pseudocode:
+
+ void ForwardBitMaskPacket (Packet)
+ {
+ SI=GetPacketSI(Packet);
+ Offset=SI*BitStringLength;
+ for (Index = GetFirstBitPosition(Packet->BitString); Index ;
+ Index = GetNextBitPosition(Packet->BitString, Index)) {
+ F-BM = BIFT[Index+Offset]->F-BM;
+ if (!F-BM) continue;
+ BFR-NBR = BIFT[Index+Offset]->BFR-NBR;
+ PacketCopy = Copy(Packet);
+ PacketCopy->BitString &= F-BM;
+ PacketSend(PacketCopy, BFR-NBR);
+ Packet->BitString &= ~F-BM;
+ }
+ }
+
+ Figure 4: Pseudocode
+
+ This pseudocode assumes that, at a given BFER, the BFR-NBR entry
+ corresponding to the BFER's own BFR-id will be the BFER's own
+ BFR-prefix. It also assumes that the corresponding F-BM has only
+ one bit set, the bit representing the BFER itself. In this case, the
+ "PacketSend" function sends the packet to the multicast flow overlay.
+
+ This pseudocode also assumes that the F-BM for the null next hop
+ contains a 1 in a given bit position if and only if that bit position
+ corresponds to either an unused BFR-id or an unreachable BFER. When
+ the BFR-NBR is null, the "PacketSend" function discards the packet.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 22]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+6.6. Examples of BIER Forwarding
+
+ In this section, we give two examples of BIER forwarding, based on
+ the topology in Figure 1. In these examples, all packets have been
+ assigned to the default sub-domain, all packets have SI=0, and the
+ BitStringLength is 4. Figure 5 shows the BIFT entries for SI=0 only.
+ For compactness, we show the first column of the BIFT, the BFR-id,
+ only as an integer.
+
+ BFR-A BIFT BFR-B BIFT BFR-C BIFT
+ ------------------- ------------------- -------------------
+ | Id | F-BM | NBR | | Id | F-BM | NBR | | Id | F-BM | NBR |
+ =================== =================== ===================
+ | 1 | 0111 | B | | 1 | 0011 | C | | 1 | 0001 | D |
+ ------------------- ------------------- -------------------
+ | 2 | 0111 | B | | 2 | 0011 | C | | 2 | 0010 | F |
+ ------------------- ------------------- -------------------
+ | 3 | 0111 | B | | 3 | 0100 | E | | 3 | 1100 | B |
+ ------------------- ------------------- -------------------
+ | 4 | 1000 | A | | 4 | 1000 | A | | 4 | 1100 | B |
+ ------------------- ------------------- -------------------
+
+ Figure 5: BIFTs Used in the Forwarding Examples
+
+6.6.1. Example 1
+
+ BFR-D, BFR-E, and BFR-F are BFERs. BFR-A is the BFIR. Suppose that
+ BFIR-A has learned from the multicast flow overlay that BFER-D is
+ interested in a given multicast flow. If BFIR-A receives a packet of
+ that flow from outside the BIER domain, BFIR-A applies the BIER
+ encapsulation to the packet. The encapsulation must be such that the
+ SI is zero. The encapsulation also includes a BitString, with just
+ bit 1 set and with all other bits clear (i.e., 0001). This indicates
+ that BFER-D is the only BFER that needs to receive the packet.
+ BFIR-A then follows the procedures of Section 6.5, as follows:
+
+ o Since the packet's BitString is 0001, BFIR-A finds that the first
+ bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-A
+ determines that the bit mask F-BM is 0111 and the BFR-NBR is
+ BFR-B.
+
+ o BFR-A then makes a copy of the packet and applies the F-BM to the
+ copy: Copy->BitString &= 0111. The copy's BitString is now 0001
+ (0001 & 0111).
+
+ o The copy is now sent to BFR-B.
+
+
+
+
+
+Wijnands, et al. Experimental [Page 23]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ o BFR-A then updates the packet's BitString by applying the inverse
+ of the F-BM: Packet->BitString &= ~F-BM. As a result, the
+ packet's BitString is now 0000 (0001 & 1000).
+
+ o As the packet's BitString is now zero, the forwarding procedure is
+ complete.
+
+ When BFR-B receives the multicast packet from BFR-A, it follows the
+ same procedure. The result is that a copy of the packet, with a
+ BitString of 0001, is sent to BFR-C. BFR-C applies the same
+ procedures and, as a result, sends a copy of the packet, with a
+ BitString of 0001, to BFR-D.
+
+ At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an
+ F-BM of 0001 and a BFR-NBR of BFR-D itself. This will cause a copy
+ of the packet to be delivered to the multicast flow overlay at BFR-D.
+ The packet's BitString will be set to 0000, and the packet will not
+ be forwarded any further.
+
+6.6.2. Example 2
+
+ This example is similar to example 1, except that BFIR-A has learned
+ from the multicast flow overlay that both BFER-D and BFER-E are
+ interested in a given multicast flow. If BFIR-A receives a packet of
+ that flow from outside the BIER domain, BFIR-A applies the BIER
+ encapsulation to the packet. The encapsulation must be such that the
+ SI is zero. The encapsulation also includes a BitString with
+ two bits set: bit 1 is set (as in example 1) to indicate that BFR-D
+ is a BFER for this packet, and bit 3 is set to indicate that BFR-E is
+ a BFER for this packet. That is, the BitString (assuming again a
+ BitStringLength of 4) is 0101. To forward the packet, BFIR-A follows
+ the procedures of Section 6.5, as follows:
+
+ o Since the packet's BitString is 0101, BFIR-A finds that the first
+ bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-A
+ determines that the bit mask F-BM is 0111 and the BFR-NBR is
+ BFR-B.
+
+ o BFR-A then makes a copy of the packet and applies the F-BM to the
+ copy: Copy->BitString &= 0111. The copy's BitString is now 0101
+ (0101 & 0111).
+
+ o The copy is now sent to BFR-B.
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 24]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ o BFR-A then updates the packet's BitString by applying the inverse
+ of the F-BM: Packet->BitString &= ~F-BM. As a result, the
+ packet's BitString is now 0000 (0101 & 1000).
+
+ o As the packet's BitString is now zero, the forwarding procedure is
+ complete.
+
+ When BFR-B receives the multicast packet from BFR-A, it follows the
+ procedure of Section 6.5, as follows:
+
+ o Since the packet's BitString is 0101, BFR-B finds that the first
+ bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-B
+ determines that the bit mask F-BM is 0011 and the BFR-NBR is
+ BFR-C.
+
+ o BFR-B then makes a copy of the packet and applies the F-BM to the
+ copy: Copy->BitString &= 0011. The copy's BitString is now 0001
+ (0101 & 0011).
+
+ o The copy is now sent to BFR-C.
+
+ o BFR-B then updates the packet's BitString by applying the inverse
+ of the F-BM: Packet->BitString &= ~F-BM. As a result, the
+ packet's BitString is now 0100 (0101 & 1100).
+
+ o Now BFR-B finds the next bit in the packet's (modified) BitString.
+ This is bit 3. Looking at entry 3 in its BIFT, BFR-B determines
+ that the F-BM is 0100 and the BFR-NBR is BFR-E.
+
+ o BFR-B then makes a copy of the packet and applies the F-BM to the
+ copy: Copy->BitString &= 0100. The copy's BitString is now 0100
+ (0100 & 0100).
+
+ o The copy is now sent to BFR-E.
+
+ o BFR-B then updates the packet's BitString by applying the inverse
+ of the F-BM: Packet->BitString &= ~F-BM. As a result, the
+ packet's BitString is now 0000 (0100 & 1011).
+
+ o As the packet's BitString is now zero, the forwarding procedure is
+ complete.
+
+ Thus, BFR-B forwards two copies of the packet. One copy of the
+ packet, with BitString 0001, has now been sent from BFR-B to BFR-C.
+ Following the same procedures, BFR-C will forward the packet to
+ BFER-D.
+
+
+
+
+
+Wijnands, et al. Experimental [Page 25]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an
+ F-BM of 0001 and a BFR-NBR of BFR-D itself. This will cause a copy
+ of the packet to be delivered to the multicast flow overlay at BFR-D.
+ The packet's BitString will be set to 0000, and the packet will not
+ be forwarded any further.
+
+ The other copy of the packet has been sent from BFR-B to BFER-E, with
+ BitString 0100.
+
+ At BFER-E, the BIFT entry (not pictured) for BFR-id 3 will specify an
+ F-BM of 0100 and a BFR-NBR of BFR-E itself. This will cause a copy
+ of the packet to be delivered to the multicast flow overlay at BFR-E.
+ The packet's BitString will be set to 0000, and the packet will not
+ be forwarded any further.
+
+6.7. Equal-Cost Multipath Forwarding
+
+ In many networks, the routing underlay will provide multiple
+ equal-cost paths from a given BFR to a given BFER. When forwarding
+ multicast packets through the network, it can be beneficial to take
+ advantage of this by load-balancing among those paths. This feature
+ is known as "Equal-Cost Multipath (ECMP) forwarding".
+
+ BIER supports ECMP forwarding, but the procedures of Section 6.5 must
+ be modified slightly. Two ECMP procedures are defined. In the first
+ (described in Section 6.7.1), the choice among equal-cost paths taken
+ by a given packet from a given BFR to a given BFER depends on
+ (a) routing, (b) the packet's entropy, and (c) the other BFERs to
+ which that packet is destined. In the second (described in
+ Section 6.7.2), the choice depends only upon the packet's entropy.
+
+ There are trade-offs between the two forwarding procedures described
+ here. In the procedure of Section 6.7.1, the number of packet
+ replications is minimized. The procedure in Section 6.7.1 also uses
+ less memory in the BFR. In the procedure of Section 6.7.2, the path
+ traveled by a given packet from a given BFR to a given BFER is
+ independent of the other BFERs to which the packet is destined.
+ While the procedures of Section 6.7.2 may cause more replications,
+ they provide a more predictable behavior.
+
+ The two procedures described here operate on identical packet formats
+ and will interoperate correctly. However, if deterministic behavior
+ is desired, then all BFRs would need to use the procedure from
+ Section 6.7.2.
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 26]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+6.7.1. Non-deterministic ECMP
+
+ Figure 6 shows the operation of non-deterministic ECMP in BIER.
+
+ BFR-A BIFT BFR-B BIFT BFR-C BIFT
+ ------------------- ------------------- -------------------
+ | Id | F-BM | NBR | | Id | F-BM | NBR | | Id | F-BM | NBR |
+ =================== =================== ===================
+ | 1 | 0111 | B | | 1 | 0011 | C | | 1 | 0001 | D |
+ ------------------- ------------------- -------------------
+ | 2 | 0111 | B | | 2 | 0011 | C | | 2 | 0010 | F |
+ ------------------- | | 0110 | E | -------------------
+ | 3 | 0111 | B | ------------------- | 3 | 1100 | B |
+ ------------------- | 3 | 0110 | E | -------------------
+ | 4 | 1000 | A | ------------------| | 4 | 1100 | B |
+ ------------------- | 4 | 1000 | A | -------------------
+ -------------------
+
+ ( A ) ------------ ( B ) ------------ ( C ) ------------ ( D )
+ 4 (0:1000) \ \ 1 (0:0001)
+ \ \
+ ( E ) ------------ ( F )
+ 3 (0:0100) 2 (0:0010)
+
+ Figure 6: Example of Non-deterministic ECMP
+
+ In this example, BFR-B has two equal-cost paths to reach BFER-F: one
+ via BFR-C and one via BFR-E. Since the BFR-id of BFER-F is 2, this
+ is reflected in entry 2 of BFR-B's BIFT. Entry 2 shows that BFR-B
+ has a choice of two BFR-NBRs for BFER-B and that a different F-BM is
+ associated with each choice. When BFR-B looks up entry 2 in the
+ BIFT, it can choose either BFR-NBR. However, when following the
+ procedures of Section 6.5, it MUST use the F-BM corresponding to the
+ BFR-NBR that it chooses.
+
+ How the choice is made is an implementation matter. However, the
+ usual rules for ECMP apply: packets of a given flow SHOULD NOT be
+ split among two paths, and any entropy field in the packet's
+ encapsulation SHOULD be respected.
+
+ Note, however, that by the rules of Section 6.5, any packet destined
+ for both BFER-D and BFER-F will be sent via BFR-C.
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 27]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+6.7.2. Deterministic ECMP
+
+ With the procedures of Section 6.7.1, where ECMP paths exist, the
+ path a packet takes to reach any particular BFER depends not only on
+ routing and on the packet's entropy but also on the set of other
+ BFERs to which the packet is destined.
+
+ For example, consider the following scenario in the network of
+ Figure 6.
+
+ o There is a sequence of packets being transmitted by BFR-A, some of
+ which are destined for both D and F and some of which are destined
+ only for F.
+
+ o All the packets in this sequence have the same entropy value (call
+ it "Q").
+
+ o At BFR-B, when a packet with entropy value Q is forwarded via
+ entry 2 in the BIFT, the packet is sent to E.
+
+ Using the forwarding procedure of Section 6.7.1, packets of this
+ sequence that are destined for both D and F are forwarded according
+ to entry 1 in the BIFT and thus will reach F via the path A-B-C-F.
+ However, packets of this sequence that are destined only for F are
+ forwarded according to entry 2 in the BIFT and thus will reach F via
+ the path A-B-E-F.
+
+ That procedure minimizes the number of packets transmitted by BFR-B.
+ However, consider the following scenario:
+
+ o Beginning at time t0, the multicast flow in question needs to be
+ received ONLY by BFER-F.
+
+ o Beginning at a later time, t1, the flow needs to be received by
+ both BFER-D and BFER-F.
+
+ o Beginning at a later time, t2, the flow no longer needs to be
+ received by D, but still needs to be received by F.
+
+ Then, from t0 until t1, the flow will travel to F via the path
+ A-B-E-F. From t1 until t2, the flow will travel to F via the path
+ A-B-C-F. And from t2, the flow will again travel to F via the path
+ A-B-E-F.
+
+ The problem is that if D repeatedly joins and leaves the flow, the
+ flow's path from B to F will keep switching. This could cause F to
+ receive packets out of order. It also makes troubleshooting
+ difficult. For example, if there is some problem on the E-F link,
+
+
+
+Wijnands, et al. Experimental [Page 28]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ receivers at F will get good service when the flow is also going to D
+ (avoiding the E-F link) but bad service when the flow is not going
+ to D. Since it is hard to know which path is being used at any given
+ time, this may be hard to troubleshoot. Also, it is very difficult
+ to perform a traceroute that is known to follow the path taken by the
+ flow at any given time.
+
+ The source of this difficulty is that, in the procedures of
+ Section 6.7.1, the path taken by a particular flow to a particular
+ BFER depends upon whether there are lower-numbered BFERs that are
+ also receiving the flow. Thus, the choice among the ECMP paths is
+ fundamentally non-deterministic.
+
+ Deterministic forwarding can be achieved by using multiple BIFTs,
+ such that each row in a BIFT has only one path to each destination
+ but the multiple ECMP paths to any particular destination are spread
+ across the multiple tables. When a BIER-encapsulated packet arrives
+ to be forwarded, the BFR uses a hash of the BIER entropy field to
+ determine which BIFT to use, and then the normal BIER forwarding
+ algorithm (as described in Sections 6.5 and 6.6) is used with the
+ selected BIFT.
+
+ As an example, suppose there are two paths to destination X (call
+ them "X1" and "X2") and four paths to destination Y (call them "Y1",
+ "Y2", "Y3", and "Y4"). If there are, say, four BIFTs, one BIFT would
+ have paths X1 and Y1, one would have X1 and Y2, one would have X2 and
+ Y3, and one would have X2 and Y4. If traffic to X is split evenly
+ among these four BIFTs, the traffic will be split evenly between the
+ two paths to X; if traffic to Y is split evenly among these four
+ BIFTs, the traffic will be split evenly between the four paths to Y.
+
+ Note that if there are three paths to one destination and four paths
+ to another, 12 BIFTs would be required in order to get even splitting
+ of the load to each of those two destinations. Of course, each BIFT
+ uses some memory, and one might be willing to have less optimal
+ splitting in order to have fewer BIFTs. How that trade-off is made
+ is an implementation or deployment decision.
+
+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.
+
+
+
+
+Wijnands, et al. Experimental [Page 29]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ 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.
+
+
+
+
+
+Wijnands, et al. Experimental [Page 30]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ 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.
+
+
+
+
+
+Wijnands, et al. Experimental [Page 31]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ 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.
+
+
+
+Wijnands, et al. Experimental [Page 32]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+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.
+
+
+
+
+
+Wijnands, et al. Experimental [Page 33]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ 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.
+
+
+
+
+Wijnands, et al. Experimental [Page 34]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 35]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+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.
+
+
+
+Wijnands, et al. Experimental [Page 36]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+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.
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 37]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+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.
+
+
+
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 38]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+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.
+
+
+
+
+
+Wijnands, et al. Experimental [Page 39]
+
+RFC 8279 Multicast with BIER November 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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 40]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+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
+
+
+
+
+Wijnands, et al. Experimental [Page 41]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+ 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
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Wijnands, et al. Experimental [Page 42]
+
+RFC 8279 Multicast with BIER November 2017
+
+
+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
+
+
+
+
+
+Wijnands, et al. Experimental [Page 43]
+