draft-ietf-bier-architecture-00.txt   draft-ietf-bier-architecture-01.txt 
Internet Engineering Task Force IJ. Wijnands, Ed. Internet Engineering Task Force IJ. Wijnands, Ed.
Internet-Draft Cisco Systems, Inc. Internet-Draft Cisco Systems, Inc.
Intended status: Standards Track E. Rosen, Ed. Intended status: Standards Track E. Rosen, Ed.
Expires: October 29, 2015 Juniper Networks, Inc. Expires: December 27, 2015 Juniper Networks, Inc.
A. Dolganow A. Dolganow
Alcatel-Lucent Alcatel-Lucent
T. Przygienda T. Przygienda
Ericsson Ericsson
S. Aldrin S. Aldrin
Huawei Technologies Google, Inc.
April 27, 2015 June 25, 2015
Multicast using Bit Index Explicit Replication Multicast using Bit Index Explicit Replication
draft-ietf-bier-architecture-00 draft-ietf-bier-architecture-01
Abstract Abstract
This document specifies a new architecture for the forwarding of This document specifies a new architecture for the forwarding of
multicast data packets. It provides optimal forwarding of multicast multicast data packets. It provides optimal forwarding of multicast
packets through a "multicast domain". However, it does not require packets through a "multicast domain". However, it does not require a
any explicit tree-building protocol, nor does it require intermediate protocol for explicitly building multicast distribution trees, nor
nodes to maintain any per-flow state. This architecture is known as does it require intermediate nodes to maintain any per-flow state.
"Bit Index Explicit Replication" (BIER). When a multicast data This architecture is known as "Bit Index Explicit Replication"
packet enters the domain, the ingress router determines the set of (BIER). When a multicast data packet enters the domain, the ingress
egress routers to which the packet needs to be sent. The ingress router determines the set of egress routers to which the packet needs
router then encapsulates the packet in a BIER header. The BIER to be sent. The ingress router then encapsulates the packet in a
header contains a bitstring in which each bit represents exactly one BIER header. The BIER header contains a bitstring in which each bit
egress router in the domain; to forward the packet to a given set of represents exactly one egress router in the domain; to forward the
egress routers, the bits corresponding to those routers are set in packet to a given set of egress routers, the bits corresponding to
the BIER header. Elimination of the per-flow state and the explicit those routers are set in the BIER header. Elimination of the per-
tree-building protocols results in a considerable simplification. flow state and the explicit tree-building protocols results in a
considerable simplification.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on October 29, 2015. This Internet-Draft will expire on December 27, 2015.
Copyright Notice Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. The BFR Identifier and BFR-Prefix . . . . . . . . . . . . . . 5 2. The BFR Identifier and BFR-Prefix . . . . . . . . . . . . . . 6
3. Encoding BFR Identifiers in BitStrings . . . . . . . . . . . 6 3. Encoding BFR Identifiers in BitStrings . . . . . . . . . . . 6
4. Layering . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4. Layering . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.1. The Routing Underlay . . . . . . . . . . . . . . . . . . 8 4.1. The Routing Underlay . . . . . . . . . . . . . . . . . . 9
4.2. The BIER Layer . . . . . . . . . . . . . . . . . . . . . 9 4.2. The BIER Layer . . . . . . . . . . . . . . . . . . . . . 10
4.3. The Multicast Flow Overlay . . . . . . . . . . . . . . . 10 4.3. The Multicast Flow Overlay . . . . . . . . . . . . . . . 11
5. Advertising BFR-ids and BFR-Prefixes . . . . . . . . . . . . 10 5. Advertising BFR-ids and BFR-Prefixes . . . . . . . . . . . . 11
6. BIER Intra-Domain Forwarding Procedures . . . . . . . . . . . 12 6. BIER Intra-Domain Forwarding Procedures . . . . . . . . . . . 13
6.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 12 6.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 13
6.2. BFR Neighbors . . . . . . . . . . . . . . . . . . . . . . 13 6.2. BFR Neighbors . . . . . . . . . . . . . . . . . . . . . . 14
6.3. The Bit Index Routing Table . . . . . . . . . . . . . . . 14 6.3. The Bit Index Routing Table . . . . . . . . . . . . . . . 15
6.4. The Bit Index Forwarding Table . . . . . . . . . . . . . 14 6.4. The Bit Index Forwarding Table . . . . . . . . . . . . . 16
6.5. The BIER Forwarding Procedure . . . . . . . . . . . . . . 15 6.5. The BIER Forwarding Procedure . . . . . . . . . . . . . . 16
6.6. Examples of BIER Forwarding . . . . . . . . . . . . . . . 17 6.6. Examples of BIER Forwarding . . . . . . . . . . . . . . . 18
6.6.1. Example 1 . . . . . . . . . . . . . . . . . . . . . . 18 6.6.1. Example 1 . . . . . . . . . . . . . . . . . . . . . . 19
6.6.2. Example 2 . . . . . . . . . . . . . . . . . . . . . . 18 6.6.2. Example 2 . . . . . . . . . . . . . . . . . . . . . . 20
6.7. Equal Cost Multi-path Forwarding . . . . . . . . . . . . 20 6.7. Equal Cost Multi-path Forwarding . . . . . . . . . . . . 22
6.7.1. Non-deterministic ECMP . . . . . . . . . . . . . . . 21 6.7.1. Non-deterministic ECMP . . . . . . . . . . . . . . . 22
6.7.2. Deterministic ECMP . . . . . . . . . . . . . . . . . 22 6.7.2. Deterministic ECMP . . . . . . . . . . . . . . . . . 23
6.8. Prevention of Loops and Duplicates . . . . . . . . . . . 24 6.8. Prevention of Loops and Duplicates . . . . . . . . . . . 25
6.9. When Some Nodes do not Support BIER . . . . . . . . . . . 24 6.9. When Some Nodes do not Support BIER . . . . . . . . . . . 26
6.10. Use of Different BitStringLengths within a Domain . . . . 26 6.10. Use of Different BitStringLengths within a Domain . . . . 28
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27 6.10.1. BitStringLength Compatibility Check . . . . . . . . 29
8. Security Considerations . . . . . . . . . . . . . . . . . . . 27 6.10.2. Handling BitStringLength Mismatches . . . . . . . . 30
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 27 6.10.3. Transitioning from One BitStringLength to Another . 31
10. Contributor Addresses . . . . . . . . . . . . . . . . . . . . 28 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 31
11. References . . . . . . . . . . . . . . . . . . . . . . . . . 29 8. Security Considerations . . . . . . . . . . . . . . . . . . . 31
11.1. Normative References . . . . . . . . . . . . . . . . . . 29 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 32
11.2. Informative References . . . . . . . . . . . . . . . . . 29 10. Contributor Addresses . . . . . . . . . . . . . . . . . . . . 32
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 30 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 33
11.1. Normative References . . . . . . . . . . . . . . . . . . 33
11.2. Informative References . . . . . . . . . . . . . . . . . 34
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 34
1. Introduction 1. Introduction
This document specifies a new architecture for the forwarding of This document specifies a new architecture for the forwarding of
multicast data packets. It provides optimal forwarding of multicast multicast data packets. It provides optimal forwarding of multicast
data packets through a "multicast domain". However, it does not data packets through a "multicast domain". However, it does not
require any explicit tree-building protocol, and does not require require the use of a protocol for explicitly building multicast
intermediate nodes to maintain any per-flow state. This architecture distribution trees, and it does not require intermediate nodes to
is known as "Bit Index Explicit Replication" (BIER). 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" A router that supports BIER is known as a "Bit-Forwarding Router"
(BFR). A BIER domain is a connected set of BFRs. The BIER control (BFR). The BIER control plane protocols (see Section 4.2) run within
plane protocols (see Section 4.2) run within a BIER domain, allowing a "BIER domain", allowing the BFRs within that domain to exchange the
the BFRs within that domain to exchange the necessary information. information needed for them to forward packets to each other using
BIER.
A multicast data packet enters a BIER domain at a "Bit-Forwarding A multicast data packet enters a BIER domain at a "Bit-Forwarding
Ingress Router" (BFIR), and leaves the BIER domain at one or more Ingress Router" (BFIR), and leaves the BIER domain at one or more
"Bit-Forwarding Egress Routers" (BFERs). A BFR that receives a "Bit-Forwarding Egress Routers" (BFERs). A BFR that receives a
multicast data packet from another BFR in the same BIER domain, and 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 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 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 for some multicast traffic while also being a BFER for some multicast
traffic and a transit BFR for some multicast traffic. In fact, a BFR traffic and a transit BFR for some multicast traffic. In fact, a BFR
may be the BFIR for a given packet and may also be (one of) the may be the BFIR for a given packet and may also be (one of) the
skipping to change at page 3, line 43 skipping to change at page 3, line 48
A BIER domain may contain one or more sub-domains. Each BIER domain 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 MUST contain at least one sub-domain, the "default sub-domain" (also
denoted "sub-domain zero"). If a BIER domain contains more than one denoted "sub-domain zero"). If a BIER domain contains more than one
sub-domain, each BFR in the domain MUST be provisioned to know the 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 set of sub-domains to which it belongs. Each sub-domain is
identified by a sub-domain-id in the range [0,255]. 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 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 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 "BFR-id" that is unique within the sub-domain. A BFR-id is a small
unstructured number. For instance, if a particular BIER sub-domain unstructured positive integer. For instance, if a particular BIER
contains 1,374 BFRs, each one could be given a BFR-id in the range sub-domain contains 1,374 BFRs, each one could be given a BFR-id in
1-1374. the range 1-1374.
If a given BFR belongs to more than one sub-domain, it may (though it 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. need not) have a different BFR-id for each sub-domain.
When a multicast packet arrives from outside the domain at a BFIR, When a multicast packet arrives from outside the domain at a BFIR,
the BFIR determines the set of BFERs to which the packet must be the BFIR determines the set of BFERs to which the packet will be
sent. The BFIR also determines the sub-domain over which the packet sent. The BFIR also determines the sub-domain in which the packet
must be sent. (Procedures for assigning a particular packet to a will be sent. Determining the sub-domain in which a given packet
particular sub-domain are outside the scope of this document.) The will be sent is known as "assigning the packet to a sub-domain".
BFIR then encapsulates the packet in a "BIER header". The BIER Procedures for choosing the sub-domain to which a particular packet
header contains a bit string in which each bit represents a single is assigned are outside the scope of this document. However, once a
BFR-id. To indicate that a particular BFER needs to receive a given particular packet has been assigned to a particular sub-domain, it
packet, the BFIR sets the bit corresponding to that BFER's BFR-id in remains assigned to that sub-domain until it leaves the BIER domain.
the sub-domain to which the packet has been assigned. We will use That is, the sub-domain to which a packet is assigned MUST NOT be
term "BitString" to refer to the bit string field in the BIER header. changed while the packet is in flight through the BIER domain.
We will use the term "payload" to refer to the packet that has been
encapsulated. Thus a "BIER-encapsulated" packet consists of a "BIER Once the BFIR determines sub-domain and the set of BFERs for a given
header" followed by a "payload". 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 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 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. limited only by the length of the BitString in the BIER header.
Different deployments can use different BitString lengths. We will Different deployments can use different BitString lengths. We will
use the term "BitStringLength" to refer to the number of bits in the use the term "BitStringLength" to refer to the number of bits in the
BitString. It is possible that some deployment will have more BFERs BitString. It is possible that some deployment will have more BFERs
in a given sub-domain than there are bits in the BitString. To in a given sub-domain than there are bits in the BitString. To
accommodate this case, the BIER encapsulation includes both the accommodate this case, the BIER encapsulation includes both the
BitString and a "Set Identifier" (SI). It is the BitString and 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 SI together that determine the set of BFERs to which a given packet
skipping to change at page 4, line 50 skipping to change at page 5, line 15
Suppose that a given packet has been assigned to sub-domain 0, and 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 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 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 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 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 BitString would be clear.) If the packet also needs to be sent to a
BFER whose BFR-id is 257, the BFIR would have to create a second copy BFER whose 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, 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. and a BitString with bit 1 set and all the other bits clear.
Note that it is generally advantageous to assign the BFR-ids so that Note that it is generally advantageous to assign the BFR-ids of a
as many BFERs as possible can be represented in a single bit string. 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 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, 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, 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 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. Then BFR-A will replicate the packet, path to BFER 235 is via BFR-C. Then BFR-A will replicate the packet,
sending one copy to BFR-B and one copy to BFR-C. However, BFR-A will 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, 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 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 sends to BFR-C. As a result, BFR-B will forward the packet only
skipping to change at page 6, line 51 skipping to change at page 7, line 20
bit 1, and the high-order bit is bit BitStringLength, the bit bit 1, and the high-order bit is bit BitStringLength, the bit
position that represents BFR-id N is position that represents BFR-id N is
((N-1) modulo BitStringLength)+1. ((N-1) modulo BitStringLength)+1.
If several different BFR-ids all resolve to the same SI, then all If several different BFR-ids all resolve to the same SI, then all
those BFR-ids can be represented in a single BitString. The those BFR-ids can be represented in a single BitString. The
BitStrings for all of those BFR-ids are combined using a bitwise BitStrings for all of those BFR-ids are combined using a bitwise
logical OR operation. logical OR operation.
Different BIER domains may use different values of BitStringLength. Different BIER domains may use different values of BitStringLength.
Each BFIR in a given BIER domain MUST be provisioned to know the Each BFR in a given BIER domain MUST be provisioned to know the
BitStringLength to use when imposing a BIER encapsulation on a following:
particular set of packets. This value of BitStringLength SHOULD be a
value that is supported by all the BFRs in the domain. (That is, the
BitStringLength value used by a BFIR when imposing a BIER
encapsulation on a particular packet SHOULD be a value that is
supported by all the BFRs and BFERs in the domain that might have to
forward or receive the packet.) However, under certain
circumstances, it is possible to make exceptions to this rule. This
is discussed in Section 6.10.
Every BFIR MUST be able to impose a BIER encapsulation whose o the BitStringLength ("Imposition BitStringLength") and sub-domain
BitStringLength of 256. Every BFR MUST be able to forward a BIER- ("Imposition sub-domain") to use when it imposes (as a BFIR) a
encapsulated packet whose BitStringLength is 256. Every BFER MUST be BIER encapsulation on a particular set of packets, and
able to receive and properly process a BIER-encapsulated packet whose
BitStringLength is 256. 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
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.
Every BFIR MUST be capable of being provisioned with an Imposition
BitStringLength of 256. Every BFR and BFER MUST be capable of being
provisioned with a Disposition BitStringLength of 256.
Particular BIER encapsulation types MAY allow other BitStringLengths Particular BIER encapsulation types MAY allow other BitStringLengths
to be OPTIONALLY supported. For example, when using the to be OPTIONALLY supported. For example, when using the
encapsulation specified in [MPLS_BIER_ENCAPS], a BFR may support any encapsulation specified in [MPLS_BIER_ENCAPS], a BFR may be capable
or all of the following BitStringLengths: 64, 128, 256, 512, 1024, of being provisioned to use any or all of the following
2048, and 4096. BitStringLengths as Imposition BitStringLengths and as Disposition
BitStringLengths: 64, 128, 256, 512, 1024, 2048, and 4096.
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 all legal smaller values of BitStringLength as both
Imposition and Disposition BitStringLength.
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 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 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 range" means, in this context, that any value in the given range is
legal, and will be properly interpreted.) legal, and will be properly interpreted.)
When a BFIR determines that a multicast data packet, assigned to a When a BFIR determines that a multicast data packet, assigned to a
given sub-domain, needs to be forwarded to a particular set of given sub-domain, needs to be forwarded to a particular set of
destination BFERs, the BFIR partitions that set of BFERs into destination BFERs, the BFIR partitions that set of BFERs into
subsets, where each subset contains the target BFERs whose BFR-ids in subsets, where each subset contains the target BFERs whose BFR-ids in
skipping to change at page 9, line 47 skipping to change at page 10, line 39
Note that specification of the protocol and procedures of the routing Note that specification of the protocol and procedures of the routing
underlay is outside the scope of this document. underlay is outside the scope of this document.
4.2. The BIER Layer 4.2. The BIER Layer
The BIER layer consists of the protocol and procedures that are used The BIER layer consists of the protocol and procedures that are used
in order to transmit a multicast data packet across a BIER domain, in order to transmit a multicast data packet across a BIER domain,
from its BFIR to its BFERs. This includes the following components: from its BFIR to its BFERs. This includes the following components:
o Protocols and procedures that advertise, to all other BFRs in the o Protocols and procedures that a given BFR uses to advertise, to
same BIER domain, each BFR's BFR-prefix. all other BFRs in the same BIER domain:
o Protocols and procedures that advertise, to all other BFRs in the * its BFR-prefix;
same BIER domain, each BFR's BFR-id for each sub-domain.
o The imposition by a BFIR of a BIER header on a multicast data * its BFR-id in each sub-domain for which it has been provisioned
packet. 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 o The procedures for forwarding BIER-encapsulated packets, and for
modifying the BIER header during transit. modifying the BIER header during transit.
4.3. The Multicast Flow Overlay 4.3. The Multicast Flow Overlay
The "multicast flow overlay" consists of the set of protocols and The "multicast flow overlay" consists of the set of protocols and
procedures that enable the following set of functions. procedures that enable the following set of functions.
o When a BFIR receives a multicast data packet from outside the BIER o When a BFIR receives a multicast data packet from outside the BIER
skipping to change at page 10, line 49 skipping to change at page 11, line 49
MVPN is just one example of a multicast flow overlay. Protocols and MVPN is just one example of a multicast flow overlay. Protocols and
procedures for other overlays will be provided in companion procedures for other overlays will be provided in companion
documents. It is also possible to implement the multicast flow documents. It is also possible to implement the multicast flow
overlay by means of a "Software Defined Network" (SDN) controller. overlay by means of a "Software Defined Network" (SDN) controller.
Specification of the protocols and procedures of the multicast flow Specification of the protocols and procedures of the multicast flow
overlay is outside the scope of this document. overlay is outside the scope of this document.
5. Advertising BFR-ids and BFR-Prefixes 5. Advertising BFR-ids and BFR-Prefixes
As stated in Section 2, each BFER is assigned a BFR-id (for a given As stated in Section 2, each BFER is assigned (by provisioning) a
BIER sub-domain). Each BFER must advertise these assignments to all BFR-id (for a given BIER sub-domain). Each BFER must advertise these
the other BFRs in the domain. Similarly, each BFR is assigned a assignments to all the other BFRs in the domain. Similarly, each BFR
BFR-prefix (for a given BIER domain), and must advertise this is assigned (by provisioning) a BFR-prefix (for a given BIER domain),
assignment to all the other BFRs in the domain. Finally, it is and must advertise this assignment to all the other BFRs in the
useful for each BFR to advertise its supported values of domain. Finally, each BFR has been provisioned to use a certain set
BitStringLength (for a given BIER domain). of Disposition BitStringLengths for each sub-domain, and must
advertise these to all other BFRs in the domain.
If the BIER domain is also a link state routing IGP domain (i.e., an 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- OSPF or IS-IS domain), the advertisement of the BFR-prefix, <sub-
domain-id,BFR-id> and BitStringLength can be done using the domain-id,BFR-id> and BitStringLength can be done using the
advertisement capabilities of the IGP. For example, if a BIER domain advertisement capabilities of the IGP. For example, if a BIER domain
is also an OSPF domain, these advertisements can be done using the is also an OSPF domain, these advertisements can be done using the
OSPF "Opaque Link State Advertisement" (Opaque LSA) mechanism. OSPF "Opaque Link State Advertisement" (Opaque LSA) mechanism.
Details of the necessary extensions to OSPF and IS-IS will be Details of the necessary extensions to OSPF and IS-IS will be
provided in companion documents. (See [OSPF_BIER_EXTENSIONS] and provided in companion documents. (See [OSPF_BIER_EXTENSIONS] and
[ISIS_BIER_EXTENSIONS].) [ISIS_BIER_EXTENSIONS].)
skipping to change at page 12, line 25 skipping to change at page 13, line 25
6.1. Overview 6.1. Overview
This section provides a brief overview of the BIER forwarding This section provides a brief overview of the BIER forwarding
procedures. Subsequent sub-sections specify the procedures in more procedures. Subsequent sub-sections specify the procedures in more
detail. detail.
To forward a BIER-encapsulated packet: To forward a BIER-encapsulated packet:
1. Determine the packet's sub-domain. 1. Determine the packet's sub-domain.
2. Determine the packet's SI. 2. Determine the packet's BitStringLength and BitString.
3. From the sub-domain, the SI and the BitString, determine the set 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. of destination BFERs for the packet.
4. Using information provided by the routing underlay associated 5. Using information provided by the routing underlay associated
with the packet's sub-domain, determine the next hop adjacency with the packet's sub-domain, determine the next hop adjacency
for each of the destination BFERs. for each of the destination BFERs.
5. Partition the set of destination BFERs such that all the BFERs in 6. 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 a single partition have the same next hop. We will say that each
partition is associated with a next hop. partition is associated with a next hop.
6. For each partition: 7. For each partition:
a. Make a copy of the packet. a. Make a copy of the packet.
b. Clear any bit in the packet's BitString that identifies a b. Clear any bit in the packet's BitString that identifies a
BFER that is not in the partition. BFER that is not in the partition.
c. Transmit the packet to the associated next hop. c. Transmit the packet to the associated next hop.
If a BFR receives a BIER-encapsulated packet whose sub-domain, SI and If a BFR receives a BIER-encapsulated packet whose sub-domain, SI and
BitString identify that BFR itself, then the BFR is also a BFER for BitString identify that BFR itself, then the BFR is also a BFER for
that packet. As a BFER, it must pass the payload to the multicast that packet. As a BFER, it must pass the payload to the multicast
flow overlay. If the BitString has more than one bit set, the packet flow overlay. If the BitString has bits set for other BFRs, the
also needs to be forwarded further within the BIER domain. If the packet also needs to be forwarded further within the BIER domain. If
BF(E)R also forwards one or more copies of the packet within the BIER the BF(E)R also forwards one or more copies of the packet within the
domain, the bit representing the BFR's own BFR-id will be cleared in BIER domain, the bit representing the BFR's own BFR-id MUST be clear
all the copies. in all the copies.
When BIER on a BFER passes a packet to the multicast flow overlay, it When BIER on a BFER passes a packet to the multicast flow overlay, it
may need to provide contextual information obtained from the BIER may need to provide contextual information obtained from the BIER
encapsulation. The information that needs to pass between the BIER encapsulation. The information that needs to pass between the BIER
layer and the multicast flow layer is specific to the multicast flow layer and the multicast flow overlay is specific to the multicast
layer. Specification of the interaction between the BIER layer and flow overlay. Specification of the interaction between the BIER
the multicast flow layer is outside the scope of this specification. layer and the multicast flow overlay is outside the scope of this
specification.
When BIER on a BFER passes a packet to the 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 overlay will determine how to further dispatch the packet. If
the packet needs to be forwarded into another BIER domain, then the 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. BFR will act as a BFER in one BIER domain and as a BFIR in another.
A BIER-encapsulated packet cannot pass directly from one BIER domain A BIER-encapsulated packet cannot pass directly from one BIER domain
to another; at the boundary between BIER domains, the packet must be to another; at the boundary between BIER domains, the packet must be
decapsulated and passed to the multicast flow layer. decapsulated and passed to the multicast flow overlay.
Note that when a BFR transmits multiple copies of a packet within a 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. BIER domain, only one copy will be destined to any given BFER.
Therefore it is not possible for any BIER-encapsulated packet to be Therefore it is not possible for any BIER-encapsulated packet to be
delivered more than once to any BFER. delivered more than once to any BFER.
6.2. BFR Neighbors 6.2. BFR Neighbors
The "BFR Neighbors" (BFR-NBRs) of a given BFR, say BFR-A, are those The "BFR Neighbors" (BFR-NBRs) of a given BFR, say BFR-A, are those
BFRs that, according to the routing underlay, are adjacencies of BFRs that, according to the routing underlay, are adjacencies of
skipping to change at page 15, line 38 skipping to change at page 16, line 46
------------------------------------- -------------------------------------
Figure 3: Bit Index Forwarding Table Figure 3: Bit Index Forwarding Table
This Bit Index Forwarding Table (BIFT) is programmed into the data- This Bit Index Forwarding Table (BIFT) is programmed into the data-
plane and used to forward packets, applying the rules specified below plane and used to forward packets, applying the rules specified below
in Section 6.5. in Section 6.5.
6.5. The BIER Forwarding Procedure 6.5. The BIER Forwarding Procedure
Below is the procedure for forwarding a BIER-encapsulated packet. Below is the procedure that a BFR uses for forwarding a BIER-
encapsulated packet.
1. Determine the packet's SI. 1. Determine the packet's SI, BitStringLength, and sub-domain.
2. Find the position of least significant (rightmost) bit in the 2. If the BitString consists entirely of zeroes, discard the packet;
packet's BitString that is set. (Remember, bits are numbered the forwarding process has been completed. Otherwise proceed to
from 1, starting with the least significant bit.) Use that bit step 3.
position, together with the SI, as the 'index' into the BIFT.
3. Extract from the BIFT the F-BM and the BFR-NBR. 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. Copy the packet. Update the copy's BitString by AND'ing it with 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 the F-BM (i.e., PacketCopy->BitString &= F-BM). Then forward the
copy to the BFR-NBR. Note that when a packet is forwarded to a copy to the BFR-NBR. Note that when a packet is forwarded to a
particular BFR-NBR, its BitString identifies only those BFERs particular BFR-NBR, its BitString identifies only those BFERs
that are to be reached via that BFR-NBR. that are to be reached via that BFR-NBR.
5. Now update the original packet's BitString by AND'ing it with the 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 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 clears the bits that identify the BFERs to which a copy of the
packet has just been forwarded.) Go to step 2. packet has just been forwarded.) Go to step 2.
Note that this procedure causes the packet to be forwarded to a Note that this procedure causes the packet to be forwarded to a
particular BFR-NBR only once. The number of lookups in the BIFT is 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 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 forwarded; it is not necessary to do a separate lookup for each
destination BFER. destination BFER.
skipping to change at page 17, line 23 skipping to change at page 18, line 37
BFR-NBR = BIFT[Index+Offset]->BFR-NBR; BFR-NBR = BIFT[Index+Offset]->BFR-NBR;
PacketCopy = Copy(Packet); PacketCopy = Copy(Packet);
PacketCopy->BitString &= F-BM; PacketCopy->BitString &= F-BM;
PacketSend(PacketCopy, BFR-NBR); PacketSend(PacketCopy, BFR-NBR);
Packet->BitString &= ~F-BM; Packet->BitString &= ~F-BM;
} }
} }
Figure 4: Pseudocode Figure 4: Pseudocode
Note that at a given BFER, the BFR-NBR entry corresponding to the This pseudocode assumes that at a given BFER, the BFR-NBR entry
BFER's own BFR-id will be the BFER's own BFR-prefix. In this case, corresponding to the BFER's own BFR-id will be the BFER's own
the "PacketSend" function sends the packet to the multicast flow BFR-prefix. It also assumes that the corresponding F-BM has only one
layer. bit set, the bit representing the BFER itself. In this case, the
"PacketSend" function sends the packet to the multicast flow overlay.
6.6. Examples of BIER Forwarding 6.6. Examples of BIER Forwarding
In this section, we give two examples of BIER forwarding, based on In this section, we give two examples of BIER forwarding, based on
the topology in Figure 1. In these examples, all packets have been 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 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. 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, For compactness, we show the first column of the BIFT, the BFR-id,
only as an integer. only as an integer.
skipping to change at page 18, line 8 skipping to change at page 19, line 23
| 3 | 0111 | B | | 3 | 0100 | E | | 3 | 1100 | B | | 3 | 0111 | B | | 3 | 0100 | E | | 3 | 1100 | B |
------------------- ------------------- ------------------- ------------------- ------------------- -------------------
| 4 | 1000 | A | | 4 | 1000 | A | | 4 | 1100 | B | | 4 | 1000 | A | | 4 | 1000 | A | | 4 | 1100 | B |
------------------- ------------------- ------------------- ------------------- ------------------- -------------------
Figure 5: BIFTs for Forwarding Examples Figure 5: BIFTs for Forwarding Examples
6.6.1. Example 1 6.6.1. Example 1
BFR-D, BFR-E and BFR-F are BFER's. BFR-A is the BFIR. Suppose that BFR-D, BFR-E and BFR-F are BFER's. BFR-A is the BFIR. Suppose that
BFIR-A has learned from the multicast flow layer that BFER-D is 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 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 that flow from outside the BIER domain, BFIR-A applies the BIER
encapsulation to the packet. The encapsulation must be such that the encapsulation to the packet. The encapsulation must be such that the
SI is zero. The encapsulation also includes a BitString, with just 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 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. Then that BFER-D is the only BFER that needs to receive the packet. Then
BFIR-A follows the procedures of Section 6.5: BFIR-A follows the procedures of Section 6.5:
o Since the packet's BitString is 0001, BFIR-A finds that the first 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 bit in the string is bit 1. Looking at entry 1 in its BIFT, BFR-A
skipping to change at page 18, line 43 skipping to change at page 20, line 9
complete. complete.
When BFR-B receives the multicast packet from BFR-A, it follows the 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 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 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 procedures, and as a result sends a copy of the packet, with a
BitString of 0001, to BFR-D. BitString of 0001, to BFR-D.
At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an
F-BM of 0000 and a BFR-NBR of BFR-D itself. This will cause a copy F-BM of 0000 and a BFR-NBR of BFR-D itself. This will cause a copy
of the packet to be delivered to the multicast flow layer at BFR-D. 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 The packet's BitString will be set to 0000, and the packet will not
be forwarded any further. be forwarded any further.
6.6.2. Example 2 6.6.2. Example 2
This example is similar to Example 1, except that BFIR-A has learned This example is similar to Example 1, except that BFIR-A has learned
from the multicast flow layer that both BFER-D and BFER-E are 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 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 that flow from outside the BIER domain, BFIR-A applies the BIER
encapsulation to the packet. The encapsulation must be such that the encapsulation to the packet. The encapsulation must be such that the
SI is zero. The encapsulation also includes a BitString with two 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 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, and bit 3 is set to indicate that BFR-E is a
BFER for this packet. I.e., the BitString (assuming again a BFER for this packet. I.e., the BitString (assuming again a
BitStringLength of 4) is 0101. To forward the packet, BFIR-A follows BitStringLength of 4) is 0101. To forward the packet, BFIR-A follows
the procedures of Section 6.5: the procedures of Section 6.5:
skipping to change at page 20, line 25 skipping to change at page 21, line 39
o As the packet's BitString is now zero, the forwarding procedure is o As the packet's BitString is now zero, the forwarding procedure is
complete. complete.
Thus BFR-B forwards two copies of the packet. One copy of the 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. 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 Following the same procedures, BFR-C will forward the packet to
BFER-D. BFER-D.
At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an At BFER-D, the BIFT entry (not pictured) for BFR-id 1 will specify an
F-BM of 0000 and a BFR-NBR of BFR-D itself. This will cause a copy F-BM of 0000 and a BFR-NBR of BFR-D itself. This will cause a copy
of the packet to be delivered to the multicast flow layer at BFR-D. 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 The packet's BitString will be set to 0000, and the packet will not
be forwarded any further. be forwarded any further.
The other copy of the packet has been sent from BFR-B to BFER-E, with The other copy of the packet has been sent from BFR-B to BFER-E, with
BitString 0100. BitString 0100.
At BFER-E, the BIFT entry (not pictured) for BFR-id 3 will specify an At BFER-E, the BIFT entry (not pictured) for BFR-id 3 will specify an
F-BM of 0000 and a BFR-NBR of BFR-E itself. This will cause a copy F-BM of 0000 and a BFR-NBR of BFR-E itself. This will cause a copy
of the packet to be delivered to the multicast flow layer at BFR-E. 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 The packet's BitString will be set to 0000, and the packet will not
be forwarded any further. be forwarded any further.
6.7. Equal Cost Multi-path Forwarding 6.7. Equal Cost Multi-path Forwarding
In many networks, the routing underlay will provide multiple equal In many networks, the routing underlay will provide multiple equal
cost paths from a given BFR to a given BFER. When forwarding cost paths from a given BFR to a given BFER. When forwarding
multicast packets through the network, it can be beneficial to take multicast packets through the network, it can be beneficial to take
advantage of this by load balancing among those paths. This feature advantage of this by load balancing among those paths. This feature
is known as "equal cost multiple path forwarding", or "ECMP". is known as "equal cost multiple path forwarding", or "ECMP".
skipping to change at page 26, line 35 skipping to change at page 28, line 14
use the multi-topology features of the IGP to set up a BIER-specific use the multi-topology features of the IGP to set up a BIER-specific
topology. This topology would exclude all the non-BIER-capable topology. This topology would exclude all the non-BIER-capable
interfaces that attach to BFRs. BIER would then have to be run in a 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 sub-domain that is bound to this topology. If unicast tunnels are
used to bypass non-BFRs, either the tunnels have to be restricted to used to bypass non-BFRs, either the tunnels have to be restricted to
this topology, or the tunnel endpoints have to be BFRs that do not this topology, or the tunnel endpoints have to be BFRs that do not
have any non-BIER-capable interfaces. have any non-BIER-capable interfaces.
6.10. Use of Different BitStringLengths within a Domain 6.10. Use of Different BitStringLengths within a Domain
When a BFIR imposes a BIER header on a particular packet, it uses the It is possible for different BFRs within a BIER domain to be using
value of BitStringLength that it has been provisioned to use when different Imposition and/or Disposition BitStringLengths. As stated
imposing a BIER header. For the BIER forwarding procedures to work in Section 3:
properly, this BitStringLength must be supported by the intermediate
BFRs and by the BFERs that may receive that packet.
Suppose one wants to migrate the BitStringLength used in a particular "if a particular BFIR is provisioned to use a particular
domain from one value (X) to another value (Y). The following Imposition BitStringLength and a particular Imposition sub-domain
migration procedure can be used. First, upgrade all the BFRs in the when imposing the encapsulation on a given set of packets, all
domain so that they support both value X and value Y. Once this is other BFRs with BFR-ids in that sub-domain SHOULD be provisioned
done, reprovision the BFIRs so that they use BitStringLength value Y. 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)."
However, it is always possible that the following situation will Note that mis-provisioning can result in "black holes". If a BFIR
occur. Suppose a packet has been BIER-encapsulated with a creates a BIER packet with a particular BitStringLength, and if that
BitStringLength value of X, and that the packet has arrived at BFR-A. packet needs to travel through a BFR that cannot process received
How suppose that according to the routing underlay, the next hop is BIER packets with that BitStringLength, then it may be impossible to
BFR-B, but BFR-B does not support the BitStringLength value of X. forward the packet to all of the BFERs identified in its BIER header.
What should BFR-A do with the packet? BFR-A has three choices. It Section 6.10.1 defines a procedure, the "BitStringLength
MUST be able to do one of the three, but the choice of which Compatibility Check", that can be used to detect the possibility of
procedure to follow is a local matter. The three choices are: such black holes.
o BFR-A MAY discard the packet. 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.
o BFR-A MAY re-encapsulate the packet, using a BIER header whose If the procedures of Section 6.10.2 are not deployed, but the
BitStringLength value is supported by BFR-B. (Note that if BFR-B BitStringLength Compatibility Check fails at some BFIR, the BFIR has
only supports BitStringLength values that are smaller than the two choices:
BitStringLength value of the packet, this may require creating an
additional copy of the packet.)
o BFR-A MAY treat BFR-B as if BFR-B did not support BIER at all, and o Create BIER packets with the provisioned Imposition
apply the rules of Section 6.9. 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. Then the BFIR chooses an Imposition
BitStringLength L for the packet. The choice of Imposition
BitStringLength is 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 the MPLS encapsulation [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 choice
about what to do with the packets:
1. The BFIR MAY use the provisioned Imposition BitStringLength
anyway. If the procedure Paragraph 2 or Paragraph 3 of
Section 6.10.2 are 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
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.
This fallback procedure will work best if the value of F is
established by the architecture, rather than by provisioning.
6.10.2. Handling BitStringLength Mismatches
Suppose 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,
and apply 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, and 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".
First, upgrade all the BFRs in the domain so that they use both value
X and value Y as their Disposition BitStringLengths. Once this is
done, reprovision the BFIRs so that they use BitStringLength value Y
as the Imposition BitStringLength. Once that is done, one may
optionally reprovision all the BFRs so that they no longer use
Dispostion BitStringLength X.
7. IANA Considerations 7. IANA Considerations
This document contains no actions for IANA. This document contains no actions for IANA.
8. Security Considerations 8. Security Considerations
When BIER is paired with a particular multicast flow layer, it When BIER is paired with a particular multicast flow overlay, it
inherits the security considerations of that layer. Similarly, when inherits the security considerations of that layer. Similarly, when
BIER is paired with a particular routing underlay, it inherits the BIER is paired with a particular routing underlay, it inherits the
security considerations of that layer. security considerations of that layer.
If the BIER encapsulation of a particular packet specifies an SI or a 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 BitString other than the one intended by the BFIR, the packet is
likely to be misdelivered. If the BIER encapsulation of a 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 modified (through error or malfeasance) in a way other than that
specified in this document, the packet may be misdelivered. specified in this document, the packet may be misdelivered.
skipping to change at page 29, line 36 skipping to change at page 34, line 12
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
11.2. Informative References 11.2. Informative References
[Boivie_Feldman] [Boivie_Feldman]
Boivie, R. and N. Feldman, "Small Group Multicast", Boivie, R. and N. Feldman, "Small Group Multicast",
(expired) draft-boivie-sgm-02.txt, February 2001. (expired) draft-boivie-sgm-02.txt, February 2001.
[ISIS_BIER_EXTENSIONS] [ISIS_BIER_EXTENSIONS]
Przygienda, T., Ginsberg, L., Aldrin, S., and J. Zhang, Ginsberg, L., Przygienda, T., Aldrin, S., and J. Zhang,
"OSPF Extensions for Bit Index Explicit Replication", "BIER Support via ISIS", internet-draft draft-ietf-bier-
internet-draft draft-przygienda-bier-isis-ranges-01.txt, isis-ranges-00.txt, April 2015.
October 2014.
[MPLS_BIER_ENCAPS] [MPLS_BIER_ENCAPS]
Wijnands, IJ., Rosen, E., Dolganow, A., Tantsura, J., and Wijnands, IJ., Rosen, E., Dolganow, A., Tantsura, J., and
S. Aldrin, "Encapsulation for Bit Index Explicit S. Aldrin, "Encapsulation for Bit Index Explicit
Replication in MPLS Networks", internet-draft draft-ietf- Replication in MPLS Networks", internet-draft draft-ietf-
bier-mpls-encaps-00.txt, April 2015. bier-mpls-encapsulation-00.txt, April 2015.
[OSPF_BIER_EXTENSIONS] [OSPF_BIER_EXTENSIONS]
Psenak, P., Kumar, N., Wijnands, IJ., Dolganow, A., Psenak, P., Kumar, N., Wijnands, IJ., Dolganow, A.,
Przygienda, T., and J. Zhang, "OSPF Extensions for Bit Przygienda, T., and J. Zhang, "OSPF Extensions for Bit
Index Explicit Replication", internet-draft draft-psenak- Index Explicit Replication", internet-draft draft-ietf-
ospf-bier-extensions-01.txt, October 2014. ospf-bier-extensions-00.txt, April 2015.
[RFC6513] Rosen, E. and R. Aggarwal, "Multicast in MPLS/BGP IP [RFC6513] Rosen, E. and R. Aggarwal, "Multicast in MPLS/BGP IP
VPNs", RFC 6513, February 2012. VPNs", RFC 6513, February 2012.
[RFC6514] Aggarwal, R., Rosen, E., Morin, T., and Y. Rekhter, "BGP [RFC6514] Aggarwal, R., Rosen, E., Morin, T., and Y. Rekhter, "BGP
Encodings and Procedures for Multicast in MPLS/BGP IP Encodings and Procedures for Multicast in MPLS/BGP IP
VPNs", RFC 6514, February 2012. VPNs", RFC 6514, February 2012.
Authors' Addresses Authors' Addresses
skipping to change at page 31, line 4 skipping to change at page 35, line 19
Email: andrew.dolganow@alcatel-lucent.com Email: andrew.dolganow@alcatel-lucent.com
Tony Przygienda Tony Przygienda
Ericsson Ericsson
300 Holger Way 300 Holger Way
San Jose, California 95134 San Jose, California 95134
United States United States
Email: antoni.przygienda@ericsson.com Email: antoni.przygienda@ericsson.com
Sam K Aldrin Sam K Aldrin
Huawei Technologies Google, Inc.
2330 Central Express Way 1600 Amphitheatre Parkway
Santa Clara, California Mountain View, California
United States United States
Email: aldrin.ietf@gmail.com Email: aldrin.ietf@gmail.com
 End of changes. 51 change blocks. 
170 lines changed or deleted 370 lines changed or added

This html diff was produced by rfcdiff 1.42. The latest version is available from http://tools.ietf.org/tools/rfcdiff/