BGP for BIER-TE Path

1.1. Terminologies

The following terminologies are used in this document.¶

BIER:

Bit Index Explicit Replication.¶

BIER-TE:

BIER Tree Engineering.¶

BFR:

Bit-Forwarding Router.¶

BFIR:

Bit-Forwarding Ingress Router.¶

BFER:

Bit-Forwarding Egress Router.¶

BFR-id:

BFR Identifier. It is a number in the range [1,65535].¶

BFR-NBR:

BFR Neighbor.¶

BFR-prefix:

An IP address (either IPv4 or IPv6) of a BFR.¶

BIRT:

Bit Index Routing Table. It is a table that maps from the BFR-id (in a particular sub-domain) of a BFER to the BFR-prefix of that BFER, and to the BFR-NBR on the path to that BFER.¶

BIFT:

Bit Index Forwarding Table.¶

P-tunnel:

A multicast tunnel through the network of one or more SPs.¶

PMSI:

Provider Multicast Service Interface. PMSI is an abstraction that represents a multicast service for carrying packets. A PMSI is instantiated via one or more P-tunnels.¶

I-PMSI A-D Route:

Inclusive PMSI Auto-Discovery route.¶

S-PMSI A-D route:

Selective PMSI Auto-Discovery route.¶

x-PMSI A-D route:

A route that is either an I-PMSI A-D route or an S-PMSI A-D route.¶

2.1. Example BIER-TE Topology with BGP

