Patent Description:
BIER mechanisms provide optimized forwarding of multicast data packets through a BIER domain. BIER domains may not require the use of a protocol for explicitly building multicast distribution trees. Further, BIER domains may not require intermediate nodes to maintain any per-flow state. BIER is described in further detail in Internet Engineering Task Force (IETF) document Request for Comments (RFC) <NUM> entitled "<NPL>.

Document <NPL>, discusses that BIER is a scalable multicast overlay [RFC8279] that utilizes a routing underlay, e.g., IP, to build up its Bit Index Forwarding Tables (BIFTs). Fast Reroute Extensions for BIER (BIER-FRR) are proposed. This protects BIER traffic after detecting the failure of a link or node in the core of a BIER domain until affected BIFT entries are recomputed after reconvergence of the routing underlay. The BIER-FRR extensions are applied locally at the point of local repair (PLR) and do not introduce any per-flow state.

The disclosed aspects/embodiments provide architectures for supporting BIER-FRR. Each architecture is configured to build a bit index forwarding table (BIFT) that has been enhanced for BIER-FRR. The BIFT that has been enhanced for BIER-FRR is referred to as an enhanced BIFT, an extended BIFT, or a BIFTe. The enhanced BIFT, or BIFTe, provides fast rerouting when network failures (e.g., the failure of a network node or link) are encountered. Thus, packet routing within the BIER domain is improved. The present invention is defined by the attached set of claims. Embodiments and aspects which are not covered by the invention should be considered as examples useful for understanding the invention.

A first aspect relates to a method implemented by a network node in a Bit Index Explicit Replication (BIER) domain, comprising: obtaining, by a control plane of the network node, an internet protocol (IP) loop-free alternate (LFA) from a forwarding information base (FIB) or a routing information base (RIB) through a first interface; using, by the control plane of the network node, the IP LFA to build an enhanced bit index forwarding table (BIFTe) when the IP LFA is an expected type; accessing, by the control plane of the network node, a BIER network topology in a link state database (LSDB) through a second interface, computing an LFA of the expected type, and using the LFA to build the BIFTe when the IP LFA is not of the expected type; updating, by the control plane of the network node, the BIFTe in a data plane of the network node through a third interface; and forwarding, by the data plane of the network node, BIER packets using the BIFTe to avoid a failure.

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the network node comprises a bit forwarding router (BFR) or a bit forwarding egress router (BFER).

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the failure comprises a neighbor network node failure in the BIER domain.

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the IP-LFA is based on an IP network, and wherein the LFA is based on the BIER network topology.

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the BIER packets are forwarded to a backup network node neighbor of the network node using the BIFTe.

The expected type comprises a basic LFA or a topology independent (TI) LFA.

A second aspect relates to a network node in a Bit Index Explicit Replication (BIER) domain, comprising: a memory storing instructions; and a processor coupled to the memory, the processor configured to execute the instructions to cause the network node to: obtain, by a control plane of the network node, an internet protocol (IP) loop-free alternate (LFA) from a forwarding information base (FIB) or a routing information base (RIB) through a first interface; use, by the control plane of the network node, the IP LFA to build an enhanced bit index forwarding table (BIFTe) when the IP LFA is an expected type; access, by the control plane of the network node, a BIER network topology in a link state database (LSDB) through a second interface, compute an LFA of the expected type, and use the LFA to build the BIFTe when the IP LFA is not of the expected type; update, by the control plane of the network node, the BIFTe in a data plane of the network node; and forward, by the data plane of the network node, BIER packets using the BIFTe to avoid a failure.

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the failure comprises a link failure in the BIER domain.

A third aspect relates to a method implemented by a controller of a Bit Index Explicit Replication (BIER) domain, comprising: obtaining an internet protocol (IP) loop-free alternate (LFA) for a network node from a forwarding information base (FIB) or a routing information base (RIB) through a first interface; using the IP LFA to build an enhanced bit index forwarding table (BIFTe) for the network node when the IP LFA is an expected type; accessing a BIER network topology in a link state database (LSDB) through a second interface, computing an LFA of the expected type, and using the LFA to build the BIFTe for the network node when the IP LFA is not of the expected type; and sending the BIFTe for the network node to the network node through a third interface.

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the method is performed for every network node in the BIER domain.

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the BIFTe is sent to a control plane of the network node in a message comprising a Type-Length-Value (TLV).

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the TLV comprises a protection type, a bit forwarding router neighbor (BFR-NBR) of the network node, and a forwarding entry for each bit forwarding egress router (BFER) for forwarding a packet to avoid a failure of the BFR-NBR, and wherein the forwarding entry comprises a BFR identifier (BFR-id) of the BFER, a forwarding bit mask (F-BM), a backup BFR-NBR (BBFR-NBR), a BBFR-NBR Type (BN-Type), and a backup path when the BN-Type is the TI-LFA.

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the protection type has a value of one (<NUM>) to indicate node protection, and wherein the forwarding entry is used to forward the packet to avoid a failure of the BFR-NBR.

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the protection type has a value of two (<NUM>) to indicate link protection, and wherein the forwarding entry is for forwarding the packet to avoid a failure of a link to the BFR-NBR.

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the TLV comprises a protection type and a forwarding entry for each bit forwarding egress router (BFER), and wherein the forwarding entry comprises a BFR identifier (BFR-id) of the BFER, a forwarding bit mask (F-BM), a BFR-NBR, a backup forwarding bit mask (BF-BM), a backup BFR-NBR (BBFR-NBR), a BBFR-NBR Type (BN-Type), and a backup path when the BN-Type is the TI-LFA.

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the protection type has a value of one (<NUM>) indicating node protection, and wherein the BFR-id of the BFER, a bit forwarding router neighbor (BFR-NBR) of the network node, the BF-BM, the BBFR-NBR, the BN-Type, and a backup path in the forwarding entry are used to forward the packet to avoid failure of the BFR-NBR.

Optionally, in any of the preceding aspects, another implementation of the aspect provides that the protection type has a value of two (<NUM>) indicating link protection, and wherein the BFR-id of the BFER, a bit forwarding router neighbor (BFR-NBR) of the network node (BFR-NBR), the BF-BM, the BBFR-NBR, the BN-Type, and a backup path in the forwarding entry are used to forward a packet to avoid a failure of a link to the BFR-NBR.

