Fast reroute using loop free alternate next hops for multipoint label switched paths

The techniques of this disclosure provide local protection for network traffic in multipoint label switched paths (LSPs) due to link or node failure using loop-free alternate (LFA) next hops. The techniques include establishing a vanilla or point-to-point (P2P) LSP with LFA next hops between routers of a multipoint LSP for use in the event of link or node failure in the multipoint LSP. Upon a failure, the multicast traffic is tunneled between the routers using the P2P LSP with LFA to an alternate next hop with an associated label stack. The techniques of this disclosure define the label stack as including a P2P LSP label as well as a multipoint LSP label. In this way, the P2P LSP with LFA may be used for fast reroute (FRR) of traffic in the multipoint LSP until a convergence process completes for a new multipoint branch of the multipoint LSP.

TECHNICAL FIELD

The disclosure relates to computer networks and, more particularly, to forwarding network traffic within computer networks.

BACKGROUND

Routing devices within a network, often referred to as routers, maintain routing information that describe available routes through the network. Upon receiving an incoming packet, the router examines information within the packet and forwards the packet in accordance with the routing information. In order to maintain an accurate representation of the network, routers exchange routing information in accordance with one or more defined routing protocol, such as a link state protocol Interior Gateway Protocol (IGP).

The connection between two devices on a network is generally referred to as a link. A link state protocol, as one type of IGP, allows routers to exchange and accumulate information describing the various links within the network. With a typical link state routing protocol, the routers exchange information related to available interfaces, metrics and other variables associated with network links. This allows a router to construct its own topology or map of the network. Some examples of link state protocols include the Open Shortest Path First (OSPF) protocol and the Intermediate-System to Intermediate System (IS-IS) protocol.

Upon failure of a link or failure of a node interfacing with the link, routers in the network transmit new connectivity information to neighboring devices, allowing each device to update its local routing table. When a link or node in the network fails, routers using traditional link state protocols may take a long time to adapt their forwarding tables in response to the topological change resulting from link and node failures in the network. The process of adapting the forwarding tables is known as convergence. This time delay occurs because recovery from a failure requires each router to re-compute the shortest path algorithm to calculate the next hop for the affected routers in the network. Until the next hops are re-computed, traffic being sent toward the failed link or node may be dropped.

One approach to reduce failure recovery time is to select an alternate next-hop in addition to the best next-hop for a destination. Along with the best next-hop, the alternate next-hop is installed in the packet forwarding engine. When a link or node failure occurs, the router uses the alternate next-hop for packet forwarding until the shortest path algorithm has re-computed the next hops for the updated network topology and installed the re-computed next hops in the packet forwarding engine.

SUMMARY

In general, the techniques of this disclosure provide local protection for network traffic in multipoint label switched paths (LSPs) due to link or node failure using loop-free alternate (LFA) next hops. The multipoint LSPs may include point-to-multipoint (P2MP) LSPs or multipoint-to-multipoint (MP2MP) LSPs. In this disclosure, the multipoint LSPs may be established using multipoint extensions for the Label Distribution Protocol (mLDP). The techniques include establishing a vanilla or point-to-point (P2P) LSP with LFA next hops between routers of a multipoint LSP for use in the event of link or node failure in the multipoint LSP. Upon a failure, the multicast traffic is tunneled between the routers using the P2P LSP with LFA to an alternate next hop with a label stack. The techniques of this disclosure define the label stack as including a P2P LSP label as well as a multipoint LSP label. In this way, the P2P LSP with LFA may be used for fast reroute (FRR) of traffic in the multipoint LSP until a convergence process completes for a new multipoint branch of the multipoint LSP.

In the case of link protection for multipoint LSPs, the techniques include establishing a targeted adjacency session between routers connected by a protected link of a multipoint LSP. The upstream router installs an LFA next hop in its forwarding table with a label stack including a targeted adjacency session label for the multipoint LSP and a P2P LSP label. In the case of node protection for multipoint LSPs, the techniques include extensions to mLDP that enable allocation of next next hop labels from a downstream router in a multipoint LSP. In this way, an upstream router may receive both a next hop label for a downstream peer router and a next next hop label for a subsequent downstream router of the multipoint LSP. The upstream router then installs an LFA next hop in its forwarding table with a label stack including the next next hop label for the multipoint LSP and a P2P LSP label.

In one example, the disclosure is directed to a method comprising establishing, with an upstream router, a P2P LSP to a downstream router, wherein the upstream router and the downstream router are included in a multipoint LSP, installing an alternate next hop with an associated label stack into forwarding information of the upstream router, wherein the label stack includes a P2P LSP label and a multipoint LSP label, forwarding multicast traffic from the upstream router toward the downstream router along the multipoint LSP, and, upon detecting a failure in the multipoint LSP, tunneling the multicast traffic from the upstream router toward the downstream router along the P2P LSP to the alternate next hop with the associated label stack.

In another example, the disclosure is directed to an upstream router of a multipoint LSP comprising forwarding information that stores a primary next hop for the multipoint LSP and an alternate next hop with an associated label stack for a P2P LSP. The upstream router also comprises a control unit configured to establish the P2P LSP to a downstream router of the multipoint LSP, install the alternate next hop with the associated label stack into the forwarding information, wherein the label stack includes a P2P LSP label and a multipoint LSP label, forward multicast traffic toward the downstream router along the multipoint LSP, and upon detecting a failure in the multipoint LSP, tunnel the multicast traffic toward the downstream router along the P2P LSP to the alternate next hop with the associated label stack.

In a further example, the disclosure is directed to a computer-readable storage medium comprising program instructions for causing a programmable processor to establish, with an upstream router, a P2P LSP to a downstream router, wherein the upstream router and the downstream router are included in a multipoint LSP, install an alternate next hop with an associated label stack into forwarding information of the upstream router, wherein the label stack includes a P2P LSP label and a multipoint LSP label, forward multicast traffic from the upstream router toward the downstream router along the multipoint LSP, and upon detecting a failure in the multipoint LSP, tunnel the multicast traffic from the upstream router toward the downstream router along the P2P LSP to the alternate next hop with the associated label stack.

DETAILED DESCRIPTION

FIG. 1is a block diagram illustrating an example network10including a multipoint Label Switched Path (LSP)12established between root router14and leaf routers18A and18B (“leaf routers18”), configured to provide link protection using loop-free alternate (LFA) next hops. In the illustrated example ofFIG. 1, the techniques of this disclosure provide local protection for multicast traffic on link20between an upstream transit router15and a downstream transit router16of multipoint LSP12.

