< draft-ietf-bier-te-arch-12.txt   draft-ietf-bier-te-arch-13.txt >
Network Working Group T.T.E. Eckert, Ed. Network Working Group T.T.E. Eckert, Ed.
Internet-Draft Futurewei Internet-Draft Futurewei
Intended status: Standards Track M.M. Menth Intended status: Standards Track M.M. Menth
Expires: 1 August 2022 University of Tuebingen Expires: 27 October 2022 University of Tuebingen
G.C. Cauchie G.C. Cauchie
Bouygues Telecom KOEVOO
January 2022 April 2022
Tree Engineering for Bit Index Explicit Replication (BIER-TE) Tree Engineering for Bit Index Explicit Replication (BIER-TE)
draft-ietf-bier-te-arch-12 draft-ietf-bier-te-arch-13
Abstract Abstract
This memo describes per-packet stateless strict and loose path This memo describes per-packet stateless strict and loose path
steered replication and forwarding for "Bit Index Explicit steered replication and forwarding for "Bit Index Explicit
Replication" (BIER, RFC8279) packets. It is called BIER Tree Replication" (BIER, RFC8279) packets. It is called BIER Tree
Engineering (BIER-TE) and is intended to be used as the path steering Engineering (BIER-TE) and is intended to be used as the path steering
mechanism for Traffic Engineering with BIER. mechanism for Traffic Engineering with BIER.
BIER-TE introduces a new semantic for "bit positions" (BP). They BIER-TE introduces a new semantic for "bit positions" (BP). They
skipping to change at page 1, line 34 skipping to change at page 1, line 34
BIER in which BPs indicate "Bit-Forwarding Egress Routers" (BFER). A BIER in which BPs indicate "Bit-Forwarding Egress Routers" (BFER). A
BIER-TE packets BitString therefore indicates the edges of the (loop- BIER-TE packets BitString therefore indicates the edges of the (loop-
free) tree that the packet is forwarded across by BIER-TE. BIER-TE free) tree that the packet is forwarded across by BIER-TE. BIER-TE
can leverage BIER forwarding engines with little changes. Co- can leverage BIER forwarding engines with little changes. Co-
existence of BIER and BIER-TE forwarding in the same domain is existence of BIER and BIER-TE forwarding in the same domain is
possible, for example by using separate BIER "sub-domains" (SDs). possible, for example by using separate BIER "sub-domains" (SDs).
Except for the optional routed adjacencies, BIER-TE does not require Except for the optional routed adjacencies, BIER-TE does not require
a BIER routing underlay, and can therefore operate without depending a BIER routing underlay, and can therefore operate without depending
on an "Interior Gateway Routing protocol" (IGP). on an "Interior Gateway Routing protocol" (IGP).
As it operates on the same per-packet stateless forwarding
principles, BIER-TE can also be a good fit to support multicast path
steering in "Segment Routing" (SR) networks.
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 https://datatracker.ietf.org/drafts/current/. Drafts is at https://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 5 July 2022. This Internet-Draft will expire on 3 October 2022.
Copyright Notice Copyright Notice
Copyright (c) 2022 IETF Trust and the persons identified as the Copyright (c) 2022 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 (https://trustee.ietf.org/ Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document. license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights Please review these documents carefully, as they describe your rights
skipping to change at page 3, line 4 skipping to change at page 2, line 46
3.3. The BIER-TE Forwarding Plane . . . . . . . . . . . . . . 16 3.3. The BIER-TE Forwarding Plane . . . . . . . . . . . . . . 16
3.4. The Routing Underlay . . . . . . . . . . . . . . . . . . 17 3.4. The Routing Underlay . . . . . . . . . . . . . . . . . . 17
3.5. Traffic Engineering Considerations . . . . . . . . . . . 17 3.5. Traffic Engineering Considerations . . . . . . . . . . . 17
4. BIER-TE Forwarding . . . . . . . . . . . . . . . . . . . . . 18 4. BIER-TE Forwarding . . . . . . . . . . . . . . . . . . . . . 18
4.1. The BIER-TE Bit Index Forwarding Table (BIFT) . . . . . . 18 4.1. The BIER-TE Bit Index Forwarding Table (BIFT) . . . . . . 18
4.2. Adjacency Types . . . . . . . . . . . . . . . . . . . . . 20 4.2. Adjacency Types . . . . . . . . . . . . . . . . . . . . . 20
4.2.1. Forward Connected . . . . . . . . . . . . . . . . . . 21 4.2.1. Forward Connected . . . . . . . . . . . . . . . . . . 21
4.2.2. Forward Routed . . . . . . . . . . . . . . . . . . . 21 4.2.2. Forward Routed . . . . . . . . . . . . . . . . . . . 21
4.2.3. ECMP . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2.3. ECMP . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2.4. Local Decap(sulation) . . . . . . . . . . . . . . . . 22 4.2.4. Local Decap(sulation) . . . . . . . . . . . . . . . . 22
4.3. Encapsulation / Co-existence with BIER . . . . . . . . . 22 4.3. Encapsulation / Co-existence with BIER . . . . . . . . . 22
4.4. BIER-TE Forwarding Pseudocode . . . . . . . . . . . . . . 23 4.4. BIER-TE Forwarding Pseudocode . . . . . . . . . . . . . . 23
4.5. Basic BIER-TE Forwarding Example . . . . . . . . . . . . 26 4.5. BFR Requirements for BIER-TE forwarding . . . . . . . . . 26
4.6. BFR Requirements for BIER-TE forwarding . . . . . . . . . 28 5. BIER-TE Controller Operational Considerations . . . . . . . . 27
5. BIER-TE Controller Operational Considerations . . . . . . . . 29 5.1. Bit Position Assignments . . . . . . . . . . . . . . . . 27
5.1. Bit Position Assignments . . . . . . . . . . . . . . . . 29 5.1.1. P2P Links . . . . . . . . . . . . . . . . . . . . . . 27
5.1.1. P2P Links . . . . . . . . . . . . . . . . . . . . . . 29 5.1.2. BFER . . . . . . . . . . . . . . . . . . . . . . . . 27
5.1.2. BFER . . . . . . . . . . . . . . . . . . . . . . . . 29 5.1.3. Leaf BFERs . . . . . . . . . . . . . . . . . . . . . 27
5.1.3. Leaf BFERs . . . . . . . . . . . . . . . . . . . . . 29 5.1.4. LANs . . . . . . . . . . . . . . . . . . . . . . . . 29
5.1.4. LANs . . . . . . . . . . . . . . . . . . . . . . . . 31 5.1.5. Hub and Spoke . . . . . . . . . . . . . . . . . . . . 30
5.1.5. Hub and Spoke . . . . . . . . . . . . . . . . . . . . 32 5.1.6. Rings . . . . . . . . . . . . . . . . . . . . . . . . 30
5.1.6. Rings . . . . . . . . . . . . . . . . . . . . . . . . 32 5.1.7. Equal Cost MultiPath (ECMP) . . . . . . . . . . . . . 31
5.1.7. Equal Cost MultiPath (ECMP) . . . . . . . . . . . . . 33 5.1.8. Forward Routed adjacencies . . . . . . . . . . . . . 34
5.1.8. Forward Routed adjacencies . . . . . . . . . . . . . 36 5.1.8.1. Reducing bit positions . . . . . . . . . . . . . 34
5.1.8.1. Reducing bit positions . . . . . . . . . . . . . 36 5.1.8.2. Supporting nodes without BIER-TE . . . . . . . . 35
5.1.8.2. Supporting nodes without BIER-TE . . . . . . . . 37 5.1.9. Reuse of bit positions (without DNC) . . . . . . . . 35
5.1.9. Reuse of bit positions (without DNC) . . . . . . . . 37 5.1.10. Summary of BP optimizations . . . . . . . . . . . . . 36
5.1.10. Summary of BP optimizations . . . . . . . . . . . . . 38 5.2. Avoiding duplicates and loops . . . . . . . . . . . . . . 37
5.2. Avoiding duplicates and loops . . . . . . . . . . . . . . 39 5.2.1. Loops . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2.1. Loops . . . . . . . . . . . . . . . . . . . . . . . . 40 5.2.2. Duplicates . . . . . . . . . . . . . . . . . . . . . 38
5.2.2. Duplicates . . . . . . . . . . . . . . . . . . . . . 40 5.3. Managing SI, sub-domains and BFR-ids . . . . . . . . . . 39
5.3. Managing SI, sub-domains and BFR-ids . . . . . . . . . . 41 5.3.1. Why SI and sub-domains . . . . . . . . . . . . . . . 39
5.3.1. Why SI and sub-domains . . . . . . . . . . . . . . . 41 5.3.2. Assigning bits for the BIER-TE topology . . . . . . . 40
5.3.2. Assigning bits for the BIER-TE topology . . . . . . . 42 5.3.3. Assigning BFR-id with BIER-TE . . . . . . . . . . . . 41
5.3.3. Assigning BFR-id with BIER-TE . . . . . . . . . . . . 43 5.3.4. Mapping from BFR to BitStrings with BIER-TE . . . . . 42
5.3.4. Mapping from BFR to BitStrings with BIER-TE . . . . . 44 5.3.5. Assigning BFR-ids for BIER-TE . . . . . . . . . . . . 43
5.3.5. Assigning BFR-ids for BIER-TE . . . . . . . . . . . . 45 5.3.6. Example bit allocations . . . . . . . . . . . . . . . 43
5.3.6. Example bit allocations . . . . . . . . . . . . . . . 45 5.3.6.1. With BIER . . . . . . . . . . . . . . . . . . . . 43
5.3.6.1. With BIER . . . . . . . . . . . . . . . . . . . . 45 5.3.6.2. With BIER-TE . . . . . . . . . . . . . . . . . . 44
5.3.6.2. With BIER-TE . . . . . . . . . . . . . . . . . . 46 5.3.7. Summary . . . . . . . . . . . . . . . . . . . . . . . 45
5.3.7. Summary . . . . . . . . . . . . . . . . . . . . . . . 47 6. Security Considerations . . . . . . . . . . . . . . . . . . . 46
6. Security Considerations . . . . . . . . . . . . . . . . . . . 48 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 47
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 49 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 47
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 49 9. Change log [RFC Editor: Please remove] . . . . . . . . . . . 48
9. Change log [RFC Editor: Please remove] . . . . . . . . . . . 50 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 61
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 62 10.1. Normative References . . . . . . . . . . . . . . . . . . 61
10.1. Normative References . . . . . . . . . . . . . . . . . . 62 10.2. Informative References . . . . . . . . . . . . . . . . . 61
10.2. Informative References . . . . . . . . . . . . . . . . . 63 Appendix A. BIER-TE and Segment Routing (SR) . . . . . . . . . . 64
Appendix A. BIER-TE and Segment Routing . . . . . . . . . . . . 66 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 65
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 67
1. Overview 1. Overview
BIER-TE is based on the (non-TE) BIER architecture, terminology and BIER-TE is based on the (non-TE) BIER architecture, terminology and
packet formats as described in [RFC8279] and [RFC8296]. This packet formats as described in [RFC8279] and [RFC8296]. This
document describes BIER-TE in the expectation that the reader is document describes BIER-TE in the expectation that the reader is
familiar with these two documents. familiar with these two documents.
BIER-TE introduces a new semantic for "bit positions" (BP). They BIER-TE introduces a new semantic for "bit positions" (BP). They
indicate adjacencies of the network topology, as opposed to (non-TE) indicate adjacencies of the network topology, as opposed to (non-TE)
skipping to change at page 4, line 13 skipping to change at page 4, line 4
familiar with these two documents. familiar with these two documents.
BIER-TE introduces a new semantic for "bit positions" (BP). They BIER-TE introduces a new semantic for "bit positions" (BP). They
indicate adjacencies of the network topology, as opposed to (non-TE) indicate adjacencies of the network topology, as opposed to (non-TE)
BIER in which BPs indicate "Bit-Forwarding Egress Routers" (BFER). A BIER in which BPs indicate "Bit-Forwarding Egress Routers" (BFER). A
BIER-TE packets BitString therefore indicates the edges of the (loop- BIER-TE packets BitString therefore indicates the edges of the (loop-
free) tree that the packet is forwarded across by BIER-TE. With free) tree that the packet is forwarded across by BIER-TE. With
BIER-TE, the "Bit Index Forwarding Table" (BIFT) of each "Bit BIER-TE, the "Bit Index Forwarding Table" (BIFT) of each "Bit
Forwarding Router" (BFR) is only populated with BP that are adjacent Forwarding Router" (BFR) is only populated with BP that are adjacent
to the BFR in the BIER-TE Topology. Other BPs are empty in the BIFT. to the BFR in the BIER-TE Topology. Other BPs are empty in the BIFT.
The BFR replicate and forwards BIER packets to adjacent BPs that are The BFR replicate and forwards BIER packets to adjacent BPs that are
set in the packet. BPs are normally also cleared upon forwarding to set in the packet. BPs are normally also cleared upon forwarding to
avoid duplicates and loops. avoid duplicates and loops.
BIER-TE can leverage BIER forwarding engines with little or no BIER-TE can leverage BIER forwarding engines with little or no
changes. It can also co-exist with BIER forwarding in the same changes. It can also co-exist with BIER forwarding in the same
domain, for example by using separate BIER sub-domains. Except for domain, for example by using separate BIER sub-domains. Except for
the optional routed adjacencies, BIER-TE does not require a BIER the optional routed adjacencies, BIER-TE does not require a BIER
routing underlay, and can therefore operate without depending on an routing underlay, and can therefore operate without depending on an
"Interior Gateway Routing protocol" (IGP). "Interior Gateway Routing protocol" (IGP).
As it operates on the same per-packet stateless forwarding
principles, BIER-TE can also be a good fit to support multicast path
steering in "Segment Routing" (SR) networks ([RFC8402]).
This document is structured as follows: This document is structured as follows:
* Section 2 introduces BIER-TE with two forwarding examples, * Section 2 introduces BIER-TE with two forwarding examples,
followed by an introduction of the new concepts of the BIER-TE followed by an introduction of the new concepts of the BIER-TE
(overlay) topology and finally a summary of the relationship (overlay) topology and finally a summary of the relationship
between BIER and BIER-TE and a discussion of accelerated hardware between BIER and BIER-TE and a discussion of accelerated hardware
forwarding. forwarding.
* Section 3 describes the components of the BIER-TE architecture, * Section 3 describes the components of the BIER-TE architecture,
Flow overlay, BIER-TE layer with the BIER-TE control plane Flow overlay, BIER-TE layer with the BIER-TE control plane
skipping to change at page 5, line 15 skipping to change at page 4, line 44
* Section 5 describes operational considerations for the BIER-TE * Section 5 describes operational considerations for the BIER-TE
controller, foremost how the BIER-TE controller can optimize the controller, foremost how the BIER-TE controller can optimize the
use of BP by using specific type of BIER-TE adjacencies for use of BP by using specific type of BIER-TE adjacencies for
different type of topological situations, but also how to assign different type of topological situations, but also how to assign
bits to avoid loops and duplicates (which in BIER-TE does not come bits to avoid loops and duplicates (which in BIER-TE does not come
for free), and finally how "Set Identifier" (SI), "sub-domain" for free), and finally how "Set Identifier" (SI), "sub-domain"
(SD) and BFR-ids can be managed by a BIER-TE controller, examples (SD) and BFR-ids can be managed by a BIER-TE controller, examples
and summary. and summary.
* Appendix A concludes the technology specific sections of the * Appendix A concludes the technology specific sections of the
document by further relating BIER-TE to SR. document by further relating BIER-TE to Segment Routing (SR).
Note that related work, [I-D.ietf-roll-ccast] uses Bloom filters Note that related work, [I-D.ietf-roll-ccast] uses Bloom filters
[Bloom70] to represent leaves or edges of the intended delivery tree. [Bloom70] to represent leaves or edges of the intended delivery tree.
Bloom filters in general can support larger trees/topologies with Bloom filters in general can support larger trees/topologies with
fewer addressing bits than explicit BitStrings, but they introduce fewer addressing bits than explicit BitStrings, but they introduce
the heuristic risk of false positives and cannot clear bits in the the heuristic risk of false positives and cannot clear bits in the
BitString during forwarding to avoid loops. For these reasons, BIER- BitString during forwarding to avoid loops. For these reasons, BIER-
TE uses explicit BitStrings like BIER. The explicit BitStrings of TE uses explicit BitStrings like BIER. The explicit BitStrings of
BIER-TE can also be seen as a special type of Bloom filter, and this BIER-TE can also be seen as a special type of Bloom filter, and this
is how related work [ICC] describes it. is how related work [ICC] describes it.
skipping to change at page 10, line 9 skipping to change at page 10, line 9
2. BIER-TE has the following key changes with respect to BIER: 2. BIER-TE has the following key changes with respect to BIER:
1. In BIER, bits in the BitString of a BIER packet header 1. In BIER, bits in the BitString of a BIER packet header
indicate a BFER and bits in the BIFT indicate the BIER indicate a BFER and bits in the BIFT indicate the BIER
control plane calculated next-hop toward that BFER. In BIER- control plane calculated next-hop toward that BFER. In BIER-
TE, a bit in the BitString of a BIER packet header indicates TE, a bit in the BitString of a BIER packet header indicates
an adjacency in the BIER-TE topology, and only the BFR that an adjacency in the BIER-TE topology, and only the BFR that
is the upstream of that adjacency has its BP populated with is the upstream of that adjacency has its BP populated with
the adjacency in its BIFT. the adjacency in its BIFT.
2. In BIER, the implied reference option for the core part of 2. In BIER, the implied reference options for the core part of
the BIER layer control plane are the BIER extensions for the BIER layer control plane are the BIER extensions for
distributed routing protocols. This includes ISIS/OSPF distributed routing protocols. This includes ISIS/OSPF
extensions for BIER, [RFC8401] and [RFC8444]. extensions for BIER, [RFC8401] and [RFC8444].
3. The reference option for the core part of the BIER-TE control 3. The reference option for the core part of the BIER-TE control
plane is the BIER-TE controller. Nevertheless, both the BIER plane is the BIER-TE controller. Nevertheless, both the BIER
and BIER-TE BIFTs forwarding plane state could equally be and BIER-TE BIFTs forwarding plane state could equally be
populated by any mechanism. populated by any mechanism.
4. Assuming the reference options for the control plane, BIER-TE 4. Assuming the reference options for the control plane, BIER-TE
skipping to change at page 11, line 27 skipping to change at page 11, line 27
See also Section 5.3.3. See also Section 5.3.3.
2.4. Accelerated/Hardware forwarding comparison 2.4. Accelerated/Hardware forwarding comparison
BIER-TE forwarding rules, especially the BitString parsing are BIER-TE forwarding rules, especially the BitString parsing are
designed to be as close as possible to those of BIER in the designed to be as close as possible to those of BIER in the
expectation that this eases the programming of BIER-TE forwarding expectation that this eases the programming of BIER-TE forwarding
code and/or BIER-TE forwarding hardware on platforms supporting BIER. code and/or BIER-TE forwarding hardware on platforms supporting BIER.
The pseudocode in Section 4.4 shows how existing (non-TE) BIER/BIFT The pseudocode in Section 4.4 shows how existing (non-TE) BIER/BIFT
forwarding can be modified to support the required BIER-TE forwarding forwarding can be modified to support the required BIER-TE forwarding
functionality (Section 4.6), by using BIER BIFT's "Forwarding Bit functionality (Section 4.5), by using BIER BIFT's "Forwarding Bit
Mask" (F-BM): Only the clearing of bits to avoid duplicate packets to Mask" (F-BM): Only the clearing of bits to avoid duplicate packets to
a BFR's neighbor is skipped in BIER-TE forwarding because it is not a BFR's neighbor is skipped in BIER-TE forwarding because it is not
necessary and could not be done when using BIER F-BM. necessary and could not be done when using BIER F-BM.
Whether to use BIER or BIER-TE forwarding is simply a choice of the Whether to use BIER or BIER-TE forwarding is simply a choice of the
mode of the BIFT indicated by the packet (BIER or BIER-TE BIFT). mode of the BIFT indicated by the packet (BIER or BIER-TE BIFT).
This is determined by the BFR configuration for the encapsulation, This is determined by the BFR configuration for the encapsulation,
see Section 4.3. see Section 4.3.
3. Components 3. Components
skipping to change at page 19, line 28 skipping to change at page 19, line 28
In BIER, each BIFT-index addresses one BFER by its BFR-id = BIFT- In BIER, each BIFT-index addresses one BFER by its BFR-id = BIFT-
index + 1 and is populated on each BFR with the next-hop "BFR index + 1 and is populated on each BFR with the next-hop "BFR
Neighbor" (BFR-NBR) towards that BFER. Neighbor" (BFR-NBR) towards that BFER.
In BIER-TE, each BIFT-index and therefore SI:BP indicates one or more In BIER-TE, each BIFT-index and therefore SI:BP indicates one or more
adjacencies between BFRs in the topology and is only populated with adjacencies between BFRs in the topology and is only populated with
those adjacencies forwarding entries on the BFR that is the upstream those adjacencies forwarding entries on the BFR that is the upstream
for these adjacencies. The BIFT entry are empty on all other BFRs. for these adjacencies. The BIFT entry are empty on all other BFRs.
In BIER, each BIFT rows also requires a "Forwarding Bit Mask" (F-BM) In BIER, each BIFT row also requires a "Forwarding Bit Mask" (F-BM)
entry for BIER forwarding rules. In BIER-TE forwarding, F-BM is not entry for BIER forwarding rules. In BIER-TE forwarding, F-BM is not
required, but can be used when implementing BIER-TE on forwarding required, but can be used when implementing BIER-TE on forwarding
hardware derived from BIER forwarding, that must use F-BM. This is hardware derived from BIER forwarding, that must use F-BM. This is
discussed in the first BIER-TE forwarding pseudocode in Section 4.4. discussed in the first BIER-TE forwarding pseudocode in Section 4.4.
------------------------------------------------------------------ ------------------------------------------------------------------
| BIFT-index | | Adjacencies: | | BIFT-index | | Adjacencies: |
| (SI:BP) |(FBM)| <empty> or one or more per entry | | (SI:BP) |(FBM)| <empty> or one or more per entry |
================================================================== ==================================================================
| BIFT indices for Packets with SI=0 | | BIFT indices for Packets with SI=0 |
skipping to change at page 25, line 6 skipping to change at page 25, line 6
2. All BIFT BPs with an adjacency (with DNC flag clear) have an F-BM 2. All BIFT BPs with an adjacency (with DNC flag clear) have an F-BM
that has only those BPs set for which this BFR does not have an that has only those BPs set for which this BFR does not have an
adjacency. This causes [2] to clear all bits from adjacency. This causes [2] to clear all bits from
PacketCopy->BitString for which this BFR does have an adjacency. PacketCopy->BitString for which this BFR does have an adjacency.
3. [1] is not performed for BIER-TE. All bit clearing required by 3. [1] is not performed for BIER-TE. All bit clearing required by
BIER-TE is performed by [2]. BIER-TE is performed by [2].
This Forwarding Pseudocode can support the required BIER-TE This Forwarding Pseudocode can support the required BIER-TE
forwarding functions (see Section 4.6), forward_connected(), forwarding functions (see Section 4.5), forward_connected(),
forward_routed() and local_decap(), but not the recommended functions forward_routed() and local_decap(), but not the recommended functions
DNC flag and multiple adjacencies per bit nor the optional function, DNC flag and multiple adjacencies per bit nor the optional function,
ECMP() adjacencies. The DNC flag cannot be supported when using only ECMP() adjacencies. The DNC flag cannot be supported when using only
[1] to mask bits. [1] to mask bits.
The modified and expanded Forwarding Pseudocode in Figure 6 specifies The modified and expanded Forwarding Pseudocode in Figure 6 specifies
how to support all BIER-TE forwarding functions (required, how to support all BIER-TE forwarding functions (required,
recommended and optional): recommended and optional):
* This pseudocode eliminates per-bit F-BM, therefore reducing the * This pseudocode eliminates per-bit F-BM, therefore reducing the
skipping to change at page 26, line 45 skipping to change at page 26, line 45
DecapBierHeader(PacketCopy); DecapBierHeader(PacketCopy);
PassTo(PacketCopy,{VRF,}Packet->NextProto); PassTo(PacketCopy,{VRF,}Packet->NextProto);
} }
} }
} }
} }
Figure 6: Complete BIER-TE Forwarding Pseudocode for required, Figure 6: Complete BIER-TE Forwarding Pseudocode for required,
recommended and optional functions recommended and optional functions
4.5. Basic BIER-TE Forwarding Example 4.5. BFR Requirements for BIER-TE forwarding
[RFC Editor: remove this section.]
THIS SECTION TO BE REMOVED IN RFC BECAUSE IT WAS SUPERSEDED BY
SECTION 1.1 EXAMPLE - IN CASE FINAL REVIES FIND A GOOD REASON TO KEEP
IT, BUT DOESN'T SEEM TO SHOW IMPORTANT NEW STUFF OVER INITIAL
EXAMPLES.
Step-by-step example of basic BIER-TE forwarding. This example does
not use ECMP() or forward_routed() adjacencies nor does it try to
minimize the number of required BitPositions for the topology.
[BIER-TE Controller]
/ | \
v v v
. .
| p13 p1 | .
+- BFIR2 --+ | .
| . | p2 p6 | . LAN2
| . +-- BFR3 --+ . |
| . | | p7 p11 |
Src -+ . +-- BFER1 --+
| . | p3 p8 | . |
| . +-- BFR4 --+ . +-- Rcv1
| . | | . |
| . | .
| p14 p4 | .
+- BFIR1 --+ | .
| . +-- BFR5 --+ p10 p12 |
LAN1 . | p5 p9 +-- BFER2 --+
. | . +-- Rcv2
. . |
. . LAN3
. .
IP |..... BIER-TE network.....| IP
Figure 7: BIER-TE Forwarding Example
pXX indicate the BitPositions number assigned by the BIER-TE
Controller to adjacencies in the BIER-TE topology. For example, p9
is the adjacency towards BFR5 on the LAN connecting to BFER2.
BIFT BFIR2:
p13: local_decap
p2: forward_connected(BFR3)
BIFT BFR3:
p1: forward_connected(BFIR2)
p7: forward_connected(BFER1)
p8: forward_connected(BFR4)
BIFT BFER1:
p11: local_decap
p6: forward_connected(BFR3)
p8: forward_connected(BFR4)
Figure 8: BIER-TE Forwarding Example Adjacencies
...and so on.
For example, we assume that some multicast traffic seen on LAN1 needs
to be sent via BIER-TE by BFIR2 towards Rcv1 and Rcv2. The BIER-TE
Controller determines it wants it to pass this traffic across the
following paths:
-> BFER1 ---------------> Rcv1
BFIR2 -> BFR3
-> BFR4 -> BFR5 -> BFER2 -> Rcv2
Figure 9: BIER-TE Forwarding Example Paths
These paths equal to the following BitString: p2, p5, p7, p8, p10,
p11, p12.
This BitString is assigned by BFIR2 to the example multicast traffic
received from LAN1.
Then BFIR2 forwards this multicast traffic with BIER-TE based on that
BitString. The BIFT of BFIR2 has only p2 and p13 populated. Only p2
is in the BitString and this is an adjacency towards BFR3. BFIR2
therefore clears p2 in the BitString and sends a copy towards BFR2.
BFR3 sees a BitString of p5,p7,p8,p10,p11,p12. For those BPs, it has
only adjacencies for p7,p8. It creates a copy of the packet to BFER1
(due to p7) and one to BFR4 (due to p8). It clears both p7 and p8
before sending.
BFER1 sees a BitString of p5,p10,p11,p12. For those BPs, it only has
an adjacency for p11. p11 is a local_decap() adjacency installed by
the BIER-TE Controller to receive a copy of the BIER packet - dispose
of the BIER header and pass the payload to IP multicast. IP
multicast will then forward the packet out to LAN2 because it did
receive PIM or IGMP joins on LAN2 for the traffic.
Further processing of the packet in BFR4, BFR5 and BFER2 accordingly.
4.6. BFR Requirements for BIER-TE forwarding
BFR that support BIER-TE and BIER MUST support configuration that BFR that support BIER-TE and BIER MUST support configuration that
enables BIER-TE instead of (non-TE) BIER forwarding rules for all enables BIER-TE instead of (non-TE) BIER forwarding rules for all
BIFT of one or more BIER sub-domains. Every BP in a BIER-TE BIFT BIFT of one or more BIER sub-domains. Every BP in a BIER-TE BIFT
MUST support to have zero or one adjacency. BIER-TE forwarding MUST MUST support to have zero or one adjacency. BIER-TE forwarding MUST
support the adjacency types forward_connected() with the DNC flag not support the adjacency types forward_connected() with the DNC flag not
set, forward_routed() and local_decap(). As explained in set, forward_routed() and local_decap(). As explained in
Section 4.4, these required BIER-TE forwarding functions can be Section 4.4, these required BIER-TE forwarding functions can be
implemented via the same Forwarding Pseudocode as BIER forwarding implemented via the same Forwarding Pseudocode as BIER forwarding
except for one modification (skipping one masking with F-BM). except for one modification (skipping one masking with F-BM).
skipping to change at page 30, line 15 skipping to change at page 28, line 15
| \ / | | | | \ / | | |
| X | | | | X | | |
| / \ | | | | / \ | | |
BFER1(PE) BFER2(PE) BFER1(PE)----BFER2(PE) BFER1(PE) BFER2(PE) BFER1(PE)----BFER2(PE)
^ U-turn link ^ U-turn link
Leaf BFER / Non-Leaf BFER / Leaf BFER / Non-Leaf BFER /
PE-router PE-router PE-router PE-router
Figure 10: Leaf vs. non-Leaf BFER Example Figure 7: Leaf vs. non-Leaf BFER Example
A leaf BFER is one where incoming BIER-TE packets never need to be A leaf BFER is one where incoming BIER-TE packets never need to be
forwarded to another BFR but are only sent to the BFER to exit the forwarded to another BFR but are only sent to the BFER to exit the
BIER-TE domain. For example, in networks where Provider Edge (PE) BIER-TE domain. For example, in networks where Provider Edge (PE)
router are spokes connected to Provider (P) routers, those PEs are router are spokes connected to Provider (P) routers, those PEs are
Leaf BFERs unless there is a U-turn between two PEs. Leaf BFERs unless there is a U-turn between two PEs.
Consider how redundant disjoint traffic can reach BFER1/BFER2 in Consider how redundant disjoint traffic can reach BFER1/BFER2 in
Figure 10: When BFER1/BFER2 are Non-Leaf BFER as shown on the right- Figure 7: When BFER1/BFER2 are Non-Leaf BFER as shown on the right-
hand side, one traffic copy would be forwarded to BFER1 from BFR1, hand side, one traffic copy would be forwarded to BFER1 from BFR1,
but the other one could only reach BFER1 via BFER2, which makes BFER2 but the other one could only reach BFER1 via BFER2, which makes BFER2
a non-Leaf BFER. Likewise, BFER1 is a non-Leaf BFER when forwarding a non-Leaf BFER. Likewise, BFER1 is a non-Leaf BFER when forwarding
traffic to BFER2. Note that the BFERs in the left-hand picture are traffic to BFER2. Note that the BFERs in the left-hand picture are
only guaranteed to be leaf-BFER by fitting routing configuration that only guaranteed to be leaf-BFER by fitting routing configuration that
prohibits transit traffic to pass through the BFERs, which is prohibits transit traffic to pass through the BFERs, which is
commonly applied in these topologies. commonly applied in these topologies.
In most situations, leaf-BFER that are to be addressed via the same In most situations, leaf-BFER that are to be addressed via the same
BitString can share a single bit position for their local_decap() BitString can share a single bit position for their local_decap()
skipping to change at page 31, line 10 skipping to change at page 29, line 10
created the packet copy for the leaf-BFER in question) is populated created the packet copy for the leaf-BFER in question) is populated
with multiple adjacencies as an optimization, such as in with multiple adjacencies as an optimization, such as in
Section 5.1.4 or Section 5.1.5. With either of these two Section 5.1.4 or Section 5.1.5. With either of these two
optimizations, the sender of the packet could only control explicitly optimizations, the sender of the packet could only control explicitly
whether the packet was to be decapsulated on the leaf-BFER in whether the packet was to be decapsulated on the leaf-BFER in
question, if the leaf-BFER has a unique bit position for its question, if the leaf-BFER has a unique bit position for its
local_decap() adjacency. local_decap() adjacency.
However, if the bit position is shared across leaf-BFER, and packets However, if the bit position is shared across leaf-BFER, and packets
are therefore decapsulated potentially unnecessarily, this may still are therefore decapsulated potentially unnecessarily, this may still
be appropriate if the decapsulated payload of the BIER-TE packet does be appropriate if the decapsulated payload of the BIER-TE packet
indicate whether or not the packet needs to be further processed/ indicates whether or not the packet needs to be further processed/
received. This is typically true for example if the payload is IP received. This is typically true for example if the payload is IP
multicast because IP multicast on a BFER would know the membership multicast because IP multicast on a BFER would know the membership
state of the IP multicast payload and be able to discard it if the state of the IP multicast payload and be able to discard it if the
packet was delivered unnecessarily by the BIER-TE layer. If the packet was delivered unnecessarily by the BIER-TE layer. If the
payload has no such membership indication, and the BFIR wants to have payload has no such membership indication, and the BFIR wants to have
explicit control about which BFER are to receive and decapsulate a explicit control about which BFER are to receive and decapsulate a
packet, then these two optimizations can not be used together with packet, then these two optimizations can not be used together with
shared bit positions optimization for leaf-BFER. shared bit positions optimization for leaf-BFER.
5.1.4. LANs 5.1.4. LANs
skipping to change at page 31, line 34 skipping to change at page 29, line 34
position. The adjacency of this bit position is a position. The adjacency of this bit position is a
forward_connected() adjacency towards the BFR and this bit position forward_connected() adjacency towards the BFR and this bit position
is populated into the BIFT of all the other BFRs on that LAN. is populated into the BIFT of all the other BFRs on that LAN.
BFR1 BFR1
|p1 |p1
LAN1-+-+---+-----+ LAN1-+-+---+-----+
p3| p4| p2| p3| p4| p2|
BFR3 BFR4 BFR7 BFR3 BFR4 BFR7
Figure 11: LAN Example Figure 8: LAN Example
If Bandwidth on the LAN is not an issue and most BIER-TE traffic If Bandwidth on the LAN is not an issue and most BIER-TE traffic
should be copied to all neighbors on a LAN, then bit positions can be should be copied to all neighbors on a LAN, then bit positions can be
saved by assigning just a single bit position to the LAN and saved by assigning just a single bit position to the LAN and
populating the bit position of the BIFTs of each BFRs on the LAN with populating the bit position of the BIFTs of each BFRs on the LAN with
a list of forward_connected() adjacencies to all other neighbors on a list of forward_connected() adjacencies to all other neighbors on
the LAN. the LAN.
This optimization does not work in the case of BFRs redundantly This optimization does not work in the case of BFRs redundantly
connected to more than one LAN with this optimization because these connected to more than one LAN with this optimization because these
skipping to change at page 32, line 30 skipping to change at page 30, line 30
optimization can then be used to explicitly steer different traffic optimization can then be used to explicitly steer different traffic
flows across different ECMP paths in Data-Center or broadband- flows across different ECMP paths in Data-Center or broadband-
aggregation networks with minimal use of BPs. aggregation networks with minimal use of BPs.
5.1.6. Rings 5.1.6. Rings
In L3 rings, instead of assigning a single bit position for every p2p In L3 rings, instead of assigning a single bit position for every p2p
link in the ring, it is possible to save bit positions by setting the link in the ring, it is possible to save bit positions by setting the
"DoNotClear" (DNC) flag on forward_connected() adjacencies. "DoNotClear" (DNC) flag on forward_connected() adjacencies.
For the rings shown in Figure 12, a single bit position will suffice For the rings shown in Figure 9, a single bit position will suffice
to forward traffic entering the ring at BFRa or BFRb all the way up to forward traffic entering the ring at BFRa or BFRb all the way up
to BFR1: to BFR1:
On BFRa, BFRb, BFR30,... BFR3, the bit position is populated with a On BFRa, BFRb, BFR30,... BFR3, the bit position is populated with a
forward_connected() adjacency pointing to the clockwise neighbor on forward_connected() adjacency pointing to the clockwise neighbor on
the ring and with DNC set. On BFR2, the adjacency also points to the the ring and with DNC set. On BFR2, the adjacency also points to the
clockwise neighbor BFR1, but without DNC set. clockwise neighbor BFR1, but without DNC set.
Handling DNC this way ensures that copies forwarded from any BFR in Handling DNC this way ensures that copies forwarded from any BFR in
the ring to a BFR outside the ring will not have the ring bit the ring to a BFR outside the ring will not have the ring bit
skipping to change at page 33, line 4 skipping to change at page 31, line 4
v v v v
| | | |
L1 | L2 | L3 L1 | L2 | L3
/-------- BFRa ---- BFRb --------------------\ /-------- BFRa ---- BFRb --------------------\
| | | |
\- BFR1 - BFR2 - BFR3 - ... - BFR29 - BFR30 -/ \- BFR1 - BFR2 - BFR3 - ... - BFR29 - BFR30 -/
| | L4 | | | | L4 | |
p33| p15| p33| p15|
BFRd BFRc BFRd BFRc
Figure 12: Ring Example Figure 9: Ring Example
Note that this example only permits for packets intended to make it Note that this example only permits for packets intended to make it
all the way around the ring to enter it at BFRa and BFRb, and that all the way around the ring to enter it at BFRa and BFRb, and that
packets will always travel clockwise. If packets should be allowed packets will always travel clockwise. If packets should be allowed
to enter the ring at any ring BFR, then one would have to use two to enter the ring at any ring BFR, then one would have to use two
ring bit positions. One for each direction: clockwise and ring bit positions. One for each direction: clockwise and
counterclockwise. counterclockwise.
Both would be set up to stop rotating on the same link, e.g. L1. Both would be set up to stop rotating on the same link, e.g. L1.
When the ingress ring BFR creates the clockwise copy, it will clear When the ingress ring BFR creates the clockwise copy, it will clear
skipping to change at page 33, line 32 skipping to change at page 31, line 32
[RFC-Editor: A reviewer (Lars Eggert) noted that the infinite "to [RFC-Editor: A reviewer (Lars Eggert) noted that the infinite "to
use" in the following sentence is not correct. The same was also use" in the following sentence is not correct. The same was also
noted for several other similar instances. The following URL seems noted for several other similar instances. The following URL seems
to indicate though that this is a per-case decision, which seems to indicate though that this is a per-case decision, which seems
undefined: https://writingcenter.gmu.edu/guides/choosing-between- undefined: https://writingcenter.gmu.edu/guides/choosing-between-
infinitive-and-gerund-to-do-or-doing. What exactly should be done infinitive-and-gerund-to-do-or-doing. What exactly should be done
about this ?]. about this ?].
An ECMP() adjacency allows to use just one BP to deliver packets to An ECMP() adjacency allows to use just one BP to deliver packets to
one one of N adjacencies instead of one BP for each adjacency. In one of N adjacencies instead of one BP for each adjacency. In the
the common example case Figure 13, a link-bundle of three links common example case Figure 10, a link-bundle of three links L1,L2,L3
L1,L2,L3 connects BFR1 and BFR2, and only one BP is used instead of connects BFR1 and BFR2, and only one BP is used instead of three BP
three BP to deliver packets from BFR1 to BFR2. to deliver packets from BFR1 to BFR2.
--L1----- --L1-----
BFR1 --L2----- BFR2 BFR1 --L2----- BFR2
--L3----- --L3-----
BIFT entry in BFR1: BIFT entry in BFR1:
------------------------------------------------------------------ ------------------------------------------------------------------
| Index | Adjacencies | | Index | Adjacencies |
================================================================== ==================================================================
| 0:6 | ECMP({forward_connected(L1, BFR2), | | 0:6 | ECMP({forward_connected(L1, BFR2), |
skipping to change at page 34, line 27 skipping to change at page 32, line 27
BIFT entry in BFR2: BIFT entry in BFR2:
------------------------------------------------------------------ ------------------------------------------------------------------
| Index | Adjacencies | | Index | Adjacencies |
================================================================== ==================================================================
| 0:6 | ECMP({forward_connected(L1, BFR1), | | 0:6 | ECMP({forward_connected(L1, BFR1), |
| | forward_connected(L2, BFR1), | | | forward_connected(L2, BFR1), |
| | forward_connected(L3, BFR1)}, seed) | | | forward_connected(L3, BFR1)}, seed) |
------------------------------------------------------------------ ------------------------------------------------------------------
Figure 13: ECMP Example Figure 10: ECMP Example
This document does not standardize any ECMP algorithm because it is This document does not standardize any ECMP algorithm because it is
sufficient for implementations to document their freely chosen ECMP sufficient for implementations to document their freely chosen ECMP
algorithm. Figure 14 shows an example ECMP algorithm, and would algorithm. Figure 11 shows an example ECMP algorithm, and would
double as its documentation: A BIER-TE controller could determine double as its documentation: A BIER-TE controller could determine
which adjacency is chosen based on the seed and adjacencies which adjacency is chosen based on the seed and adjacencies
parameters and the packet entropy. parameters and the packet entropy.
forward(packet, ECMP(adj(0), adj(1),... adj(N-1), seed)): forward(packet, ECMP(adj(0), adj(1),... adj(N-1), seed)):
i = (packet(bier-header-entropy) XOR seed) % N i = (packet(bier-header-entropy) XOR seed) % N
forward packet to adj(i) forward packet to adj(i)
Figure 14: ECMP algorithm Example Figure 11: ECMP algorithm Example
In the following example, all traffic from BFR1 towards BFR10 is In the following example, all traffic from BFR1 towards BFR10 is
intended to be ECMP load split equally across the topology. This intended to be ECMP load split equally across the topology. This
example is not meant as a likely setup, but to illustrate that ECMP example is not meant as a likely setup, but to illustrate that ECMP
can be used to share BPs not only across link bundles, but also can be used to share BPs not only across link bundles, but also
across alternative paths across different transit BFR, and it across alternative paths across different transit BFR, and it
explains the use of the seed parameter. explains the use of the seed parameter.
BFR1 (BFIR) BFR1 (BFIR)
/L11 \L12 /L11 \L12
skipping to change at page 35, line 52 skipping to change at page 33, line 52
BIFT entry in BFR6, BFR7: BIFT entry in BFR6, BFR7:
------------------------------------------------------------------ ------------------------------------------------------------------
| 0:8 | forward_connected(Lxx, BFR9) |xx differs on BFR6/BFR7| | 0:8 | forward_connected(Lxx, BFR9) |xx differs on BFR6/BFR7|
------------------------------------------------------------------ ------------------------------------------------------------------
BIFT entry in BFR8, BFR9: BIFT entry in BFR8, BFR9:
------------------------------------------------------------------ ------------------------------------------------------------------
| 0:9 | forward_connected(Lxx, BFR10) |xx differs on BFR8/BFR9| | 0:9 | forward_connected(Lxx, BFR10) |xx differs on BFR8/BFR9|
------------------------------------------------------------------ ------------------------------------------------------------------
Figure 15: Polarization Example Figure 12: Polarization Example
Note that for the following discussion of ECMP, only the BIFT ECMP Note that for the following discussion of ECMP, only the BIFT ECMP
adjacencies on BFR1, BFR2, BFR3 are relevant. The re-use of BP adjacencies on BFR1, BFR2, BFR3 are relevant. The re-use of BP
across BFR in this example is further explained in Section 5.1.9 across BFR in this example is further explained in Section 5.1.9
below. below.
With the setup of ECMP in the topology above, traffic would not be With the setup of ECMP in the topology above, traffic would not be
equally load-split. Instead, links L22 and L31 would see no traffic equally load-split. Instead, links L22 and L31 would see no traffic
at all: BFR2 will only see traffic from BFR1 for which the ECMP hash at all: BFR2 will only see traffic from BFR1 for which the ECMP hash
in BFR1 selected the first adjacency in the list of 2 adjacencies in BFR1 selected the first adjacency in the list of 2 adjacencies
skipping to change at page 37, line 5 skipping to change at page 35, line 5
............... ...............
...BFR1--... ...--L1-- BFR2... ...BFR1--... ...--L1-- BFR2...
... .Routers. ...--L2--/ ... .Routers. ...--L2--/
...BFR4--... ...--L3-- BFR3... ...BFR4--... ...--L3-- BFR3...
... ...--L4--/ | ... ...--L4--/ |
............... | ............... |
LO LO
Network Area 1 Network Area 1
Figure 16: Forward Routed Adjacencies Example Figure 13: Forward Routed Adjacencies Example
Assume the requirement in Figure 16 is to explicitly steer traffic Assume the requirement in Figure 13 is to explicitly steer traffic
flows that have arrived at BFR1 or BFR4 via a path in the routing flows that have arrived at BFR1 or BFR4 via a path in the routing
underlay "Network Area 1" to one of the following three next underlay "Network Area 1" to one of the following three next
segments: (1) BFR2 via link L1, (2) BFR2 via link L2, or (3) via BFR3 segments: (1) BFR2 via link L1, (2) BFR2 via link L2, or (3) via BFR3
and then nor caring whether the packet is forwarded via L3 or L4. and then nor caring whether the packet is forwarded via L3 or L4.
To enable this, both BFR1 and BFR4 are set up with a forward_routed To enable this, both BFR1 and BFR4 are set up with a forward_routed
adjacency bit position towards an address of BFR2 on link L1, another adjacency bit position towards an address of BFR2 on link L1, another
forward_routed() bit position towards an address of BFR2 on link L2 forward_routed() bit position towards an address of BFR2 on link L2
and a third forward_routed() bit position towards a node address LO and a third forward_routed() bit position towards a node address LO
of BFR3. of BFR3.
skipping to change at page 37, line 46 skipping to change at page 35, line 46
with duplicates or loops that do not also exist when every adjacency with duplicates or loops that do not also exist when every adjacency
has a unique BP. Instead, the challenge when reusing BP is whether has a unique BP. Instead, the challenge when reusing BP is whether
it allows to still achieve the desired Tree Engineering goals. it allows to still achieve the desired Tree Engineering goals.
BP cannot be reused across two BFRs that would need to be passed BP cannot be reused across two BFRs that would need to be passed
sequentially for some path: The first BFR will clear the BP, so those sequentially for some path: The first BFR will clear the BP, so those
paths cannot be built. BP can be set across BFR that would (A) only paths cannot be built. BP can be set across BFR that would (A) only
occur across different paths or (B) across different branches of the occur across different paths or (B) across different branches of the
same tree. same tree.
An example of (A) was given in Figure 15, where BP 0:7, BP 0:8 and BP An example of (A) was given in Figure 12, where BP 0:7, BP 0:8 and BP
0:9 are each reused across multiple BFRs because a single packet/path 0:9 are each reused across multiple BFRs because a single packet/path
would never be able to reach more than one BFR sharing the same BP. would never be able to reach more than one BFR sharing the same BP.
Assume the example was changed: BFR1 has no ECMP() adjacency for BP Assume the example was changed: BFR1 has no ECMP() adjacency for BP
0:6, but instead BP 0:5 with forward_connected() to BFR2 and BP 0:6 0:6, but instead BP 0:5 with forward_connected() to BFR2 and BP 0:6
with forward_connected() to BFR3. Packets with both BP 0:5 and BP with forward_connected() to BFR3. Packets with both BP 0:5 and BP
0:6 would now be able to reach both BFR2 and BFR3 and the still 0:6 would now be able to reach both BFR2 and BFR3 and the still
existing re-use of BP 0:7 between BFR2 and BFR3 is a case of (B) existing re-use of BP 0:7 between BFR2 and BFR3 is a case of (B)
where reuse of BP is perfect because it does not limit the set of where reuse of BP is perfect because it does not limit the set of
useful path choices: useful path choices:
skipping to change at page 38, line 30 skipping to change at page 36, line 30
. Core . . Core .
.................................... ....................................
| / \ / \ | | / \ / \ |
BFR2a BFR2b BFR3a BFR3b BFR6a BFR6b BFR2a BFR2b BFR3a BFR3b BFR6a BFR6b
/-------\ /---------\ /--------\ /-------\ /---------\ /--------\
| area2 | | area3 | ... | area6 | | area2 | | area3 | ... | area6 |
| ring | | ring | | ring | | ring | | ring | | ring |
\-------/ \---------/ \--------/ \-------/ \---------/ \--------/
more BFR more BFR more BFR more BFR more BFR more BFR
Figure 17: Reuse of BP Figure 14: Reuse of BP
Reuse may also save BPs in larger topologies. Consider the topology Reuse may also save BPs in larger topologies. Consider the topology
shown in Figure 17. A BFIR/sender (e.g.: video headend) is attached shown in Figure 14. A BFIR/sender (e.g.: video headend) is attached
to area 1, and area 2...6 contain receivers/BFER. Assume each area to area 1, and area 2...6 contain receivers/BFER. Assume each area
had a distribution ring, each with two BPs to indicate the direction had a distribution ring, each with two BPs to indicate the direction
(as explained before). These two BPs could be reused across the 5 (as explained before). These two BPs could be reused across the 5
areas. Packets would be replicated through other BPs for the Core to areas. Packets would be replicated through other BPs for the Core to
the desired subset of areas, and once a packet copy reaches the ring the desired subset of areas, and once a packet copy reaches the ring
of the area, the two ring BPs come into play. This reuse is a case of the area, the two ring BPs come into play. This reuse is a case
of (B), but it limits the topology choices: Packets can only flow of (B), but it limits the topology choices: Packets can only flow
around the same direction in the rings of all areas. This may or may around the same direction in the rings of all areas. This may or may
not be acceptable based on the desired path steering options: If not be acceptable based on the desired path steering options: If
resilient transmission is the path engineering goal, then it is resilient transmission is the path engineering goal, then it is
skipping to change at page 40, line 23 skipping to change at page 38, line 23
L1 | L2 | L3 L1 | L2 | L3
/-------- BFRa ---- BFRb ---------------------\ /-------- BFRa ---- BFRb ---------------------\
| . | | . |
| ...... Wrong link wiring | | ...... Wrong link wiring |
| . | | . |
\- BFR1 - BFR2 BFR3 - ... - BFR29 - BFR30 -/ \- BFR1 - BFR2 BFR3 - ... - BFR29 - BFR30 -/
| | L4 | | | | L4 | |
p33| p15| p33| p15|
BFRd BFRc BFRd BFRc
Figure 18: Miswired Ring Example Figure 15: Miswired Ring Example
With DNC set, looping can happen. Consider in Figure 18 that link L4 With DNC set, looping can happen. Consider in Figure 15 that link L4
from BFR3 is (inadvertently) plugged into the L1 interface of BFRa from BFR3 is (inadvertently) plugged into the L1 interface of BFRa
(instead of BFR2). This creates a loop where the rings clockwise bit (instead of BFR2). This creates a loop where the rings clockwise bit
position is never cleared for copies of the packets traveling position is never cleared for copies of the packets traveling
clockwise around the ring. clockwise around the ring.
To inhibit looping in the face of such physical misconfiguration, To inhibit looping in the face of such physical misconfiguration,
only forward_connected() adjacencies are permitted to have DNC set, only forward_connected() adjacencies are permitted to have DNC set,
and the link layer port unique unicast destination address of the and the link layer port unique unicast destination address of the
adjacency (e.g. MAC address) protects against closing the loop. adjacency (e.g. MAC address) protects against closing the loop.
Link layers without port unique link layer addresses should not be Link layers without port unique link layer addresses should not be
skipping to change at page 40, line 48 skipping to change at page 38, line 48
5.2.2. Duplicates 5.2.2. Duplicates
BFIR1 BFIR1
/ \ / \
/ p2 \ p3 / p2 \ p3
BFR2 BFR3 BFR2 BFR3
\ p4 / p5 \ p4 / p5
\ / \ /
BFER4 BFER4
Figure 19: Duplicates Example Figure 16: Duplicates Example
Duplicates happen when the graph expressed by a BitString is not a Duplicates happen when the graph expressed by a BitString is not a
tree but redundantly connecting BFRs with each other. In Figure 19, tree but redundantly connecting BFRs with each other. In Figure 16,
a BitString of p2,p3,p4,p5 would result in duplicate packets to a BitString of p2,p3,p4,p5 would result in duplicate packets to
arrive on BFER4. The BIER-TE Controller must therefore ensure to arrive on BFER4. The BIER-TE Controller must therefore ensure to
only create BitStrings that are trees. only create BitStrings that are trees.
When links are incorrectly physically re-connected before the BIER-TE When links are incorrectly physically re-connected before the BIER-TE
Controller updates BitStrings in BFIRs, duplicates can happen. Like Controller updates BitStrings in BFIRs, duplicates can happen. Like
loops, these can be inhibited by link layer addressing in loops, these can be inhibited by link layer addressing in
forward_connected() adjacencies. forward_connected() adjacencies.
If interface or loopback addresses used in forward_routed() If interface or loopback addresses used in forward_routed()
skipping to change at page 45, line 34 skipping to change at page 43, line 34
B. BIER and BIER-TE share the same BFR-id. The BFR-ids are assigned B. BIER and BIER-TE share the same BFR-id. The BFR-ids are assigned
as explained above for BIER-TE and simply reused for BIER. The as explained above for BIER-TE and simply reused for BIER. The
replication efficiency for BIER will be as low as that for BIER-TE in replication efficiency for BIER will be as low as that for BIER-TE in
this approach. this approach.
5.3.6. Example bit allocations 5.3.6. Example bit allocations
5.3.6.1. With BIER 5.3.6.1. With BIER
Consider a network setup with a BSL of 256 for a network topology as Consider a network setup with a BSL of 256 for a network topology as
shown in Figure 20. The network has 6 areas, each with 170 BFERs, shown in Figure 17. The network has 6 areas, each with 170 BFERs,
connecting via a core with 4 (core) BFRs. To address all BFERs with connecting via a core with 4 (core) BFRs. To address all BFERs with
BIER, 4 SIs are required. To send a BIER packet to all BFER in the BIER, 4 SIs are required. To send a BIER packet to all BFER in the
network, 4 copies need to be sent by the BFIR. On the BFIR it does network, 4 copies need to be sent by the BFIR. On the BFIR it does
not make a difference how the BFR-ids are allocated to BFER in the not make a difference how the BFR-ids are allocated to BFER in the
network, but for efficiency further down in the network it does make network, but for efficiency further down in the network it does make
a difference. a difference.
area1 area2 area3 area1 area2 area3
BFR1a BFR1b BFR2a BFR2b BFR3a BFR3b BFR1a BFR1b BFR2a BFR2b BFR3a BFR3b
| \ / \ / | | \ / \ / |
................................ ................................
. Core . . Core .
................................ ................................
| / \ / \ | | / \ / \ |
BFR4a BFR4b BFR5a BFR5b BFR6a BFR6b BFR4a BFR4b BFR5a BFR5b BFR6a BFR6b
area4 area5 area6 area4 area5 area6
Figure 20: Scaling BIER-TE bits by reuse Figure 17: Scaling BIER-TE bits by reuse
With random allocation of BFR-id to BFER, each receiving area would With random allocation of BFR-id to BFER, each receiving area would
(most likely) have to receive all 4 copies of the BIER packet because (most likely) have to receive all 4 copies of the BIER packet because
there would be BFR-id for each of the 4 SIs in each of the areas. there would be BFR-id for each of the 4 SIs in each of the areas.
Only further towards each BFER would this duplication subside - when Only further towards each BFER would this duplication subside - when
each of the 4 trees runs out of branches. each of the 4 trees runs out of branches.
If BFR-ids are allocated intelligently, then all the BFER in an area If BFR-ids are allocated intelligently, then all the BFER in an area
would be given BFR-id with as few as possible different SIs. Each would be given BFR-id with as few as possible different SIs. Each
area would only have to forward one or two packets instead of 4. area would only have to forward one or two packets instead of 4.
skipping to change at page 46, line 48 skipping to change at page 44, line 48
Every time that different sub-topologies have overlap, bits need to Every time that different sub-topologies have overlap, bits need to
be repeated across the BitStrings, increasing the overall amount of be repeated across the BitStrings, increasing the overall amount of
bits required across all BitString/SIs. In the worst case, one bits required across all BitString/SIs. In the worst case, one
assigns random subsets of BFERs to different SIs. This will result assigns random subsets of BFERs to different SIs. This will result
in an outcome much worse than in (non-TE) BIER: It maximizes the in an outcome much worse than in (non-TE) BIER: It maximizes the
amount of unnecessary topology overlap across SI and therefore amount of unnecessary topology overlap across SI and therefore
reduces the number of BFER that can be reached across each individual reduces the number of BFER that can be reached across each individual
SI. Intelligent BFER to SI assignment and selecting specific SI. Intelligent BFER to SI assignment and selecting specific
"desired" subtopologies can minimize this problem. "desired" subtopologies can minimize this problem.
To set up BIER-TE efficiently for the topology of Figure 20, the To set up BIER-TE efficiently for the topology of Figure 17, the
following bit allocation method can be used. This method can easily following bit allocation method can be used. This method can easily
be expanded to other, similarly structured larger topologies. be expanded to other, similarly structured larger topologies.
Each area is allocated one or more SIs depending on the number of Each area is allocated one or more SIs depending on the number of
future expected BFERs and number of bits required for the topology in future expected BFERs and number of bits required for the topology in
the area. In this example, 6 SIs, one per area. the area. In this example, 6 SIs, one per area.
In addition, we use 4 bits in each SI: bia, bib, bea, beb: (b)it In addition, we use 4 bits in each SI: bia, bib, bea, beb: (b)it
(i)ngress (a), (b)it (i)ngress (b), (b)it (e)gress (a), (b)it (i)ngress (a), (b)it (i)ngress (b), (b)it (e)gress (a), (b)it
(e)gress (b). These bits will be used to pass BIER packets from any (e)gress (b). These bits will be used to pass BIER packets from any
skipping to change at page 50, line 12 skipping to change at page 48, line 12
Benjamin Kaduk (SEC), Tommy Pauly (TSV), Zaheduzzaman Sarker (TSV), Benjamin Kaduk (SEC), Tommy Pauly (TSV), Zaheduzzaman Sarker (TSV),
Eric Vyncke (INT), Martin Vigoureux (RTG), Robert Wilton (OPS), Eric Eric Vyncke (INT), Martin Vigoureux (RTG), Robert Wilton (OPS), Eric
Kline (INT), Lars Eggert (GEN), Roman Danyliv (SEC), Ines Robles Kline (INT), Lars Eggert (GEN), Roman Danyliv (SEC), Ines Robles
(RTGDIR), Robert Sparks (Gen-ART), Yingzhen Qu (RTGdir), Martin Duke (RTGDIR), Robert Sparks (Gen-ART), Yingzhen Qu (RTGdir), Martin Duke
(TSV). (TSV).
9. Change log [RFC Editor: Please remove] 9. Change log [RFC Editor: Please remove]
draft-ietf-bier-te-arch: draft-ietf-bier-te-arch:
13:
Changed Gregs author association/email.
Fixed Nits in -12 from Ben Kaduk.
Fixed Alvaro's concerns: (1) Removed references to SR in Abstract/
Overview (2) removed section 4.5.
12: 12:
AD review Alvaro Retana. AD review Alvaro Retana.
Various textual/editorial nits including adding () to all Various textual/editorial nits including adding () to all
instances of forwarding adjacency name instances. instances of forwarding adjacency name instances.
3.1 Added new paragraph outlining possible use of BGP as RR in 3.1 Added new paragraph outlining possible use of BGP as RR in
BIER-TE controller as core of multicast flow overlay component of BIER-TE controller as core of multicast flow overlay component of
BIER-TE. BIER-TE.
skipping to change at page 64, line 15 skipping to change at page 62, line 34
[I-D.ietf-roll-ccast] [I-D.ietf-roll-ccast]
Bergmann, O., Bormann, C., Gerdes, S., and H. Chen, Bergmann, O., Bormann, C., Gerdes, S., and H. Chen,
"Constrained-Cast: Source-Routed Multicast for RPL", Work "Constrained-Cast: Source-Routed Multicast for RPL", Work
in Progress, Internet-Draft, draft-ietf-roll-ccast-01, 30 in Progress, Internet-Draft, draft-ietf-roll-ccast-01, 30
October 2017, <https://www.ietf.org/archive/id/draft-ietf- October 2017, <https://www.ietf.org/archive/id/draft-ietf-
roll-ccast-01.txt>. roll-ccast-01.txt>.
[I-D.ietf-teas-rfc3272bis] [I-D.ietf-teas-rfc3272bis]
Farrel, A., "Overview and Principles of Internet Traffic Farrel, A., "Overview and Principles of Internet Traffic
Engineering", Work in Progress, Internet-Draft, draft- Engineering", Work in Progress, Internet-Draft, draft-
ietf-teas-rfc3272bis-13, 8 November 2021, ietf-teas-rfc3272bis-16, 24 March 2022,
<https://www.ietf.org/archive/id/draft-ietf-teas- <https://www.ietf.org/archive/id/draft-ietf-teas-
rfc3272bis-13.txt>. rfc3272bis-16.txt>.
[ICC] Reed, M. J., Al-Naday, M., Thomos, N., Trossen, D., [ICC] Reed, M. J., Al-Naday, M., Thomos, N., Trossen, D.,
Petropoulos, G., and S. Spirou, "Stateless multicast Petropoulos, G., and S. Spirou, "Stateless multicast
switching in software defined networks", IEEE switching in software defined networks", IEEE
International Conference on Communications (ICC), Kuala International Conference on Communications (ICC), Kuala
Lumpur, Malaysia, 2016, May 2016, Lumpur, Malaysia, 2016, May 2016,
<https://ieeexplore.ieee.org/document/7511036>. <https://ieeexplore.ieee.org/document/7511036>.
[RCSD94] Zhang, H. and D. Domenico, "Rate-Controlled Service [RCSD94] Zhang, H. and D. Domenico, "Rate-Controlled Service
Disciplines", Journal of High-Speed Networks, 1994, May Disciplines", Journal of High-Speed Networks, 1994, May
skipping to change at page 66, line 21 skipping to change at page 64, line 37
Przygienda, T., Zhang, J., and S. Aldrin, "OSPFv2 Przygienda, T., Zhang, J., and S. Aldrin, "OSPFv2
Extensions for Bit Index Explicit Replication (BIER)", Extensions for Bit Index Explicit Replication (BIER)",
RFC 8444, DOI 10.17487/RFC8444, November 2018, RFC 8444, DOI 10.17487/RFC8444, November 2018,
<https://www.rfc-editor.org/info/rfc8444>. <https://www.rfc-editor.org/info/rfc8444>.
[RFC8556] Rosen, E., Ed., Sivakumar, M., Przygienda, T., Aldrin, S., [RFC8556] Rosen, E., Ed., Sivakumar, M., Przygienda, T., Aldrin, S.,
and A. Dolganow, "Multicast VPN Using Bit Index Explicit and A. Dolganow, "Multicast VPN Using Bit Index Explicit
Replication (BIER)", RFC 8556, DOI 10.17487/RFC8556, April Replication (BIER)", RFC 8556, DOI 10.17487/RFC8556, April
2019, <https://www.rfc-editor.org/info/rfc8556>. 2019, <https://www.rfc-editor.org/info/rfc8556>.
Appendix A. BIER-TE and Segment Routing Appendix A. BIER-TE and Segment Routing (SR)
SR (xref target="RFC8402"/>) aims to enable lightweight path steering SR ([RFC8402]) aims to enable lightweight path steering via loose
via loose source routing. Compared to its more heavy-weight source routing. Compared to its more heavy-weight predecessor RSVP-
predecessor RSVP-TE, SR does for example not require per-path TE, SR does for example not require per-path signaling to each of
signaling to each of these hops. these hops.
BIER-TE supports the same design philosophy for multicast. Like in BIER-TE supports the same design philosophy for multicast. Like in
SR, it relies on source-routing - via the definition of a BitString. SR, it relies on source-routing - via the definition of a BitString.
Like SR, it only requires to consider the "hops" on which either Like SR, it only requires to consider the "hops" on which either
replication has to happen, or across which the traffic should be replication has to happen, or across which the traffic should be
steered (even without replication). Any other hops can be skipped steered (even without replication). Any other hops can be skipped
via the use of routed adjacencies. via the use of routed adjacencies.
BIER-TE bit position (BP) can be understood as the BIER-TE equivalent BIER-TE bit position (BP) can be understood as the BIER-TE equivalent
of "forwarding segments" in SR, but they have a different scope than of "forwarding segments" in SR, but they have a different scope than
skipping to change at page 67, line 27 skipping to change at page 65, line 42
indicate a sequence of SID to reach the destination. This is what indicate a sequence of SID to reach the destination. This is what
BIER-TE and its adjacency scoped BP enables. BIER-TE and its adjacency scoped BP enables.
Authors' Addresses Authors' Addresses
Toerless Eckert (editor) Toerless Eckert (editor)
Futurewei Technologies Inc. Futurewei Technologies Inc.
2330 Central Expy 2330 Central Expy
Santa Clara, 95050 Santa Clara, 95050
United States of America United States of America
Email: tte+ietf@cs.fau.de Email: tte+ietf@cs.fau.de
Michael Menth Michael Menth
University of Tuebingen University of Tuebingen
Email: menth@uni-tuebingen.de Email: menth@uni-tuebingen.de
Gregory Cauchie Gregory Cauchie
Bouygues Telecom KOEVOO
Email: gregory@koevoo.tech
Email: GCAUCHIE@bouyguestelecom.fr
 End of changes. 46 change blocks. 
190 lines changed or deleted 92 lines changed or added

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