An example BIER-TE domain topology using SDN controllor with a BGP to distribute BIER-TE path is shown in Figure 1. There are 8 nodes/BFRs A, B, C, D, E, F, G and H in the domain. Nodes/BFRs A, H, E, F and D are BFIRs (i.e., ingress nodes) or BFERs (i.e., egress nodes). The controller has a BGP session with each of the edge nodes in the domain, including BFIRs (i.e., ingress nodes A, H, E, F and D), and each of the non edge nodes in the domain (i.e., nodes B, C and G). Note that some of connections and the BGP on each edge node are not shown in the figure.¶

                    +------------------------------------+
                    |      SND controller with BGP       |
                    +------------------------------------+
                    /        ...         \               \
                   /                      \               \
                  /                    4'  \   17'    18'  \
                 /            /-----------( G )----------( H )
                /            /           19'\_______   12'/4
               /            /                _______)____/
              /            /                /      (_____
             /            /3'              /             \
            /   1'   2'  /    5'     6'   /11'  13'    20'\
 (CE) --- ( A )--------( B )------------( C )------------( D )
            5            \7'              \15'       14'   1
                          \                \
                           \8'   9'    10'  \16'
                          ( E )------------( F )
                            3                2

Nodes/BFRs D, F, E, H and A are BFERs (or BFIRs) and have local decap adjacency BitPositions 1, 2, 3, 4, and 5 respectively. For simplicity, these BPs are represented by (SI:BitString), where SI = 0 and BitString is of 8 bits. BPs 1, 2, 3, 4, and 5 are represented by 1 (0:00000001), 2 (0:00000010), 3 (0:00000100), 4 (0:00001000) and 5 (0:00010000) respectively.¶

The BitPositions for the forward connected adjacencies are represented by i', where i is from 1 to 20. In one option, they are encoded as (n+i), where n is a power of 2 such as 32768. For simplicity, these BitPositions are represented by (SI:BitString), where SI = (6 + (i-1)/8) and BitString is of 8 bits. BitPositions i' (i from 1 to 20) are represented by 1'(6:00000001), 2'(6:00000010), 3'(6:00000100), 4'(6:00001000), 5'(6:00010000), 6'(6:00100000), 7'(6:01000000), 8'(6:10000000), 9'(7:00000001), 10'(7:00000010), . . . , 16'(7:10000000), 17'(8:00000001), 18'(8:00000010), . . . , 20'(8:00001000).¶

For a link between two nodes X and Y, there are two BitPositions for two forward connected adjacencies. These two forward connected adjacency BitPositions are assigned on nodes X and Y respectively. The BitPosition assigned on X is the forward connected adjacency from Y to X. The BitPosition assigned on Y is the forward connected adjacency from X to Y.¶

For example, for the link between nodes B and C in the figure, two forward connected adjacency BitPositions 5' and 6' are assigned to two ends of the link. BitPosition 5' is assigned on node B to B's end of the link. It is the forward connected adjacency from C to B. BitPosition 6' is assigned on node C to C's end of the link. It is the forward connected adjacency from B to C.¶

2.2. BIER-TE BIFT on a BFR

Every BFR in a BIER-TE domain has a BIER-TE BIFT. For the BIER-TE topology in Figure 1, each of 8 nodes/BFRs A, B, C, D, E, F, G and H has its BIER-TE BIFT for the topology.¶

The controller sends each BFR all its BitPositions including its local decap adjacency BitPosition and forward connected adjacency BitPositions after the BitPositions are determined and assigned in the controller. For example, the controller sends BFR A BitPosition 5 and BitPosition 2', where the former is A's local decap adjacency BitPosition and the latter is A's forward connected adjacency BitPosition from A to B. The controller sends BFR B BitPositions 1', 4', 6' and 8', which are B's forward connected adjacency BitPositions from B to A, G, C and E respectively.¶

When a BFR (i.e., the BGP running on the BFR) receives its BitPositions from the controller, it creates its BIER-TE BIFT based on them. For example, when BFR A receives its BitPositions, it creates its BIER-TE BIFT, which is shown in Figure 2. There are two forwarding entries in the BIFT.¶

The 1st forwarding entry in the BIFT will locally decapsulate a multicast packet with BitPosition 5 and pass a copy of the payload of the packet to the packet's NextProto.¶

The 2nd forwarding entry in the BIFT will forward a multicast packet with BitPosition 2' to B.¶

           +------------------+--------------+------------+
           |   Adjacency BP   |    Action    |  BFR-NBR   |
           |  (SI:BitString)  |              | (Next Hop) |
           +==================+==============+============+
           | 5  (0:00000005)  | local-decap  |            |
           +------------------+--------------+------------+
           | 2' (6:00000010)  | fw-connected |     B      |
           +------------------+--------------+------------+

When BFR B receives its BitPositions 1', 4', 6' and 8', it creates its BIER-TE BIFT, which is shown in Figure 3. There are four forwarding entries in the BIFT.¶

The 1st forwarding entry in the BIFT will forward a multicast packet with BitPosition 1' to A.¶

The 2nd forwarding entry in the BIFT will forward a multicast packet with BitPosition 4' to G.¶

The 3rd forwarding entry in the BIFT will forward a multicast packet with BitPosition 6' to C.¶

The 4-th forwarding entry in the BIFT will forward a multicast packet with BitPosition 8' to E.¶

           +------------------+--------------+------------+
           |   Adjacency BP   |    Action    |  BFR-NBR   |
           |  (SI:BitString)  |              | (Next Hop) |
           +==================+==============+============+
           | 1' (6:00000001)  | fw-connected |     A      |
           +------------------+--------------+------------+
           | 4' (6:00001000)  | fw-connected |     G      |
           +------------------+--------------+------------+
           | 6' (6:00100000)  | fw-connected |     C      |
           +------------------+--------------+------------+
           | 8' (6:10000000)  | fw-connected |     E      |
           +------------------+--------------+------------+

2.3. Distributing Path to Ingress

This section describes how the SDN controller distributes a BIER-TE path to its ingress node.¶

There are two scenarios for distributing the BIER-TE path information. In the first scenario, the ingress node is directly connected to the controller. The path information should not be propagated beyond the ingress node. In the second scenario, the ingress node is not directly connected to the controller. The path information should be propagated throughout the domain until it reaches the ingress node.¶

Suppose that node A in Figure 1 wants to have a BIER-TE path from ingress node A to egress nodes H and F. The path satisfies a set of constraints. The controller obtains the request from an application or user configuration. It finds a BIER-TE path satisfying the constraints and distributes the path to ingress node A.¶

If A is directly connected to the controller (e.g., as the example network in Figure 1), then the controller sends A the information about the path in a Update message in one of two ways. In one way, the controller sends each of its BGP peers, including the BGP peer running on node A, a Update message about the explicit path, with a route target matching the BGP identifier of ingress node A, and NO_ADVERTISE community. Ingress node A accepts this message from the controller and installs a forwarding entry for the BIER-TE path, but will not advertise it to any peer. All the other peers do not accept the message.¶

In another way, the controller sends A a Update message directly through the local session between them, but does not send the message to any other peers. The message contains the information about the path, a route target matching the BGP identifier of ingress node A and the NO_ADVERTISE community. Ingress node A accepts this message from the controller and installs a forwarding entry for the BIER-TE path, but will not advertise it.¶

If A is not directly connected to the controller, then the controller distributes the information about the explicit path to the ingress node A across the network. To achieve this, the controller advertises a BGP Update message to all its BGP peers, where the message contains the information about the path, a route target matching the BGP identifier of ingress node A, but does not have NO_ADVERTISE community. Each of the BGP peers advertises the received Update to its BGP neighbors according to normal BGP propagation rules. Eventually, ingress node A accepts this message and installs a forwarding entry for the BIER-TE path, which imports the packets to be transported by the path into the path.¶

For example, assume that the BIER-TE path computed by the controller traverses the link/adjacency from A to B (indicated by BP 2'), the link/adjacency from B to G (indicated by BP 4') and the link/adjacency from B to C (indicated by BP 6'), the link/adjacency from G to H (indicated by BP 18'), and the link/adjacency from C to F (indicated by BP 16'). This path is represented by {2', 4', 6', 16', 18', 2, 4}, where BitPositions 2 and 4 indicate egress nodes F and H respectively. The Update message distributed to the BGP on node A by the controller contains the path represented by {2', 4', 6', 16', 18', 2, 4}.¶

After receiving the BIER-TE path, the ingress node installs a forwarding entry for the path. For any packet from CE to be transported by the path, the ingress node encapsulates the packet with the BitPositions representing the path and forwards the packet according to its BIFT.¶

For example, when ingress node A receives the path represented by BitPositions {2', 4', 6', 16', 18', 2, 4}, it installs a forwarding entry for the path. Node A encapsulates a packet to be carried by the path with a BIER header containing BitPositions {2', 4', 6', 16', 18', 2, 4} using the entry and forwards the encapsulated packet along the path according to its BIFT.¶

A forwards the packet to B according to the forwarding entry for BP 2' in its BIFT.¶

After receiving the packet from A, B forwards the packet to G and C according to the forwarding entries for BPs 4' and 6' in B's BIFT respectively. The packet received by G has path {16', 18', 2, 4}. The packet received by C has path {16', 18', 2, 4}.¶

After receiving the packet from B, G sends the packet to H according to the forwarding entry for BP 18' in G's BIFT.¶

After receiving the packet from B, C sends the packet to F according to the forwarding entry for BP 16' in C's BIFT.¶

Egress node H of the BIER-TE path receives the packet with BitPosition 4. It decapsulates the packet and pass the payload of the packet to the packet's NextProto.¶

Egress node F of the BIER-TE path receives the packet with BitPosition 2. It decapsulates the packet and pass the payload of the packet to the packet's NextProto.¶

3.1. Extensions to PMSI_TUNNEL Attribute

This section defines a new Tunnel Type (or TLV) for BIER-TE path/tunnel under the PMSI_TUNNEL Attribute (PTA) defined in [RFC6514]. It describes a couple of new sub-TLVs encoding the information about a BIER-TE path.¶

  0                   1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |  Attr Flags   | Attr Type(22) | Length(1/2 byte)   ~
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |      Flag     |TunnelType(TBD)|          MPLS Label           |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |  MPLS Label   |       Tunnel Identifier (11/23 bytes)         |
 +-+-+-+-+-+-+-+-+                                               +
 |                                                               ~
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                             sub-TLVs                          ~
 ~                                                               ~
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Type (TBD3) |        Length (variable)      |   Reserved    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    SI-Len     | BitStringLen  | sub-domain-id |     MT-ID     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                BIFT-id-1              |  RSV  |     SI-1      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            BitString-1                        ~
|                                                               ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
:                                                               :
:                                                               :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                BIFT-id-n              |  RSV  |     SI-n      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            BitString-n                        ~
|                                                               ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

  0                   1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |   Type (TBD3) |          Length = 13          |   Reserved    |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |  SI-Len = 8   | BitStringLen  |sub-domain-id=0|   MT-ID = 0   |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |       BIFT-id-1 = 100         |    SI-1 = 8   |0 0 0 0 0 0 1 0|
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |       BIFT-id-2 = 200         |    SI-2 = 7   |1 0 0 0 0 0 0 0|
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |       BIFT-id-3 = 300         |    SI-3 = 6   |0 0 1 0 1 0 1 0|
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |       BIFT-id-4 = 400         |    SI-4 = 0   |0 0 0 0 1 0 1 0|
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Type (TBD4) |        Length (variable)      |   Reserved    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
//                        Path Name String                     //
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

3.2. Extensions to Tunnel Encapsulation Attribute

This section define a new Tunnel Type (or say TLV) for BIER-TE path/tunnel under Tunnel Encapsulation Attribute and a new SAFI. This new SAFI and the existing AFI for IPv4/IPv6 pair uses a new NLRI for indicating a BIER-TE Path.¶

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+
|  NLRI Length  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      Distinguisher (4 octets)                 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      Endpoint (4/16 octets)                   ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    Attributes:
        Tunnel Encaps Attribute (23)
            Tunnel Type (TBD2): BIER-TE Path
                Path BitPositions sub-TLV
                Path Name sub-TLV
                Traffic Description sub-TLV

  0                   1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |   Type (TBD5) |             Length            |   Reserved    |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |        Reserved           |S|G|  Src Mask Len | Grp Mask Len  |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                Source Address (up to 4 bytes)                 ~
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |            Group Multicast Address (up to 4 bytes)            ~
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

  0                   1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |   Type (TBD6) |             Length            |   RESERVED    |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |        Reserved           |S|G|  Src Mask Len | Grp Mask Len  |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                        Source Address                         ~
 ~                       (up to 16 bytes)                        ~
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                   Group multicast Address                     ~
 ~                       (up to 16 bytes)                        ~
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

7.1. Normative References

[RFC2119]

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

[RFC6514]

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

[RFC8174]

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

[RFC8279]

Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A., Przygienda, T., and S. Aldrin, "Multicast Using Bit Index Explicit Replication (BIER)", RFC 8279, DOI 10.17487/RFC8279, November 2017, <https://www.rfc-editor.org/info/rfc8279>.

[RFC8296]

Wijnands, IJ., Ed., Rosen, E., Ed., Dolganow, A., Tantsura, J., Aldrin, S., and I. Meilik, "Encapsulation for Bit Index Explicit Replication (BIER) in MPLS and Non-MPLS Networks", RFC 8296, DOI 10.17487/RFC8296, January 2018, <https://www.rfc-editor.org/info/rfc8296>.

[RFC9012]

Patel, K., Van de Velde, G., Sangli, S., and J. Scudder, "The BGP Tunnel Encapsulation Attribute", RFC 9012, DOI 10.17487/RFC9012, April 2021, <https://www.rfc-editor.org/info/rfc9012>.

7.2. Informative References

[I-D.ietf-bier-te-arch]

Eckert, T., Cauchie, G., and M. Menth, "Tree Engineering for Bit Index Explicit Replication (BIER-TE)", Work in Progress, Internet-Draft, draft-ietf-bier-te-arch-10, 9 July 2021, <https://www.ietf.org/archive/id/draft-ietf-bier-te-arch-10.txt>.

[RFC5226]

Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", RFC 5226, DOI 10.17487/RFC5226, May 2008, <https://www.rfc-editor.org/info/rfc5226>.

[RFC5575]

Marques, P., Sheth, N., Raszuk, R., Greene, B., Mauch, J., and D. McPherson, "Dissemination of Flow Specification Rules", RFC 5575, DOI 10.17487/RFC5575, August 2009, <https://www.rfc-editor.org/info/rfc5575>.