The techniques include establishing a vanilla or point-to-point (P2P) LSP with LFA next hops24between upstream router15and downstream router16to provide fast reroute (FRR) of multicast traffic in the event of a failure of link20. LSP with LFA next hops24provides an alternate path for the multicast traffic around at least a protected portion of multipoint LSP12. The alternate path includes LFA next hops, meaning that the next hops of the alternate path will not send the traffic back through the protected portion of multicast LSP12. Upon the failure of link20, the multicast traffic is tunneled between upstream router15and downstream router16along P2P LSP with LFA24to an LFA next hop with a label stack including a P2P LSP outer label as well as a multipoint LSP inner label stored in forwarding information of transit router15.

In some examples, multipoint LSP12may comprise a path through network10to connect remotely located networks or devices (not shown inFIG. 1). For example, a source network may be connected to root router14and subscriber networks may be connected to leaf routers18. The source network may comprise any public or private network or the Internet that provides multicast traffic to root router14in network10. The subscriber networks may include local area networks (LANs) or wide area networks (WANs) that comprise a plurality of subscriber devices. The subscriber devices may include personal computers, laptops, workstations, personal digital assistants (PDAs), wireless devices, network-ready appliances, file servers, print servers or other devices that access network10.

Routers14-18in network10each maintain routing information that describes available routes through network10. Upon receiving an incoming packet, each of the routers examines information within the packet and forwards the packet in accordance with the routing information. In order to maintain an accurate representation of network10, the routers exchange routing information, e.g., bandwidth availability of links, in accordance with a defined routing protocol, such as an Interior Gateway Protocol (IGP). For example, each of routers14-18may use a link-state routing protocol, such as the Open Shortest Path First (OSPF) protocol or the Intermediate-System to Intermediate System (IS-IS) protocol, to exchange link-state routing information to learn the topology of network10. Further details regarding OSPF are found in Moy, J., “OSPF Version 2,” RFC 2328, April 1998, the entire contents of which are incorporated by reference herein. Further details regarding IS-IS are found in Callon, R., “Use of OSI IS-IS for Routing in TCP/IP and Dual Environments,” RFC 1195, December 1990, the entire contents of which are incorporated by reference herein.

In the example ofFIG. 1, multipoint LSP12through network10conforms to a Multi-Protocol Label Switching (MPLS) tunnel and, specifically, comprises a Point-to-Multipoint (P2MP) Label Distribution Protocol (LDP) LSP. In other examples, multipoint LSP12may comprise a Multipoint-to-Multipoint (MP2MP) LDP LSP. Routers14,15,16and18utilize multicast extensions to the LDP (mLDP) to establish multipoint LSP12and forward multicast traffic over multipoint LSP12. More information about mLDP may be found in Minei, I., “Label Distribution Protocol Extensions for Point-to-Multipoint and Multipoint-to-Multipoint Label Switched Paths,” draft-ietf-mpls-ldp-p2mp-15, Aug. 4, 2011, the entire contents of which are incorporated by reference herein.

In the illustrated example ofFIG. 1, root router14establishes multipoint LSP12through network10from root router14to leaf routers18A and18B. According to the mLDP, the setup of multipoint LSP12is initiated by leaf routers18and propagated upstream along the shortest upstream path toward root router14. Downstream routers15,16and18may calculate the shortest upstream path toward root router14on a hop-by-hop basis based on the routing information maintained by the routers. In addition, mLDP Label Mapping Messages are downstream-assigned such that each downstream router assigns itself a label. Each downstream router then sends an mLDP Label Mapping Message including the assigned label and a multipoint forwarding equivalence class (FEC) identifying multipoint LSP12to the selected upstream router for multipoint LSP12.

In the illustrated example ofFIG. 1, after receiving the downstream-assigned label, each of upstream routers14,15and16associates the label with a next hop used to transmit packets on multipoint LSP12through network10. Each of routers14,15and16may install the next hop for multipoint LSP12with the associated label in forwarding information of the router. Upstream routers14,15and16then use the next hops with the assigned labels to forward multicast traffic hop-by-hop along multipoint LSP12to leaf routers18. In multipoint LSP12, transit router16acts as a branch router to replicate the multicast traffic and send one copy of the traffic to leaf router18A and another copy of the traffic to leaf router18B.

In the event of a link failure in multipoint LSP12, multicast traffic can no longer reach leaf routers18using multipoint LSP12according to the next hops previously installed in the routers because the traffic would be dropped at the failed link. For example, after a failure of link20, any multicast traffic forwarded from transit router15to transit router16over link20to the next hop for multipoint LSP12would be dropped. The failure of link20detaches the entire multipoint LSP branch beginning at transit router16from the upstream portion of multipoint LSP12until the routing protocol on transit router16converges to determine a new shortest upstream path toward root router14. In addition to multipoint LSP12, any other LSPs that use failed link20to forward traffic between transit router15and transit router16will also drop the traffic.

When the link failure occurs, transit router16, first determines that the upstream interface to router15is down, and then recalculates a new shortest upstream path toward root router14for multipoint LSP12. As an example, it may take approximately 300-400 milliseconds (ms) for transit router16to determine that the upstream interface to router15is down. It may take another approximately 400 ms for the routing protocol on transit router16to converge on the new shortest upstream path, and for mLDP to send new label assignments to the new upstream router. In addition, it may take more than several seconds for new upstream router17, for example, to receive this label and program forwarding for P2MP LSP12. Router17will then select router15as its upstream router and send a label assignment to router15for P2MP LSP12. Finally, it may take more than several seconds for upstream router15to receive the new label from router17and program forwarding for P2MP LSP12. Afterwards, the traffic will start flowing on the new path. Until new paths are re-calculated, any traffic being sent on failed link20will be dropped.

In the case of a unicast or P2P LSP, local link protection may be provided at an upstream router by selecting an alternate path to reach a downstream router of the unicast LSP in the event that the protected link between the routers goes down. The alternate path may comprise an alternate unicast LSP. The upstream router may be referred to as the point of local repair (PLR) router, which is capable of redirecting traffic onto the alternate path, and the downstream router may be referred to at the merge point (MP) router where the alternate path merges with the primary unicast LSP.

The PLR router may install both a primary next hop to reach the MP using the primary unicast LSP and an alternate next hop toward the MP using the alternate path. In some cases, the alternate path may include one or more next hops between the PLR router and the MP router. The alternate path must include loop-free alternate (LFA) next hops, meaning that the next hops of the alternate path will not send the traffic to the MP router on a path that goes back through PLR router and onto the protected link.

When the protected link fails, the PLR router selects the alternate next hop to forward unicast traffic using the alternate path to the MP router to avoid the failed link. The PLR router may use the alternate next hop until the MP router converges on a new shortest upstream path for the updated network topology, and the PLR router installs new primary and alternate next hops in its forwarding information. Fast Reroute (FRR) using LFA is described in more detail in Atlas, A., “Basic Specification for IP Fast Reroute: Loop-Free Alternates,” RFC 5286, September, 2008, the entire contents of which are incorporated by reference herein.