A further aspect relates to a non-transitory computer readable medium comprising a computer program product for use by a network node in a Bit Index Explicit Replication (BIER) domain, the computer program product comprising computer executable instructions stored on the non-transitory computer readable medium that, when executed by one or more processors, cause the network node to execute the method in any of the disclosed embodiments.

An further aspect relates to a non-transitory computer readable medium comprising a computer program product for use by a controller of a Bit Index Explicit Replication (BIER) domain, the computer program product comprising computer executable instructions stored on the non-transitory computer readable medium that, when executed by one or more processors, cause the controller to execute the method in any of the disclosed embodiments.

The disclosure should in no way be limited to the illustrative implementations, drawings, and techniques illustrated below, including the exemplary designs and implementations illustrated and described herein, but may be modified within the scope of the appended claims.

While there is an architecture for supporting BIER, there is currently no architecture for supporting BIER fast re-route (BIER-FRR). As used herein, fast re-route may also be designated fast reroute, fast re-route, fast ReRoute, and so on.

Disclosed herein are architectures for supporting BIER-FRR. Each architecture is configured to build a bit index forwarding table (BIFT) that has been enhanced for BIER-FRR. The BIFT that has been enhanced for BIER-FRR is referred to as an enhanced BIFT, an extended BIFT, or a BIFTe. The enhanced BIFT, or BIFTe, provides fast rerouting when network failures (e.g., the failure of a network node or link) are encountered. Thus, packet routing within the BIER domain is improved.

<FIG> is a schematic diagram of a BIER topology <NUM> including a BIER domain <NUM>. The BIER domain <NUM> may be part of a larger BIER domain (not shown). As such, the BIER domain <NUM> may be referred to herein as a BIER sub-domain. The BIER domain <NUM> comprises a plurality of network nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. While eight network nodes <NUM>-<NUM> are shown in the BIER domain <NUM>, more or fewer nodes may be included in practical applications.

For ease of discussion, all of the network nodes <NUM>-<NUM> have been given a letter designation. For example, the network node <NUM> has the designation A, the network node <NUM> has the designation B, the network node <NUM> has the designation C, the network node <NUM> has the designation D, the network node <NUM> has the designation E, the network node <NUM> has the designation F, the network node <NUM> has the designation G, and the network node <NUM> has the designation H.

Each of the network nodes <NUM>-<NUM> is a bit forwarding router (BFR). Some of the network nodes, namely the network nodes <NUM>, <NUM>, <NUM>, <NUM> and <NUM>, are disposed at an edge of the BIER domain <NUM>. The network nodes <NUM>, <NUM>, <NUM>, <NUM> and <NUM> receiving multicast packets from outside the BIER domain <NUM> may be referred to as an ingress BFR (BFIR). The network nodes <NUM>, <NUM>, <NUM>, <NUM> and <NUM> transmitting multicast packets out of the BIER domain <NUM> may be referred to as an egress BFR (BFER). Depending on the direction of multicast packet traffic, each of the network nodes <NUM>-<NUM> may function as a BFIR or a BFER.

Each of the network nodes <NUM>, <NUM>, <NUM>, <NUM> and <NUM> may be referred to herein as a destination network node. The network nodes <NUM>, <NUM>, <NUM>, <NUM> and <NUM> have each been assigned a BFR identifier (BFR-id), a set index (SI), and a bitstring. For example, the network node <NUM> has a BFR-id of <NUM>, has a SI of <NUM>, and has a bitstring of <NUM> (collectively illustrated as <NUM> (<NUM>:<NUM>) in <FIG>). The network node <NUM> has a BFR-id of <NUM>, has a SI of <NUM>, and has a bitstring of <NUM> (collectively illustrated as <NUM> (<NUM>:<NUM>)). The network node <NUM> has a BFR-id of <NUM>, has a SI of <NUM>, and has a bitstring of <NUM> (collectively illustrated as <NUM> (<NUM>:<NUM>)). The network node <NUM> has a BFR-id of <NUM>, has a SI of <NUM>, and has a bitstring of <NUM> (collectively illustrated as <NUM> (<NUM>:<NUM>)). The network node <NUM> has a BFR-id of <NUM>, has a SI of <NUM>, and has a bitstring of <NUM> (collectively illustrated as <NUM> (<NUM>:<NUM>)).

Each of the network nodes <NUM>-<NUM> has one or more neighbor nodes. As used herein, a neighbor node refers to a network node that is only one hop away from the network node. For example, network node <NUM> has four neighbor nodes in <FIG>, namely network node <NUM>, network node <NUM>, network node <NUM>, and network node <NUM>. Indeed, each of network node <NUM>, network node <NUM>, network node <NUM>, and network node <NUM> are only one hop away from network node <NUM>. The network nodes <NUM>-<NUM> in <FIG> are coupled to, and communicate with each other, via links <NUM>. The links <NUM> may be wired, wireless, or some combination thereof. Each of the links <NUM> have a cost. For example, the cost of the link between network node <NUM> and network node <NUM> is <NUM> as shown in <FIG>. Likewise, the cost of the link between network node <NUM> and network node <NUM> is <NUM>, the cost of the link between network node <NUM> and network node <NUM> is also <NUM>, the cost of the link between network node <NUM> and network node <NUM> is <NUM> and the cost of the link between network node <NUM> and network node <NUM> is also <NUM>. For any link <NUM> in <FIG> not showing a numerical value next to the link, the default cost is <NUM>. For example, the cost of the link between network node <NUM> and network node <NUM> is <NUM>.

In an embodiment, the BIER domain <NUM> may be controlled by a network controller <NUM> (a. , BIER controller, controller) capable of implementing a routing protocol such as, for example, a Path Computation Element Protocol (PCEP), border gateway protocol (BGP), or Intermediate-System Intermediate System (IS-IS). PCEP is a special set of rules that allows a Path Computation Client (PCC) to request path computations from Path Computation Elements (PCEs). The protocol also lets the PCEs return responses. BGP is a standardized exterior gateway protocol designed to exchange routing and reachability information among autonomous systems (AS) on the Internet. BGP is classified as a path-vector routing protocol, and BGP makes routing decisions based on paths, network policies, or rule-sets configured by a network administrator. IS-IS (also written ISIS) is a routing protocol designed to move information efficiently within a computer network, a group of physically connected computers, or similar devices. IS-IS accomplishes this by determining the best route for data through a packet switching network.

