BIER WG Sandy. Zhang Internet-Draft Bo. Wu Intended status: Standards Track ZTE Corporation Expires: May 4, 2016 November 1, 2015 Designed Routing in BIER Forwarding draft-zhang-bier-designed-routing-01.txt Abstract BIER specifies a new architecture for the forwarding of multicast data packets. As the [I-D.ietf-bier-architecture] said, in the BIER domain, it does not require a protocol for explicitly building multicast distributing trees, nor does it require intermediate nodes to maintain any per-flow state. In some deployments, some specific multicast flows may be forwarded by special routing; it cannot be achieved by the forwarding rule that is provided. In this document we will defined a new routing list in BIER header, the packets will be steered according to the routing list. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on May 4, 2016. Copyright Notice Copyright (c) 2015 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect Zhang & Wu Expires May 4, 2016 [Page 1] Internet-Draft Designed Routing in BIER Forwarding November 2015 to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Designed Routing . . . . . . . . . . . . . . . . . . . . . . 3 2.1. The node's level . . . . . . . . . . . . . . . . . . . . 3 3. Format of designed routing list . . . . . . . . . . . . . . . 3 3.1. BitString . . . . . . . . . . . . . . . . . . . . . . . . 4 3.1.1. unified BSL . . . . . . . . . . . . . . . . . . . . . 4 3.1.2. Different BSL . . . . . . . . . . . . . . . . . . . . 5 4. Encapsulate the designed routing list . . . . . . . . . . . . 6 5. Decapsulate the packet . . . . . . . . . . . . . . . . . . . 7 6. Forwarding treatment . . . . . . . . . . . . . . . . . . . . 7 6.1. Process the designed routing list . . . . . . . . . . . . 8 7. Security Considerations . . . . . . . . . . . . . . . . . . . 13 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 9. Normative References . . . . . . . . . . . . . . . . . . . . 13 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 1. Introduction As the [I-D.ietf-bier-architecture] described, BIER specifies a new architecture for the forwarding of multicast data packets. And the extension of OSPF/ISIS is used to flood the BIER information to establish the BIER forwarding table. The calculation algorithm of IGP is calculating the shortest path to every BIER node. It means that the forwarding in BIER is along the shortest path. --------- B ------ C -------- | | | | A ------- D ------ E ------ F | | | | --------- G ------ H -------- Figure 1: An example of packets forwarding For example, in figure 1, in the forwarding table of node A, here supposes that the shortest path to node C is node B, the shortest path to node H is node G. If there is one specific multicast flow that should be forwarding to node C, node F and node H. Then the forwarding path will be node A --- node B --- node C, node A--- node D --- node E --- node F, node A --- node G --- node H. If we want to merge the flows in one optimizing path of node A --- node D --- node E --- node C/ node F/ node H, we cannot implement it due to the shortest forwarding algorithm. Zhang & Wu Expires May 4, 2016 [Page 2] Internet-Draft Designed Routing in BIER Forwarding November 2015 This document specifies a way to forward multicast packets by designed routing. These multicast packets are encapsulated by specific header. The BIER nodes forward the packets by designed routing that is carried in specific BIER header. In figure 1, node A send the packets with designed routing list. The packets will be forwarded by the nodes list in the designed routing list of node A --- node D --- node E --- node C/ node F/ node H. 2. Designed Routing The packets that are forwarded by BIER nodes are filled with designed routing in the BIER header, which carries the nodes list in order. The nodes are divided into differentiate levels that are classified by the distance from the ingress node. 2.1. The node's level ------- B ------ D ------ F | A-------C ------ E Figure 2 For example, in figure2, node A is ingress node, the node F and node E are egress nodes. Node B and C are the first level nodes that one specific multicast flow should be forwarded to, node D and E are the second level nodes that the flow should be forwarded to. There is only one node F in the third level. 3. Format of designed routing list The designed routing list that is followed by the BIER header should be distinguished by some specific flag in the BIER header. One of the reserved bits may be used for the proposal. When the rightmost bit of the reserved field is set to 1, it indicates that the designed routing list is followed by the BIER header of the packet. As showed below: Zhang & Wu Expires May 4, 2016 [Page 3] Internet-Draft Designed Routing in BIER Forwarding November 2015 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 1 0 1| Ver | Len | Entropy | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | BitString (first 32 bits) ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ BitString (last 32 bits) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |OAM| Reserved 1| Proto | BFIR-id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3 The designed routing list is comprised of a TLV, include type, length and value. The type of TLV indicates the routing information and form. There are many different types for the designed routing that may have many various formats, which may be expressed by bitstring, bfr-id list, or bfr-prefix list, and so on. The following section defines how to use the bitstring to express the designed routing list. 3.1. BitString The BitPosition(BP) is used to indicate the nodes in BIER header. And it can be used in the list of designed routing. It's flexible to choose the corresponding BSL for packet's encapsulation. So it's also flexible to encapsulate the list of designed routing. The neighbor's format in the routing list should be used for two types. 3.1.1. unified BSL Figure 4 illustrates using one unified BSL in the designed routing list, which means all level nodes in the list share the same BSL. Zhang & Wu Expires May 4, 2016 [Page 4] Internet-Draft Designed Routing in BIER Forwarding November 2015 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 | Length | Current level | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Bit String Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | level | Bit String ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ Bit String | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | level | Bit String ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ Bit String | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 4 o Type : TBD. Suggest type 1. o Length: The length of this TLV. o Current level: Indicate the recent level that should be processed by the receiving node in the designed routing list. It will be increased by 1 after the processing of nodes in the designed routing. o Bit String Length: Indicate the BSL that be used in the designed routing list. o Level: Indicate the node's level of the designed routing. o Bit String: All the nodes in the same level should be encapsulated in one bitstring. 3.1.2. Different BSL Also different BSL should be used to express the nodes in the designed routing list. As sketched in Figure 5, different level nodes may be encapsulated in different BSL. Zhang & Wu Expires May 4, 2016 [Page 5] Internet-Draft Designed Routing in BIER Forwarding November 2015 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 | Length | Current level | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | level | Bit String Length ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ | Bit String ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ Bit String | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | level | Bit String Length ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ | Bit String ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ Bit String | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 5 o Type : TBD. Suggest type 2. o Length: The length of this TLV. o Current level: Indicate the recent level that should be processed by the receiving node in the designed routing list. It will be increased by 1 after the processing of nodes in the designed routing. o Level: Indicate the node's level of the designed routing. o Bit String Length: Indicate the BSL that be used in this level. o Bit String: All the nodes in the same level do be encapsulated in one bitstring. 4. Encapsulate the designed routing list When the ingress node gathers all the egress nodes in the BIER domain, it should encapsulate the BIER header as regular function first when traffic arrives. If this traffic is classified to be forwarded by one designed routing, the ingress node then encapsulates the nodes' list in the designed routing list. The designed routing list may be provided from the controller or the module of PCE, and so on. The nodes in one same level should be encapsulated together. Zhang & Wu Expires May 4, 2016 [Page 6] Internet-Draft Designed Routing in BIER Forwarding November 2015 ------- B ------ C ------ D | | A-------E ------ F | | ------- G ------ H ----- K Figure 6 For example, there are several nodes in one BIER domain. Suppose that for one specific multicast flow, the ingress node is A, and the egress nodes are D, F and K. The designed routing list is A-E-F-C-D, A-E-F-H-K. What is more, node B is the shortest path next hop from A to D, node G is the shortest path next hop from A to K. The designed routing is divided into four levels, the first level includes node E. The second level includes node F. The third level includes node C and node H. The fourth level includes node D and node K. Node A encapsulates all the nodes in the path to the designed routing list. The current level is set to 1. 5. Decapsulate the packet When the packet is forwarded to one of the egress nodes, the egress node will detect that it is one of the egress nodes due to the bitstring in the BIER header. The egress nodes decapsulate the BIER header and forward it to the previous domain by reductive format. And if the egress node notices that there are still many nodes in the designed routing list that should be forwarded, the egress node will forward packets to next node due to the designed routing list. 6. Forwarding treatment When the BIER nodes receive a packet that is encapsulated by BIER header and designed routing list extension, the BIER nodes will process the designed routing list in the BIER header and forward the packet according to the list. The current nodes receive a packet from the control plane or one previous node. The current nodes will process the designed routing list due to the indication in the BIER header. If there is no indication of designed routing list in the BIER header, the current nodes will forward the packet according to the BIER forwarding defined in [I-D.ietf-bier-architecture]. If there is a designed routing list in the BIER header, the current nodes will forward the packet due to the rules below. Zhang & Wu Expires May 4, 2016 [Page 7] Internet-Draft Designed Routing in BIER Forwarding November 2015 At first, if the node is one of the egress nodes due to the BIER header, the nodes should decapsulate the packet and forward it to outside. Second, if the node detect that there is a designed routing list in the BIER header, the node will process the designed routing list, and forward the packet to the nodes in the list. The detail of processing is described in the subsection. At last, the node increases the current level in the designed routing list, and forwards the packet to the next level nodes in the list. 6.1. Process the designed routing list Step 1, the node gets the nodes' list in the designed routing list belong to current level. For example, if the value of current level field is set to 1, then the node will get the nodes that are encapsulate in level 1. Step 2, the node looks up the BIER forwarding table and gets the table items which the next-hop are same to the nodes that get from the designed routing list. Step 3, the node copies the bitstring in the BIER header and updates it by AND'ing with all the table items. After INVERSE the result, do And'ing with the original bitstring. Then the result is reserved egress nodes. It can be simplified to Rev-enodes. Step 4, the node update the origin bitstring by AND'ing with one item that are get from step2, and merge the result with the Rev-enodes, increase the current level field by 1 and forwards the packet to the next-hop of the item. If there are several items get from step2, the node will do the processing with all the items. Every node in the designed routing list repeats the step, the packet will be forwarded by the nodes in the designed routing list. At last the packet is forwarded to outside of the BIER domain. As the example of section 4, Suppose that the BitPositions for all nodes are: A(1),B(2),C(3),D(4),E(5),F(6),G(7),H(8), K(9). And suppose that the BSL is 9. Zhang & Wu Expires May 4, 2016 [Page 8] Internet-Draft Designed Routing in BIER Forwarding November 2015 ---10---- B --10---- C --10---- D | | | 50 | | A--20-----E --20---- F | | | 50 | | ---10---- G --10---- H --10--- K Figure 7 The packet BIER header that is sent to D/F/K is encapsulated with 100101000. The path that we want the packet to travel is: E---F---C/ H---D/K. A is an ingress node, so the path list is escapsulated with: level1: E level2: F level3: C/H level4: D/K After OSPF/ISIS calculation, The BIER forwarding tables are: Node A: 000001110 B 000110000 E 111000000 G Node C: 111010011 B 000001000 D 000100000 F Node D: 111110111 C Node E: 111001111 A 000100000 F Node F: 001010011 E Zhang & Wu Expires May 4, 2016 [Page 9] Internet-Draft Designed Routing in BIER Forwarding November 2015 000001100 C 110000000 H Node H: 001011111 G 000100000 F 100000000 K Node K: 011111111 H The header of packet is: 100101000. Now the process on node A is: 1, A looks at the path list, and finds that E is next node, A picks out the routing item which next-hop is E from the forwarding table, get the item"000110000"; Because the node in this level is only F, so we only pick out one item of F. 2, Use the header of packet"100101000" AND the item of E"000110000"; the result is "000100000"; 3, Now INVERSE the result"000100000", will get "111011111". Let we use the header "100101000" AND the "111011111", we get the "Rev- enodes""100001000"; 4, A is ready to forward the packet to E, according to the rule defined in BIER-arch, the header"100101000" AND the item which next- hop is E"000110000", and OR the "Rev-enodes" "100001000", the result is still "100101000", A sends the packet with the header"100101000" to E. The process on node E is: 5, When E receives the packet with header"100101000", E look at the path list, fine that F is next node. E pick out the routing item which next-hop is F from the forwarding table, get the item"000100000". Because the node in this level is only F, so we only pick out one item of F. 6, Use the header of packet"100101000" AND the item of F"000100000"; the result is "000100000"; Zhang & Wu Expires May 4, 2016 [Page 10] Internet-Draft Designed Routing in BIER Forwarding November 2015 7, Now INVERSE the result"000100000", will get "111011111". Let we use the header"100101000" AND the "111011111", we get the "Rev- enodes""100001000"; 8, E is ready to forward the packet to F, according to the rule defined in BIER-arch, the header"100101000" AND the item which next- hop is F"000100000", and OR the "Rev-enodes""100001000", the result is still "100101000", E sends the packet with the header"100101000" to F. The process on node F is: 9, When F receives the packet with header"100101000", at first F find that F itself is one of the egress nodes, after decapsulated and forwarded the packet out of BIER domain, F clears own bit in packet header, the header change to"100001000"; 10, F looks at the path list, find that C and H are next nodes. F picks out the routing item which next-hop is C from the forwarding table, gets the item"000001100"; and F picks out the routing item which next-hop is H from the forwarding table, gets the item"110000000"; 11, Use the header of packet"100001000" AND the item of C"000001100"; the result is "000001000". And we use the header"100001000" AND the item of H"110000000"; the result is "100000000". Because there are two results, so the mix result is "100001000". 12, Now INVERSE the result"100001000", will get "011110111". Let we use the header"100001000" AND the "011110111", we get the "Rev- enodes""000000000"; 13, F is ready to forward the packet to C, according to the rule defined in BIER-arch, the header "100001000" AND the item which next- hop is C"000001100", and OR the "Rev-enodes""000000000", the result is"000001000", F then sends the packet with the header"000001000" to C. 14, similar to 13, F is ready to forward the packet to H, according to the rule defined in BIER-arch, the header"100001000" AND the item which next-hop is H"110000000", and OR the "Rev-enodes" "000000000", the result is"100000000", F then send the packet with the header "100000000" to H. The process on node C is: 15, When the packet which header"000001000" reaches C, C will find that D and K are next nodes. C picks out the routing item which Zhang & Wu Expires May 4, 2016 [Page 11] Internet-Draft Designed Routing in BIER Forwarding November 2015 next-hop is D from the forwarding table, gets the item"000001000". And there is no routing item which next-hop is K in the forwarding table, so we only get one item which next-hop is C. 16, Use the header of packet"000001000" AND the item of C"000001000"; the result is "000001000"; 17, Now INVERSE the result"000001000", will get "111110111". Let we use the header"000001000" AND the "111110111", we get the "Rev- enodes""000000000"; 18, C is ready to forwards the packet to D, according to the rule defined in BIER-arch, the header"000001000" AND the item which next- hop is C"000001000", and OR the "Rev-enodes""000000000", the result is"000001000", C then send the packet with the header"000001000" to D. The process on node H is: 19, similar to the process in node C, node H will send the packet with header"100000000" to K. The process on node D and K are: 20, When the packet reaches D and K, the process is follow the rules defined in BIER-arch, the packet is decapsulated and forwarded out of BIER domain. The brief process is: Node A receives the packet from the control plane. The current level field is 1. Node A gets node E from the designed routing list due to the current level. Then node A lookups the BIER forwarding table and gets the item which the next-hop is node E. Because the shortest path from node A to node D and K is not go through node E, so the node A will get the Rev-enodes that include node D and K due to the steps in section 6.1. Node A forwards the packet to node E, with the bitstring in the BIER header is set to D, F and K, and the current level field is set to 2. Node E receives the packet from node A, finds the items from the BIER forwarding table which the next-hop is node F, do the same steps, set the current level field to 3, and then forwards the packet to F. Node F receives the packet from node E. At first node F decapsulates the packet and forwards it outside of the BIER domain due to the bitstring in the BIER header. Then node F finds the items from the Zhang & Wu Expires May 4, 2016 [Page 12] Internet-Draft Designed Routing in BIER Forwarding November 2015 BIER forwarding table which the next-hop is node C and H, does the same steps in section 6.1, increase the current level value and forward to node C and H. Node C and H receive the packet from node F separately, repeat the steps, increase the current level value to 4 and forwards it to node D and K. Node D and node K receive the packet from node F, repeat the steps, decapsulate the packet and forward it out the BIER domain. 7. Security Considerations For general BIER Security Considerations. 8. IANA Considerations IANA is requested to allocate types in TLVs of BIER header. 9. Normative References [I-D.ietf-bier-architecture] Wijnands, I., Rosen, E., Dolganow, A., Przygienda, T., and S. Aldrin, "Multicast using Bit Index Explicit Replication", draft-ietf-bier-architecture-02 (work in progress), July 2015. [I-D.ietf-bier-mpls-encapsulation] Wijnands, I., Rosen, E., Dolganow, A., Tantsura, J., and S. Aldrin, "Encapsulation for Bit Index Explicit Replication in MPLS Networks", draft-ietf-bier-mpls- encapsulation-02 (work in progress), August 2015. [I-D.ietf-bier-use-cases] Kumar, N., Asati, R., Chen, M., Xu, X., Dolganow, A., Przygienda, T., arkadiy.gulko@thomsonreuters.com, a., Robinson, D., and V. Arya, "BIER Use Cases", draft-ietf- bier-use-cases-01 (work in progress), August 2015. Authors' Addresses Zhang & Wu Expires May 4, 2016 [Page 13] Internet-Draft Designed Routing in BIER Forwarding November 2015 Sandy Zhang ZTE Corporation No. 50 Software Ave, Yuhuatai Distinct Nanjing 210000 China Phone: +86-025-88014634 Email: zhang.zheng@zte.com.cn Bo Wu ZTE Corporation No. 50 Software Ave, Yuhuatai Distinct Nanjing 210000 China Phone: +86-025-88016575 Email: wu.bo@zte.com.cn Zhang & Wu Expires May 4, 2016 [Page 14]