< draft-ietf-bier-te-arch-03.txt   draft-ietf-bier-te-arch-04.txt >
Network Working Group T. Eckert, Ed. Network Working Group T. Eckert, Ed.
Internet-Draft Huawei Internet-Draft Futurewei
Intended status: Standards Track G. Cauchie Intended status: Standards Track G. Cauchie
Expires: January 9, 2020 Bouygues Telecom Expires: April 24, 2020 Bouygues Telecom
M. Menth M. Menth
University of Tuebingen University of Tuebingen
July 8, 2019 October 22, 2019
Traffic Engineering for Bit Index Explicit Replication (BIER-TE) Traffic Engineering for Bit Index Explicit Replication (BIER-TE)
draft-ietf-bier-te-arch-03 draft-ietf-bier-te-arch-04
Abstract Abstract
This memo introduces per-packet stateless strict and loose path This memo introduces per-packet stateless strict and loose path
engineered replication and forwarding for Bit Index Explicit engineered replication and forwarding for Bit Index Explicit
Replication packets ([RFC8279]). This is called BIER-TE. Replication packets ([RFC8279]). This is called BIER-TE.
BIER-TE leverages the BIER architecture ([RFC8279]) and extends it BIER-TE leverages the BIER architecture ([RFC8279]) and extends it
with a new semantic for bits in the bitstring. BIER-TE can leverage with a new semantic for bits in the bitstring. BIER-TE can leverage
BIER forwarding engines with little or no changes. BIER forwarding engines with little or no changes.
skipping to change at page 1, line 36 skipping to change at page 1, line 36
Routing Underlay such as an IGP. Routing Underlay such as an IGP.
In BIER-TE, BitPositions indicate adjacencies. The BIFT of each BFR In BIER-TE, BitPositions indicate adjacencies. The BIFT of each BFR
are only populated with BPs that are adjacent to the BFR in the BIER- are only populated with BPs that are adjacent to the BFR in the BIER-
TE topology. The BIER-TE topology can consist of layer 2 or remote TE topology. The BIER-TE topology can consist of layer 2 or remote
(route) adjacencies. The BFR then replicates and forwards BIER (route) adjacencies. The BFR then replicates and forwards BIER
packets to those adjacencies. This results in the aforementioned packets to those adjacencies. This results in the aforementioned
strict and loose path forwarding. strict and loose path forwarding.
BIER-TE can co-exist with BIER forwarding in the same domain, for BIER-TE can co-exist with BIER forwarding in the same domain, for
example by using seperate sub-domains. In the absence of routed example by using separate sub-domains. In the absence of routed
adjacencies, BIER-TE does not require a BIER routing underlay, and adjacencies, BIER-TE does not require a BIER routing underlay, and
can then be operated without requiring an IGP routing protocol. can then be operated without requiring an IGP routing protocol.
BIER-TE operates without explicit in-network tree-building and BIER-TE operates without explicit in-network tree-building and
carries the multicast distribution tree in the packet header. It can carries the multicast distribution tree in the packet header. It can
therefore be a good fit to support multicast path steering in Segment therefore be a good fit to support multicast path steering in Segment
Routing (SR) networks. Routing (SR) networks.
Status of This Memo Status of This Memo
skipping to change at page 2, line 15 skipping to change at page 2, line 15
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 January 9, 2020. This Internet-Draft will expire on April 24, 2020.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 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
(https://trustee.ietf.org/license-info) in effect on the date of (https://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
skipping to change at page 2, line 39 skipping to change at page 2, line 39
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
1.1. Basic Examples . . . . . . . . . . . . . . . . . . . . . 4 1.1. Basic Examples . . . . . . . . . . . . . . . . . . . . . 4
1.2. BIER-TE Topology and adjacencies . . . . . . . . . . . . 7 1.2. BIER-TE Topology and adjacencies . . . . . . . . . . . . 7
1.3. Comparison with BIER . . . . . . . . . . . . . . . . . . 8 1.3. Comparison with BIER . . . . . . . . . . . . . . . . . . 8
1.4. Requirements Language . . . . . . . . . . . . . . . . . . 8 1.4. Requirements Language . . . . . . . . . . . . . . . . . . 8
2. Layering . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2. Components . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1. The Multicast Flow Overlay . . . . . . . . . . . . . . . 9 2.1. The Multicast Flow Overlay . . . . . . . . . . . . . . . 9
2.2. The BIER-TE Controller Host . . . . . . . . . . . . . . . 9 2.2. The BIER-TE Controller Host . . . . . . . . . . . . . . . 9
2.2.1. Assignment of BitPositions to adjacencies of the 2.2.1. Assignment of BitPositions to adjacencies of the
network topology . . . . . . . . . . . . . . . . . . 10 network topology . . . . . . . . . . . . . . . . . . 10
2.2.2. Changes in the network topology . . . . . . . . . . . 10 2.2.2. Changes in the network topology . . . . . . . . . . . 10
2.2.3. Set up per-multicast flow BIER-TE state . . . . . . . 10 2.2.3. Set up per-multicast flow BIER-TE state . . . . . . . 10
2.2.4. Link/Node Failures and Recovery . . . . . . . . . . . 10 2.2.4. Link/Node Failures and Recovery . . . . . . . . . . . 11
2.3. The BIER-TE Forwarding Layer . . . . . . . . . . . . . . 11 2.3. The BIER-TE Forwarding Layer . . . . . . . . . . . . . . 11
2.4. The Routing Underlay . . . . . . . . . . . . . . . . . . 11 2.4. The Routing Underlay . . . . . . . . . . . . . . . . . . 11
3. BIER-TE Forwarding . . . . . . . . . . . . . . . . . . . . . 11 3. BIER-TE Forwarding . . . . . . . . . . . . . . . . . . . . . 11
3.1. The Bit Index Forwarding Table (BIFT) . . . . . . . . . . 11 3.1. The Bit Index Forwarding Table (BIFT) . . . . . . . . . . 11
3.2. Adjacency Types . . . . . . . . . . . . . . . . . . . . . 12 3.2. Adjacency Types . . . . . . . . . . . . . . . . . . . . . 13
3.2.1. Forward Connected . . . . . . . . . . . . . . . . . . 12 3.2.1. Forward Connected . . . . . . . . . . . . . . . . . . 13
3.2.2. Forward Routed . . . . . . . . . . . . . . . . . . . 13 3.2.2. Forward Routed . . . . . . . . . . . . . . . . . . . 13
3.2.3. ECMP . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.3. ECMP . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.4. Local Decap . . . . . . . . . . . . . . . . . . . . . 13 3.2.4. Local Decap . . . . . . . . . . . . . . . . . . . . . 14
3.3. Encapsulation considerations . . . . . . . . . . . . . . 14 3.3. Encapsulation considerations . . . . . . . . . . . . . . 14
3.4. Basic BIER-TE Forwarding Example . . . . . . . . . . . . 14 3.4. Basic BIER-TE Forwarding Example . . . . . . . . . . . . 14
3.5. Forwarding comparison with BIER . . . . . . . . . . . . . 16 3.5. Forwarding comparison with BIER . . . . . . . . . . . . . 17
3.6. Requirements . . . . . . . . . . . . . . . . . . . . . . 17 3.6. Requirements . . . . . . . . . . . . . . . . . . . . . . 17
4. BIER-TE Controller Host BitPosition Assignments . . . . . . . 17 4. BIER-TE Controller Host BitPosition Assignments . . . . . . . 18
4.1. P2P Links . . . . . . . . . . . . . . . . . . . . . . . . 18 4.1. P2P Links . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2. BFER . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2. BFER . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3. Leaf BFERs . . . . . . . . . . . . . . . . . . . . . . . 18 4.3. Leaf BFERs . . . . . . . . . . . . . . . . . . . . . . . 18
4.4. LANs . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.4. LANs . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.5. Hub and Spoke . . . . . . . . . . . . . . . . . . . . . . 19 4.5. Hub and Spoke . . . . . . . . . . . . . . . . . . . . . . 19
4.6. Rings . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.6. Rings . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.7. Equal Cost MultiPath (ECMP) . . . . . . . . . . . . . . . 20 4.7. Equal Cost MultiPath (ECMP) . . . . . . . . . . . . . . . 20
4.8. Routed adjacencies . . . . . . . . . . . . . . . . . . . 23 4.8. Routed adjacencies . . . . . . . . . . . . . . . . . . . 23
4.8.1. Reducing BitPositions . . . . . . . . . . . . . . . . 23 4.8.1. Reducing BitPositions . . . . . . . . . . . . . . . . 23
4.8.2. Supporting nodes without BIER-TE . . . . . . . . . . 23 4.8.2. Supporting nodes without BIER-TE . . . . . . . . . . 23
5. Avoiding loops and duplicates . . . . . . . . . . . . . . . . 23 5. Avoiding loops and duplicates . . . . . . . . . . . . . . . . 24
5.1. Loops . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.1. Loops . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.2. Duplicates . . . . . . . . . . . . . . . . . . . . . . . 24 5.2. Duplicates . . . . . . . . . . . . . . . . . . . . . . . 24
6. BIER-TE Forwarding Pseudocode . . . . . . . . . . . . . . . . 24 6. BIER-TE Forwarding Pseudocode . . . . . . . . . . . . . . . . 24
7. Managing SI, subdomains and BFR-ids . . . . . . . . . . . . . 27 7. Managing SI, subdomains and BFR-ids . . . . . . . . . . . . . 27
7.1. Why SI and sub-domains . . . . . . . . . . . . . . . . . 28 7.1. Why SI and sub-domains . . . . . . . . . . . . . . . . . 28
7.2. Bit assignment comparison BIER and BIER-TE . . . . . . . 29 7.2. Bit assignment comparison BIER and BIER-TE . . . . . . . 29
7.3. Using BFR-id with BIER-TE . . . . . . . . . . . . . . . . 29 7.3. Using BFR-id with BIER-TE . . . . . . . . . . . . . . . . 29
7.4. Assigning BFR-ids for BIER-TE . . . . . . . . . . . . . . 30 7.4. Assigning BFR-ids for BIER-TE . . . . . . . . . . . . . . 30
7.5. Example bit allocations . . . . . . . . . . . . . . . . . 31 7.5. Example bit allocations . . . . . . . . . . . . . . . . . 31
7.5.1. With BIER . . . . . . . . . . . . . . . . . . . . . . 31 7.5.1. With BIER . . . . . . . . . . . . . . . . . . . . . . 31
7.5.2. With BIER-TE . . . . . . . . . . . . . . . . . . . . 32 7.5.2. With BIER-TE . . . . . . . . . . . . . . . . . . . . 32
7.6. Summary . . . . . . . . . . . . . . . . . . . . . . . . . 33 7.6. Summary . . . . . . . . . . . . . . . . . . . . . . . . . 33
8. BIER-TE and Segment Routing (SR) . . . . . . . . . . . . . . 33 8. BIER-TE and Segment Routing (SR) . . . . . . . . . . . . . . 33
9. Security Considerations . . . . . . . . . . . . . . . . . . . 34 9. Security Considerations . . . . . . . . . . . . . . . . . . . 34
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 34 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 35
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 34 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 35
12. Change log [RFC Editor: Please remove] . . . . . . . . . . . 35 12. Change log [RFC Editor: Please remove] . . . . . . . . . . . 35
13. References . . . . . . . . . . . . . . . . . . . . . . . . . 38 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 39
13.1. Normative References . . . . . . . . . . . . . . . . . . 38 13.1. Normative References . . . . . . . . . . . . . . . . . . 39
13.2. Informative References . . . . . . . . . . . . . . . . . 38 13.2. Informative References . . . . . . . . . . . . . . . . . 39
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 38 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 40
1. Introduction 1. Introduction
BIER-TE shares architecture, terminology and packet formats with BIER BIER-TE shares architecture, terminology and packet formats with BIER
as described in [RFC8279] and [RFC8296]. This document describes as described in [RFC8279] and [RFC8296]. This document describes
BIER-TE in the expectation that the reader is familiar with these two BIER-TE in the expectation that the reader is familiar with these two
documents. documents.
In BIER-TE, BitPositions (BP) indicate adjacecies. The BIFT of each In BIER-TE, BitPositions (BP) indicate adjacencies. The BIFT of each
BFR is only populated with BP that are adjacent to the BFR in the BFR is only populated with BP that are adjacent to the BFR in the
BIER-TE Topology. Other BPs are left without adjacency. The BFR BIER-TE Topology. Other BPs are left without adjacency. The BFR
replicate and forwards BIER packets to adjacent BPs that are set in replicate and forwards BIER packets to adjacent BPs that are set in
the packet. BPs are normally also reset upon forwarding to avoid the packet. BPs are normally also reset upon forwarding to avoid
duplicates and loops. This is detailled further below. duplicates and loops. This is detailed further below.
Note that related work [ICC], [I-D.ietf-roll-ccast] uses bloom
filters to represent leaves or edges of the intended delivery tree.
Bloom filters can support larger trees with fewer addressing bits,
but they introduce the heuristic risk of false positives and cannot
reset bits in the bitstring during forwarding to avoid loops. For
these reasons, BIER-TE does not use bloom filters, but explicit
bitstrings like BIER.
1.1. Basic Examples 1.1. Basic Examples
BIER-TE forwarding is best introduced with simple examples. BIER-TE forwarding is best introduced with simple examples.
BIER-TE Topology: BIER-TE Topology:
Diagram: Diagram:
p5 p6 p5 p6
skipping to change at page 5, line 44 skipping to change at page 5, line 44
BFR5: p6 -> forward_connected to BFR3 BFR5: p6 -> forward_connected to BFR3
p9 -> forward_connected to BFR4 p9 -> forward_connected to BFR4
p12 -> forward_connected to BFR6 p12 -> forward_connected to BFR6
BFR6: p11 -> forward_connected to BFR5 BFR6: p11 -> forward_connected to BFR5
p12 -> local_decap p12 -> local_decap
Figure 1: BIER-TE basic example Figure 1: BIER-TE basic example
Consider the simple network in the above BIER-TE overview example Consider the simple network in the above BIER-TE overview example
picture with 6 BFR. p1...p14 are the BitPositions (BP) used. All BFR picture with 6 BFRs. p1...p14 are the BitPositions (BP) used. All
can act as ingres BFR (BFIR), BFR1, BFR3, BFR4 and BFR6 can also be BFRs can act as ingress BFR (BFIR), BFR1, BFR3, BFR4 and BFR6 can
egres BFR (BFER). Forward_connected is the name for adjacencies that also be egress BFR (BFER). Forward_connected is the name for
are representing subnet adjacencies of the network. Local_decap is adjacencies that are representing subnet adjacencies of the network.
the name of the adjacency to decapsulate BIER-TE packets and pass Local_decap is the name of the adjacency to decapsulate BIER-TE
their payload to higher layer processing. packets and pass their payload to higher layer processing.
Assume a packet from BFR1 should be sent via BFR4 to BFR6. This Assume a packet from BFR1 should be sent via BFR4 to BFR6. This
requires a bitstring (p2,p8,p10,p12). When this packet is examined requires a bitstring (p2,p8,p10,p12). When this packet is examined
by BIER-TE on BFR1, the only BitPosition from the bitstring that is by BIER-TE on BFR1, the only BitPosition from the bitstring that is
also set in the BIFT is p2. This will cause BFR1 to to send the only also set in the BIFT is p2. This will cause BFR1 to send the only
copy of the packet to BFR2. Similarily, BFR2 will forward to BFR4 copy of the packet to BFR2. Similarly, BFR2 will forward to BFR4
because of p8, BFR4 to BFR5 because of p10 and BFR5 to BFR6 because because of p8, BFR4 to BFR5 because of p10 and BFR5 to BFR6 because
of p12. p12 also makes BFR6 receive and decapsulate the packet. of p12. p12 also makes BFR6 receive and decapsulate the packet.
To send in addition to BFR6 via BFR4 also a copy to BFR3, the To send in addition to BFR6 via BFR4 also a copy to BFR3, the
bitstring needs to be (p2,p5,p8,p10,p12,p13). When this packet is bitstring needs to be (p2,p5,p8,p10,p12,p13). When this packet is
examined by BFR2, p5 causes one copy to be sent to BFR3 and p8 one examined by BFR2, p5 causes one copy to be sent to BFR3 and p8 one
copy to BFR4. When BFR3 receives the packet, p13 will cause it to copy to BFR4. When BFR3 receives the packet, p13 will cause it to
receive and decapsulate the packet. receive and decapsulate the packet.
If instead the bitstring was (p2,p6,p8,p10,p12,p13), the packet would If instead the bitstring was (p2,p6,p8,p10,p12,p13), the packet would
be copied by BFR5 towards BFR3 because p6 instead of BFR2 to BFR5 be copied by BFR5 towards BFR3 because p6 instead of BFR2 to BFR5
because of p6 in the prior casse. This is showing the ability of the because of p6 in the prior case. This is showing the ability of the
shown BIER-TE Topology to make the traffic pass across any possible shown BIER-TE Topology to make the traffic pass across any possible
path and be replicated where desired. path and be replicated where desired.
BIER-TE has various options to minimize BP assignments, many of which BIER-TE has various options to minimize BP assignments, many of which
are based on assumptions about the required multicast traffic paths are based on assumptions about the required multicast traffic paths
and bandwidth consumption in the network. and bandwidth consumption in the network.
The following picture shows a modified example, in which Rtr2 and The following picture shows a modified example, in which Rtr2 and
Rtr5 are assumed not to support BIER-TE, so traffic has to be unicast Rtr5 are assumed not to support BIER-TE, so traffic has to be unicast
encapsulated across them. Unicast tunneling of BIER-TE packets can encapsulated across them. Unicast tunneling of BIER-TE packets can
skipping to change at page 7, line 46 skipping to change at page 7, line 46
(p1,p5). From BFR1 via BFR4 to BFR6 it is (p2,p6). A packet from (p1,p5). From BFR1 via BFR4 to BFR6 it is (p2,p6). A packet from
BFR1 to BFR3,BFR4 and BFR6 can use (p1,p2,p3,p4,p5) or BFR1 to BFR3,BFR4 and BFR6 can use (p1,p2,p3,p4,p5) or
(p1,p2,p3,p4,p6), or via BFR6 (p2,p3,p4,p6,p7) or (p1.p3,p4,p5,p8). (p1,p2,p3,p4,p6), or via BFR6 (p2,p3,p4,p6,p7) or (p1.p3,p4,p5,p8).
1.2. BIER-TE Topology and adjacencies 1.2. BIER-TE Topology and adjacencies
The key new component in BIER-TE to control where replication can or The key new component in BIER-TE to control where replication can or
should happens and how to minimize the required BP for segments is - should happens and how to minimize the required BP for segments is -
as shown in these two examples - the BIER-TE topology. as shown in these two examples - the BIER-TE topology.
The BIER-TE Topology effectively consists of the BIFT of all the the The BIER-TE Topology effectively consists of the BIFT of all the BFR
BFR and can also be expressed in a diagram as a graph where the edges and can also be expressed in a diagram as a graph where the edges are
are the adjacencies between the BFR. Adjacencies are naturally the adjacencies between the BFR. Adjacencies are naturally
unidirectional. BP can be reused across multiple adjacencies as long unidirectional. BP can be reused across multiple adjacencies as long
as this does not lead to undesired duplicates or loops as explained as this does not lead to undesired duplicates or loops as explained
further down in the text. further down in the text.
If the BIER-TE topology represents the underlying (layer 2) topology If the BIER-TE topology represents the underlying (layer 2) topology
of the network, this is called "native" BIER-TE as shown in the first of the network, this is called "native" BIER-TE as shown in the first
example. This can be freely mixed with "overlay" BIER-TE, in example. This can be freely mixed with "overlay" BIER-TE, in
"forward_routed" adjacencies are used. "forward_routed" adjacencies are used.
1.3. Comparison with BIER 1.3. Comparison with BIER
The key differences over BIER are: The key differences over BIER are:
o BIER-TE replaces in-network autonomous path calculation by o BIER-TE replaces in-network autonomous path calculation by
explicit paths calculated offpath by the BIER-TE controller host. explicit paths calculated off-path by the BIER-TE controller host.
o In BIER-TE every BitPosition of the BitString of a BIER-TE packet o In BIER-TE every BitPosition of the BitString of a BIER-TE packet
indicates one or more adjacencies - instead of a BFER as in BIER. indicates one or more adjacencies - instead of a BFER as in BIER.
o BIER-TE in each BFR has no routing table but only a BIER-TE o BIER-TE in each BFR has no routing table but only a BIER-TE
Forwarding Table (BIFT) indexed by SI:BitPosition and populated Forwarding Table (BIFT) indexed by SI:BitPosition and populated
with only those adjacencies to which the BFR should replicate with only those adjacencies to which the BFR should replicate
packets to. packets to.
BIER-TE headers use the same format as BIER headers. BIER-TE headers use the same format as BIER headers.
skipping to change at page 8, line 47 skipping to change at page 8, line 47
values, then the allocation of BFIR-ID values in BIER-TE packets can values, then the allocation of BFIR-ID values in BIER-TE packets can
be done through other mechanisms outside the scope of this document, be done through other mechanisms outside the scope of this document,
as long as this is appropriately agreed upon between all BFIR/BFER. as long as this is appropriately agreed upon between all BFIR/BFER.
1.4. Requirements Language 1.4. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119]. document are to be interpreted as described in RFC 2119 [RFC2119].
2. Layering 2. Components
End to end BIER-TE operations consists of four layers: The "Multicast End to end BIER-TE operations consists of four mayor components: The
Flow Overlay", the "BIER-TE Controller Host", the "Routing Underlay" "Multicast Flow Overlay", the "BIER-TE control plane" consisting of
and the "BIER-TE forwarding layer". The Bier-TE Controller Host is the "BIER-TE Controller Host" and its signaling channels to the BFR,
the new architectural element in BIER-TE compared toBIER . the "Routing Underlay" and the "BIER-TE forwarding layer". The Bier-
TE Controller Host is the new architectural component in BIER-TE
compared to BIER.
Picture 2: Layers of BIER-TE Picture 2: Components of BIER-TE
<------BGP/PIM-----> <------BGP/PIM----->
|<-IGMP/PIM-> multicast flow <-PIM/IGMP->| |<-IGMP/PIM-> multicast flow <-PIM/IGMP->|
overlay overlay
[BIER-TE Controller Host] <=> [BIER-TE Topology] [BIER-TE Controller Host] <=> [BIER-TE Topology]
BIER-TE control plane
^ ^ ^ ^ ^ ^
/ | \ BIER-TE control protocol / | \ BIER-TE control protocol
| | | eg.: Netconf/Restconf/Yang | | | e.g. Netconf/Restconf/Yang
v v v v v v
Src -> Rtr1 -> BFIR-----BFR-----BFER -> Rtr2 -> Rcvr Src -> Rtr1 -> BFIR-----BFR-----BFER -> Rtr2 -> Rcvr
|--------------------->| |<----------------->|
BIER-TE forwarding layer BIER-TE forwarding layer
|<- BIER-TE domain-->| |<- BIER-TE domain->|
|<--------------------->| |<--------------------->|
Routing underlay Routing underlay
Figure 3: BIER-TE architecture Figure 3: BIER-TE architecture
2.1. The Multicast Flow Overlay 2.1. The Multicast Flow Overlay
The Multicast Flow Overlay operates as in BIER. See [RFC8279]. The Multicast Flow Overlay operates as in BIER. See [RFC8279].
Instead of interacting with the BIER forwarding layer layer (as in Instead of interacting with the BIER forwarding layer (as in BIER),
BIER), it interacts with the BIER-TE Controller Host. it interacts with the BIER-TE Controller Host.
2.2. The BIER-TE Controller Host 2.2. The BIER-TE Controller Host
The BIER-TE controller host is representing the control plane of The BIER-TE controller host is representing the control plane of
BIER-TE. It communicates two sets of information with BFRs: BIER-TE. It communicates two sets of information with BFRs:
During bring-up or modifications of the network topology, the During initial provisioning or modifications of the network topology,
controller discovers the network topology and creates the BIER-TE the controller discovers the network topology and creates the BIER-TE
topology from it: determine which adjacencies are required/desired topology from it: determine which adjacencies are required/desired
and assign BitPositions to them. Then it signals the resulting of and assign BitPositions to them. Then it signals the resulting of
BitPositions and their adjacencies to each BFR to set up their BIER- BitPositions and their adjacencies to each BFR to set up their BIER-
TE BIFTs. TE BIFTs.
During day-to-day operations of the network, the controller signals During day-to-day operations of the network, the controller signals
to BFIRs what multicast flows are mapped to what BitStrings. to BFIRs what multicast flows are mapped to what BitStrings.
Communications between the BIER-TE controller host to BFRs is ideally Communications between the BIER-TE controller host to BFRs is ideally
via standardized protocols and data-models such as Netconf/Retconf/ via standardized protocols and data-models such as Netconf/Restconf/
Yang. This is currently outside the scope of this document. Vendor- Yang. This is currently outside the scope of this document. Vendor-
specific CLI on the BFRs is also a possible stopgap option (as in specific CLI on the BFRs is also a possible stopgap option (as in
many other SDN solutions lacking definition of standardized data many other SDN solutions lacking definition of standardized data
model). model).
For simplicity, the procedures of the BIER-TE controller host are For simplicity, the procedures of the BIER-TE controller host are
described in this document as if it is a single, centralized described in this document as if it is a single, centralized
automated entity, such as an SDN controller. It could equally be an automated entity, such as an SDN controller. It could equally be an
operator setting up CLI on the BFRs. Distribution of the functions operator setting up CLI on the BFRs. Distribution of the functions
of the BIER-TE controller host is currently outside the scope of this of the BIER-TE controller host is currently outside the scope of this
skipping to change at page 10, line 39 skipping to change at page 10, line 43
If the network topology changes (not failure based) so that If the network topology changes (not failure based) so that
adjacencies that are assigned to BitPositions are no longer needed, adjacencies that are assigned to BitPositions are no longer needed,
the controller can re-use those BitPositions for new adjacencies. the controller can re-use those BitPositions for new adjacencies.
First, these BitPositions need to be removed from any BFIR flow state First, these BitPositions need to be removed from any BFIR flow state
and BFR BIFT state, then they can be repopulated, first into BIFT and and BFR BIFT state, then they can be repopulated, first into BIFT and
then into the BFIR. then into the BFIR.
2.2.3. Set up per-multicast flow BIER-TE state 2.2.3. Set up per-multicast flow BIER-TE state
The BIER-TE controller host tracks the multicast flow overlay to The BIER-TE controller host interacts with the multicast flow overlay
determine what multicast flow needs to be sent by a BFIR to which set to determine what multicast flow needs to be sent by a BFIR to which
of BFER. It calculates the desired distribution tree across the set of BFER. It calculates the desired distribution tree across the
BIER-TE domain based on algorithms outside the scope of this document BIER-TE domain based on algorithms outside the scope of this document
(eg.: CSFP, Steiner Tree,...). It then pushes the calculated (e.g. CSFP, Steiner Tree, ...). It then pushes the calculated
BitString into the BFIR. BitString into the BFIR.
See [I-D.ietf-bier-multicast-http-response] for a solution describing
this interaction.
2.2.4. Link/Node Failures and Recovery 2.2.4. Link/Node Failures and Recovery
When link or nodes fail or recover in the topology, BIER-TE can When link or nodes fail or recover in the topology, BIER-TE can
quickly respond with the optional FRR procedures described in [I- quickly respond with the optional FRR procedures described in [I-
D.eckert-bier-te-frr]. It can also more slowly react by D.eckert-bier-te-frr]. It can also more slowly react by
recalculating the BitStrings of affected multicast flows. This recalculating the BitStrings of affected multicast flows. This
reaction is slower than the FRR procedure because the controller reaction is slower than the FRR procedure because the controller
needs to receive link/node up/down indications, recalculate the needs to receive link/node up/down indications, recalculate the
desired BitStrings and push them down into the BFIRs. With FRR, this desired BitStrings and push them down into the BFIRs. With FRR, this
is all performed locally on a BFR receiving the adjacency up/down is all performed locally on a BFR receiving the adjacency up/down
notification. notification.
2.3. The BIER-TE Forwarding Layer 2.3. The BIER-TE Forwarding Layer
When the BIER-TE Forwarding Layer receives a packet, it simply looks When the BIER-TE Forwarding Layer receives a packet, it simply looks
up the BitPositions that are set in the BitString of the packet in up the BitPositions that are set in the BitString of the packet in
the Bit Index Forwarding Table (BIFT) that was populated by the BIER- the Bit Index Forwarding Table (BIFT) that was populated by the BIER-
TE controller host. For every BP that is set in the BitString, and TE controller host. For every BP that is set in the BitString, and
that has one or more adjacencies in the BIFT, a copy is made that has one or more adjacencies in the BIFT, a copy is made
according to the type of adjacencies for that BP in the BIFT. Before according to the type of adjacencies for that BP in the BIFT. Before
sending any copy, the BFR resets all BitPositions in the BitString of sending any copy, the BFR resets all BP in the BitString of the
the packet to which it can create a copy. This is done to inhibit packet for which the BFR has one or more adjacencies in the BIFT,
that packets can loop. except when the adjacency indicates "DoNotReset" (DNR, see
Section 3.2.1). This is done to inhibit that packets can loop.
2.4. The Routing Underlay 2.4. The Routing Underlay
BIER-TE is sending BIER packets to directly connected BIER-TE BIER-TE is sending BIER packets to directly connected BIER-TE
neighbors as L2 (unicasted) BIER packets without requiring a routing neighbors as L2 (unicasted) BIER packets without requiring a routing
underlay. BIER-TE forwarding uses the Routing underlay for underlay. BIER-TE forwarding uses the Routing underlay for
forward_routed adjacencies which copy BIER-TE packets to not- forward_routed adjacencies which copy BIER-TE packets to not-
directly-connected BFRs (see below for adjacency definitions). directly-connected BFRs (see below for adjacency definitions).
If the BFR intends to support FRR for BIER-TE, then the BIER-TE If the BFR intends to support FRR for BIER-TE, then the BIER-TE
forwarding plane needs to receive fast adjacency up/down forwarding plane needs to receive fast adjacency up/down
notifications: Link up/down or neighbor up/down, eg.: from BFD. notifications: Link up/down or neighbor up/down, e.g. from BFD.
Providing these notifications is considered to be part of the routing Providing these notifications is considered to be part of the routing
underlay in this document. underlay in this document.
3. BIER-TE Forwarding 3. BIER-TE Forwarding
3.1. The Bit Index Forwarding Table (BIFT) 3.1. The Bit Index Forwarding Table (BIFT)
The Bit Index Forwarding Table (BIFT) exists in every BFR. For every The Bit Index Forwarding Table (BIFT) exists in every BFR. For every
subdomain in use, it is a table indexed by SI:BitPosition and is subdomain in use, it is a table indexed by SI:BitPosition and is
populated by the BIER-TE control plane. Each index can be empty or populated by the BIER-TE control plane. Each index can be empty or
skipping to change at page 12, line 41 skipping to change at page 12, line 49
------------------------------------------------------------------ ------------------------------------------------------------------
Bit Index Forwarding Table Bit Index Forwarding Table
Figure 4: BIFT adjacencies Figure 4: BIFT adjacencies
The BIFT is programmed into the data plane of BFRs by the BIER-TE The BIFT is programmed into the data plane of BFRs by the BIER-TE
controller host and used to forward packets, according to the rules controller host and used to forward packets, according to the rules
specified in the BIER-TE Forwarding Procedures. specified in the BIER-TE Forwarding Procedures.
Adjacencies for the same BP when populated in more than one BFR by Adjacencies for the same BP when populated in more than one BFR by
the controller do not have to have the same adjacencies. This is up the controller does not have to have the same adjacencies. This is
to the controller. BPs for p2p links are one case (see below). up to the controller. BPs for p2p links are one case (see below).
3.2. Adjacency Types 3.2. Adjacency Types
3.2.1. Forward Connected 3.2.1. Forward Connected
A "forward_connected" adjacency is towards a directly connected BFR A "forward_connected" adjacency is towards a directly connected BFR
neighbor using an interface address of that BFR on the connecting neighbor using an interface address of that BFR on the connecting
interface. A forward_connected adjacency does not route packets but interface. A forward_connected adjacency does not route packets but
only L2 forwards them to the neighbor. only L2 forwards them to the neighbor.
Packets sent to an adjacency with "DoNotReset" (DNR) set in the BIFT Packets sent to an adjacency with "DoNotReset" (DNR) set in the BIFT
will not have the BitPosition for that adjacency reset when the BFR will not have the BitPosition for that adjacency reset when the BFR
creates a copy for it. The BitPosition will still be reset for creates a copy for it. The BitPosition will still be reset for
copies of the packet made towards other adjacencies. The can be used copies of the packet made towards other adjacencies. This can be
for example in ring topologies as explained below. used for example in ring topologies as explained below.
3.2.2. Forward Routed 3.2.2. Forward Routed
A "forward_routed" adjacency is an adjacency towards a BFR that is A "forward_routed" adjacency is an adjacency towards a BFR that is
not a forward_connected adjacency: towards a loopback address of a not a forward_connected adjacency: towards a loopback address of a
BFR or towards an interface address that is non-directly connected. BFR or towards an interface address that is non-directly connected.
Forward_routed packets are forwarded via the Routing Underlay. Forward_routed packets are forwarded via the Routing Underlay.
If the Routing Underlay has multiple paths for a forward_routed If the Routing Underlay has multiple paths for a forward_routed
adjacency, it will perform ECMP independent of BIER-TE for packets adjacency, it will perform ECMP independent of BIER-TE for packets
forwarded across a forward_routed adjacency. forwarded across a forward_routed adjacency.
If the Routing Underlay has FRR, it will perform FRR independent of If the Routing Underlay has FRR, it will perform FRR independent of
BIER-TE for packets forwarded across a forward_routed adjacency. BIER-TE for packets forwarded across a forward_routed adjacency.
3.2.3. ECMP 3.2.3. ECMP
The ECMP mechanisms in BIER are tied to the BIER BIFT and are are The ECMP mechanisms in BIER are tied to the BIER BIFT and are
therefore not directly useable with BIER-TE. The following therefore not directly useable with BIER-TE. The following
procedures describe ECMP for BIER-TE that we consider to be procedures describe ECMP for BIER-TE that we consider to be
lightweight but also well manageable. It leverages the existing lightweight but also well manageable. It leverages the existing
entropy parameter in the BIER header to keep packets of the flows on entropy parameter in the BIER header to keep packets of the flows on
the same path and it introduces a "seed" parameter to allow the same path and it introduces a "seed" parameter to allow
engineering traffic to be polarized or randomized across multiple engineering traffic to be polarized or randomized across multiple
hops. hops.
An "Equal Cost Multipath" (ECMP) adjacency has a list of two or more An "Equal Cost Multipath" (ECMP) adjacency has a list of two or more
adjacencies included in it. It copies the BIER-TE to one of those adjacencies included in it. It copies the BIER-TE to one of those
skipping to change at page 14, line 36 skipping to change at page 14, line 43
"forward_routed" requires an encapsulation permitting to unicast "forward_routed" requires an encapsulation permitting to unicast
BIER-TE packets to a specific interface address on a target BFR. BIER-TE packets to a specific interface address on a target BFR.
With MPLS encapsulation, this can simply be done via a label stack With MPLS encapsulation, this can simply be done via a label stack
with that addresses label as the top label - followed by the label with that addresses label as the top label - followed by the label
assigned to (SI,subdomain) - and if necessary (see above) BIER-TE. assigned to (SI,subdomain) - and if necessary (see above) BIER-TE.
With non-MPLS encapsulation, some form of IP tunneling (IP in IP, With non-MPLS encapsulation, some form of IP tunneling (IP in IP,
LISP, GRE) would be required. LISP, GRE) would be required.
The encapsulation used for "forward_routed" adjacencies can equally The encapsulation used for "forward_routed" adjacencies can equally
support existing advanced adjacency information such as "loose source support existing advanced adjacency information such as "loose source
routes" via eg: MPLS label stacks or appropriate header extensions routes" via e.g. MPLS label stacks or appropriate header extensions
(eg: for IPv6). (e.g. for IPv6).
3.4. Basic BIER-TE Forwarding Example 3.4. Basic BIER-TE Forwarding Example
[RFC Editor: remove this section.]
THIS SECTION TO BE REMOVED IN RFC BECAUSE IT WAS SUPERCEEDED BY
SECTION 1.1 EXAMPLE - UNLESS REVIEWERS CHIME IN AND EXPRESS DESIRE TO
KEEP THIS ADDITIONAL EXAMPLE SECTION.
Step by step example of basic BIER-TE forwarding. This does not use Step by step example of basic BIER-TE forwarding. This does not use
ECMP or forward_routed adjacencies nor does it try to minimize the ECMP or forward_routed adjacencies nor does it try to minimize the
number of required BitPositions for the topology. number of required BitPositions for the topology.
[Bier-Te Controller Host] [Bier-Te Controller Host]
/ | \ / | \
v v v v v v
| p13 p1 | | p13 p1 |
+- BFIR2 --+ | +- BFIR2 --+ |
skipping to change at page 15, line 33 skipping to change at page 15, line 37
| +-- Rcv2 | +-- Rcv2
| |
LAN3 LAN3
IP |..... BIER-TE network......| IP IP |..... BIER-TE network......| IP
Figure 5: BIER-TE Forwarding Example Figure 5: BIER-TE Forwarding Example
pXX indicate the BitPositions number assigned by the BIER-TE pXX indicate the BitPositions number assigned by the BIER-TE
controller host to adjacencies in the BIER-TE topology. For example, controller host to adjacencies in the BIER-TE topology. For example,
p9 is the adjacency towards BFR9 on the LAN connecting to BFER2. p9 is the adjacency towards BFR5 on the LAN connecting to BFER2.
BIFT BFIR2: BIFT BFIR2:
p13: local_decap() p13: local_decap()
p2: forward_connected(BFR3) p2: forward_connected(BFR3)
BIFT BFR3: BIFT BFR3:
p1: forward_connected(BFIR2) p1: forward_connected(BFIR2)
p7: forward_connected(BFER1) p7: forward_connected(BFER1)
p8: forward_connected(BFR4) p8: forward_connected(BFR4)
BIFT BFER1: BIFT BFER1:
p11: local_decap() p11: local_decap()
p6: forward_connected(BFR3) p6: forward_connected(BFR3)
p8: forward_connected(BFR4) p8: forward_connected(BFR4)
Figure 6: BIER-TE Forwarding Example Adjacencies Figure 6: BIER-TE Forwarding Example Adjacencies
...and so on. ...and so on.
Traffic needs to flow from BFIR2 towards Rcv1, Rcv2. The controller For example, we assume that some multicast traffic seen on LAN1 needs
determines it wants it to pass across the following paths: to be sent via BIER-TE by BFIR2 towards Rcv1 and Rcv2. The
controller determines it wants it to pass this traffic across the
following paths:
-> BFER1 ---------------> Rcv1 -> BFER1 ---------------> Rcv1
BFIR2 -> BFR3 BFIR2 -> BFR3
-> BFR4 -> BFR5 -> BFER2 -> Rcv2 -> BFR4 -> BFR5 -> BFER2 -> Rcv2
Figure 7: BIER-TE Forwarding Example Paths Figure 7: BIER-TE Forwarding Example Paths
These paths equal to the following BitString: p2, p5, p7, p8, p10, These paths equal to the following BitString: p2, p5, p7, p8, p10,
p11, p12. p11, p12.
This BitString is set up in BFIR2. Multicast packets arriving at This BitString is assigned by BFIR2 to the example multicast traffic
BFIR2 from Src are assigned this BitString. received from LAN1.
BFIR2 forwards based on that BitString. It has p2 and p13 populated. Then BFIR2 forwards this multicast traffic with BIER-TE based on that
Only p13 is in BitString which has an adjacency towards BFR3. BFIR2 BitString. The BIFT of BFIR2 has only p2 and p13 populated. Only p2
resets p2 in BitString and sends a copy towards BFR2. is in the BitString and this is an adjacency towards BFR3. BFIR2
therefore resets p2 in the BitString and sends a copy towards BFR2.
BFR3 sees a BitString of p5,p7,p8,p10,p11,p12. It is only interested BFR3 sees a BitString of p5,p7,p8,p10,p11,p12. It is only interested
in p1,p7,p8. It creates a copy of the packet to BFER1 (due to p7) in p1,p7,p8. It creates a copy of the packet to BFER1 (due to p7)
and one to BFR4 (due to p8). It resets p7, p8 before sending. and one to BFR4 (due to p8). It resets p7, p8 before sending.
BFER1 sees a BitString of p5,p10,p11,p12. It is only interested in BFER1 sees a BitString of p5,p10,p11,p12. It is only interested in
p6,p7,p8,p11 and therefore considers only p11. p11 is a "local_decap" p6,p7,p8,p11 and therefore considers only p11. p11 is a "local_decap"
adjacency installed by the BIER-TE controller host because BFER1 adjacency installed by the BIER-TE controller host because BFER1
should pass packets to IP multicast. The local_decap adjacency should pass packets to IP multicast. The local_decap adjacency
instructs BFER1 to create a copy, decapsulate it from the BIER header instructs BFER1 to create a copy, decapsulate it from the BIER header
and pass it on to the NextProtocol, in this example IP multicast. IP and pass it on to the NextProtocol, in this example IP multicast. IP
multicast will then forward the packet out to LAN2 because it did multicast will then forward the packet out to LAN2 because it did
receive PIM or IGMP joins on LAN2 for the traffic. receive PIM or IGMP joins on LAN2 for the traffic.
Further processing of the packet in BFR4, BFR5 and BFER2 accordingly. Further processing of the packet in BFR4, BFR5 and BFER2 accordingly.
3.5. Forwarding comparison with BIER 3.5. Forwarding comparison with BIER
Forwarding of BIER-TE is designed to allow common forwarding hardware Forwarding of BIER-TE is designed to allow common forwarding hardware
with BIER. In fact, one of the main goals of this document is to with BIER. In fact, one of the main goals of this document is to
encourage the building of forwarding hardware that can not only encourage the building of forwarding hardware that cannot only
support BIER, but also BIER-TE - to allow experimentation with BIER- support BIER, but also BIER-TE - to allow experimentation with BIER-
TE and support building of BIER-TE control plane code. TE and support building of BIER-TE control plane code.
The pseudocode in Section 6 shows how existing BIER/BIFT forwarding The pseudocode in Section 6 shows how existing BIER/BIFT forwarding
can be amended to support basic BIER-TE forwarding, by using BIER can be amended to support basic BIER-TE forwarding, by using BIER
BIFT's F-BM. Only the masking of bits due to avoid duplicates must BIFT's F-BM. Only the masking of bits due to avoid duplicates must
be skipped when forwarding is for BIER-TE. be skipped when forwarding is for BIER-TE.
Whether to use BIER or BIER-TE forwarding can simply be a configured Whether to use BIER or BIER-TE forwarding can simply be a configured
choice per subdomain and accordingly be set up by a BIER-TE choice per subdomain and accordingly be set up by a BIER-TE
skipping to change at page 17, line 19 skipping to change at page 17, line 38
adjacency does not leverage the entropy field so that field would be adjacency does not leverage the entropy field so that field would be
unused when BIER-TE forwarding is used. unused when BIER-TE forwarding is used.
3.6. Requirements 3.6. Requirements
Basic BIER-TE forwarding MUST support to configure Subdomains to use Basic BIER-TE forwarding MUST support to configure Subdomains to use
basic BIER-TE forwarding rules (instead of BIER). With basic BIER-TE basic BIER-TE forwarding rules (instead of BIER). With basic BIER-TE
forwarding, every bit MUST support to have zero or one adjacency. It forwarding, every bit MUST support to have zero or one adjacency. It
MUST support the adjacency types forward_connected without DNR flag, MUST support the adjacency types forward_connected without DNR flag,
forward_routed and local_decap. All other BIER-TE forwarding forward_routed and local_decap. All other BIER-TE forwarding
features are optional. This Basic BIER-TE requirements make BIER-TE features are optional. These basic BIER-TE requirements make BIER-TE
forwarding exactly the same as BIER forwarding with the exception of forwarding exactly the same as BIER forwarding with the exception of
skipping the aforementioned F-BM masking on egres. skipping the aforementioned F-BM masking on egress.
BIER-TE forwarding SHOULD support the DNR flag, as this is highly BIER-TE forwarding SHOULD support the DNR flag, as this is highly
useful to save bits in rings (see Section 4.6). useful to save bits in rings (see Section 4.6).
BIER-TE forwarding MAY support more than one djacency on a bit and BIER-TE forwarding MAY support more than one adjacency on a bit and
ECMP adjacencies. The importance of ECMP adjacencies is unclear when ECMP adjacencies. The importance of ECMP adjacencies is unclear when
traffic engineering is used because it may be more desirable to traffic engineering is used because it may be more desirable to
explicitly steer traffic across non-ECMP paths to make per-path explicitly steer traffic across non-ECMP paths to make per-path
traffic calculation easier for controllers. Having more than one traffic calculation easier for controllers. Having more than one
adjacency for a bit allows further savings of bits in hub&spoke adjacency for a bit allows further savings of bits in hub&spoke
scenarios, but unlike rings it is less "natural" to flood traffic scenarios, but unlike rings it is less "natural" to flood traffic
across multuple links unconditional. Both ECMP and multiple across multiple links unconditional. Both ECMP and multiple
adjacencies are forwarding plane features that should be possible to adjacencies are forwarding plane features that should be possible to
support later when needed as they do not impact the basic BIER-TE support later when needed as they do not impact the basic BIER-TE
replication loop. This is true because there is no inter-copy replication loop. This is true because there is no inter-copy
depency through resetting of F-BM as in BIER. dependency through resetting of F-BM as in BIER.
4. BIER-TE Controller Host BitPosition Assignments 4. BIER-TE Controller Host BitPosition Assignments
This section describes how the BIER-TE controller host can use the This section describes how the BIER-TE controller host can use the
different BIER-TE adjacency types to define the BitPositions of a different BIER-TE adjacency types to define the BitPositions of a
BIER-TE domain. BIER-TE domain.
Because the size of the BitString is limiting the size of the BIER-TE Because the size of the BitString is limiting the size of the BIER-TE
domain, many of the options described exist to support larger domain, many of the options described exist to support larger
topologies with fewer BitPositions (4.1, 4.3, 4.4, 4.5, 4.6, 4.7, topologies with fewer BitPositions (4.1, 4.3, 4.4, 4.5, 4.6, 4.7,
skipping to change at page 20, line 23 skipping to change at page 20, line 32
BFRd BFRc BFRd BFRc
Figure 9: Ring Example Figure 9: Ring Example
Note that this example only permits for packets to enter the ring at Note that this example only permits for packets to enter the ring at
BFRa and BFRb, and that packets will always travel clockwise. If BFRa and BFRb, and that packets will always travel clockwise. If
packets should be allowed to enter the ring at any ring BFR, then one packets should be allowed to enter the ring at any ring BFR, then one
would have to use two ring BitPositions. One for clockwise, one for would have to use two ring BitPositions. One for clockwise, one for
counterclockwise. counterclockwise.
Both would be set up to stop rotating on the same link, eg: L1. When Both would be set up to stop rotating on the same link, e.g. L1.
the ingress ring BFR creates the clockwise copy, it will reset the When the ingress ring BFR creates the clockwise copy, it will reset
counterclockwise BitPosition because the DNR bit only applies to the the counterclockwise BitPosition because the DNR bit only applies to
bit for which the replication is done. Likewise for the clockwise the bit for which the replication is done. Likewise for the
BitPosition for the counterclockwise copy. In result, the ring clockwise BitPosition for the counterclockwise copy. In result, the
ingress BFR will send a copy in both directions, serving BFRs on ring ingress BFR will send a copy in both directions, serving BFRs on
either side of the ring up to L1. either side of the ring up to L1.
4.7. Equal Cost MultiPath (ECMP) 4.7. Equal Cost MultiPath (ECMP)
The ECMP adjacency allows to use just one BP per link bundle between The ECMP adjacency allows to use just one BP per link bundle between
two BFRs instead of one BP for each p2p member link of that link two BFRs instead of one BP for each p2p member link of that link
bundle. In the following picture, one BP is used across L1,L2,L3 and bundle. In the following picture, one BP is used across L1,L2,L3 and
BFR1/BFR2 have for the BP BFR1/BFR2 have for the BP
--L1----- --L1-----
BFR1 --L2----- BFR2 BFR1 --L2----- BFR2
skipping to change at page 21, line 24 skipping to change at page 21, line 24
BIFT entry in BFR2: BIFT entry in BFR2:
------------------------------------------------------------------ ------------------------------------------------------------------
| Index | Adjacencies | | Index | Adjacencies |
================================================================== ==================================================================
| 0:6 | ECMP({L1-to-BFR1,L2-to-BFR1,L3-to-BFR1}, seed) | | 0:6 | ECMP({L1-to-BFR1,L2-to-BFR1,L3-to-BFR1}, seed) |
------------------------------------------------------------------ ------------------------------------------------------------------
Figure 10: ECMP Example Figure 10: ECMP Example
This document does not standardize any ECMP algorithm because it is
sufficient for implementations to document their freely chosen ECMP
algorithm. This allows the BIER-TE controller host to calculate ECMP
paths and seeds. The following picture shows an example ECMP
algorithm:
forward(packet, ECMP(adj(0), adj(1),... adj(N-1), seed)):
i = (packet(bier-header-entropy) XOR seed) % N
forward packet to adj(i)
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 mean 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, and it can be used to share BPs not only across link bundles, and it
explains the use of the seed parameter. explains the use of the seed parameter.
BFR1 BFR1
/ \ / \
/L11 \L12 /L11 \L12
BFR2 BFR3 BFR2 BFR3
/ \ / \ / \ / \
/L21 \L22 /L31 \L32 /L21 \L22 /L31 \L32
BFR4 BFR5 BFR6 BFR7 BFR4 BFR5 BFR6 BFR7
\ / \ / \ / \ /
\ / \ / \ / \ /
BFR8 BFR9 BFR8 BFR9
\ / \ /
\ / \ /
BFR10 BFR10
BIFT entry in BFR1: BIFT entry in BFR1:
------------------------------------------------------------------ ------------------------------------------------------------------
| 0:6 | ECMP({L11-to-BFR2,L12-to-BFR3}, seed) | | 0:6 | ECMP({L11-to-BFR2,L12-to-BFR3}, seed1) |
------------------------------------------------------------------ ------------------------------------------------------------------
BIFT entry in BFR2: BIFT entry in BFR2:
------------------------------------------------------------------ ------------------------------------------------------------------
| 0:6 | ECMP({L21-to-BFR4,L22-to-BFR5}, seed) | | 0:6 | ECMP({L21-to-BFR4,L22-to-BFR5}, seed1) |
------------------------------------------------------------------ ------------------------------------------------------------------
BIFT entry in BFR3: BIFT entry in BFR3:
------------------------------------------------------------------ ------------------------------------------------------------------
| 0:6 | ECMP({L31-to-BFR6,L32-to-BFR7}, seed) | | 0:6 | ECMP({L31-to-BFR6,L32-to-BFR7}, seed1) |
------------------------------------------------------------------ ------------------------------------------------------------------
Figure 11: Polarization Example Figure 12: Polarization Example
With the setup of ECMP in above topology, traffic would not be With the setup of ECMP in above topology, 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 a list of 2 adjacencies: link in BFR1 selected the first adjacency in the list of 2 adjacencies
L11-to-BFR2. When forwarding in BFR2 performs again an ECMP with two given as parameters to the ECMP. It is link L11-to-BFR2. BFR2
adjacencies on that subset of traffic, then it will again select the performs again ECMP with two adjacencies on that subset of traffic
first of its two adjacencies to it: L21-to-BFR4. And therefore L22 using the same seed1, and will therefore again select the first of
and BFR5 sees no traffic. its two adjacencies: L21-to-BFR4. And therefore L22 and BFR5 sees no
traffic. Likewise for L31 and BFR6.
To resolve this issue, the ECMP adjacency on BFR1 simply needs to be To resolve this issue, the ECMP adjacency on BFR1 simply needs to be
set up with a different seed than the ECMP adjacencies on BFR2/BFR3 set up with a different seed2 than the ECMP adjacencies on BFR2/BFR3.
ECMP in BFR2 could use the same seed2 to avoid its issue.
This issue is called polarization. It depends on the ECMP hash. It This issue in BFR2/BFR3 is called polarization. It depends on the
is possible to build ECMP that does not have polarization, for ECMP hash. Instead of explicitly setting up different seeds in
example by taking entropy from the actual adjacency members into consecutive BFR in a topology subject to polarization, it is possible
account, but that can make it harder to achieve evenly balanced load- to build ECMP that does not have polarization, for example by taking
splitting on all BFR without making the ECMP hash algorithm entropy from the actual adjacency members into account such as the
potentially too complex for fast forwarding in the BFRs. next-hop identifiers like L11-to-BFR2 and, but that can make it
harder to achieve evenly balanced load-splitting on all BFR without
making the ECMP hash algorithm potentially too complex for fast
forwarding in the BFRs. In addition, these type of polarization free
ECMP algorithms likely make it harder for a BIER-TE controller host
to calculate entropy fields for BIER-TE headers that would flow on
the same or different ECMP paths. With polarizing algorithms, this
is typically easier.
4.8. Routed adjacencies 4.8. Routed adjacencies
4.8.1. Reducing BitPositions 4.8.1. Reducing BitPositions
Routed adjacencies can reduce the number of BitPositions required Routed adjacencies can reduce the number of BitPositions required
when the traffic engineering requirement is not hop-by-hop explicit when the traffic engineering requirement is not hop-by-hop explicit
path selection, but loose-hop selection. path selection, but loose-hop selection.
............... ............... ............... ...............
BFR1--... Redundant ...--L1-- BFR2... Redundant ...--- BFR1--... Redundant ...--L1-- BFR2... Redundant ...---
\--... Network ...--L2--/ ... Network ...--- \--... Network ...--L2--/ ... Network ...---
BFR4--... Segment 1 ...--L3-- BFR3... Segment 2 ...--- BFR4--... Segment 1 ...--L3-- BFR3... Segment 2 ...---
............... ............... ............... ...............
Figure 12: Routed Adjacencies Example Figure 13: Routed Adjacencies Example
Assume the requirement in above network is to explicitly engineer Assume the requirement in above network is to explicitly engineer
paths such that specific traffic flows are passed from segment 1 to paths such that specific traffic flows are passed from segment 1 to
segment 2 via link L1 (or via L2 or via L3). segment 2 via link L1 (or via L2 or via L3).
To achieve this, BFR1 and BFR4 are set up with a forward_routed To achieve this, BFR1 and BFR4 are set up with a forward_routed
adjacency BitPosition towards an address of BFR2 on link L1 (or link adjacency BitPosition towards an address of BFR2 on link L1 (or link
L2 BFR3 via L3). L2 BFR3 via L3).
For paths to be engineered through a specific node BFR2 (or BFR3), For paths to be engineered through a specific node BFR2 (or BFR3),
BFR1 and BFR4 are set up up with a forward_routed adjacency BFR1 and BFR4 are set up with a forward_routed adjacency BitPosition
BitPosition towards a loopback address of BFR2 (or BFR3). towards a loopback address of BFR2 (or BFR3).
4.8.2. Supporting nodes without BIER-TE 4.8.2. Supporting nodes without BIER-TE
Routed adjacencies also enable incremental deployment of BIER-TE. Routed adjacencies also enable incremental deployment of BIER-TE.
Only the nodes through which BIER-TE traffic needs to be steered - Only the nodes through which BIER-TE traffic needs to be steered -
with or without replication - need to support BIER-TE. Where they with or without replication - need to support BIER-TE. Where they
are not directly connected to each other, forward_routed adjacencies are not directly connected to each other, forward_routed adjacencies
are used to pass over non BIER-TE enabled nodes. are used to pass over non BIER-TE enabled nodes.
5. Avoiding loops and duplicates 5. Avoiding loops and duplicates
skipping to change at page 24, line 12 skipping to change at page 24, line 21
adjacencies in the BFR. This inhibits looping of packets. The only adjacencies in the BFR. This inhibits looping of packets. The only
exception are adjacencies with DNR set. exception are adjacencies with DNR set.
With DNR set, looping can happen. Consider in the ring picture that With DNR set, looping can happen. Consider in the ring picture that
link L4 from BFR3 is plugged into the L1 interface of BFRa. This link L4 from BFR3 is plugged into the L1 interface of BFRa. This
creates a loop where the rings clockwise BitPosition is never reset creates a loop where the rings clockwise BitPosition is never reset
for copies of the packets traveling clockwise around the ring. for copies of the packets traveling 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 DNR set, and only forward_connected adjacencies are permitted to have DNR set, and
the link layer destination address of the adjacency (eg.: MAC the link layer destination address of the adjacency (e.g. MAC
address) protects against closing the loop. Link layers without port address) protects against closing the loop. Link layers without port
unique link layer addresses should not used with the DNR flag set. unique link layer addresses should not be used with the DNR flag set.
5.2. Duplicates 5.2. Duplicates
Duplicates happen when the topology of the BitString is not a tree Duplicates happen when the topology of the BitString is not a tree
but redundantly connecting BFRs with each other. The controller must but redundantly connecting BFRs with each other. The controller must
therefore ensure to only create BitStrings that are trees in the therefore ensure to only create BitStrings that are trees in the
topology. topology.
When links are incorrectly physically re-connected before the When links are incorrectly physically re-connected before the
controller updates BitStrings in BFIRs, duplicates can happen. Like controller updates BitStrings in BFIRs, duplicates can happen. Like
skipping to change at page 25, line 22 skipping to change at page 25, line 22
if (!F-BM) continue; if (!F-BM) continue;
BFR-NBR = BIFT[Index+Offset]->BFR-NBR; BFR-NBR = BIFT[Index+Offset]->BFR-NBR;
PacketCopy = Copy(Packet); PacketCopy = Copy(Packet);
PacketCopy->BitString &= F-BM; [2] PacketCopy->BitString &= F-BM; [2]
PacketSend(PacketCopy, BFR-NBR); PacketSend(PacketCopy, BFR-NBR);
// The following must not be done for BIER-TE: // The following must not be done for BIER-TE:
// Packet->BitString &= ~F-BM; [1] // Packet->BitString &= ~F-BM; [1]
} }
} }
Figure 13: Simplified BIER-TE Forwarding Pseudocode Figure 14: Simplified BIER-TE Forwarding Pseudocode
The difference is that in BIER-TE, step [1] must not be performed. The difference is that in BIER-TE, step [1] must not be performed.
In BIER, this step is necessary to avoid duplicates when two or more In BIER, this step is necessary to avoid duplicates when two or more
BFER are reachable via the same neighbor. The F-BM of all those BFER BFER are reachable via the same neighbor. The F-BM of all those BFER
bits will indicate each others bits, and step [1] will reset all bits will indicate each other's bits, and step [1] will reset all
these bits on the first copy made for the first of those BFER bits these bits on the first copy made for the first of those BFER bits
set in the BitString, hence skipping any further copies to that set in the BitString, hence skipping any further copies to that
neighbor. neighbor.
Whereas in BIER, the F-BM of bits toward a specific neighbor contain Whereas in BIER, the F-BM of bits toward a specific neighbor contain
only the bits of those BFER destined to be forwarded across this only the bits of those BFER destined to be forwarded across this
neighbor, in BIER-TE the F-BM for a neighbor needs to have all bits neighbor, in BIER-TE the F-BM for a neighbor needs to have all bits
set except all those bits that are actual (non-empty) adjacencies of set except all those bits that are actual (non-empty) adjacencies of
this BFR. Step [2] will reset those adjacency bits to avoid loops, this BFR. Step [2] will reset those adjacency bits to avoid loops,
but all the other bits that are not adjacencies of this BFR need to but all the other bits that are not adjacencies of this BFR need to
skipping to change at page 26, line 11 skipping to change at page 26, line 11
Eliminating the need to perform [1] also makes processing of bits in Eliminating the need to perform [1] also makes processing of bits in
the BIER-TE bitstring independent of processing other bits, which may the BIER-TE bitstring independent of processing other bits, which may
also simplify forwarding plane implementations. also simplify forwarding plane implementations.
The following pseudocode is comprehensive: The following pseudocode is comprehensive:
o This pseudocode eliminates per-bit F-BM, therefore reducing state o This pseudocode eliminates per-bit F-BM, therefore reducing state
by BitStringLength^2*SI and eliminating the need for per-packet- by BitStringLength^2*SI and eliminating the need for per-packet-
copy masking operation except for adjacencies with DNR flag set: copy masking operation except for adjacencies with DNR flag set:
* AdjacentBits[SI] are bits with a non-empty list of adjcencies. * AdjacentBits[SI] are bits with a non-empty list of adjacencies.
This can be computed whenever the BIER-TE controller host This can be computed whenever the BIER-TE controller host
updates the adjacencies. updates the adjacencies.
* Only the AdjacentBits need to be examined in the loop for * Only the AdjacentBits need to be examined in the loop for
packet copies. packet copies.
* The packets BitString is masked with those AdjacentBits on * The packets BitString is masked with those AdjacentBits on
ingres to avoid packet loopings. ingress to avoid packets looping.
o The code loops over the adjacencies because there may be more than o The code loops over the adjacencies because there may be more than
one adjacency for a bit. one adjacency for a bit.
o When an adjacency has the DNR bit, the bit is set in the packet o When an adjacency has the DNR bit, the bit is set in the packet
copy (to save bits in rings for example). copy (to save bits in rings for example).
o The ECMP adjacency is shown. Its parameters are a o The ECMP adjacency is shown. Its parameters are a
ListOfAdjacencies from which one is picked. ListOfAdjacencies from which one is picked.
skipping to change at page 27, line 37 skipping to change at page 27, line 37
SendToL3(PacketCopy,{VRF,}l3-neighbor); SendToL3(PacketCopy,{VRF,}l3-neighbor);
case local_decap({VRF},neighbor): case local_decap({VRF},neighbor):
DecapBierHeader(PacketCopy); DecapBierHeader(PacketCopy);
PassTo(PacketCopy,{VRF,}Packet->NextProto); PassTo(PacketCopy,{VRF,}Packet->NextProto);
} }
} }
} }
} }
Figure 14: BIER-TE Forwarding Pseudocode Figure 15: BIER-TE Forwarding Pseudocode
7. Managing SI, subdomains and BFR-ids 7. Managing SI, subdomains and BFR-ids
When the number of bits required to represent the necessary hops in When the number of bits required to represent the necessary hops in
the topology and BFER exceeds the supported bitstring length, the topology and BFER exceeds the supported bitstring length,
multiple SI and/or subdomains must be used. This section discusses multiple SI and/or subdomains must be used. This section discusses
how. how.
BIER-TE forwarding does not require the concept of BFR-id, but BIER-TE forwarding does not require the concept of BFR-id, but
routing underlay, flow overlay and BIER headers may. This section routing underlay, flow overlay and BIER headers may. This section
also discusses how BFR-id can be assigned to BFIR/BFER for BIER-TE. also discusses how BFR-ids can be assigned to BFIR/BFER for BIER-TE.
7.1. Why SI and sub-domains 7.1. Why SI and sub-domains
For BIER and BIER-TE forwarding, the most important result of using For BIER and BIER-TE forwarding, the most important result of using
multiple SI and/or subdomains is the same: Packets that need to be multiple SI and/or subdomains is the same: Packets that need to be
sent to BFER in different SI or subdomains require different BIER sent to BFER in different SI or subdomains require different BIER
packets: each one with a bitstring for a different (SI,subdomain) packets: each one with a bitstring for a different (SI,subdomain)
bitstring. Each such bitstring uses one bitstring length sized SI bitstring. Each such bitstring uses one bitstring length sized SI
block in the BIFT of the subdomain. We call this a BIFT:SI (block). block in the BIFT of the subdomain. We call this a BIFT:SI (block).
skipping to change at page 29, line 7 skipping to change at page 29, line 7
when BIER-TE forwarding is added, we therefore reuse SI and subdomain when BIER-TE forwarding is added, we therefore reuse SI and subdomain
logically in the same way as they are used in BIER: All necessary logically in the same way as they are used in BIER: All necessary
BFIR/BFER for a service use a single BIER-TE BIFT and are split BFIR/BFER for a service use a single BIER-TE BIFT and are split
across as many SI as necessary (see below). Different services may across as many SI as necessary (see below). Different services may
use different subdomains that primarily exist to provide more use different subdomains that primarily exist to provide more
efficient replication (and for BIER-TE desirable traffic engineering) efficient replication (and for BIER-TE desirable traffic engineering)
for different subsets of BFIR/BFER. for different subsets of BFIR/BFER.
7.2. Bit assignment comparison BIER and BIER-TE 7.2. Bit assignment comparison BIER and BIER-TE
In BIER, bitstrings only need to carry bits for BFER, which lead to In BIER, bitstrings only need to carry bits for BFER, which leads to
the model that BFR-ids map 1:1 to each bit in a bitstring. the model that BFR-ids map 1:1 to each bit in a bitstring.
In BIER-TE, bitstrings need to carry bits to indicate not only the In BIER-TE, bitstrings need to carry bits to indicate not only the
receiving BFER but also the intermediate hops/links across which the receiving BFER but also the intermediate hops/links across which the
packet must be sent. The maximum number of BFER that can be packet must be sent. The maximum number of BFER that can be
supported in a single bitstring or BIFT:SI depends on the number of supported in a single bitstring or BIFT:SI depends on the number of
bits necessary to represent the desired topology between them. bits necessary to represent the desired topology between them.
"Desired" topology because it depends on the physical topology, and "Desired" topology because it depends on the physical topology, and
on the desire of the operator to allow for explicit traffic on the desire of the operator to allow for explicit traffic
engineering across every single hop (which requires more bits), or engineering across every single hop (which requires more bits), or
reducing the number of required bits by exploiting optimizations such reducing the number of required bits by exploiting optimizations such
as unicast (forward_route), ECMP or flood (DNR) over "uninteresting" as unicast (forward_route), ECMP or flood (DNR) over "uninteresting"
sub-parts of the topology - eg: parts where different trees do not sub-parts of the topology - e.g. parts where different trees do not
need to take different paths due to traffic-engineering reasons. need to take different paths due to traffic-engineering reasons.
The total number of bits to describe the topology in a BIFT:SI can The total number of bits to describe the topology vs. the BFER in a
therefore easily be as low as 20% or as high as 80%. The higher the BIFT:SI can range widely based on the size of the topology and the
percentage, the higher the likelihood, that those topology bits are amount of alternative paths in it. The higher the percentage, the
not just BIER-TE overhead without additional benefit, but instead higher the likelihood, that those topology bits are not just BIER-TE
they will allow to express the desired traffic-engineering overhead without additional benefit, but instead that they will allow
alternatives. to express desirable traffic-engineering path alternatives.
7.3. Using BFR-id with BIER-TE 7.3. Using BFR-id with BIER-TE
Because there is no 1:1 mapping between bits in the bitstring and Because there is no 1:1 mapping between bits in the bitstring and
BFER, BIER-TE can not simply rely on the BIER 1:1 mapping between BFER, BIER-TE cannot simply rely on the BIER 1:1 mapping between bits
bits in a bitstring and BFR-id. in a bitstring and BFR-id.
In BIER, automatic schemes could assign all possible BFR-ids In BIER, automatic schemes could assign all possible BFR-ids
sequentially to BFERs. This will not work in BIER-TE. In BIER-TE, sequentially to BFERs. This will not work in BIER-TE. In BIER-TE,
the operator or BIER-TE controller host has to determine a BFR-id for the operator or BIER-TE controller host has to determine a BFR-id for
each BFER in each required subdomain. The BFR-id may or may not have each BFER in each required subdomain. The BFR-id may or may not have
a relationship with a bit in the bitstring. Suggestions are detailed a relationship with a bit in the bitstring. Suggestions are detailed
below. Once determined, the BFR-id can then be configured on the below. Once determined, the BFR-id can then be configured on the
BFER and used by flow overlay, routing underlay and the BIER header BFER and used by flow overlay, routing underlay and the BIER header
almost the same as the BFR-id in BIER. almost the same as the BFR-id in BIER.
skipping to change at page 30, line 32 skipping to change at page 30, line 32
Note that in either case (unlike in BIER), the bits in BIER-TE may Note that in either case (unlike in BIER), the bits in BIER-TE may
need to change upon link/node failure/recovery, network expansion and need to change upon link/node failure/recovery, network expansion and
network load by other traffic (as part of traffic engineering goals). network load by other traffic (as part of traffic engineering goals).
Interactions between such BFIR applications and the BIER-TE Interactions between such BFIR applications and the BIER-TE
controller host do therefore need to support dynamic updates to the controller host do therefore need to support dynamic updates to the
bitstrings. bitstrings.
7.4. Assigning BFR-ids for BIER-TE 7.4. Assigning BFR-ids for BIER-TE
For non-leaf BFER, there is usually a single bit k for that BFER with For a non-leaf BFER, there is usually a single bit k for that BFER
a local_decap() adjacency on the BFER. The BFR-id for such a BFER is with a local_decap() adjacency on the BFER. The BFR-id for such a
therefore most easily the one it would have in BIER: SI * bitstring- BFER is therefore most easily the one it would have in BIER: SI *
length + k. bitstring-length + k.
As explained earlier in the document, leaf BFER do not need such a As explained earlier in the document, leaf BFERs do not need such a
separate bit because the fact alone that the BIER-TE packet is separate bit because the fact alone that the BIER-TE packet is
forwarded to the leaf BFER indicates that the BFER should decapsulate forwarded to the leaf BFER indicates that the BFER should decapsulate
it. Such a BFER will have one or more bits for the links leading it. Such a BFER will have one or more bits for the links leading
only to it. The BFR-id could therefore most easily be the BFR-id only to it. The BFR-id could therefore most easily be the BFR-id
derived from the lowest bit for those links. derived from the lowest bit for those links.
These two rules are only recommendations for the operator or BIER-TE These two rules are only recommendations for the operator or BIER-TE
controller assigning the BFR-ids. Any allocation scheme can be used, controller assigning the BFR-ids. Any allocation scheme can be used,
the BFR-ids just need to be unique across BFRs in each subdomain. the BFR-ids just need to be unique across BFRs in each subdomain.
skipping to change at page 31, line 23 skipping to change at page 31, line 23
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. Depending on topology, only the same 20%..80% of bits this approach. Depending on topology, only the same 20%..80% of bits
as possible for BIER-TE can be used for BIER. as possible for BIER-TE can be used for BIER.
7.5. Example bit allocations 7.5. Example bit allocations
7.5.1. With BIER 7.5.1. With BIER
Consider a network setup with a bitstring length of 256 for a network Consider a network setup with a bitstring length of 256 for a network
topology as shown in the picture below. The network has 6 areas, topology as shown in the picture below. The network has 6 areas,
each with ca. 180 BFR, connecting via a core with some larger (core) each with ca. 170 BFR, connecting via a core with some larger (core)
BFR. To address all BFER with BIER, 4 SI are required. To send a BFR. To address all BFER with BIER, 4 SI are required. To send a
BIER packet to all BFER in the network, 4 copies need to be sent by BIER packet to all BFER in the network, 4 copies need to be sent by
the BFIR. On the BFIR it does not make a difference how the BFR-id the BFIR. On the BFIR it does not make a difference how the BFR-id
are allocated to BFER in the network, but for efficiency further down are allocated to BFER in the network, but for efficiency further down
in the network it does make a difference. in the network it does make 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 15: Scaling BIER-TE bits by reuse Figure 16: 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 SI in each of the areas. there would be BFR-id for each of the 4 SI 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-id are allocated intelligently, then all the BFER in an area If BFR-id are allocated intelligently, then all the BFER in an area
would be given BFR-id with as few as possible different SI. Each would be given BFR-id with as few as possible different SI. 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 34, line 15 skipping to change at page 34, line 15
BIER-TE BitPosition (BP) can be understood as the BIER-TE equivalent BIER-TE BitPosition (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
SR forwarding segments. Whereas forwarding segments in SR are global SR forwarding segments. Whereas forwarding segments in SR are global
or local, BPs in BIER-TE have a scope that is the group of BFR(s) or local, BPs in BIER-TE have a scope that is the group of BFR(s)
that have adjacencies for this BP in their BIFT. This can be called that have adjacencies for this BP in their BIFT. This can be called
"adjacency" scoped forwarding segments. "adjacency" scoped forwarding segments.
Adjacency scope could be global, but then every BFR would need an Adjacency scope could be global, but then every BFR would need an
adjacency for this BP, for example a forward_routed adjacency with adjacency for this BP, for example a forward_routed adjacency with
encapsulation to the global SR SID of the destination. Such a BP encapsulation to the global SR SID of the destination. Such a BP
would always result in ingres replication though. The first BFR would always result in ingress replication though. The first BFR
encountering this BP would directly replicate to it. Only by using encountering this BP would directly replicate to it. Only by using
non-global adjacency scope for BPs can traffic be steered and non-global adjacency scope for BPs can traffic be steered and
replicated on non-ingres BFR. replicated on non-ingress BFR.
SR can naturally be combined with BIER-TE and help to optimize it. SR can naturally be combined with BIER-TE and help to optimize it.
For example, instead of defining BitPositions for non-replicating For example, instead of defining BitPositions for non-replicating
hops, it is equally possible to use segment routing encapsulations hops, it is equally possible to use segment routing encapsulations
(eg: MPLS label stacks) for the encapsulation of "forward_routed" (eg: MPLS label stacks) for the encapsulation of "forward_routed"
adjacencies. adjacencies.
Note that BIER itself can also be seen to be similar to SR. BIER BPs Note that BIER itself can also be seen to be similar to SR. BIER BPs
act as global destination Node-SIDs and the BIER bitstring is simply act as global destination Node-SIDs and the BIER bitstring is simply
a highly optimized mechanism to indicate multiple such SIDS and let a highly optimized mechanism to indicate multiple such SIDS and let
the network take care of effectively replicating the packet hop-by- the network take care of effectively replicating the packet hop-by-
hop to each destination Node-SID. What BIER does not allow is to hop to each destination Node-SID. What BIER does not allow is to
indicate intermediate hops, or terms of SR the ability to indicate a indicate intermediate hops, or terms of SR the ability to indicate a
sequence of SID to reach the destination. This is what BIER-TE and sequence of SID to reach the destination. This is what BIER-TE and
its adjacency scoped BP enables. its adjacency scoped BP enables.
Both BIER and BIER-TE allow BFIR to "opportunistically" copy packets
to a set of desired BFER on a packet-by-packet basis. In BIER, this
is done by OR'ing the BP for the desired BFER. In BIER-TE this can
be done by OR'ing for each desired BFER a bitstring using the
"independent branches" approach described in Section 7.3 and
therefore also indicating the engineered path towards each desired
BFER. This is the approach that
[I-D.ietf-bier-multicast-http-response] relies on.
9. Security Considerations 9. Security Considerations
The security considerations are the same as for BIER with the The security considerations are the same as for BIER with the
following differences: following differences:
BFR-ids and BFR-prefixes are not used in BIER-TE, nor are procedures BFR-ids and BFR-prefixes are not used in BIER-TE, nor are procedures
for their distribution, so these are not attack vectors against BIER- for their distribution, so these are not attack vectors against BIER-
TE. TE.
10. IANA Considerations 10. IANA Considerations
skipping to change at page 35, line 9 skipping to change at page 35, line 18
11. Acknowledgements 11. Acknowledgements
The authors would like to thank Greg Shepherd, Ijsbrand Wijnands and The authors would like to thank Greg Shepherd, Ijsbrand Wijnands and
Neale Ranns for their extensive review and suggestions. Neale Ranns for their extensive review and suggestions.
12. Change log [RFC Editor: Please remove] 12. Change log [RFC Editor: Please remove]
draft-ietf-bier-te-arch: draft-ietf-bier-te-arch:
04: spell check run.
Addded remaining fixes for Sandys (Zhang Zheng) review:
4.7 Enhance ECMP explanations:
example ECMP algorithm, highlight that doc does not standardize
ECMP algorithm.
Review from Dirk Trossen:
1. Added mentioning of prior work for traffic engineered paths
with bloom filters.
2. Changed title from layers to components and added "BIER-TE
control plane" to "BIER-TE controller host" to make it clearer,
what it does.
2.2.3. Added reference to I-D.ietf-bier-multicast-http-response
as an example solution.
2.3. clarified sentence about resetting BPs before sending copies
(also forgot to mention DNR here).
3.4. Added text saying this section will be removed unless IESG
review finds enough redeeming value in this example given how -03
introduced section 1.1 with basic examples.
7.2. Removed explicit numbers 20%/80% for number of topology bits
in BIER-TE, replaced with more vague (high/low) description,
because we do not have good reference material Added text saying
this section will be removed unless IESG review finds enough
redeeming value in this example given how -03 introduced section
1.1 with basic examples.
many typos fixed. Thanks a lot.
03: Last call textual changes by authors to improve readability: 03: Last call textual changes by authors to improve readability:
removed Wolfgang Braun as co-authors (as requested). removed Wolfgang Braun as co-authors (as requested).
Improved abstract to be more explanatory. Removed mentioning of Improved abstract to be more explanatory. Removed mentioning of
FRR (not conluded on so far). FRR (not concluded on so far).
Added new text into Introduction setion because the text was too Added new text into Introduction section because the text was too
difficult to jump into (too many forward pointers). This difficult to jump into (too many forward pointers). This
primarily consists of examples and the early introduction of the primarily consists of examples and the early introduction of the
BIER-TE Topology concept enabled by these examples. BIER-TE Topology concept enabled by these examples.
Amended comparison to SR. Amended comparison to SR.
Changed syntax from [VRF] to {VRF} to indicate its optional and to Changed syntax from [VRF] to {VRF} to indicate its optional and to
make idnits happy. make idnits happy.
Split references into normative / informative, added references. Split references into normative / informative, added references.
02: Refresh after IETF104 discussion: changed intended status back 02: Refresh after IETF104 discussion: changed intended status back
to standard. Reasoning: to standard. Reasoning:
Tighter review of standards document == ensures arch will be Tighter review of standards document == ensures arch will be
better prepared for possible adoption by other WGs (e.g.: DetNet) better prepared for possible adoption by other WGs (e.g. DetNet)
or std. bodies. or std. bodies.
Requirement against the degree of existing implementations is self Requirement against the degree of existing implementations is self
defined by the WG. BIER WG seems to think it is not necessary to defined by the WG. BIER WG seems to think it is not necessary to
apply multiple interoperating implementions against an apply multiple interoperating implementations against an
architecture level document at this time to make it qualify to go architecture level document at this time to make it qualify to go
to standards track. Also, the levels of support introduced in -01 to standards track. Also, the levels of support introduced in -01
rev. should allow all BIER forwarding engines to also be able to rev. should allow all BIER forwarding engines to also be able to
support the base level BIER-TE forwarding. support the base level BIER-TE forwarding.
01: Added note comparing BIER and SR to also hopefully clarify 01: Added note comparing BIER and SR to also hopefully clarify
BIER-TE vs. BIER comparison re. SR. BIER-TE vs. BIER comparison re. SR.
- added requirements section mandating only most basic BIER-TE - added requirements section mandating only most basic BIER-TE
forwarding features as MUST. forwarding features as MUST.
- reworked comparison with BIER forwarding section to only - reworked comparison with BIER forwarding section to only
summarize and point to pseudocode section. summarize and point to pseudocode section.
- reworked pseudocode section to have one pseodcode that mirrors - reworked pseudocode section to have one pseudocode that mirrors
the BIER forwarding pseudocode to make comparison easier and a the BIER forwarding pseudocode to make comparison easier and a
second pseudocode that shows the complete set of BIER-TE second pseudocode that shows the complete set of BIER-TE
forwarding options and simplification/optimization possible vs. forwarding options and simplification/optimization possible vs.
BIER forwarding. BIER forwarding. Removed MyBitsOfInterest (was pure
optimization).
- Added captions to pictures. - Added captions to pictures.
- Part of review feedback from Sandy (Zhang Zheng) integrated.
00: Changed target state to experimental (WG conclusion), updated 00: Changed target state to experimental (WG conclusion), updated
references, mod auth association. references, mod auth association.
- Source now on http://www.github.com/toerless/bier-te-arch - Source now on http://www.github.com/toerless/bier-te-arch
- Please open issues on the github for change/improvement requests - Please open issues on the github for change/improvement requests
to the document - in addition to posting them on the list to the document - in addition to posting them on the list
(bier@ietf.). Thanks!. (bier@ietf.). Thanks!.
draft-eckert-bier-te-arch: draft-eckert-bier-te-arch:
skipping to change at page 38, line 23 skipping to change at page 39, line 23
<https://www.rfc-editor.org/info/rfc8279>. <https://www.rfc-editor.org/info/rfc8279>.
[RFC8296] Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A., [RFC8296] Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A.,
Tantsura, J., Aldrin, S., and I. Meilik, "Encapsulation Tantsura, J., Aldrin, S., and I. Meilik, "Encapsulation
for Bit Index Explicit Replication (BIER) in MPLS and Non- for Bit Index Explicit Replication (BIER) in MPLS and Non-
MPLS Networks", RFC 8296, DOI 10.17487/RFC8296, January MPLS Networks", RFC 8296, DOI 10.17487/RFC8296, January
2018, <https://www.rfc-editor.org/info/rfc8296>. 2018, <https://www.rfc-editor.org/info/rfc8296>.
13.2. Informative References 13.2. Informative References
[I-D.ietf-bier-multicast-http-response]
Trossen, D., Rahman, A., Wang, C., and T. Eckert,
"Applicability of BIER Multicast Overlay for Adaptive
Streaming Services", draft-ietf-bier-multicast-http-
response-01 (work in progress), June 2019.
[I-D.ietf-roll-ccast]
Bergmann, O., Bormann, C., Gerdes, S., and H. Chen,
"Constrained-Cast: Source-Routed Multicast for RPL",
draft-ietf-roll-ccast-01 (work in progress), October 2017.
[ICC] Reed, M., Al-Naday, M., Thomos, N., Trossen, D.,
Petropoulos, G., and S. Spirou, "Stateless multicast
switching in software defined networks", IEEE
International Conference on Communications (ICC), Kuala
Lumpur, Malaysia, 2016, May 2016,
<https://ieeexplore.ieee.org/document/7511036>.
[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, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., [RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V.,
and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP
Tunnels", RFC 3209, DOI 10.17487/RFC3209, December 2001, Tunnels", RFC 3209, DOI 10.17487/RFC3209, December 2001,
<https://www.rfc-editor.org/info/rfc3209>. <https://www.rfc-editor.org/info/rfc3209>.
[RFC8402] Filsfils, C., Ed., Previdi, S., Ed., Ginsberg, L., [RFC8402] Filsfils, C., Ed., Previdi, S., Ed., Ginsberg, L.,
Decraene, B., Litkowski, S., and R. Shakir, "Segment Decraene, B., Litkowski, S., and R. Shakir, "Segment
Routing Architecture", RFC 8402, DOI 10.17487/RFC8402, Routing Architecture", RFC 8402, DOI 10.17487/RFC8402,
July 2018, <https://www.rfc-editor.org/info/rfc8402>. July 2018, <https://www.rfc-editor.org/info/rfc8402>.
Authors' Addresses Authors' Addresses
Toerless Eckert (editor) Toerless Eckert (editor)
Huawei USA - Futurewei Technologies Inc. Futurewei Technologies Inc.
2330 Central Expy 2330 Central Expy
Santa Clara 95050 Santa Clara 95050
USA USA
Email: tte+ietf@cs.fau.de Email: tte+ietf@cs.fau.de
Gregory Cauchie Gregory Cauchie
Bouygues Telecom Bouygues Telecom
Email: GCAUCHIE@bouyguestelecom.fr Email: GCAUCHIE@bouyguestelecom.fr
 End of changes. 95 change blocks. 
143 lines changed or deleted 255 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/