In an embodiment, one or more of the network nodes <NUM>-<NUM> may request that the network controller <NUM> calculate the BIER path through the BIER domain <NUM>. Once calculated, the BIER-TE path may be distributed to one or more of the network nodes <NUM>-<NUM> by the network controller <NUM>.

<FIG> is a schematic diagram of a bit index forwarding table (BIFT) <NUM> of a network node (e.g., network node <NUM>). Each of the network nodes <NUM>-<NUM> in the BIER topology <NUM> in <FIG> derives a BIFT <NUM>.

The BIFT <NUM> depicted in <FIG> is built on the network node <NUM> in <FIG>. As shown, the BIFT <NUM> includes three columns of information. A first column <NUM> includes the BFR-id of each destination network node in the BIER topology <NUM>. A second column <NUM> includes a forwarding bit mask (F-BM). A third column <NUM> in the BIFT <NUM> identifies the neighbor node (BFR-NBR) of the network node <NUM> used to reach the destination network node identified in the first column <NUM>, which is why the neighbor node in the third column <NUM> may also be referred to as the next hop of the network node <NUM>.

Because the destination network nodes with the BFR-id of <NUM>, <NUM>, and <NUM> in the first row <NUM>, the second row <NUM>, and the fourth row <NUM> in the BIFT <NUM> each have an SI of <NUM> and each have the same BFR-NBR of network node C, the F-BM for those rows is a combination of the bitstrings of the destination nodes with the BFR-id of <NUM>, <NUM>, and <NUM>. In particular, a logical OR operation is applied to the bitstrings of the destination nodes with the BFR-id of <NUM>, <NUM>, and <NUM>. A logical OR of the bitstrings <NUM>, <NUM>, and <NUM> results in a F-BM of <NUM> in the first row <NUM>, the second row <NUM>, and the fourth row <NUM> in the BIFT <NUM>.

Because there are no other destination network nodes except for the destination network node E (a. , network node <NUM>) with the BFR-NBR of network node E, the F-BM in the third row <NUM> of the BIFT <NUM> is the same as the bitstring of the destination network node E, which is <NUM>. Likewise, because there are no other destination network nodes except for the destination network node A (a. , network node <NUM>) with the BFR-NBR of network node A, the F-BM in the fifth row <NUM> of the BIFT <NUM> is the same as the bitstring of the destination network node A, which is <NUM>. <FIG> is a schematic diagram of a reference architecture of a network node for BIER fast reroute (BIER-FRR) <NUM> according to an embodiment of the disclosure. For the purpose of discussion, the reference architecture of <FIG> may be referred to herein as a distributed architecture. In an embodiment, the network node is one of the network nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> in the BIER domain <NUM> of <FIG>.

As shown in <FIG>, the reference architecture of the network node for BIER-FRR <NUM> includes an interior gate way protocol (IGP) <NUM>, a BFR control plane <NUM>, a routing table manager (RTM) <NUM>, and a BFR data plane <NUM>. In an embodiment, the reference architecture of the network node for BIER-FRR <NUM> includes additional components in practical applications.

The IGP <NUM> includes a link state database (LSDB) <NUM> that contains the topology of the BIER domain <NUM>. The LSDB <NUM> is built by a network node using information contained in link state announcements (LSAs) received from other network nodes in the BIER domain <NUM>. The LSDB is synchronized between the network nodes within the same area (e.g., the BIER domain <NUM>). In an embodiment, the network node uses the BIER topology in the LSDB <NUM> to compute a loop-free alternative (LFA) to each BFER to build the BIFTe. In an embodiment, the BIFTe comprises a fast reroute BIFT (FRR-BIFT) or an integrated BIFT.

The BFR control plane <NUM> includes a bit index routing table (BIRT)/enhanced BIFT (BIFTe) <NUM>. The BIRT/BIFTe <NUM> stores the routing and/or forwarding entries generated by the network node. As shown, the BFR control plane <NUM> is coupled to the IGP <NUM> by way of the Ia interface. In an embodiment, the Ia interface is bi-directional. A control plane comprises software configured to manage or instruct a data plane. By contrast, the data plane is the part of the software that processes data requests. The data plane is also sometimes referred to as the forwarding plane.

The RTM <NUM> incudes a routing information base (RIB)/forwarding information base (FIB) <NUM>. The RIB/FIB <NUM> contains internet protocol (IP) loop-free alternates (IP-LFAs). The network node uses the IP-LFAs to build the BIFTe. In an embodiment, the network node builds the BIFTe when there is an IP-LFA of an expected type in the RIB/FIB <NUM>. The expected type may be a basic LFA or a topology independent (TI) LFA. As shown, the RTM <NUM> is coupled to the BFR control plane <NUM> by way of the Ib interface. In an embodiment, the Ib interface is bi-directional.

The BFR data plane <NUM> includes a BIFTe <NUM>. The BIFTe contains the forwarding entries built by the network node. As shown, the BFR data plane <NUM> is coupled to the BFR control plane <NUM> by way of the Ic interface. In an embodiment, the Ic interface is bi-directional. In an embodiment, the BFR control plane <NUM> sends the BIFTe to the BFR data plane <NUM>. That is, the BFR data plane <NUM> receives the BIFTe from the BFR control plane <NUM>.

In an embodiment, each network node in the BIER domain <NUM> of <FIG> builds its own BIFTe by utilizing the reference architecture of the network node for BIER-FRR <NUM> depicted in <FIG>. For example, to develop a BIFTe (a. , an LFA-based BIER-FRR), the BFR control plane <NUM> uses three interfaces in <FIG>, namely Ia, Ib, and Ic. Through interface Ib, the BFR control plane <NUM> obtains the IP LFAs in the RIB/FIB <NUM> built by the routing underlay. When an IP LFA is of an expected type, the BFR control plane <NUM> uses the IP LFA to build the BIFTe for the network node. Otherwise (i.e., when the IP LFA is not of an expected type), the BFR control plane <NUM> accesses the BIER network topology in the LSDB <NUM> through interface Ia to compute an LFA of the expected type and uses the LFA to build the BIFTe for the network node. The BIFTe provides a backup next hop to every BFER in the network domain <NUM>. Thus, the BIFTe can be used to support BIER-FRR or BIER fast protection.