As an example, the MP router of the unicast LSP allocates a label L1to the PLR router of the unicast LSP over the protected link. The MP router may also allocate the same label L1to a router of the alternate path. In the case of a two-hop alternate path, the router of the alternate path then allocates a label L2to the PLR router. The PLR router installs a primary next hop with the label L1to reach the MP router using the primary unicast LSP over the protected link. The PLR router also installs an alternate next hop with label L2to reach the MP router using the alternate path avoiding the protected link. When the protected link fails, the PLR router forwards the unicast traffic along the alternate path to the alternate next hop with label L2. Upon receiving the unicast traffic with the label L2, the router of the alternate path swaps the label L2with the label L1to reach the MP router of the primary unicast LSP.

In the link protection mechanisms for a unicast LSP, the PLR router can switch the unicast traffic from the primary unicast LSP to an alternate path because all paths are capable of carrying unicast traffic without requiring additional setup or capability advertisements. In the case of a multipoint LSP, such as multipoint LSP12, a PLR router cannot simply forward the multicast traffic onto any alternate path that is not capable of forwarding multicast traffic.

The techniques of this disclosure provide local link and node protection mechanisms for multicast traffic in multipoint LSPs using loop-free alternate (LFA) next hops. More specifically, one or more of upstream routers14,15and16may establish alternate paths for the multicast traffic to reach leaf routers18in the event of a failure in multipoint LSP12. The alternate paths comprise vanilla or P2P LSPs with LFA next hops that are calculated, as in the case of unicast LDP LSPs, to be the backup shortest downstream path toward leaf routers18. The P2P LSPs with LFA next hops comprise vanilla, i.e., simple, P2P LDP LSPs with no LDP enhancements. The P2P LSPs with LFA next hops, therefore, cannot directly forward the multicast traffic for multipoint LSP12using the mLDP assigned labels. The P2P LSPs with LFA next hops may, however, tunnel the multicast traffic using P2P LSP labels.

The link protection mechanisms are described with respect toFIG. 1. As an example, upstream transit router15may comprise a PLR router for multipoint LSP12and downstream transit router16may comprise a MP router for multipoint LSP12. According to the techniques, transit router15establishes P2P LSP with LFA24from transit router15to transit router16to provide local link protection to link20for multipoint LSP12. According to LDP, the setup of P2P LSP with LFA24is initiated by downstream transit router16and propagated upstream along the alternate path toward upstream transit router15via transit router17. As described above, P2P LSP with LFA24may comprise a simple P2P LDP LSP with no LDP enhancements such that it is not necessary for transit router17to support mLDP capabilities. Transit router16allocates an implicit null label or a non-null label to transit router17of P2P LSP with LFA24. Transit router17, in turn, allocates a non-null label to upstream router15.

In order to tunnel multicast traffic through P2P LSP with LFA24, transit router15establishes a targeted adjacency session22between transit router15and transit router16. For example, transit router15may establish targeted adjacency session22by periodically sending targeted unicast hello messages to transit router16over any link between transit router15and transit router16. In this way, even when link20goes down, targeted adjacency session22will not go down as long as at least one link remains between transit router15and transit router16over which the routers may exchange targeted hello messages. Downstream transit router16may, therefore, allocate a label for targeted adjacency session22instead of for each of the individual links between router15and router16.

Generally, an LDP targeted adjacency established between two routers enables the routers to view each other as LDP neighbors even if the two routers are separated by multiple hops. For example, LDP targeted adjacencies are typically used to establish LDP LSPs across a portion of a network that uses the Resource Reservation Protocol (RSVP). In this case, the downstream router for the LDP LSP may allocate an LDP LSP label to its upstream peer router on the other side of the RSVP portion of the network. The upstream router cannot, however, forward traffic on the LDP LSP using only the LDP LSP label because multiple hops exist between the two routers within the RSVP portion of the network. The LDP targeted adjacency enables the traffic for the LDP LSP to be tunneled through an RSVP LSP with an RSVP LSP label as an “outer label” while maintaining the targeted adjacency session label for the LDP LSP as an “inner label.”

According to the techniques described in this disclosure, targeted adjacency session22is established between upstream transit router15and downstream transit router16in order to tunnel the multicast traffic for multipoint LSP12through P2P LSP with LFA24with the P2P LSP label as the outer label while maintaining the targeted adjacency session label for multipoint LSP12as the inner label. In this way, when downstream transit router16receives the tunneled multicast traffic from transit router17with the targeted adjacency session label, router16is able to continue forwarding the multicast traffic along multipoint LSP12to the next hops installed in its forwarding information.

When transit router15begins tunneling the multicast traffic through P2P LSP with LFA24upon the failure of link20, upstream transit router15may start a targeted adjacency expiry timer, referred to as protection expiry, of length greater than a make-before-break (MBB) timer on downstream transit router16to tear down targeted adjacency session22. It may be assumed that downstream transit router16will be able to converge and signal the new multipoint LSP branch during the MBB interval. Once the MBB timer on transit router16expires, router16will withdraw the targeted adjacency session label from old upstream transit router15, which in turn will stop sending multicast traffic on multipoint LSP12. The protection expiry timer on transit router15will remove targeted adjacency session22from its forwarding information.

In order to facilitate proper forwarding of the multicast traffic for multipoint LSP12, transit router15installs a primary next hop with the targeted adjacency session label for multipoint LSP12in the forwarding information of upstream transit router15. According to the techniques of this disclosure, transit router15also installs a LFA next hop with a label stack in the forwarding information of upstream transit router15. The label stack includes the targeted adjacency session label for multipoint LSP12and the P2P LSP label.

After the primary and LFA next hops are installed in the forwarding information, upstream transit router15forwards multicast traffic along multipoint LSP12to the primary next hop with the targeted adjacency session label. Upon detecting that a failure of link20has occurred, upstream transit router15begins tunneling the multicast traffic to downstream transit router16along P2P LSP with LFA24to the LFA next hop with the label stack. In this way, during a failure of link20, upstream router15tunnels the multicast traffic for multipoint LSP12through P2P LSP with LFA24to transit router17as the LFA next hop with the P2P LSP label as the outer label and the targeted adjacency session label as the inner label. Upon receiving the tunneled multicast traffic, transit router17removes the outer P2P LSP label and tunnels the multicast traffic with the targeted adjacency session label through P2P LSP with LFA24to downstream router16.

As described above, downstream router16may send an implicit null label for P2P LSP with LFA24to transit router17. In that case, transit router17pops the outer P2P LSP label from the multicast traffic and sends the multicast traffic to transit router16without another P2P LSP label. Transit router16may then act directly on the targeted adjacency session label for multipoint LSP12. In other examples, downstream router16may allocate a non-null label for P2P LSP with LFA24to transit router17. In that case, transit router17may send the multicast traffic to transit router16with the non-null P2P LSP label as the outer label, and downstream router16will first pop the non-null P2P LSP label in order to act on the targeted adjacency session label for multipoint LSP12.