Through interface Ic, the control plane <NUM> updates the BIFTe <NUM> of the BFR data plane <NUM>. The BFR data plane <NUM> then forwards packets (e.g., BIER packets, data packets) using the BIFTe to get around a failure in the BIER domain. In an embodiment, the failure is the failure of a network node (e.g., network node <NUM>), the failure of a link (e.g., link <NUM>) coupling the network nodes, or a combination thereof.

<FIG> is a schematic diagram of a reference architecture of a controller for BIER-FRR <NUM> according to an embodiment of the disclosure. For the purpose of discussion, the reference architecture of <FIG> may be referred to herein as a centralized architecture. In an embodiment, the controller comprises controller <NUM> in <FIG>. In an embodiment, the controller is one of the network nodes <NUM>-<NUM> in the BIER domain <NUM> of <FIG>. In another embodiment, the controller is a network node other than the network nodes <NUM>-<NUM> in the BIER domain <NUM> of <FIG>.

As shown in <FIG>, the reference architecture of the controller for BIER-FRR <NUM> includes an interior gate way protocol (IGP) <NUM>, a BIFTs manager <NUM>, a RTM <NUM>, and a storage unit <NUM>. In an embodiment, the reference architecture of the controller for BIER-FRR <NUM> includes additional components in practical applications.

The BIFT manager <NUM> is configured to access the BIER topology in the LSDB <NUM> of the IGP <NUM> through interface Ia'. The BIFT manager <NUM> uses the BIER topology to compute an LFA of an expected type to each BFER for every network node (e.g., for every BFR-i up to n, where i is a positive integer representing one of the network nodes in the BIER domain <NUM> and where n represents the total number of the network nodes in the BIER domain <NUM>).

The BIFT manager <NUM> is also configured to access an IP LFA to each BFER for every network node (e.g., BFR-i) from one of the RIB-i/FIB-i <NUM> in the RTM <NUM> through interface Ib' (where i is an integer from <NUM> to n). The BIFT manager <NUM> uses the IP-LFA to build a BIFTe-i for BFR-i when there is any IP-LFA of an expected type in the RIB-i/FIB-i <NUM>. In an embodiment, the Ib' interface is bi-directional.

The BIFT manager <NUM> is also configured to store routing tables and/or forwarding tables in one of the BIRT-i/BIFTe-i <NUM> of the storage unit <NUM> through interface Ic' (where i is an integer from <NUM> to n). After being stored, the BIFT manager <NUM> may access, update, delete, etc., the routing and/or forwarding tables in the storage unit <NUM>. In an embodiment, the Ic' interface is bi-directional.

The BIFT manager <NUM> is further configured to send the BIFTe-i for every BFR-i to the BFR-i though interface Id. In an embodiment, the Id interface is bi-directional. As such, the BIFT manager <NUM> may receive information from one or more of the network nodes in the BIER domain <NUM> via the interface Id.

In an embodiment, the controller in the BIER domain <NUM> of <FIG> builds BIFTe-i (e.g., a BIFTe for each network node, i) by utilizing the reference architecture of the controller for BIER-FRR <NUM> depicted in <FIG>. For example, to develop the BIFTe-i (a. , an LFA-based BIER-FRR), the controller uses four interfaces: Ia', Ib', Ic' and Id, and every BFR-i control plane (e.g., control plane <NUM>) uses two interfaces: Id and Ic. Through interface Ib', the controller obtains an IP LFA in the RIB-i or FIB-i <NUM> for BFR-i. When the IP LFA is of an expected type, the controller uses the IP LFA to build the BIFTe-i <NUM> for BFR-i. Otherwise (i.e., when the IP LFA is not of an expected type), the controller accesses the BIER network topology in the LSDB <NUM> through interface Ia' to compute an LFA of the expected type and uses the LFA to build the BIFTe-i <NUM> for BFR-i. The controller stores and/or updates the BIFTe-i <NUM> for BFR-i in <NUM> through interface Ic' while building the BIFTe-i <NUM> for BFR-i. Through interface Id, the controller sends the BIFTe-i <NUM> to BFR-i control plane <NUM> of the BFR-i (e.g., one of the network nodes <NUM>-<NUM> in the BIER domain <NUM>).

In an embodiment, the BIFTe for a BFR comprises multiple FRR-BIFTs. A BFR has a FRR-BIFT for each of the BFR's BFR-NBR failures. For example, the network node <NUM> (a. , network node B) has a FRR-BIFT used in case of a failure of the network node <NUM> (a. , network node G), which may be referred to as a FRR-BIFT for G for short. The network node <NUM> also has a FRR-BIFT used in case of a failure of the network node <NUM> (a. , network node C), which may be referred to as a FRR-BIFT for C for short. The network node <NUM> further has a FRR-BIFT used in case of a failure of the network node <NUM> (a. , network node E) and a FRR-BIFT used in case of a failure of the network node <NUM> (a. , network node A). The BFR forwards packets using the FRR-BIFT for X when X failed (e.g., network node B forwards packets using the FRR-BIFT for C when the network node C fails).

<FIG> is a schematic diagram of a FRR BIFT <NUM> of a network node according to an embodiment of the disclosure. Each of the network nodes <NUM>-<NUM> in the BIER topology <NUM> in <FIG> has a FRR-BIFT <NUM> for each of the BFR-NBRs of the network node.

The FRR-BIFT <NUM> depicted in <FIG> is the FRR-BIFT <NUM> of the network node <NUM> (a. , the network node B) in <FIG> for the network node <NUM> (a. , network node C or BFR-NBR <NUM>) of the node <NUM> (a. , network node B). As shown, the FRR-BIFT <NUM> includes four columns <NUM>, <NUM>, <NUM>, <NUM> of information and five rows <NUM>, <NUM>, <NUM>, <NUM>, <NUM> of information. The first column <NUM> is the same as the first column <NUM> in the BIFT <NUM> of <FIG>. A second column <NUM> and a third column <NUM> include an F-BM/backup F-BM (BF-BM) and a BFR-NBR/backup BFR-NBR (BBFR-NBR), respectively, that have been updated as noted below. A fourth column <NUM> includes a BBFR-NBR Type (BN-Type).