The techniques of this disclosure enable P2P LSP with LFA24to be used for FRR of multicast traffic in multipoint LSP12until a convergence process completes for a new path through network10. The techniques, therefore, reduce packet loss while a routing protocol on the MP router converges on a new multipoint LSP branch for the new topology, and mLDP signals the new multipoint LSP branch to the new upstream routers. If the new upstream routers do not already have the multipoint state for a particular multipoint FEC, the upstream routers signal the new multipoint LSP branch further upstream until it joins the multipoint LSP tree and the multipoint states are installed in forwarding information on all the routers along the new multipoint LSP branch.

As described above, mLDP may setup P2MP LSP12by allocating labels from the leaf nodes18toward root node14according to the smallest upstream metrics of the links. In one example, the path with the smallest upstream metric from downstream router16to upstream router15may be along the direct link between the routers, i.e., protected link20. In the case of an asymmetric topology, the smallest downstream metric from upstream router15to downstream router16may be via router17. The primary forwarding next hop at router15would then be toward router17, and the alternate forwarding next hop would be directly to router16. The techniques of this disclosure, however, describe calculating an LFA next hop as an alternate path to a protected link between upstream router15and downstream router16. The LFA next hop described herein is not necessarily the same as the alternate forwarding next hop for router15.

The techniques of this disclosure are therefore applicable to networks with asymmetric topologies in which metrics on each side of the protected link20between upstream router15and downstream router16are different. The techniques apply to both symmetric and asymmetric topologies because the multicast traffic for multipoint LSP12is tunneled along P2P LSP with LFA24, instead of simply using an alternate next hop label to forward the multicast traffic.

FIG. 2is a block diagram illustrating another example network30including a multipoint LSP32established between root router34and leaf routers38A and38B (“leaf routers38”), configured to provide node protection using LFA next hops. In the illustrated example ofFIG. 2, the techniques of this disclosure provide local protection for multicast traffic through intermediate transit router35between root router34and a downstream transit router36of multipoint LSP32. The techniques include establishing a vanilla or P2P LSP with LFA next hops44between root router34and downstream router36to provide fast reroute (FRR) of multicast traffic in the event of a failure of node35. Upon the failure of node35, the multicast traffic is tunneled between root router34and downstream router36along P2P LSP with LFA44to an LFA next hop with a label stack including a P2P LSP outer label as well as a multipoint LSP inner label.

Similar to the multipoint LSP described above with respect toFIG. 1, in some examples, multipoint LSP32may comprise a path through network30to connect remotely located networks or devices (not shown inFIG. 2). For example, a source network may be connected to root router34and subscriber networks may be connected to leaf routers38. Routers34-38in network30each maintain routing information that describes available routes through network10. In the example ofFIG. 2, multipoint LSP32through network30conforms to a MPLS tunnel and, specifically, comprises a P2MP LDP LSP. In other examples, multipoint LSP32may comprise a MP2MP LDP LSP.

In the illustrated example ofFIG. 2, root router34establishes multipoint LSP32through network30from root router34to leaf routers38A and38B. According to the mLDP, the setup of multipoint LSP32is initiated by leaf routers38and propagated upstream along the shortest upstream path toward root router34. Downstream routers35,36and38may calculate the shortest upstream path toward root router34on a hop-by-hop basis based on the routing information maintained by the routers. In addition, mLDP Label Mapping Messages are downstream-assigned such that each downstream router assigns itself a label. Each downstream router then sends an mLDP Label Mapping Message including the assigned label and a multipoint forwarding equivalence class (FEC) identifying multipoint LSP32to the selected upstream router for multipoint LSP32.

In the illustrated example ofFIG. 2, after receiving the downstream-assigned label, each of upstream routers34,35and36associates the label with a next hop used to transmit packets on multipoint LSP32through network30. Each of routers34,35and36may install the next hop for multipoint LSP32with the associated label in forwarding information of the router. Upstream routers34,35and36then use the next hops with the assigned labels to forward multicast traffic hop-by-hop along multipoint LSP32to leaf routers38. At branch router36, the multicast traffic is replicated and one copy of the traffic is sent to leaf router38A and another copy of the traffic is sent to leaf router38B.

In the event of a node failure in multipoint LSP32, multicast traffic can no longer reach leaf routers38using multipoint LSP32according to the next hops previously installed in the routers because the traffic would be dropped at the failed node. For example, after a failure of intermediate node35, any multicast traffic forwarded from root router34to node35as the installed next hop for multipoint LSP32would be dropped. The failure of node35detaches the entire multipoint LSP branch beginning at transit router36from the upstream portion of multipoint LSP32until the routing protocol on downstream transit router36converges to determine a new shortest upstream path toward root router34. In addition to multipoint LSP32, any other LSPs that use failed intermediate node35to forward traffic will also drop the traffic.

When the node failure occurs, transit router36first determines that the upstream interface to router35is down, and then recalculates a new shortest upstream path toward root router34for multipoint LSP32. As an example, it may take approximately 300-400 milliseconds (ms) for transit router36to determine that the upstream interface to router35is down. It may take another approximately 400 ms for the routing protocol on transit router36to converge on the new shortest upstream path, and for mLDP to send new label assignments to the new upstream router. In addition, it may take more than several seconds for new upstream router37to receive this label and program forwarding for P2MP LSP32. Router37will then select router34as its upstream router and send a label assignment to router34for P2MP LSP32. Finally, it may take more than several seconds for upstream router34to receive the new label from router37and program forwarding for P2MP LSP32. Afterwards, the traffic will start flowing on the new path. Until new paths are re-calculated, any traffic being sent to failed node35will be dropped.

The techniques of this disclosure provide local link and node protection mechanisms for multicast traffic in multipoint LSPs using LFA next hops. More specifically, one or more of upstream routers34,35and36may establish alternate paths for the multicast traffic to reach leaf routers38in the event of a failure in multipoint LSP32. The alternate paths comprise vanilla or P2P LSPs with LFA next hops that are calculated, as in the case of unicast LDP LSPs, to be the backup shortest downstream path toward leaf routers38. The P2P LSPs with LFA next hops comprise vanilla, i.e., simple, P2P LDP LSPs with no LDP enhancements. The P2P LSPs with LFA next hops, therefore, cannot directly forward the multicast traffic for multipoint LSP32using the mLDP assigned labels. The P2P LSPs with LFA next hops may, however, tunnel the multicast traffic using P2P LSP labels.

The node protection mechanisms are described with respect toFIG. 2. As an example, root router34may comprise a PLR router for multipoint LSP32and downstream transit router36may comprise a MP router for multipoint LSP32. According to the techniques, root router34establishes P2P LSP with LFA44from root router34to transit router36to provide local node protection to transit router35for multipoint LSP32. According to LDP, the setup of P2P LSP with LFA44is initiated by downstream transit router36and propagated upstream along the alternate path toward root router34via transit router37. As described above, P2P LSP with LFA44may comprise a simple P2P LDP LSP with no LDP enhancements such that it is not necessary for transit router37to support mLDP capabilities. Transit router36allocates an implicit null label or a non-null label to transit router37of P2P LSP with LFA44. Transit router37, in turn, allocates a non-null label to root router34.

In order to tunnel multicast traffic through P2P LSP with LFA44, the techniques of this disclosure include extensions to the mLDP that enable allocation of next next hop labels from a downstream router in a multipoint LSP. The extensions to the mLDP enable routers34,35,36and38to advertise next next hop label capability to neighboring routers in network30. The extensions to mLDP also enable capable upstream routers34,35and36to request next next hop labels from their respective capable downstream peer routers, and capable downstream routers38,36and35to send their next hop labels to their respective capable upstream peer routers. In this way, capable upstream routers34,35and36may receive both a next hop label for a downstream peer router and a next next hop label for a subsequent downstream router of multipoint LSP32. Each of upstream routers34,35and36then installs an LFA next hop in its forwarding table with a label stack including the next next hop label for the multipoint LSP and a P2P LSP label.

For example, upon establishing multipoint LSP32, root router34advertises its next next hop label capability to its neighboring routers, e.g., transit router35and transit router37, in network30. Root router34also receives next next hop label capability advertisements from one or more of its neighboring routers that support next next hop label capabilities. After receiving the next next hop label capability advertisements, upstream root router34may request next next hop labels for multipoint LSP32from capable intermediate router35. In response to the request, upstream root router34receives next next hop labels for multipoint LSP32from capable intermediate router35, which includes a next next hop label for downstream branch peer router36in multipoint LSP32. In some cases, both the next hop label and the next next hop label for multipoint LSP32may be included in a label mapping message sent from intermediate router35to upstream root router34.

According to the techniques described in this disclosure, the next next hop extensions to the mLDP are provided in order to tunnel the multicast traffic for multipoint LSP32through P2P LSP with LFA44with the P2P LSP label as the outer label while maintaining the next next hop label given by transit router36to failed node35for multipoint LSP32as the inner label. In this way, when downstream transit router36receives the tunneled multicast traffic from transit router37with the next next hop label, router36is able to continue forwarding the multicast traffic along multipoint LSP32to the next hops installed in its forwarding information.

When root router34begins tunneling the multicast traffic through P2P LSP with LFA44upon the failure of node35, root router34may start a protection expiry timer of length greater than a make-before-break (MBB) timer on downstream transit router36to stop tunneling the multicast traffic for P2MP LSP32through P2P LSP with LFA44. Downstream transit router36will hold on to the forwarding state via failed router35for P2MP LSP32until a MBB procedure is complete for P2MP LSP32. It may be assumed that downstream transit router36will be able to converge and signal the new multipoint LSP branch during the MBB interval. Once the MBB timer on transit router36expires, router36will delete the label assigned to old upstream transit router35. The protection expiry timer on root router34will clean up the old P2MP branch of P2MP LSP32, which is tunneling multicast traffic through P2P LSP with LFA44towards downstream router36.

In order to facilitate proper forwarding of the multicast traffic for multipoint LSP32, root router34installs a primary next hop with the next hop label for multipoint LSP32in the forwarding information of upstream router34. Root router34also installs a LFA next hop with a label stack in the forwarding information of upstream root router34where the label stack includes the next next hop label for multipoint LSP32and the P2P LSP label.

After the primary and LFA next hops are installed in the forwarding information, upstream root router34forwards multicast traffic along multipoint LSP32to the primary next hop with the next hop label for multipoint LSP32. Upon detecting that a failure of node35has occurred, upstream root router34begins tunneling the multicast traffic around failed intermediate router35along the P2P LSP with LFA44to the LFA next hop with the label stack. In this way, during a failure of node35, root router34tunnels the multicast traffic for multipoint LSP32through P2P LSP with LFA44to transit router37as the LFA next hop with the P2P LSP label as the outer label and the next next hop label as the inner label. Upon receiving the tunneled multicast traffic, transit router37removes the outer P2P LSP label and tunnels the multicast traffic with the next next hop label through P2P LSP with LFA44to downstream router36.

As described above, downstream router36may send an implicit null label for P2P LSP with LFA44to transit router37. In that case, transit router37pops the outer P2P LSP label from the multicast traffic and sends the multicast traffic to transit router36without another P2P LSP label. Transit router36may then act directly on the next next hop label for multipoint LSP32, which is the same label that transit router36expects to receive with traffic for multipoint LSP32from transit router35. In other examples, downstream router36may allocate a non-null label for P2P LSP with LFA44to transit router37. In that case, transit router37may send the multicast traffic to transit router36with the non-null P2P LSP label as the outer label, and downstream router36will first pop the non-null P2P LSP label in order to act on the next hop label for multipoint LSP12.

The techniques of this disclosure enable P2P LSP with LFA44to be used for FRR of multicast traffic in multipoint LSP32until a convergence process completes for a new path through network30. The techniques, therefore, reduce packet loss while a routing protocol on the MP router converges on a new multipoint LSP branch for the new topology, and mLDP signals the new multipoint LSP branch to the new upstream routers.

FIG. 3is a block diagram illustrating an exemplary router50capable of supporting fast reroute using LFA next hops to provide link and/or node protection for multipoint LSPs. As one example, router50may comprise an upstream router or root of a multipoint LSP established across a network. Router30may also comprise a downstream router or leaf of a multipoint LSP established across the network by an upstream router. Router50may operate to provide link protection as described with respect toFIG. 1, or to provide node protection as described with respect toFIG. 2. Router50may operate substantially similar to any of routers14-18fromFIG. 1and routers34-38fromFIG. 2.

In the example illustrated inFIG. 3, router50includes interface cards56A-56N (“IFCs56”) that receive multicast packets via inbound links57A-57N (“inbound links57”) and send multicast packets via outbound links58A-58N (“outbound links58”). IFCs56are typically coupled to links57,58via a number of interface ports. Router50also includes a control unit52that determines routes of received packets and forwards the packets accordingly via IFCs56.

Control unit52maintains routing information76that describes the topology of a network and, in particular, routes through the network. Routing information76may include, for example, route data that describes various routes within the network, and corresponding next hop data indicating appropriate neighboring devices within the network for each of the routes. Router50updates routing information76to accurately reflect the topology of the network.

Control unit52also maintains forwarding information78that associates network destinations with specific next hops and corresponding interface ports. In general, when router50receives a multicast packet with a label via one of inbound links57, control unit52determines a destination and associated next hop for the packet in accordance with routing information76and forwards the packet on one of outbound links58to the corresponding next hop in accordance with forwarding information78based on the destination of the packet.