Referring to <FIG>, the first row <NUM>, the second row <NUM>, and the fourth row <NUM> each identify the network node <NUM> (referred to herein as BFR-NBR C) in the third column <NUM> of the BIFT <NUM>. Each instance of the BFR-NBR C is changed to a BBFR-NBR in the third column <NUM> of the FRR-BIFT <NUM> in <FIG>. For example, the BFR-NBR C to the BFER with BFR-id <NUM> in the first row of the BIFT <NUM> is changed to the network node <NUM> (a. , BBFR-NBR G) in the first row of the FRR-BIFT <NUM>. The network node <NUM> is a topology independent (TI) LFA to the BFER. The BN-Type in the first row <NUM> of the FRR-BIFT <NUM> is set to TI and a pointer pointing a segment path from the network node <NUM> (a. , the network node B) to the network node <NUM> (a. , network node G). The segment path is from the network node B to the network node A to the network node G.

The BFR-NBR C to the BFER with BFR-id <NUM> in the second row <NUM> of the BIFT <NUM> is changed to the BBFR-NBR E in the second row <NUM> of the FRR-BIFT <NUM>. Network node E is a normal LFA to the BFER. Therefore, the BN-Type in the second row <NUM> of the FRR-BIFT <NUM> is set to Normal.

The BFR-NBR C to the BFER with BFR-id <NUM> in the fourth row <NUM> of the BIFT <NUM> is changed to the BBFR-NBR G in the fourth row <NUM> of the FRR-BIFT <NUM>. Node G is a TI LFA to the BFER. Therefore, the BN-Type in the fourth row <NUM> of the FRR-BIFT <NUM> is set to TI and a pointer pointing a segment path from the network node <NUM> (a. , network node B) to the network node G. The segment path is from the network node B to the network node A to the network node G. The third row <NUM> and the fifth row <NUM> of the fourth column <NUM> in the FRR-BIFT <NUM> are blank.

Because the destination network nodes with the BFR-id of <NUM> and <NUM> in the first row <NUM> and the fourth row <NUM> in the FRR-BIFT <NUM> each have an SI of <NUM> and each have the same BFR-NBR/BBFR-NBR of network node G, the F-BM/BF-BM for those rows is a combination of the bitstrings of the destination nodes with the BFR-id of <NUM> and <NUM>. In particular, a logical OR operation is applied to the bitstrings of the destination nodes with the BFR-id of <NUM> and <NUM>. A logical OR of the bitstrings <NUM> and <NUM> results in an F-BM/BF-BM of <NUM> in the first row <NUM> and the fourth row <NUM> in the FRR-BIFT <NUM>.

Because the destination network nodes with the BFR-id of <NUM> and <NUM> in the second row <NUM> and the third row <NUM> in the FRR-BIFT <NUM> each have an SI of <NUM> and each have the same BFR-NBR/BBFR-NBR of network node E, the F-BM/BF-BM for those rows is a combination of the bitstrings of the destination nodes with the BFR-id of <NUM> and <NUM>. In particular, a logical OR operation is applied to the bitstrings of the destination nodes with the BFR-id of <NUM> and <NUM>. A logical OR of the bitstrings <NUM> and <NUM> results in an F-BM/BF-BM of <NUM> in the second row <NUM> and the third row <NUM> in the FRR-BIFT <NUM>.

Because there are no other destination network nodes except for the destination network node A (a. , network node <NUM>) with the BFR-NBR/BBFR-NBR of network node A, the F-BM/BF-BM in the fifth row 518of the FRR-BIFT <NUM> is the same as the bitstring of the destination network node A, which is <NUM>. Once the FRR-BIFT <NUM> is derived as discussed above, a packet (e.g., a multicast packet, a BIER packet) can be routed in accordance with the FRR-BIFT <NUM> when the neighbor node C has failed.

<FIG> is a schematic diagram of an integrated BIFT <NUM> of a network node according to an embodiment of the disclosure. In an embodiment, the BIFTe for a BFR as discussed herein is an integrated BIFT <NUM> of the BFR. The integrated BIFT <NUM> combines a BIFT (e.g., BIFT <NUM>) and FRR-BIFTs (e.g., FRR-BIFR <NUM>) of the BFR. In an embodiment, each of the network nodes <NUM>-<NUM> in the BIER topology <NUM> in <FIG> has an integrated BIFT <NUM>.

The integrated BIFT <NUM> depicted in <FIG> is the integrated BIFT <NUM> of the network node <NUM> (a. , the network node B) in <FIG>. As shown, the integrated BIFT <NUM> includes seven columns <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> of information as well as five rows <NUM>, <NUM>, <NUM>, <NUM>, <NUM> of information. The first three columns <NUM>, <NUM>, and <NUM> are the same as the first three columns <NUM>, <NUM>, and <NUM> in the BIFT <NUM> of <FIG>. The last three columns <NUM>, <NUM>, and <NUM> are obtained by combining the last three columns of multiple FRR-BIFTs of the network node B that have the BF-BM, BBFR-NBR, and BN-Type values.

For example, the first, second, and fourth rows <NUM>, <NUM>, <NUM> in FRR-BIFT <NUM> of the network node B for C have the BF-BM, BBFR-NBR, and BN-Type values. The last three columns <NUM>, <NUM>, and <NUM> of the first, second, and fourth rows <NUM>, <NUM>, and <NUM> in the BIFT <NUM> are the same as the last three columns <NUM>, <NUM>, <NUM> of the first, second, and fourth rows <NUM>, <NUM>, <NUM> in the FRR-BIFT <NUM>.

The fourth column <NUM> includes a Backup Active (BA) flag. When a BFR-NBR fails, the BA flag in the row with the BFR-NBR is set to one to indicate that the last three columns <NUM>, <NUM>, <NUM> in the row are used to forward the packet with the BFER in the row.

In an embodiment, a number of protocol extensions used with the centralized architecture are discussed. The protocol extensions are implemented using type length values (TLVs) and sub-TLVs.