Control unit52includes control plane routing protocols68comprising software processes executing on one or more processors. In the example ofFIG. 3, routing protocols68include OSPF70A and IS-IS70N. Control unit52may include other routing protocols not shown inFIG. 3. Routing protocols68interact with a kernel to update routing information76based on routing protocol messages received by router50. In response, route selection unit72generates forwarding information78based on the network topology represented in routing information76.

Route selection module72and LFA module74of router50cooperate to compute primary next hops and LFA next hops to downstream routers in the multipoint LSP. Route selection module72may run a Shortest Path First (SPF) calculation with router50as the source to compute a primary next hop for the closest downstream router of the multipoint LSP. Route selection module72runs the SPF calculation based on routing information76.

To compute the LFA next hop, LFA module74computes SPF with router50as the source to compute the distance to each neighboring router of router50. LFA module74may then select the next closest downstream router along a P2P LSP toward the same downstream router as the multipoint LSP. According to the techniques of this disclosure, router50may establish the P2P LSP with LFA next hops between router50and a downstream router to avoid a protected link and/or a protected node in the multipoint LSP.

In the case where router50comprises a downstream router or leaf of a multipoint LSP, route selection module72may allocate a primary next hop label to an upstream router of the multipoint LSP having the lowest cost distance from router50. In addition, route selection module72may allocate a LFA next hop label to an alternate upstream router of the P2P LSP having the next lowest cost distance from router50.

In the case where router50comprises an upstream router or root of a multipoint LSP, route selection module72receives next hop labels from downstream routers in the multipoint LSP, and installs the route to the downstream routers with the next hop labels as primary next hops80in forwarding information78. According to the techniques of this disclosure, LFA module74receives P2P LSP labels from alternate downstream routers in the P2P LSP with LFA, and installs the routes to the alternate downstream routers as LFA next hops with label stacks82including the P2P LSP labels as outer labels and multipoint LSP labels as inner labels.

In accordance with the techniques of the disclosure, control unit52provides an operating environment for mLDP60to execute. mLDP60includes a next next hop label module62and a next next hop label capability module64to support next next hop labels. mLDP60also includes a targeted adjacency module66to support targeted adjacencies with other LDP routers.

As described above with respect toFIG. 1, in order to provide local link protection for a multipoint LSP, the techniques include establishing a targeted adjacency session between routers connected by a protected link of the multipoint LSP. The upstream router installs an LFA next hop in its forwarding table with a label stack including a targeted adjacency session label for the multipoint LSP and a P2P LSP label for the P2P LSP with LFA around the protected link.

In the case where router50comprises an upstream router or root of a multipoint LSP, router50establishes the multipoint LSP across a network having two or more downstream routers or leaves. According to the techniques, when router50requests link protection to its neighboring downstream router in the multipoint LSP and a P2P LSP with LFA is established around the protected link, targeted adjacency module66in router50establishes a targeted adjacency session with the neighboring downstream router in the multipoint LSP. Targeted adjacency module66establishes the targeted adjacency session by periodically sending targeted unicast hello messages to the neighboring downstream router over any link between the routers. In this way, even when the protected link goes down, the targeted adjacency session will not go down as long as at least one link remains over which the routers may exchange targeted hello messages.

Targeted adjacency module66may also receive a targeted adjacency session label from the downstream router. Upon receiving the P2P LSP label for the P2P LSP with LFA and the targeted adjacency session label from the downstream router of the multipoint LSP, LFA module74installs a LFA next hop with label stack82for the multipoint LSP in forwarding information78with the P2P LSP label as the outer label and the targeted adjacency session label for the multipoint LSP as the inner label of the label stack.

In the case where router50comprises a downstream router or leaf of a multipoint LSP, router50allocates next hop labels for neighboring upstream routers in the multipoint LSP and may also allocate next hop labels for alternative upstream routers in the P2P LSP with LFA. According to the techniques, when the upstream router requests link protection in the multipoint LSP and the P2P LSP with LFA is established around the protected link, targeted adjacency module66in router50receives hello messages from the upstream router to establish a targeted adjacency session and allocates a label for the targeted adjacency session to the upstream router. Based on the allocated labels, the upstream router may install primary next hops and LFA next hops with label stacks including the P2P LSP label and the targeted adjacency session label for the multipoint LSP.

As described above with respect toFIG. 2, in order to provide local node protection for a multipoint LSP, the techniques include extensions to mLDP that enable allocation of next next hop labels from a downstream router in a multipoint LSP. In this way, an upstream router may receive both a next hop label for a downstream peer router and a next next hop label for a subsequent downstream router of the multipoint LSP. The upstream router then installs an LFA next hop in its forwarding table with a label stack including the next next hop label for the multipoint LSP and a P2P LSP label for the P2P LSP with LFA around the protected node.

In the case where router50comprises an upstream router or root of a multipoint LSP, router50establishes the multipoint LSP across a network having two or more downstream routers or leaves. According to the techniques, when router50requests node protection in the multipoint LSP and a P2P LSP with LFA is established around the protected node, next next hop capability module64sends advertisements to neighboring routers in the network indicating that router50is capable of supporting next next hop labels. In addition, next next hop capability module64receives advertisements from the neighboring routers in the network indicating that at least some of neighboring routers are capable of supporting next next hop labels.

Upon receiving an advertisement from a downstream router of the multipoint LSP indicating that the downstream router is capable of supporting next next labels, router50may send a next next hop Label Request to the downstream router. Upon receiving the advertisement and the next next hop Label Request from router50, the capable downstream router of the multipoint LSP allocates a next next hop label received from a subsequent downstream router of the multipoint LSP to router50. In some cases, the capable downstream router allocates a next hop label and the next next hop label to router50in the same Label Mapping Message. Next next hop label module62recognizes that a next next hop label was received from the downstream router, and installs a LFA next hop with label stack82for the multipoint LSP in forwarding information78with the P2P LSP label as the outer label and the next next hop label for the multipoint LSP as the inner label of the label stack.

In the case where router50comprises a downstream router or leaf of a multipoint LSP, router50allocates next hop labels for neighboring upstream routers in the multipoint LSP and may also allocate next hop labels for alternative upstream routers in the P2P LSP with LFA. According to the techniques, when the upstream router requests node protection in the multipoint LSP and the P2P LSP with LFA is established around the protected node, next next hop capability module64sends advertisements to neighboring routers in the network indicating that router50is capable of supporting next next hop labels. In addition, next next hop capability module64receives advertisements from the neighboring routers in the network indicating that at least some of the neighboring routers are capable of supporting next next hop labels.

Upon receiving the advertisement from router50, an upstream router in the multipoint LSP capable of supporting next next hop labels may send a next next hop Label Request to router50. Upon receiving the advertisement and the next next hop Label Request from the upstream router, next next hop label module62within router50sends a next next hop label received from a subsequent downstream router of the multipoint LSP to the capable upstream router of the multipoint LSP that requested next next hop label. In some cases, the router50sends a next hop label and the next next hop label to the capable upstream router in the same Label Mapping Message. Based on the received labels, the upstream router may install primary next hops and LFA next hops with label stacks including the P2P LSP label and the next next hop label for the multipoint LSP.

The architecture of router50illustrated inFIG. 3is shown for exemplary purposes only. This disclosure is not limited to this architecture. In other examples, router50may be configured in a variety of ways. In one example, some of the functionally of control unit52may be distributed within IFCs56. In another example, control unit52may include a routing engine that performs routing functions and maintains routing information base (RIB), e.g., routing information76, and a forwarding engine that performs packet forwarding based on a forwarding information base (FIB), e.g., forwarding information78, generated in accordance with the RIB.

Control unit52may be implemented solely in software, or hardware, or may be implemented as a combination of software, hardware, or firmware. For example, control unit52may include one or more processors which execute software instructions. In that case, the various software modules of control unit36may comprise executable instructions stored on a computer-readable medium, such as a computer-readable storage medium, containing instructions. Instructions embedded or encoded in a computer-readable medium may cause a programmable processor, or other processor, to perform the method, e.g., when the instructions are executed. Computer-readable storage media may include random access memory (RAM), read only memory (ROM), programmable read only memory (PROM), erasable programmable read only memory (EPROM), electronically erasable programmable read only memory (EEPROM), non-volatile random access memory (NVRAM), flash memory, a hard disk, a CD-ROM, a floppy disk, a cassette, magnetic media, optical media, or other computer-readable storage media.

FIG. 4illustrates an exemplary Next Next Hop (NNH) Capability TLV84used to indicate whether a router supports next next hop labels. In accordance with techniques of this disclosure, next next hop label capability is advertised using an LDP Capability TLV that is defined in an LDP Initialization message sent from a router to neighboring routers in a network and indicates a set of capabilities supported by the router. More information about advertising LDP enhancements may be found in Thomas, B., “LDP Capabilities,” RFC 5561, July 2009, the entire contents of which are incorporated by reference herein.

The newly defined NNH Capability TLV84may indicate the capability of a router to support next next hop label mapping, withdraw, and request procedures. As shown inFIG. 4, NNH Capability TLV84includes a TLV type field (in this case NNH Capability), a length field, and a state bit (S). The state bit indicates whether the capability specified by the TLV type is being advertised or withdrawn. The reserved bits may be set to zero on transmission and ignored on receipt.

The usage of LDP Initialization messages for exchanging next next hop label capability implies that a router may exchange LDP Initialization messages with a neighboring router before sending or receiving any other LDP messages with that neighboring router. An upstream router cannot send a NNH Label Request message to downstream routers of a multipoint LDP LSP unless the upstream router knows that at least some of the downstream routers support next next hop label capabilities. In turn, a downstream router cannot send next next hop labels to an upstream router of a multipoint LDP LSP unless the downstream router knows that the upstream router supports next next hop label capabilities. When the NNH Capability TLV84is included in the LDP Initialization message, the router is capable of both allocating next next hop labels and receiving next next hop labels. When the NNH Capability TLV84is not included in the LDP Initialization message, the router is not capable of either sending or receiving next next hop labels.

FIG. 5illustrates an exemplary LDP NNH Label TLV86that signals next next hop labels to upstream routers. In accordance with the example ofFIG. 5, LDP NNH Label TLV86is defined in a message used to advertise or withdraw next next hop label mappings. LDP NNH Label TLV86is sent in messages from a NNH capable downstream router to a NNH capable upstream router of a multipoint LDP LSP. In some cases the upstream router may have requested a next next hop label from the downstream router using a Label Request message, which is described in more detail inFIG. 6.

As shown inFIG. 5, LDP NNH Label TLV86includes a type field (in this case LDP NNH TLV), a length field, and a value field87. The length field indicates the length of value field87in octets. Value field87includes at least one pair of a downstream branch router ID and a label advertised by that router. As illustrated inFIG. 5, value field87may include a first pair of Router ID1and Label1through a last pair of Router ID n and Label n, where n indicates a number of downstream branch routers connected to a router capable of allocating the next next hop labels.

In a multipoint LDP LSP, a downstream router may send its label to an upstream peer router in a Label Mapping message. In the case where the downstream router and the upstream router support NNH label capabilities, the downstream router may also send the labels of its downstream branch peer routers to the upstream router using LDP NNH Label TLV86included in the same Label Mapping message. The downstream router does not send LDP NNH Label TLV86in the Label Mapping message to the upstream router, however, if the downstream router and the upstream router did not advertise the NNH Capability TLV84(fromFIG. 4) in LDP Initialization messages.

If one of the downstream branch peer router labels is withdrawn or the downstream branch peer router goes down, the NNH capable downstream router may send LDP NNH Label TLV86including the particular downstream branch peer router ID with its label in a Label Withdraw message to the NNH capable upstream router. Similarly when a new downstream branch peer router is added to the multipoint LDP LSP, the NNH capable downstream router may send the label of the new downstream branch peer router to the NNH capable upstream router using LDP NNH Label TLV86in the Label Mapping message. The NNH capable downstream router may include LDP NNH Label TLV86in the optional parameters field of the Label Mapping message or the Label Withdraw message to send or withdraw downstream branch peer router labels to the NNH capable upstream peer router.

FIG. 6illustrates an exemplary NNH Label Request message88that requests next next hop labels from downstream routers. In accordance with the techniques of this disclosure, NNH Label Request message88is sent from a NNH capable upstream router to a NNH capable downstream router of a multipoint LDP LSP to request next next hop labels of the downstream router's downstream branch peers. An upstream router does not send NNH Label Request message88to a downstream router of a multipoint LDP LSP if the upstream router and the downstream router did not advertise the NNH Capability TLV84(fromFIG. 4) in LDP Initialization messages.

The encoding for NNH Label Request message88may be the same as a standard next hop Label Request message. As shown inFIG. 6, NNH Label Request message88includes a type field (in this case NNH Label Request), a message length field, a message ID field, a FEC TLV field to indentify a particular multipoint LDP LSP, and an optional parameters field.

If the NNH capable downstream router does not have a next next hop label for a particular prefix, it can send an appropriate notification message to the NNH capable upstream peer. If NNH label request message88is used for a P2P LDP LSP downstream router on demand, it is assumed that the next next hop router uses a global label for LDP.