<FIG> is a schematic diagram of an Internet Protocol version <NUM> (IPv4) forwarding entries TLV <NUM> for the FRR BIFT according to an embodiment of the disclosure. In an embodiment, the TLV <NUM> is used for node protection. That is, the TLV <NUM> is used for protection upon failure of a network node. The IPv4 forwarding TLV <NUM> includes a type field <NUM>, a length field <NUM>, a protection type (Pr-type) field <NUM>, a bitstring length (BSL) field <NUM>, a set identifier (SI) field <NUM> (a. , a site index field), a number of entries field <NUM>, a BFR-NBR field <NUM>, a BFR-id field <NUM>, a F-BM field <NUM>, a BBFR-NBR field <NUM>, a BN type field <NUM>, and a SID list sub-TLV field <NUM>. The BFR-id field <NUM>, the F-BM field <NUM>, the BBFR-NBR field <NUM>, the BN type field <NUM>, and the SID list sub-TLV field <NUM> may be collectively referred to as the forwarding entry <NUM> (e.g., the forwarding entry for BFR-id-<NUM>,. the forwarding entry for BFR-id-n).

The type field <NUM> includes a value indicating the type of TLV <NUM>. The value is to be determined (TBD). The length field <NUM> includes a value indicating a length of the TLV <NUM>. The protection type field <NUM> includes a value indicating a protection type (e.g., value <NUM> for node protection and value <NUM> for link protection). The BSL field <NUM> includes a value indicating a length of the F-BM and the BF-BM. The SI field <NUM> includes a value indicating the SI (e.g., <NUM>) of the BFR. The number of entries field <NUM> includes a value indicating the number of forwarding entries included in the TLV <NUM>. The BFR-NBR field <NUM> is <NUM> bytes and includes a value indicating the failed BFR-NBR when the protection type is node protection and the failed link to the BFR-NBR when the protection type is link protection.

The BFR-id field <NUM> includes a value indicating a BFR-id (e.g., BFR-id-<NUM>,. The F-BM field <NUM> includes a value indicating the F-BM. The BBFR-NBR field <NUM> is <NUM> bytes and includes a value indicating the BBFR-NBR. The BN-Type field <NUM> includes a value indicating the BN-type. The SID list sub-TLV field <NUM> includes a number of SIDs for a backup path to the BBFR-NBR when the BN-Type is TI-LFA.

<FIG> is a schematic diagram of an Internet Protocol version <NUM> (IPv6) forwarding entries TLV <NUM> for the FRR BIFT according to an embodiment of the disclosure. In an embodiment, the TLV <NUM> is used for node protection. That is, the TLV <NUM> is used for protection upon failure of a network node. The IPv6 forwarding TLV <NUM> includes a type field <NUM>, a length field <NUM>, a Pr-type field <NUM>, a BSL field <NUM>, an SI field <NUM>, a number of entries field <NUM>, a BFR-NBR field <NUM>, a BFR-id field <NUM>, a F-BM field <NUM>, a BBFR-NBR field <NUM>, a BN type field <NUM>, and a SID list sub-TLV field <NUM>. The BFR-id field <NUM>, the F-BM field <NUM>, the BBFR-NBR field <NUM>, the BN type field <NUM>, and the SID list sub-TLV field <NUM> may be collectively referred to as the forwarding entry <NUM> (e.g., the forwarding entry for BFR-id-<NUM>,. the forwarding entry for BFR-id-n).

The type field <NUM> includes a value indicating the type of TLV <NUM>. The value is to be determined (TBD). The length field <NUM> includes a value indicating a length of the TLV <NUM>. The protection type field <NUM> includes a value indicating a protection type (e.g., value <NUM> indicating node protection and value <NUM> indicating link protection). The BSL field <NUM> includes a value indicating a length of the F-BM and the BF-BM. The SI field <NUM> includes a value indicating the SI (e.g., <NUM>) of the BFR. The number of entries field <NUM> includes a value indicating the number of forwarding entries included in the TLV <NUM>. The BFR-NBR field <NUM> is <NUM> bytes and includes a value indicating the failed BFR-NBR when the protection type is node protection and the failed link to the BFR-NBR when the protection type is link protection. The BFR-id field <NUM> includes a value indicating a BFR-id (e.g., BFR-id-<NUM>,. The F-BM field <NUM> includes a value indicating the F-BM. The BBFR-NBR field <NUM> is <NUM> bytes and includes a value indicating the BBFR-NBR.

The BN-Type field <NUM> includes a value indicating the BN-type. The SID list sub-TLV field <NUM> includes a number of SIDs for a backup path to the BBFR-NBR when the BN-Type is TI-LFA.

<FIG> is a schematic diagram of an IPv4 forwarding entries TLV <NUM> for the integrated BIFT according to an embodiment of the disclosure. In an embodiment, the TLV <NUM> is used for link protection. That is, the TLV <NUM> is used for protection upon failure of a link. The IPv4 forwarding TLV <NUM> includes a type field <NUM>, a length field <NUM>, a Pr-type field <NUM>, a BSL field <NUM>, an SI field <NUM>, a number of entries field <NUM>, a BFR-id field <NUM>, a F-BM field <NUM>, a BFR-NBR field <NUM>, a BF-BM field <NUM>, a BBFR-NBR field <NUM>, a BN type field <NUM>, and a SID list sub-TLV field <NUM>. The BFR-id field <NUM>, the F-BM field <NUM>, the BFR-NBR field <NUM>, the BF-BM field <NUM>, the BBFR-NBR field <NUM>, the BN type field <NUM>, and the SID list sub-TLV field <NUM> may be collectively referred to as the forwarding entry <NUM> (e.g., the forwarding entry for BFR-id-<NUM>,. the forwarding entry for BFR-id-n).

The type field <NUM> includes a value indicating the type of TLV <NUM>. The value is to be determined (TBD). The length field <NUM> includes a value indicating a length of the TLV <NUM>. The protection type field <NUM> includes a value indicating a protection type (e.g., value <NUM> indicating node protection and value <NUM> indicating link protection). The BSL field <NUM> includes a value indicating a length of the F-BM and the BF-BM. The SI field <NUM> includes a value indicating the SI (e.g., <NUM>) of the BFR. The number of entries field <NUM> includes a value indicating the number of forwarding entries included in the TLV <NUM>.

The BFR-id field <NUM> includes a value indicating a BFR-id (e.g., BFR-id-<NUM>,. The F-BM field <NUM> includes a value indicating the F-BM. The BFR-NBR field <NUM> is <NUM> bytes and includes a value indicating the BFR-NBR. The BF-BM field <NUM> include a value indicating the BF-BM.

The BBFR-NBR field <NUM> is <NUM> bytes and includes a value indicating the BBFR-NBR. The BN-Type field <NUM> includes a value indicating the BN-type. The SID list sub-TLV field <NUM> includes a number of SIDs for a backup path to the BBFR-NBR when the BN-Type is TI-LFA.

<FIG> is a schematic diagram of an IPv6 forwarding entries TLV <NUM> for the integrated BIFT according to an embodiment of the disclosure. In an embodiment, the TLV <NUM> is used for link protection. That is, the TLV <NUM> is used for protection upon failure of a link. The IPv4 forwarding TLV <NUM> includes a type field <NUM>, a length field <NUM>, a Pr-type field <NUM>, a BSL field <NUM>, an SI field <NUM>, a number of entries field <NUM>, a BFR-id field <NUM>, a F-BM field <NUM>, a BFR-NBR field <NUM>, a BF-BM field <NUM>, a BBFR-NBR field <NUM>, a BN type field <NUM>, and a SID list sub-TLV field <NUM>. The BFR-id field <NUM>, the F-BM field <NUM>, the BFR-NBR field <NUM>, the BF-BM field <NUM>, the BBFR-NBR field <NUM>, the BN type field <NUM>, and the SID list sub-TLV field <NUM> may be collectively referred to as the forwarding entry <NUM> (e.g., the forwarding entry for BFR-id-<NUM>,. the forwarding entry for BFR-id-n).

<FIG> is a schematic diagram of a segment identifier (SID) list sub-TLV <NUM> for segment routing multiprotocol label switching (SR-MPLS) according to an embodiment of the disclosure. The SID sub-TLV <NUM> may be included in one of the SID list fields <NUM>, <NUM>, <NUM>, and <NUM> noted above. The SID sub-TLV <NUM> includes a type field <NUM>, a length field <NUM>, a reserved field (Resv) <NUM>, an SIDs type field <NUM>, and one or more SIDs fields <NUM>.

The type field <NUM> includes a value indicating the type of sub-TLV <NUM>. The value is to be determined (TBD). The length field <NUM> includes a value indicating a length of the sub-TLV <NUM>. The reserved field <NUM> is reserved for later use. The SIDs type field <NUM> includes a value indicating a SIDs type (ST) in the TLV <NUM>. When the value is one, each of the SIDs in the SIDs field <NUM> is a label, which is represented by the twenty (<NUM>) rightmost octets. When the value is two, each of the SIDs in the SIDs field <NUM> is a <NUM>-bit SID. Thus, the SIDs field <NUM> may be either <NUM> or <NUM> bytes.

<FIG> is a schematic diagram of an SID list sub-TLV <NUM> for segment routing over IPv6 (SRv6) according to an embodiment of the disclosure. The SID sub-TLV <NUM> may be included in one of the SID list fields <NUM>, <NUM>, <NUM>, and <NUM> noted above. The SID sub-TLV <NUM> includes a type field <NUM>, a length field <NUM>, and one or more SIDs fields <NUM>.

The type field <NUM> includes a value indicating the type of sub-TLV <NUM>. The value is to be determined (TBD). The length field <NUM> includes a value indicating a length of the sub-TLV <NUM>. Each of the SIDs in the SIDs field <NUM> is a <NUM>-bit value (i.e., <NUM> byte) SID (e.g., SRv6 SID).

<FIG> is a method <NUM> implemented by a network node in the BIER domain according to an embodiment of the disclosure. The network node may be any of the network nodes <NUM>-<NUM> and the BIER domain may be the BIER domain <NUM>. In an embodiment, the network node comprises a BFR or a BFER.

In block <NUM>, the control plane of the network node obtains an IP LFA from a FIB or a RIB through a first interface (e.g., Ib). The first interface is a wired or wireless communication channel that couples the control plane <NUM> and the RTM <NUM>. In an embodiment, the IP-LFA is based on an IP network.

In block <NUM>, the control plane of the network node uses the IP LFA to build BIFTe when the IP LFA is an expected type. In an embodiment, the expected type comprises basic LFA or TI LFA. In block <NUM>, the control plane of the network node accesses a BIER network topology in a LSDB through a second interface (e.g., Ia), computes an LFA of the expected type, and uses the LFA to build the BIFTe when the IP LFA is not of the expected type. The second interface is a wired or wireless communication channel that couples the control plane <NUM> and the IGP <NUM>. In an embodiment, the LFA is based on the BIER network topology.

In block <NUM>, the control plane of the network node updates the BIFTe in a data plane of the network node through a third interface (e.g., Ic). The third interface is a wired or wireless communication channel that couples the control plane <NUM> and the BFR data plane <NUM>.

In block <NUM>, the data plane of the network node forwards BIER packets using the BIFTe to avoid a failure. In an embodiment, the failure comprises a neighbor network node failure in the BIER domain. In an embodiment, the failure comprises a link failure in the BIER domain. In an embodiment, the BIER packets are forwarded to a backup network node neighbor of the network node using the BIFTe.

<FIG> is a method <NUM> implemented by a controller of the BIER domain according to an embodiment of the disclosure. The controller may be the controller <NUM> of the BIER domain <NUM>. In an embodiment, the controller comprises a BIER controller.

In block <NUM>, the controller obtains an IP LFA for a network node from a FIB or a RIB through a first interface (e.g., Ib'). The first interface is a wired or wireless communication channel that couples the BIFT manager <NUM> and the RTM <NUM>. In an embodiment, the network node comprises a BFR or a BFER.

In block <NUM>, the controller uses the IP LFA to build a BIFTe for the network node when the IP LFA is an expected type. In an embodiment, the IP-LFA is based on an IP network. In an embodiment, the expected type comprises a basic LFA or a TI LFA.

In block <NUM>, the controller accesses a BIER network topology in an LSDB through a second interface (e.g., Ia'), computes an LFA of the expected type, and uses the LFA to build the BIFTe for the network node when the IP LFA is not of the expected type. The second interface is a wired or wireless communication channel that couples the BIFT manager <NUM> and the IGP <NUM>. In an embodiment, the LFA is based on the BIER network topology.

In block <NUM>, the controller sends the BIFTe for the network node to the network node through a third interface (e.g., Id). The third interface is a wired or wireless communication channel that couples the BIFT manager <NUM> to one or more of the network nodes <NUM>-<NUM>. In an embodiment, the method <NUM> is performed for every network node in the BIER domain.

In an embodiment, the BIFTe is sent to a control plane of the network node in a message comprising a TLV. In an embodiment, the TLV comprises a protection type, a BFR-NBR of the network node, and a forwarding entry for each BFER for forwarding a packet to avoid a failure of the BFR-NBR, and wherein the forwarding entry comprises a BFR-id of the BFER, a F-BM, a BBFR-NBR, a BN-Type, and a backup path when the BN-Type is the TI-LFA.

In an embodiment, the protection type has a value of one (<NUM>) to indicate node protection, and wherein the forwarding entry is used to forward the packet to avoid a failure of the BFR-NBR. In an embodiment, the protection type has a value of two (<NUM>) to indicate link protection, and wherein the forwarding entry is for forwarding the packet to avoid a failure of a link to the BFR-NBR.

In an embodiment, the TLV comprises a protection type and a BFER, and wherein the forwarding entry comprises a BFR-id of the BFER, a F-BM, a BBFR-NBR, a BF-BM, a BBFR-NBR, a BN-Type, and a backup path when the BN-Type is the TI-LFA.

In an embodiment, the protection type has a value of one (<NUM>) indicating node protection, and wherein the BFR-id of the BFER, a bit forwarding router neighbor (BFR-NBR) of the network node, the BF-BM, the BBFR-NBR, the BN-Type, and a backup path in the forwarding entry are used to forward the packet to avoid failure of the BFR-NBR. In an embodiment, the protection type has a value of two (<NUM>) indicating link protection, and wherein the BFR-id of the BFER, a bit forwarding router neighbor (BFR-NBR) of the network node (BFR-NBR), the BF-BM, the BBFR-NBR, the BN-Type, and a backup path in the forwarding entry are used to forward a packet to avoid a failure of a link to the BFR-NBR.

<FIG> is a schematic diagram of a network apparatus <NUM> (e.g., a network node, a controller, a neighbor node, etc.). The network apparatus <NUM> is suitable for implementing the disclosed embodiments as described herein. The network apparatus <NUM> comprises ingress ports/ingress means <NUM> and receiver units (Rx)/receiving means <NUM> for receiving data; a processor, logic unit, or central processing unit (CPU)/processing means <NUM> to process the data; transmitter units (Tx)/transmitting means <NUM> and egress ports/egress means <NUM> for transmitting the data; and a memory/memory means <NUM> for storing the data. The network apparatus <NUM> may also comprise optical-to-electrical (OE) components and electrical-to-optical (EO) components coupled to the ingress ports/ingress means <NUM>, the receiver units/receiving means <NUM>, the transmitter units/transmitting means <NUM>, and the egress ports/egress means <NUM> for egress or ingress of optical or electrical signals.

The processor/processing means <NUM> is implemented by hardware and software. The processor/processing means <NUM> may be implemented as one or more CPU chips, cores (e.g., as a multi-core processor), field-programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), and digital signal processors (DSPs). The processor/processing means <NUM> is in communication with the ingress ports/ingress means <NUM>, receiver units/receiving means <NUM>, transmitter units/transmitting means <NUM>, egress ports/egress means <NUM>, and memory/memory means <NUM>. The processor/processing means <NUM> comprises a BIER fast reroute module <NUM>. The BIER fast reroute module <NUM> is able to implement the methods disclosed herein. The inclusion of the BIER fast reroute module <NUM> therefore provides a substantial improvement to the functionality of the network apparatus <NUM> and effects a transformation of the network apparatus <NUM> to a different state. Alternatively, the BIER fast reroute module <NUM> is implemented as instructions stored in the memory/memory means <NUM> and executed by the processor/processing means <NUM>.

Claim 1:
A method (<NUM>) implemented by a network node (<NUM>-<NUM>, <NUM>) supporting fast reroute, FRR, in a Bit Index Explicit Replication, BIER, domain (<NUM>), comprising:
obtaining (<NUM>), by a control plane (<NUM>, <NUM>) of the network node (<NUM>-<NUM>, <NUM>), an internet protocol, IP, loop-free alternate, LFA, from a forwarding information base (<NUM>, <NUM>, <NUM>, <NUM>), FIB, or a routing information base, RIB, through a first interface (Ib, Ib');
using (<NUM>), by the control plane (<NUM>, <NUM>) of the network node (<NUM>-<NUM>, <NUM>), the IP LFA to build an enhanced bit index forwarding table (<NUM>, <NUM>), BIFTe, when the IP LFA is an expected type, the expected type comprises a basic LFA or a topology independent, TI, LFA;
accessing (<NUM>), by the control plane (<NUM>, <NUM>) of the network node (<NUM>-<NUM>, <NUM>), a BIER network topology (<NUM>) in a link state database (<NUM>, <NUM>, <NUM>, <NUM>), LSDB, through a second interface (Ia, Ia') different from the first interface (Ib, Ib'), computing an LFA of the expected type, and using the LFA to build the BIFTe (<NUM>, <NUM>) when the IP LFA is not of the expected type;
updating (<NUM>), by the control plane (<NUM>, <NUM>) of the network node (<NUM>-<NUM>, <NUM>), the BIFTe (<NUM>, <NUM>) in a data plane (<NUM>, <NUM>) of the network node (<NUM>-<NUM>, <NUM>) through a third interface (Ic, Ic') different from the first interface (Ib, Ib') and the second interface (Ia, Ia'); and
forwarding (<NUM>), by the data plane (<NUM>, <NUM>) of the network node (<NUM>-<NUM>, <NUM>), BIER packets using the BIFTe (<NUM>, <NUM>) to get around a failure in the BIER domain (<NUM>).