FIG. 7is a flowchart illustrating an exemplary operation of providing link protection for traffic in a multipoint LSP using a P2P LSP with LFA next hops. The exemplary operation is described herein with respect to upstream transit router15fromFIG. 1that requests local protection for multicast traffic on link20of multipoint LSP12. Upstream router15uses P2P LFA LSP24to tunnel the multicast traffic to downstream transit router16in the event of a failure of link20between upstream router15and downstream router16. During the FRR using P2P LFA LSP24, downstream router16may converge and signal a new multipoint branch for multipoint LSP12based on the new network topology without link20.

In the illustrated example ofFIG. 1, root router14establishes multipoint LSP12through network10from root router14to leaf routers18A &18B via transit routers15,16. As described above with respect toFIG. 1, using the LDP, the multipoint LSP setup is initiated by leaf routers18and propagated upstream along the shortest upstream path toward root router14. The label mapping messages are downstream-assigned such that each downstream router assigns itself a label and sends a label mapping message for multipoint LSP12to its selected upstream router. In some cases, one or more of the upstream routers may establish alternate paths for the multicast traffic to reach the downstream routers in the event of a failure in multipoint LDP LSP12. For example, the upstream routers may establish P2P LSPs with LFA next hops calculated to be the backup shortest downstream paths toward leaf routers18.

According to the techniques of this disclosure, upstream router15establishes P2P LSP with LFA24between upstream router15and downstream router16of multipoint LDP LSP12to provide link protection for link20(90). In the illustrated example ofFIG. 1, P2P LSP with LFA24may be established from transit router15to transit router16via transit router17. P2P LSP with LFA24may comprise a simple point-to-point (P2P) LDP LSP with no LDP enhancements. Downstream router16may initiate the LSP setup and send an implicit null label to alternate upstream transit router17. Transit router17, in turn, may send a label mapping message with a P2P LSP label to upstream router15.

Transit router15then establishes targeted adjacency session22between transit router15and transit router16(92). For example, transit router15may establish targeted adjacency session22by periodically sending targeted unicast hello messages to transit router16over any link between transit router15and transit router16. In this way, targeted adjacency session22will not go down as long as at least one link remains between transit router15and transit router16over which the routers may exchange targeted hello messages.

Transit router15installs a primary next hop with a targeted adjacency session label for multipoint LSP12in the forwarding information of upstream transit router15(94). Transit router15also installs a LFA next hop with a label stack in the forwarding information of upstream transit router15where the label stack includes the targeted adjacency session label for multipoint LSP12and the P2P LSP label (96).

After the primary and LFA next hops are installed in the forwarding information, upstream transit router15forwards multicast traffic along multipoint LSP12to the primary next hop with the targeted adjacency session label (98). Upon detecting that a link failure has occurred affecting the primary next hop (YES branch of 100), upstream transit router15begins tunneling the multicast traffic to downstream transit router16along the P2P LSP with LFA24to the LFA next hop with the label stack (102). While the multicast traffic is tunneled using P2P LSP24, downstream transit node16will converge and signal a new branch for multipoint LDP LSP12based on the changed network topology.

FIG. 8is a flowchart illustrating an exemplary operation of providing node protection for traffic in a multipoint LSP using a P2P LSP with LFA. The exemplary operation is described herein with respect to upstream root router34fromFIG. 2that requests local protection for multicast traffic through transit router35of multipoint LSP32. Upstream router34uses P2P LFA LSP44to tunnel the multicast traffic to around transit router34to downstream transit router36in the event of a failure of intermediate router35between upstream router34and downstream router36. During the FRR using P2P LFA LSP34, downstream router36may converge and signal a new multipoint branch for multipoint LSP32based on the new network topology without router35.

In the illustrated example ofFIG. 2, root router34establishes multipoint LSP32through network30from root router34to leaf routers38A &38B via transit routers35,36. As described above with respect toFIG. 2, using the LDP, the multipoint LSP setup is initiated by leaf routers38and propagated upstream along the shortest upstream path toward root router34. The label mapping messages are downstream-assigned such that each downstream router assigns itself a label and sends a label mapping message for multipoint LSP32to its selected upstream router. In some cases, one or more of the upstream routers may establish alternate paths for the multicast traffic to reach the downstream routers in the event of a failure in multipoint LDP LSP32. For example, the upstream routers may establish P2P LSPs with LFA next hops calculated to be the backup shortest downstream path toward leaf routers38.

According to the techniques of this disclosure, upstream root router34establishes P2P LSP with LFA44between upstream router34and downstream router36of multipoint LDP LSP32to provide node protection for transit router35(110). In the illustrated example ofFIG. 2, P2P LSP with LFA44may be established from root router34to transit router36via transit router37. P2P LSP with LFA44may comprise a simple P2P LDP LSP with no LDP enhancements. Downstream router36may initiate the LSP setup and send an implicit null label to alternate upstream transit router37. Transit router37, in turn, may send a label mapping message with a P2P LSP label to upstream root router34.

Root router34then advertises its next next hop label capability to its neighboring routers, e.g., transit router35and transit router37, in network10(112). Root router34may use NNH Capability TLV84fromFIG. 4in a LDP Capability TLV to advertise its support of next next hop label mapping, withdraw, and request procedures. Root router34also receives next next hop label capability advertisements from one or more of its neighboring routers that support next next hop label capabilities (114). For example, root router34may receive a LDP Capability TLV including NNH Capability TLV84from transit router35advertising support of next next hop label mapping, withdraw, and request procedures.

After receiving the next next hop label capability advertisements, upstream root router34requests next next hop labels for multipoint LSP32from NNH capable downstream router35(116). For example, upstream router34may use NNH Label Request message88fromFIG. 6to request a next next hop label from intermediate router35for downstream router36in multipoint LSP32. In response to the request, upstream router34receives next next hop labels for multipoint LSP32from NNH capable downstream router35(118). For example, upstream router34may receive LDP NNH Label TLV86fromFIG. 5from intermediate router35including a next next hop label for downstream router36in multipoint LSP32. In some cases, both the next hop label and the next next hop label for multipoint LSP32may be included in a label mapping message sent from intermediate router35to upstream root router34.

Upstream root router34installs a primary next hop with the next hop label for multipoint LSP32in the forwarding information of upstream router34(120). Upstream router34also installs a LFA next hop with a label stack in the forwarding information of upstream root router34where the label stack includes the next next hop label for multipoint LSP32and the P2P LSP label (122).

After the primary and LFA next hops are installed in the forwarding information, upstream root router34forwards multicast traffic along multipoint LSP32to the primary next hop with the next hop label for multipoint LSP32(124). Upon detecting that a node failure has occurred affecting the primary next hop (YES branch of126), upstream root router34begins tunneling the multicast traffic around failed intermediate router35along the P2P LSP with LFA44to the LFA next hop with the label stack (128). While the multicast traffic is tunneled using P2P LSP44, downstream transit node36will converge and signal a new branch for multipoint LDP LSP32based on the changed network topology.

Various examples of the techniques of the disclosure have been described. These and other examples are within the scope of the following claims.