Patent Publication Number: US-9838246-B1

Title: Micro-loop prevention using source packet routing

Description:
BACKGROUND 
     A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets. The packets are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission. 
     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 an interior gateway protocol (IGP). An interior gateway protocol may be a distance-vector protocol or a link state protocol. With a typical link state routing protocol, the routers exchange information related to available interfaces, metrics and other variables associated with links between network devices. This allows the routers to each construct a complete 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. 
     When there is a change in network topology either due to a link failure or due to a new link addition, network devices in the network determine an updated view of the network and re-compute routes. For instance, if a link failure occurs, network devices directly coupled to the failed link may notify other network devices in the network of the link failure. Due to network latency and network device configuration time, there may be a small time window when the forwarding state of each of the network devices is not synchronized. As a result, transient loops (or “micro-loops”) may occur in the network where a particular network device, which has not yet converged to an updated network topology, sends traffic to a next-hop network device that has already converged to the updated network topology. As a result, the next-hop device may forward the traffic back to the particular network device, thus creating a micro-loop that results in traffic looping between the two network devices. 
     SUMMARY 
     In general, techniques are described for reducing or otherwise preventing micro-loops in an Internet Protocol (IP)/Multiprotocol Label Switching (MPLS) network using Source Packet Routing in Networking (SPRING). By advertising network device-specific labels, interconnected network devices implementing SPRING may enforce traffic flows through topological paths and services chains. Accordingly, each network device may configure its forwarding state based on node label ranges specific to network devices and adjacency labels specific to particular interfaces and/or network links of network devices. In the event of a link failure between two directly coupled network devices (points of local failure or “PLRs”), techniques of the present disclosure may prevent micro-loops by establishing a temporary network topology that network devices use to forward network traffic before converging to a final, new network topology. That is, although the PLRs may immediately notify other network devices of the link failure, the other network devices may not immediately begin converging to the final, new network topology and instead will temporarily forward traffic using the temporary network topology. By using the temporary network topology to forward network traffic, techniques of the disclosure enable the forwarding state of each of the network devices to become synchronized before using the final network topology, thereby reducing or otherwise preventing micro-loops. 
     To re-route network traffic in the temporary network topology, a PLR applies one or more adjacency labels to network packets, such that the network packets are forwarded using a backup sub-path. The backup sub-path, which circumvents the failed link, may include only a portion of an overall network path between a source and a destination router in the temporary network topology. A stack of adjacency labels correspond to a set of respective one-hop tunnels along the backup sub-path. Because the network packets are explicitly forwarded through the backup sub-path using one-hop tunnels along particular links/interfaces rather than according to node labels associated with device-specific label ranges, network packets may be forwarded to the destination although the forwarding states have not yet synchronized to establish new routes based on the device-specific label ranges. 
     In this way, network packets may be forwarded to the destination without micro-loops that would otherwise occur if the traffic forwarding state is not yet synchronized. Moreover, because the backup sub-path comprises only a portion of the network path, the remaining portions of the overall network path between the source and destination for the network traffic may remain unchanged in the temporary network topology. Specifically, routers forwarding network packets using the unaffected portions of the overall network path may employ a temporary label stack to forward such network packets in the temporary network topology. Thus, the backup sub-path that is temporarily used in the temporary network topology may prevent micro-loops, while only requiring re-routing through a limited portion of the overall network path. Furthermore, because the device-specific label ranges for the node labels and the adjacency labels for SPRING are advertised and exchanged when network devices are initially configured at network device startup, the labels and routes are known in advance of a link failure (and thus possible backup sub-paths), thereby potentially improving convergence times. 
     In some examples, a method includes detecting, by a near-side point of local failure (NPLR), a failure of a communication link that couples the NPLR and a far-side point of local failure (FPLR), wherein the NPLR and the FPLR are each network devices that implement a Source Packet Routing in Networking (SPRING) protocol to forward network packets using node labels according to an initial network topology of a network that comprises a plurality of other network devices; responsive to detecting the failure of the communication link, applying, by the NPLR and for a defined time duration, one or more adjacency labels to network packets destined for a destination network device, wherein the one or more adjacency labels define a set of one-hop tunnels corresponding to a backup sub-path that circumvents the failed communication link; forwarding, by the NPLR and according to a temporary network topology that is based on the set of one-hop tunnels that provide the backup sub-path, the network packets; and upon expiration of the defined time duration, forwarding, by the NPLR and according to a new network topology that is not based on applying the one or more adjacency labels that define the set of one-hop tunnels, network packets destined for the destination network device. 
     A network device, wherein the network device is a first PLR, the network device comprising: at least one processor; at least one module operable by the at least one processor to: detect a failure of a communication link that couples the first PLR and a second PLR, wherein the first PLR and the second PLR are each network devices that implement a Source Packet Routing in Networking (SPRING) protocol to forward network packets using node labels according to an initial network topology of a network that comprises a plurality of other network devices; responsive to detecting the failure of the communication link, apply, for a defined time duration, one or more adjacency labels to network packets destined for a destination network device, wherein the one or more adjacency labels define a set of one-hop tunnels corresponding to a backup sub-path that circumvents the failed communication link; forward, according to a temporary network topology that is based on the set of one-hop tunnels that provide the backup sub-path, the network packets; and upon expiration of the defined time duration, forward, according to a new network topology that is not based on applying the one or more adjacency labels that define the set of one-hop tunnels, network packets destined for the destination network device. 
     In some examples, a method includes: receiving, by a non-point of local failure (non-PLR) network device of a plurality of network devices in a segment routing domain, a link state advertisement that a communication link has failed between a near-side point of local failure (NPLR) and a far-side point of local failure (FPLR) that are each included in the segment routing domain, wherein the NPLR and the FPLR are each network devices that implement a Source Packet Routing in Networking (SPRING) protocol to forward network packets according to an initial network topology of a network that includes the plurality of network devices; responsive to receiving the link state advertisement, initiating, by the non-PLR network device, a timer; configuring, before the timer has expired, a forwarding state of the non-PLR network device, to forward network packets according to a new network topology; and forwarding, while the timer has not expired and by the non-PLR network device, network packets destined for the destination network device according to a temporary network topology that is different than the new network topology. 
     The details of one or more embodiments of the disclosure are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the disclosure will be apparent from the description and drawings, and from the claims. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  is a block diagram illustrating an example system for reducing or otherwise preventing micro-loops in an Internet Protocol (IP)/Multiprotocol Label Switching (MPLS) network using Source Packet Routing in Networking (SPRING), in accordance with techniques of the disclosure. 
         FIGS. 2A-2E  are block diagrams illustrating, in further detail, an example system for reducing or otherwise preventing micro-loops in an Internet Protocol (IP)/Multiprotocol Label Switching (MPLS) network using Source Packet Routing in Networking (SPRING), in accordance with techniques of this disclosure. 
         FIG. 3  is a block diagram illustrating an exemplary router capable of reducing or otherwise preventing micro-loops in an Internet Protocol (IP)/Multiprotocol Label Switching (MPLS) network using Source Packet Routing in Networking (SPRING), in accordance with techniques of this disclosure. 
         FIG. 4  is a flowchart that illustrates example operations of a router of  FIG. 1  that implements techniques for reducing or otherwise preventing micro-loops in an Internet Protocol (IP)/Multiprotocol Label Switching (MPLS) network using Source Packet Routing in Networking (SPRING), in accordance with techniques of this disclosure. 
         FIG. 5  is a flowchart that illustrates example operations of a non-PLR router and a PLR router of  FIGS. 1-3 , that implement techniques for reducing or otherwise preventing micro-loops in an Internet Protocol (IP)/Multiprotocol Label Switching (MPLS) network using Source Packet Routing in Networking (SPRING), in accordance with techniques of this disclosure. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  is a block diagram illustrating an example system for reducing or otherwise preventing micro-loops in an Internet Protocol (IP)/Multiprotocol Label Switching (MPLS) network using Source Packet Routing in Networking (SPRING), in accordance with techniques of the disclosure.  FIG. 1  illustrates an example network  10  including routers  12 A- 12 K (collectively, “routers  12 ”) configured to forward traffic using IGP-distributed per-neighbor labels. Throughout this disclosure “router” and “node” may be used interchangeably. As shown in  FIG. 1 , each of routers  12  may be interconnected by one or more communication links  14 A- 14 L (collectively, “links  14 ”). Each of links  14  may provide, as non-limiting examples, a 10- or 100-gigabit, physical connection. Communication links  14 , generally, may be any wired or wireless links by which network packets traverse between two routers. 
     In the example of  FIG. 1 , some of routers  12  may be source routers that operate to ingress or otherwise inject or source network packets into network  10 . Examples of source routers include routers  12 A,  12 C,  12 E, and  12 I. Some of routers  12  may be destination routers that operate to egress or otherwise drain network packets out of network  10 . Examples of destination routers include router  12 K. Some of routers  12  may be transit routers that forward traffic to other routers within network  10 , and are not source or destination routers. Examples of transit routers include routers  12 B,  12 D,  12 H, and  12 G. As further described in this document, routers  12  may include near-side point of local repair (NPLR) and far-side point of local repair (FPLR), which are each routers that could be source, destination or transit routers. For purposes of  FIG. 1 , routers  12  include router  12 F as an NPLR and router  12 J as a FPLR. In some example, source routers and destination routers may be coupled to one or more customer devices (not shown) with access to network  10 . While discussed herein with respect to a particular network device, i.e., a router, any one or more of routers  12  may represent any network device that routes, switches, bridges or otherwise forwards network traffic directed to or originating from the network. For example, any one or more of routers  12  may each represent, in certain instances, one or more of a switch, a hub, a bridge device (e.g., an Ethernet bridge), or any other L2 network device and, in some instances, L3 network devices capable of performing L2 functionality. 
     Routers  12  in network  10  each maintain routing information that describes available routes through network  10 . 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 network  10 , routers  12  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 the routers may 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 network  10 . 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. 
     Each of routers  12  may use a Source Packet Routing in Networking (SPRING) protocol to forward network packets within network  10 . Further details regarding SPRING are found in (1) “Segment Routing Architecture,” IETF draft: draft-filsfils-spring-segment-routing-04, Jul. 3, 2014; and “SPRING Problem Statement and Requirements,” and (2) IETF draft: draft-ietf-spring-problem-statement-01, Jun. 26, 2014, and (3) “Segment Routing with MPLS data plane,” IETF draft: draft-filsfils-spring-segment-routing-mpls-03, Aug. 1, 2014, the entire contents of which are incorporated by reference herein. 
     In general, SPRING provides segment routing (SR) within an IGP domain that allows routers to advertise single or multi-hop label switched paths LSPs within the IGP domain. For segment routing, the “path” information is disseminated between the routers as part of the IGP link state information for the domain. Routers are able to steer packets through a controlled set of segments defining a path by prepending an SR header (e.g., a label) to the packets. Segment routing allows routers to enforce a flow through any topological path and service chain while maintaining per-flow state only at the ingress node to the SR domain. One advantage of segment routing is that the segment routing architecture can be directly applied to the MPLS data plane with no change in the forwarding plane. 
     In this example, routers  12 , that are included in an SR domain, exchange labels in accordance with the SPRING protocol. One or more routers may be configured in an SR domain, which provides a realm of administrative autonomy, authority or control for routing packets according to the SPRING protocol. In the example of  FIG. 1 , each of routers  12  in network  10  is included in the same SR domain. 
     Each of routers  12  operates as a label switching router (LSR) that distributes labels to neighboring LSRs within network  10  to support SPRING forwarding along routed paths within network  10 . SPRING includes multiple different label types including “adjacency” labels and “node” labels. In some examples, the terms “segment” and “label” may be used interchangeably in this disclosure. To forward a packet through network  10 , one or more of routers  12  may push (and pop) one or more labels in a label stack (e.g., a “segment list”) that is applied to the packet as it is forwarded through the network. The label stack may encode the topological and service source route of the packet. 
     Different types of SPRING labels are further described hereinafter. An adjacency label may have a local semantic to a particular SR node, such as one of routers  12 . In particular, an adjacency label steers traffic onto an adjacency (e.g., communication link and/or interface) or set of adjacencies. Thus, an adjacency label may be related to a particular router. To use an adjacency label, a router may initially assign the adjacency label to a particular adjacency and advertise it to other routers in the SR domain using ISIS or OSPF. The router may be the only router in the SR domain to use the particular adjacency label. When an ingress router forwards a packet using the adjacency label, the packet may be forced, by the ingress router, to use the adjacency for the ingress router associated with the adjacency label. In this way, adjacency labels may be used to establish one-hop tunnels within network  10 . 
     A node label, by contrast, may have a global semantic within an SR domain. That is, each of routers  12  may be assigned a defined node label range that is unique to each respective router within the SR domain. An operator of network  10  may ensure unique allocation of the different node label ranges from a global range to different routers. In addition to a node label range, each particular router may also have a specific node identifier that uniquely identifies the particular router in the SR domain. Each respective router may advertise its respective node identifier and node label range to other routers in the SR domain using ISIS or OSPF. 
     Based on routes determined using equal-cost multi-path routing (ECMP) and/or best-path routing, each of routers  12  may configure its forwarding state to push and pop node labels (corresponding to other nodes in the network) onto packets in order to forward such packets using the determined route to the destination. For instance, each of routers  12  may perform path selection using topology information learned by way of IGP to compute a shortest path within network  10  on a hop-by-hop basis based on the routing information maintained by the routers. Each of routers  12  may then select a next hop along the locally computed shortest path and install forwarding information associated with the selected next hop in a forwarding plane of the router, wherein the forwarding information identifies a network interface to be used when forwarding traffic and one or more labels to be applied when forwarding the traffic out the interface. The routers use the next hops with the assigned labels to forward traffic hop-by-hop. 
     To illustrate the use of node labels, router  12 A may initially inject a packet into network  10  that is destined for router  12 K. Router  12 A determines, based on its forwarding state, that a path to router  12 K includes router  12 B as the next-hop. Router  12 A may apply a node label that indicates the node identifier for router  12 K, and the node label may be within a label range assigned to  12 B. In some examples, the node label is encoded to indicate both the node identifier and that the label is within a particular label range. Upon receiving the packet, router  12 B may determine, based on the node label, a route to router  12 K that includes router  12 C. Router  12 B may pop the node label from the packet that was previously applied by router  12 A, and push a label onto the packet that indicates the node identifier for router  12 K, and the label may be within a label range assigned to  12 C. The packet is processed and forwarded in a similar manner by each of routers  12  on the path from router  12 A to router  12 K. In this way, any router in the SR domain may forward a packet to any other router in the network by applying the appropriate node label. 
     One or more of routers  12  are configured in accordance with one or more of the techniques described herein to provide protection against small transient loops (also referred to herein as “micro-loops”) that may emerge due to link failure or other topology change events. To illustrate, conventional networks utilizing IP-based hop-by-hop routing may experience short-term micro-loops that may provide substantial congestion on one or more links. As a specific example, NPLR router  12 F may discover that communication link  14 M has failed between NPLR router  12 F and FPLR  12 J and, in response, recompute a path for reaching destination router  12 K as { 12 F,  12 H,  12 J,  12 K}. Upon reprogramming its forwarding plane, NPLR router  12 F forwards traffic destined for destination router  12 K to router  12 H. 
     In some situations, the IGP routing protocol on router  12 H may not yet have learned of the failure of link  14 M and/or completed path selection and forwarding plane reprogramming. If router  12 H was previously configured to forward network traffic to destination router  12 K using a route { 12 H,  12 F,  12 J,  12 K}, router  12 H employing conventional techniques may forward the traffic in accordance with the currently selected path { 12 H,  12 F,  12 J,  12 K}. In such an example where router  12 H has not yet updated its forwarding state although NPLR  12 F has updated its forwarding state, a potentially highly-problematic micro-loop would be formed between source router  12 H and  12 F because router  12 F would send the network traffic back to router  12 H, which just sent the network traffic to router  12 F. Where router  12 F and router  12 H employ conventional routing techniques, traffic loops between the routers may ultimately consume all of the available bandwidth until the IGP of router  12 H converges and computes a new shortest path to destination router  12 K by way of  12 J. Although described with respect to link failures, techniques of the disclosure may also be applied to prevent or otherwise reduce micro-loops caused by “link-up” event in which a new link is added to the network. Link-up and link failures may be referred to as link state events. 
     As further described with respect to  FIG. 1 , techniques are provided for reducing or otherwise preventing micro-loops in an Internet Protocol (IP)/Multiprotocol Label Switching (MPLS) network, such as described above with respect to routers  12 H and  12 F, by using Source Packet Routing in Networking (SPRING). The techniques will be described with respect to router  12 A (e.g., a source router) sending network traffic to router  12 K (e.g., a destination router), although such techniques are applicable to sending traffic between any source and destination in network  10 . 
     Initially, packets are forwarded through the network according to a path that includes { 12 A,  12 B,  12 C,  12 D,  12 F,  12 J,  12 K} using node labels as described above. Three sub-paths  16 A,  16 B, and  16 C collectively form path  16  that includes { 12 A,  12 B,  12 C,  12 D,  12 F,  12 J,  12 K}. Sub-path  16 A includes { 12 A,  12 B,  12 C,  12 D,  12 F}, sub-path  16 B includes { 12 F,  12 J}, and sub-path  16 C includes { 12 J,  12 K}. 
     A topology change may occur within network  10 , such as communication link  14 M failing. That is, NPLR router  12 F may detect a failure of a communication link  14 M that directly couples the NPLR router  12 F and FPLR router  12 J. Upon detecting the link failure, NPLR  12 F (and in some examples, FPLR  12 J) sends a link-state advertisement to all other routers in the SR domain. The link-state advertisement may indicate that link  14 M has failed. As further described below, responsive to the link failure, routers  12  may use adjacency labels, for a defined time duration, to establish a temporary network topology with a back-up sub-path that circumvents only the portion of network  10  affected by the failure of link  14 M. In this way, routers  12  may avoid the creation of micro-loops by continuing to forward network packets using unaffected sub-paths  16 A and  16 C of network  10  in a similar manner as prior to the failure of link  14 M, while ensuring that the forwarding states of all of routers  12  are able to synchronize within the defined time duration before converging from the temporary network topology to a new network topology. 
     In the current example, responsive to receiving a link-state advertisement that link  14 M has failed, each other router in the SR domain (e.g., in network  10  in the example of  FIG. 1 ) may not immediately begin converging to a new topology that does not include link  14 M. Instead, each of the other routers in network  10 , excluding PLR routers  12 F and  12 J, may start a timer having a maximum convergence time duration. The maximum convergence time duration is a time interval that is set in all routers  12 . The time interval of the maximum convergence time duration indicates a maximum amount of time for each of routers  12  to update its forwarding state to reflect the change in network topology caused by link failure  14 M and recompute routes that do not include communication link  14 M. Rather than immediately forwarding network packets according to a new network topology that does not include  14 M, each of routers  12  may configure its forwarding state to use a new network topology that does not include  14 M, but may only begin using the new network topology after the timer having the maximum convergence time has expired. 
     To illustrate, router  12 A may receive a link-state advertisement from NPLR  12 F that link  14 M has failed. Router  12 A may start a timer having a maximum convergence time duration and may not immediately converge to a new network topology in which it forwards packets to destination router  12 K using a path  18  that includes { 12 A,  12 B,  12 G,  12 J,  12 K}. Rather, router  12 A determines updated routes through network  10  for destinations affected by the failure of communication link  14 M and configures its forwarding state accordingly to apply node labels based on the updated routes, but continues to forward network traffic based on the original network topology, until the timer having a maximum convergence time duration has expired. 
     As further described in  FIGS. 2A-2E , while using the temporary network topology, routers in network  10  may use different, updated stacks of labels to temporarily forward network packets. Upon the maximum convergence time elapsing, router  12 A begins forwarding network traffic to destination router  12 K using path  18 . By not immediately converging to a new network topology in accordance with techniques of the disclosure, each router has a sufficient and defined amount of time to configure its forwarding state. In this way, the techniques may avoid the creation of micro-loops in which routers with unsynchronized forwarding information immediately begin forwarding packets on the new network topology in response to link-state advertisements. 
     In contrast to non-PLR routers (e.g., all routers except NPLR router  12 F and FPLR router  12 J), router  12 F, in response to detecting the failure of link  14 M, initiates a timer having a having a “maximum PLR duration” equal to:
 
2*(maximum convergence time duration)+maximum flooding duration
 
The maximum flooding duration may be equal to an amount of time used by a PLR router to flood network  10  with link state advertisements. The “maximum PLR duration” initiated by the PLR is also known by all of routers  12  in network  10  (e.g., within the SR domain) based on exchanging the maximum flooding duration and maximum convergence time durations when each router is initially configured and started up.
 
     During the maximum PLR duration, NPLR  12 F may re-route network traffic destined for destination router  12 K using backup sub-path  16 D that is included in a temporary network topology. Specifically, upon determining the failure of link  14 M, NPLR router  12 F re-configures its forwarding state to forward network traffic destined to destination router  12 K using backup sub-path  16 D. In some examples, backup sub-path  16 D is pre-computed by NPLR router  12 F in advance of the failure of link  14 M, while in other examples backup sub-path  16 D is computed in response to a link failure. In any case, NPLR router  12 F configures its forwarding plane to apply a stack of one or more adjacency labels to network packets destined for destination router  12 K that forces the network packets onto respective adjacencies between NPLR  12 F and FPLR  12 J, i.e., communication link  14 H and  14 I. In this way, NPLR router  12 F may forward the network packets using a set of one or more one-hop tunnels between NPLR router  12 F and router  12 J. 
     For purposes of this disclosure, an original or initial network topology, may refer to a logical topology in which node labels are applied by routers  12  in a physical topology prior to a link failure. A temporary network topology, as described in this disclosure, may refer to a logical topology in which a stack of adjacency labels are applied by one or more PLR routers to circumvent a failed communication link using a backup sub-path. In some examples of the temporary network topology, non-PLR routers may have not yet converged to a new network topology, and may apply a temporary node label stack to network packets destined for the destination as further described herein. A new or final network topology, as described in this disclosure, refers to a logical topology in which the PLR routers no longer use the stack of adjacency labels to forward network packets along the backup-sub path, but instead use node labels to forward network packets to a destination router while circumventing the failed network link. In a new network topology, one or more non-PLR routers use a node label stack to send network packets to a destination router that is different than a node label stack used to send network packets in the original network topology. 
     By using a stack of one or more adjacency labels rather than node labels to forward the network packets to router  12 H for a defined time duration, techniques of the disclosure may prevent micro-loops that would otherwise occur if the forwarding state of NPLR router  12 F were updated but the forwarding state of router  12 H had not yet been updated. That is, if routers  12 F and  12 H both continued forwarding network packets using node labels, but the assignments between node labels and routes in the forwarding state of router  12 H were not updated, router  12 H might potentially send the network packets back to NPLR router  12 F because reconfiguration of node labels corresponding to particular routes at router  12 H had not yet occurred although such reconfiguration had occurred at NPLR  12 F. Thus, techniques of the disclosure may prevent micro-loops by forwarding the network packets using the one-hop tunnel from router  12 F to router  12 H. 
     By using a stack of adjacency labels to provide one-hop tunnels in backup sub-path  16 D that circumvents failed link  14 M and re-routes traffic from NPLR router  12 F to FPLR router  12 J, techniques of the disclosure allow all other routers except those directly affected by the unavailability of sub-path  16 B to continue forwarding network packets destined to destination router  12 K in a similar manner prior to the failure of link  14 M. That is, routers using sub-paths  16 A and  16 C may continue to forward network traffic in a similar manner prior to the failure of link  14 M (but with a different stack of node labels, in some examples, as further described in  FIGS. 2A-2E ) until the expiration of the maximum convergence time duration. In this way, using the temporary network topology that includes sub-paths  16 A,  16 D and  16 C may require less forwarding state reconfiguration across all of routers  12 , while still avoiding micro-loops and providing fast re-routing. 
     As previously described, each non-PLR router of routers  12  re-configures its forwarding state to use a new network topology that does not include link  14 M within the maximum convergence time duration, but does not actually converge to the new network topology until the maximum convergence time duration has elapsed. Upon expiration of the respective timers at each respective non-PLR router of routers  12 , each non-PLR router begins forwarding network packets according to its updated forwarding state using the new topology. 
     Finally, after the expiration of a timer equal to the maximum PLR duration, NPLR router  12 F may converge onto the new network topology. In accordance with the new network topology, upon receiving a network packet from router  12 D that is destined for destination router  12 K, NPLR router  12 F applies one or more node labels to forward the network packet to router  12 H, rather than applying a stack of one or more adjacency labels that were used in the temporary network topology. In this way, router  12 F, using the new network topology after maximum PLR duration, may forward network packets to destination router  12 K using node labels. Router  12 H upon receiving the network packet may pop the node label from the packet that corresponds to NPLR router  12 F, push a node label to the packet that corresponds to router  12 H, and forward the network packet to FPLR router  12 J. As another example, router  12 B, which previously used path  16  to forward network traffic, using the new network topology, from router  12 A to destination router  12 K, may use path  18  based on its updated forwarding state. That is, router  12 B, upon receiving a network packet from router  12 A, may pop a node label that corresponds to router  12 A from the packet, push a label onto the packet that corresponds to router  12 B, and forward the network packet to router  12 G, rather than router  12 C, based on the updated forwarding state of router  12 B. Accordingly, in some examples, all routers implementing techniques of this disclosure may converge according to the process described in this disclosure. Thus, in some examples, router  12 B may also use a same two step convergence other routers, even though converging to path  18  may not cause any micro-loop. 
       FIGS. 2A-2E  are block diagrams illustrating, in further detail, an example system for reducing or otherwise preventing micro-loops in an Internet Protocol (IP)/Multiprotocol Label Switching (MPLS) network using Source Packet Routing in Networking (SPRING), in accordance with techniques of this disclosure. As shown in  FIGS. 2A-2E , network  10  of  FIG. 1  is again illustrated with routers  12  and communication links  14 .  FIG. 2A  illustrates example portions of forwarding states  32 A- 32 F (“forwarding states  32 ”) of various routers  12 . Forwarding state  32 A is included at router  12 B, forwarding state  32 B is included at router  12 C, forwarding state  32 C is included at router  12 D, forwarding state  32 D is included at router  12 F, forwarding state  32 E is included at router  12 H, forwarding state  32 F is included at router  12 J. 
     To illustrate information included in forwarding states  32 , forwarding state  32 A is further described herein for exemplary purposes. Forwarding state  32 A may include a node label range 6001-7000 this is set at initial startup and configuration of router  12 B. Node label range 6001-7000 may be globally unique to router  12 B among all other routers within the SR domain. Forwarding state  32 A may also include information that indicates a forwarding action performed by router  12 B. In particular, the information may specify the following: 6001→5001: Fwd S2. This information causes router  12 B, upon receiving a packet that includes node label 6001 to push node label 5001 onto the packet and forward to S2, which is router  12 C. In some examples, router  12 B may also pop node label 6001 prior to pushing node label 5001 onto the packet. 
     Router  12 B may determine that router  12 C is the next hop for the packet based equal-cost multi-path routing (ECMP) and/or best-path routing performed by router  12 B. That is, router  12 B, may set up or otherwise configure forwarding state  32 A to forward network packets received by router  12 B with node label 6001 to router  12 C, while applying node label 5001, based on a route determined using equal-cost multi-path routing (ECMP) and/or best-path routing. To configure forwarding states of respective routers, at initial configuration and startup of each of routers  12 , each router may advertise its label range and node identifier. Each router configures its forwarding state based on information it receives that indicates the unique label range and node identifier for each other router of routers  12 . Router  12 K has a node identifier of 1 (e.g., N-SID: 1, as shown in  FIG. 1 ), router  12 E has a node identifier of 2, router  12 I has a node identifier of 3, router  12 J has a node identifier of 4, and router  12 F has a node identifier of 5. In other words, in some examples, before detecting the failure of a communication link, NPLR router  12 F may receive at least one node label or range of node labels from one of the plurality of other network devices, wherein the at least one node label or range of node labels uniquely identifies the one of the plurality of other network devices in a segment routing domain that includes NPLR router  12 F, FPLR router  12 J and the plurality of other network devices. As further described herein, NPLR router  12 F may configure its forwarding state to apply the at least one node label or range of node labels that uniquely identifies the one of the plurality of other network devices to network packets destined for the destination network device. 
     One or more of routers  12  include respective forwarding states configured to apply node labels to forward network packets in network  10 . As one example, if router  12 A injects a packet into network  10  that is destined for destination router  12 K, it may push a label 6001 onto the packet and forward it to router  12 B. Label 6001 may be encoded to indicate both the node identifier of the destination router and a value within a range of a next hop router on the path to the destination router. For instance, the least significant digit of 6001 is a 1, which corresponds to the node identifier of destination router  12 K. Since the next hop router is router  12 B for a network packet destined to router  12 K from router  12 A, router  12 A may push a label with the value 6001 onto the packet. Based on the forwarding information included in forwarding states  32 , each of routers  12 B,  12 C,  12 D,  12 F, and  12 J forward the network packet to destination router  12 K as described above. As shown in  FIG. 2A , the network packet sent by router  12 A to destination router  12 K may traverse sub-paths  30 A- 30 C, which collectively comprise path  30 . 
     In addition to advertising node labels, each of routers  12  may advertise adjacency labels to other routers of routers  12 . For instance, router  12 H may configure its forwarding state to forward any packet with an adjacency label having a value of 102 onto communication link  14 I, as shown in  FIG. 2A . Router  12 H may advertise the adjacency label to NPLR router  12 F among other routers, which can apply the adjacency label to network packets forwarded to router  12 H, and which in turn causes router  12 H to forward the network packet onto link  14 I to FPLR router  12 J. As further described below, in the event of a link failure, rather than using a node label to re-route network packets destined for destination router  12 K to router  12 H, which may introduce micro-loops if the one or more of forwarding states  32 D and  32 E have not yet been updated, NPLR router  12 F may apply one or more adjacency labels to the network packets to re-route the packets on a backup sub-path around failed communication link  14 M. 
     In addition to configuring forwarding states at initial configuration, each of routers  12 , in accordance with techniques of the disclosure, may store a maximum flooding duration (or “MAX_FLOODING_DELAY” value) and maximum convergence time duration (or “MAX_CONVERGENCE_DELAY” value). In some examples, routers  12  may store a maximum PLR time duration based on MAX_FLOODING_DELAY and MAX_CONVERGENCE_DELAY, or may alternatively determine the maximum PLR time duration at runtime. In some examples, the maximum convergence time duration may be 1.6 seconds. In some examples, the maximum convergence time duration may be in a range of 0.1-5.0 seconds. In some examples, maximum flooding duration may be 0.5 seconds. In some examples, maximum flooding duration may be in a range of 0.1-5.0 seconds. As further described, in  FIG. 2B , each of routers  12  may set one or more timers according to MAX_FLOODING_DELAY and MAX_CONVERGENCE_DELAY in the event of a link failure. In some examples, MAX_CONVERGENCE_DELAY interval may be at least 3 times that of MAX_FLOODING_DELAY. In some examples, MAX_CONVERGENCE_DELAY may be the time needed by slowest router in the network to converge. 
     In accordance with techniques of the disclosure, one or more of routers  12  may pre-compute one or more backup sub-paths that enable the respective routers to continue forwarding packets to destinations in the event of a link failure. As one example, NPLR router  12 F may determine that a backup sub-path to FPLR router  12 J exists using communication links  14 H and  14 I, if communication link  14 M fails. Accordingly, NPLR router  12 F may store information in forwarding state  32 D that indicates a route corresponding to the backup sub-path that includes communication links  14 H and  14 I. As further described in  FIG. 2B , in the event that communication link  14 M fails, NPLR router  12 F may re-route a network packet destined for destination router  12 K to router  12 H by applying a stack of one or more adjacency labels to the packet and forwarding it using communication link  14 H. In other words, NPLR  12 F may, before detecting the failure of the communication link, receive one or more adjacency labels from one or more of the plurality of other network devices and pre-compute the backup sub-path that does not include the communication link. After detecting the failure of the communication link: NPLR router  12 F may configure, based on the pre-computing of the backup sub-path, a forwarding state of the NPLR to apply the one or more adjacency labels to network packets destined for the destination network device. Although described with respect to NPLR router  12 F, one or more other routers of routers  12  may similarly store information in their respective forwarding states that indicate routes corresponding to backup sub-paths. 
     In  FIG. 2B , NPLR router determines that link  14 M has failed. Responsive to determining the link failure, NPLR router  12 F floods the link-down/link-up event to all other routers in the network (including transit and source routers), for example, using link-state advertisements. In some examples, NPLR router  12 F sets a timer T 1  equal to a duration or interval of MAX_FLOODING_DELAY. NPLR router  12 F may flood link-state advertisements until timer T 1  expires. NPLR router  12 F may compute a new backup sub-path  16 D to FPLR router  12 J at the time of link failure, or alternatively, at initial configuration and startup. In any case, based on determining backup sub-path  16 D, NPLR router  12 F may construct a list of one or more adjacency labels that correspond to each of the communication links on backup sub-path  16 D computed by NPLR router  12 F. In other words, NPLR  12 F constructs a segment list using adjacency segments (instead of a single node segment) for each of the links on the new path computed. In the example of  FIG. 2B , NPLR router  12 F may include adjacency label  102  in the adjacency list. 
     NPLR router  12 F configures its forwarding state  32 D to push a label stack onto a packet destined for destination router  12 K that includes the adjacency label  102  in addition to the node label of FPLR router  12 J that would otherwise be applied prior to the failure of communication link  14 M. Accordingly, forwarding state  32 D includes information 3001→102, 1001: Fwd R4 that causes NPLR router  12 F, upon receiving a packet destined to destination router  12 K, to apply a label stack that includes adjacency label  102  and node label 1001, and forwards the packet to router  12 H (e.g., “R4”). In this way, NPLR router  12 F programs the segment list that includes the adjacency label(s) for the backup sub-path as the nexthop for all affected destinations which use the affected link/node (i.e., communication link  14 M) as a primary nexthop (within its own segment routing global block, a.k.a. SRGB). Consequently, if NPLR router  12 F receives a packet with the node segment for FPLR router  12 J, NPLR router  12 F will forward the traffic along backup sub-path  16 D and avoid failed communication link  14 M. NPLR router  12 F also holds convergence for each of the affected destinations (IP/IPV6/MPLS/SPRING) on to the new path in its data plane. 
     NPLR router  12 F may also initiate another timer upon detecting link failure  14 M. In particular, NPLR router  12 F may start a timer T 2  with an interval equivalent to:
 
2*MAX_CONVERGENCE_DELAY+MAX_FOODING_DELAY
 
As further described below, NPLR router  12 F may, upon expiration of T 2 , update its forwarding decisions in order to converge on the new network topology using an updated path from source router  12 A to destination router  12 K. In other words, responsive to detecting the failure of the communication link, NPLR router  12 F, for a defined time duration, applies one or more adjacency labels to network packets destined for a destination network device, wherein the one or more adjacency labels define a set of one-hop tunnels corresponding to a backup sub-path that circumvents the failed communication link. NPLR router  12 F may forward the network packets according to a temporary network topology that is based on the set of one-hop tunnels that provide the backup sub-path.
 
     Each of routers  12 , excluding NPLR router  12 F and FPLR router  12 J, upon receiving a link-state advertisement that indicates the failure of communication link  14 M, starts a timer T 3  with an interval that is equivalent to the maximum convergence delay (MAX_CONVERGENCE_DELAY). Each non-PLR router does not converge to the new network topology until timer T 3  expires. 
     In  FIG. 2C , upon receiving a link-state advertisement that indicates the failure of communication link  14 M, each of the source routers, including source routers  12 A,  12 C,  12 E, and  12 F, may perform further configuration of its respective forwarding state. Specifically, each of the source routers may determine destinations that are affected by the failure of communication link  14 M, such as destination router  12 K. For instance, source router  12 A determines that path  30  to destination router  12 K has been affected by the failure of communication link  14 M. Responsive to this determination, source router  12 A computes a label stack with a first node label that corresponds to router  12 B along path  30  and a second node label that corresponds to NPLR router  12 F. In other words, upon receiving the link-down event via IGP, each source router computes a segment list with following segments: (1) a node segment for reaching near-side PLR (e.g., router  12 B in the case of source router  12 A), (2) followed by a node segment advertised by the near-side PLR (e.g., NPLR  12 F in the case of source router  12 A) for the destination (e.g., destination router  12 K). 
     Each source router configures its forwarding state to apply its respective label stack to each network packet injected into network  10  that is destined for destination router  12 K. For example, router  12 A (a source router), when injecting a packet into network  10  that is destined for destination router  12 K applies a label stack that includes (1) a node label 6005 (e.g., a node segment ID for router  12 B that is used for reaching NPLR router  12 F) and (2) a node label 3001 (a node segment ID advertised by NPLR router  12 F that is used for reaching destination router  12 K). In other words, forwarding, while the timer T 3  has not expired, network packets destined for the destination network device according to the temporary network topology may include: responsive to determining that the network packets are destined for the destination network device, applying, by the non-PLR router (e.g., a source router or a transit router), a label stack (e.g., a temporary label stack) to each of the network packets, wherein the label stack includes (1) a first node label that corresponds to a next hop router on a path to reach the NPLR; and (2) a second node label that corresponds to destination. Then, responsive to the expiration of timer T 3 , the non-PLR router may forward network packets destined for the destination network device according to the new network topology. 
     Accordingly, router  12 A includes forwarding state  32 G that indicates LSP-to-D: Push 6005, 3001: Fwd R1. Forwarding state  32 G causes source router  12 A to, when injecting a packet into network  10  that is destined for router  12 K, apply a label stack that includes node labels 6005 and 3001, and forward the network packet to router  12 B. As shown in  FIG. 2C , the node segment for reaching the near-side PLR, i.e., 6005, includes a least significant digit of 5, which corresponds to the node identifier of NPLR  12 F. The node segment ID for reaching the near-side PLR is therefore encoded with a node identifier of the near-side PLR as the destination, while the node segment advertised by the near-side PLR, i.e., 3001, is encoded with the node identifier of the destination for the packet that is destination router  12 K. 
     As described above, each source router programs the corresponding route in its forwarding state with the above segment ID list computed above. This causes all IP/IPV6/MPLS packets to be sent to the destination, to be encapsulated in a SPRING data-plane header with the segment list computed above, forcing the packet to go all the way to near-side PLR router  12 F. The packet, on reaching near-side PLR  12 F, is forwarded to the far-side PLR router  12 J on a path (e.g., backup sub-path  30 D), computed by near-side PLR  12 F, thereby avoiding the failed link. On reaching the far-side PLR router  12 J, the packet is forwarded on its regular path from the far-side PLR to destination router  12 K. 
     As described in  FIG. 2C , upon receiving a link-state advertisement that communication link  14 M has failed, source router  12 A uses a temporary network topology comprised of sub-paths  30 A,  30 D, and  30 B to forward network traffic to destination router  12 K. While using the temporary network topology, source router  12 A re-configures its forwarding state to use a new network topology as described in  FIG. 2E , but does not converge to the new network topology until its timer T 3  expires. In this way, each of routers  12  has a duration of MAX_CONVERGENCE_DELAY to update its forwarding state to use the new network topology, while still forwarding network traffic using the temporary network topology. 
     In other words, a non-PLR router may configure, before timer T 3  has expired, its forwarding state to forward network packets according to the new network topology, but forward, while the timer T 3  has not expired, network packets destined for the destination network device according to the temporary network topology. In such examples, forwarding network packets destined for the destination network device according to the new network topology may include the non-PLR router applying, to a first network packet destined for the destination network device, a first node label that is different than a second node label, wherein the second node label was applied to a second network packet based on the original network topology, and wherein the second network packet was destined for the same destination network device. 
       FIG. 2D  illustrates the expiration of timer T 3  at all of the non-PLR routers. At the expiration of timer T 3 , each non-PLR router triggers normal convergence and converges onto the new network topology. For instance, upon expiration of timer T 3 , each of source routers  12 A,  12 C,  12 E, and  12 F configures its respective forwarding state in the following manner. Using source router  12 A as an example, upon expiration of its timer T 3 , source router  12 A computes a label stack with a first node label that corresponds to router  12 B along path  30 , a second node label that corresponds to NPLR router  12 F, and a third label that corresponds to FPLR router  12 J. In other words, upon expiration of timer T 2 , each source router computes a segment list with following segments: (1) a node segment for reaching near-side PLR (e.g., router  12 B in the case of source router  12 A), (2) a node segment advertised by the near-side PLR (e.g., NPLR  12 F in the case of source router  12 A), and (3) a node segment advertised by the far-side PLR (e.g., FPLR  12 J in the case of source router  12 A) for the destination (e.g., destination router  12 K). 
     As described in the example above with respect to source router  12 A, each source router configures its forwarding state to apply its respective label stack (e.g., segment list) to each network packet injected into network  10  that is destined for destination router  12 K. For example, router  12 A (a source router), when injecting a packet into network  10  that is destined for destination router  12 K applies a label stack that includes (1) a node label 6005 (e.g., a node segment for router  12 B that is used for reaching NPLR router  12 F) (2) a node label 3004 (a node segment advertised by NPLR router  12 F that is used for reaching FPLR  12 J), and (3) a node label 1001 (a node segment advertised by FPLR router  12 J that is used for reaching destination router  12 K). Accordingly, router  12 A includes forwarding state  32 G that indicates LSP-to-D: Push 6005, 3004, 1001: Fwd R1. Forwarding state  32 G causes source router  12 A to, when injecting a packet into network  10  that is destined for router  12 K, apply a label stack that includes node labels 6005, 3004, and 1001, and forward the network packet to router  12 B. 
     As shown in  FIG. 2D , the node segment for reaching the near-side PLR, i.e., 6005, includes a least significant digit of 5, which corresponds to the node identifier of NPLR  12 F. The node segment ID for reaching the near-side PLR is therefore encoded with a node identifier of the near-side PLR as the destination. The node segment advertised by the near-side PLR, i.e., 3004, is encoded with the node identifier of the far-side PLR, i.e., FPLR  12 J. Finally, the node segment advertised by the far-side PLR, i.e., 1001, is encoded with the node identifier of the destination for the packet that is destination router  12 K. 
       FIG. 2E  illustrates the updated forwarding states of routers  12  after the expiration of timer T 2  at NPLR router  12 F and FPLR router  12 J. Upon expiration of timer T 2 , NPLR router  12 F updates all the corresponding node segments in its global segment block for FPLR  12 J as per the new network topology. For instance, as shown in  FIG. 2E , NPLR router  12 F configures its forwarding state  32 D to update entry 3001→102, 1001: Fwd R4 from  FIG. 2D  to 3001→2001: Fwd R4 in  FIG. 2E . Accordingly, NPLR router  12 F, when receiving a network packet with node label 3001, applies a node label 2001 corresponding to router  12 H and forwards the network packet to router  12 H. Similarly, as shown in  FIG. 2E , NPLR router  12 F configures its forwarding state  32 D to update entry 3004→102: Fwd R4 from  FIG. 2D  to 3004→2004: Fwd R4. Thus, NPLR router  12 F, when receiving a network packet with node label 3004, applies a node label 2004 corresponding to router  12 H and forwards the network packet to router  12 H. In other words, upon expiration of the defined time duration, NPLR router  12 F forwards, according to the new network topology that is not based on applying the one or more adjacency labels that define the set of one-hop tunnels, network packets destined for the destination network device. 
     As further shown in  FIG. 2E , source routers  12 A,  12 C,  12 E, and  12 I, forward network packets to destination  12 K according to the new network topology. To illustrate, source router  12 A configures its forwarding state  32 G to update entry LSP-to-D: Push 6005, 3004, 1001: Fwd R1 in  FIG. 2D  to LSP-to-D: Push 6001: Fwd R1 in  FIG. 2E . Accordingly, source router  12 A, when injecting a network packet into network  10  that is destined for destination router  12 K, applies a node label 6001 corresponding to router  12 H and forwards the network packet to router  12 B. Router  12 B, which updated its forwarding information  12 B in  FIG. 2D  to include the entry 6001→7001: Fwd R3, pushes label on the label stack of the network packet and forwards the network packet to router  12 G. In other words, the network packet sent by source router  12 A to destination router  12 K traverses path  34  in the new network topology of  FIG. 2E  rather than sub-paths  30 A,  30 D and  30 C in the original and temporary network topologies of  FIGS. 2B-2D . In some examples, the nexthop for router  12 K may not change at FPLR router  12 J when link  14 M goes down in  FIG. 2E . In some examples, the techniques described in this disclosure with respect to NPLR router  12 K may be similarly applied by one or more other routers of router  12  for destinations that get impacted due to link  14 M going down. 
       FIG. 3  is a block diagram illustrating an exemplary router capable of reducing or otherwise preventing micro-loops in an Internet Protocol (IP)/Multiprotocol Label Switching (MPLS) network using Source Packet Routing in Networking (SPRING), in accordance with techniques of this disclosure. Router  51  may comprise any router in a network, such as network  10 . For example, router  51  may comprise a source router, a PLR router, a destination router, or any transit router illustrated in  FIGS. 1-2 . For purposes of illustration, router  51  is described as an NPLR router. 
     In the example of  FIG. 3 , router  51  includes control unit  50  in which routing engine  26  provides control plane functionality for router  51 . Router  51  also includes a plurality of packet-forwarding engines  52 A- 52 N (“PFEs  52 ”) and a switch fabric  54  that collectively provide a data plane for forwarding network traffic. PFEs  52  receive and send data packets via interface cards  56  (“IFCs  56 ”). In other embodiments, each of PFEs  52  may comprise more or fewer IFCs. Although not shown, PFEs  52  may each comprise a central processing unit (CPU) and a memory. In this example, routing engine  58  is connected to each of PFEs  52  by a dedicated internal communication link  60 . For example, dedicated link  60  may comprise a Gigabit Ethernet connection. Switch fabric  54  provides a high-speed interconnect for forwarding incoming data packets between PFEs  52  for transmission over a network. U.S. patent application Ser. No. 11/832,342, entitled MULTI-CHASSIS ROUTER WITH MULTIPLEXED OPTICAL INTERCONNECTS, describes a multi-chassis router in which a multi-stage switch fabric, such as a 3-stage Clos switch fabric, is used as a high-end forwarding plane to relay packets between multiple routing nodes of the multi-chassis router. The entire contents of U.S. patent application Ser. No. 11/832,342 are incorporated herein by reference. 
     Routing engine  58  provides an operating environment for execution of various protocols  60  that may comprise software processes having instructions executed by a computing environment. As described in further detail below, protocols  60  provide control plane functions for storing network topology in the form of routing tables or other structures, executing routing protocols to communicate with peer routing devices and maintain and update the routing tables, and providing management interface(s) to allow user access and configuration of router  51 . Control unit  50  provides an operating environment for routing engine  58  and may be implemented solely in software, or hardware, or may be implemented as a combination of software, hardware or firmware. For example, control unit  50  may include one or more processors which execute software instructions. In that case, routing engine  58  may include various software modules or daemons (e.g., one or more routing protocol processes, user interfaces and the like), and control unit  50  may include a computer-readable storage medium, such as computer memory or hard disk, for storing executable instructions. 
     Command line interface daemon  62  (“CLI  62 ”) provides an interface by which an administrator or other management entity may modify the configuration of router  51  using text-based commands. Simple Network Management Protocol daemon  65  (“SNMP  65 ”) comprises an SNMP agent that receives SNMP commands from a management entity to set and retrieve configuration and management information for router  51 . Using CLI  62  and SNMP  65 , management entities may enable/disable and configure services, install routes, enable/disable and configure rate limiters, and configure interfaces, for example. 
     One or more routing protocols, such as IGP  66 , maintains routing information in the form of routing information base (RIB)  68  that describes a topology of a network, and derives a forwarding information base (FIB)  72  in accordance with the routing information. In general, the routing information represents the overall topology of the network. IGP  66  interacts with kernel  70  (e.g., by way of API calls) to update routing information base (RIB)  68  based on routing protocol messages received by router  51 . RIB  68  may include information defining a topology of a network, including one or more routing tables and/or link-state databases. Typically, the routing information defines routes (i.e., series of next hops) through a network to destinations/prefixes within the network learned via a distance-vector routing protocol (e.g., BGP) or defines the network topology with interconnected links learned using a link state routing protocol (e.g., IS—IS or OSPF). In contrast, FIB  72  is generated based on selection of certain routes within the network and maps packet key information (e.g., destination information and other select information from a packet header) to one or more specific next hops and ultimately to one or more specific output interface ports of IFCs  56 . Routing engine  58  may generate the FIB in the form of a radix tree having leaf nodes that represent destinations within the network. U.S. Pat. No. 7,184,437 provides details on an exemplary embodiment of a router that utilizes a radix tree for route resolution, the contents of which is incorporated herein by reference in its entirety. 
     LDP  68  executes the Label Distribution Protocol to exchange MPLS labels for enabling label-based packet forwarding as described herein. In one example, LDP  68  operates in conformance with specifications set forth in in Andersson, L., et al, “LDP Specification”, RFC 3036, January 2001, and/or Andersson, L., et al, “LDP Specification”, RFC 5036, October 2007, the entire contents of each being incorporated herein by reference. 
     SPRING  65  executes the Source Packet Routing in Networking (SPRING) protocol. Using SPRING  65 , router  51  forwards packets using node and adjacency labels as described with respect to  FIGS. 1-2 . In some examples, SPRING  65  implements the SPRING protocol in conformance with one or more of the following specifications, the entire contents of which are incorporated herein by reference:
         (1) “SPRING Problem Statement and Requirements,” IETF draft: draft-ietf-spring-problem-statement-01, Jun. 26, 2014   (2) “Segment Routing Architecture,” IETF draft: draft-filsfils-spring-segment-routing-04, Jul. 3, 2014   (3) “Segment Routing with MPLS data plane,” IETF draft: draft-filsfils-spring-segment-routing-mpls-03, Aug. 1, 2014   (4) “Segment Routing Use Cases,” IETF draft: draft-filsfils-spring-segment-routing-use-cases-00, Mar. 27, 2014   (5) “IS-IS Extensions for Segment Routing,” IETF draft: draft-ietf-isis-segment-routing-extensions-02, Jun. 18, 2014   (6) “OSPF Extensions for Segment Routing,” IETF draft: draft-psenak-ospf-segment-routing-extensions-05, Jun. 5, 2014   (7) “OSPFv3 Extensions for Segment Routing,” IETF draft: draft-psenak-ospf-segment-routing-ospfv3-extension-02, Jul. 2, 2014   (8) “BGP Link-State extensions for Segment Routing,” IETF draft: draft-gredler-idr-bgp-1s-segment-routing-extension-00, Aug. 18, 2014   (9) “Segment Routing Egress Peer Engineering BGPLS Extensions,” IETF draft: draft-previdi-idr-bgpls-segment-routing-epe-00, May 26, 2014   (10) “IPv6 Segment Routing Header (SRH),” IETF draft: draft-previdi-6man-segment-routing-header-02, Jul. 3, 2014.
 
Although techniques of the disclosure are described with respect to MPLS labels in some instances for example purposes, techniques of the disclosure may be similarly applied using IPv6 headers.
       

     Routing engine  58  communicates data representative of a software copy of the FIB  72  into each of PFEs  52  to control forwarding of traffic within the data plane. This allows the software FIB stored in memory (e.g., RAM) in each of PFEs  52  to be updated without degrading packet-forwarding performance of router  51 . In some instances, routing engine  58  may derive separate and different software FIBs for each respective PFEs  52 . In addition, one or more of PFEs  52  include application-specific integrated circuits (ASICs  74 ) that PFEs  52  program with a hardware-copy of the FIB based on the software FIBs (i.e., hardware versions of the software FIBs) copied to each respective PFE  52 . 
     For example, kernel  70  executes on master microprocessor  52  and may comprise, for example, a UNIX operating system derivative such as Linux or Berkeley Software Distribution (BSD). Kernel  70  processes kernel calls from IPG  66 , LDP  68 , and SPRING  65  to generate forwarding information in the form of FIB  72  based on the network topology represented in RIB  68 , i.e., performs route resolution and path selection. Typically, kernel  70  generates FIB  72  in the form of radix or other lookup trees to map packet information (e.g., header information having destination information and/or a label stack) to next hops and ultimately to interface ports of interface cards associated with respective PFEs  52 . FIB  72  may associate, for example, network destinations with specific next hops and corresponding IFCs  56 . For MPLS-related traffic forwarding, FIB  72  stores, label information that includes an incoming label, an outgoing label, and a next hop for a packet. 
     Master microprocessor  52  executing kernel  70  programs PFEs  52  to install copies of the FIB  72 . Microprocessor  52  may comprise one or more general- or special-purpose processors such as a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), or any other equivalent logic device. Accordingly, the terms “processor” or “controller,” as used herein, may refer to any one or more of the foregoing structures or any other structure operable to perform techniques described herein. 
     In this example, ASICs  74  are microcode-controlled chipsets (i.e., forwarding circuits) programmably configured by a slave microprocessor executing on each of PFEs  52 . When forwarding packets, control logic with each ASIC  74  traverses the forwarding information (FIB  72 ) received from routing engine  58  and, upon reaching a FIB entry for the packet (e.g., a leaf node), microcode-implemented control logic  56  automatically selects a forwarding next hop and processes the packets in accordance with the operations defined within the next hop. In this way, ASICs  74  of PFEs  52  process packets by performing a series of operations on each packet over respective internal packet forwarding paths as the packets traverse the internal architecture of router  51 . Operations may be performed, for example, on each packet based on any of a corresponding ingress interface, an ingress PFE  52 , an egress PFE  52 , an egress interface or other components of router  51  to which the packet is directed prior to egress, such as one or more service cards. PFEs  52  each include forwarding structures that, when executed, examine the contents of each packet (or another packet property, e.g., incoming interface) and on that basis make forwarding decisions, apply filters, and/or perform accounting, management, traffic analysis, and load balancing, for example. 
     In one example, each of PFEs  52  arranges forwarding structures as next hop data that can be chained together as a series of “hops” along an internal packet forwarding path for the network device. In many instances, the forwarding structures perform lookup operations within internal memory of ASICs  74 , where the lookup may be performed against a tree (or trie) search, a table (or index) search. Other example operations that may be specified with the next hops include filter determination and application, or a rate limiter determination and application. Lookup operations locate, within a lookup data structure (e.g., a lookup tree), an item that matches packet contents or another property of the packet or packet flow, such as the inbound interface of the packet. The result of packet processing in accordance with the operations defined by the next hop forwarding structure within ASICs  74  determines the manner in which a packet is forwarded or otherwise processed by PFEs  52  from its input interface on one of IFCs  56  to its output interface on one of IFCs  56 . 
     In accordance with techniques of the disclosure, and with reference to the examples of  FIGS. 1-2 , router  51  may, at initial configuration and startup, advertise one or more adjacency labels that corresponds to adjacencies or network links/interfaces included in or coupled to router  51 . Router  51  may also advertise one or more node labels and/or one or more node label ranges. The node label(s) and/or label range(s) may be uniquely associated with router  51  in the SR domain. Routing engine  58  may store information that represents the one or more node labels and adjacency labels as label data  78 . Router  51  may also receive adjacency labels and node labels and/or node label ranges from other routers in the same SR domain. Label data  78  may also include information that represents the one or more node labels and adjacency labels received from other routers in the same SR domain. In some examples, router  51  may receive and set timer information that corresponds to MAX_FLOODING_DELAY and MAX_CONVERGENCE_DELAY. 
     As described above, routing engine  58  may use one or more protocols to determine routes through network  10  to, for example, destination router  12 K. Routing engine  58  may configure FIB  72  to use a label stack of one or more labels of label data  78  as the next hop for forwarding network packets to destination router  12 K. In some examples, forwarding state  32 A of  FIG. 2  may be included in FIB  72 , which routing engine  58  programs or otherwise uses to configure ASICS  74  of PFEs  52 . In this way, when ASICS  74  performs a lookup on a network packet destined for destination router  12 K, ASICS  74  may apply one or more labels to the network packet and forward it to the appropriate next hop router using the appropriate one of interfaces  56 . 
     Routing engine  58  may include a failover module (FM)  80  that implements techniques of this disclosure to prevent or reduce micro-loops. Although shown as a part of routing engine  58 , in some examples, FM  80  may be included in one or more of PFEs  52 . In some examples, functionality of FM  80  may be divided or otherwise split across PFEs  52  and routing engine  58 . FM  80  may be implemented as software, hardware, or a combination of software and hardware. 
     Initially, router  51  may forward network traffic destined for router  12 K using communication link  14 M, as described in  FIGS. 1-2 . However, communication link  14 M may fail at a later time. PFE  52 A may initially determine that one of IFCs  56  coupled to communication link  14 M is unable to transmit data. PFE  52 A may send information via communication link  60  to routing engine  58  indicating the link failure. Failover module  80 , upon determining a link failure has occurred, causes one or more of PFEs  52  to flood link state advertisements to the other routers of network  10  that indicates that the link failure has occurred. 
     Failover module (FM)  80 , in response to determining that communication link  14 M has failed, may determine a backup sub-path  30 D as illustrated in  FIGS. 2B-2E . As described in  FIGS. 2A-2E , backup sub-path  30  may circumvent failed communication link  14 M. Whether backup sub-path  30  is determined responsive to the failure of communication link  14 M or pre-computed at initial configuration and startup, failover module  80  may use protocols  60  to determine one or more next hop routers along backup sub-path  30 . In accordance with techniques of the disclosure, failover module  80  may construct a list of one or more adjacency labels that correspond to each of the links on backup sub-path  30 D computed by router  51 . In other words, router  51  constructs a segment list using adjacency segments for each of the links on the new path computed. Kernel  70  may receive the list of one or more adjacency labels, which kernel  70  uses to re-configure FIB  72 . As described above, master microprocessor  52  executing kernel  70  may install copies of the updated FIB  72  into one or more of PFEs  52 . 
     To further illustrate with reference to the example of  FIG. 2B-2D , ASIC  74 A, for example, upon receiving a network packet destined for router  12 K, pushes a label stack onto a packet destined for destination router  12 K that includes the adjacency label  102  in addition to the node label of FPLR router  12 J that would otherwise be applied prior to the failure of communication link  14 M. Accordingly, FIB  72  includes information 3001→102, 1001: Fwd R4 that causes ASIC  74 A (or another one of ASICs  74  if the packet is internally forwarded on switch fabric  54 ), upon receiving a packet destined to router  12 K, to apply a label stack that includes adjacency label  102  and node label 1001, and forwards the packet to router  12 H (e.g., “R4”) based on the interface that corresponds to router  12 H as indicated in FIB  72 . Consequently, if ASIC  74 A receives a packet with the node segment for FPLR router  12 J, ASIC  74 A will forward the packet using backup sub-path  30 D and avoid failed communication link  14 M. 
     In accordance with techniques of the disclosure, FM  80  sets a timer T 1  in timers  76  equal to a duration or interval of MAX_FLOODING_DELAY responsive to detecting the link failure. Router  51  may flood link-state advertisements until timer T 1  expires. FM  80  may also, responsive to detecting the link failure, start a timer T 1  in timers  76  with a duration or interval equivalent to:
 
2*MAX_CONVERGENCE_DELAY+MAX_FOODING_DELAY
 
As further described below, router  51  may, upon expiration of T 1 , update its forwarding decisions.
 
     As described in  FIGS. 2A-2E , each non-PLR router of routers  12  (e.g., excluding NPLR router  51  and FPLR router), upon receiving a link-state advertisement (e.g., using IGP) that indicates the failure of communication link  14 M, start a timer T 3  with an interval that is equivalent to the maximum convergence delay (MAX_CONVERGENCE_DELAY). Each non-PLR router of routers refrains from converging onto the new network topology until the expiration of timer T 3 . 
     Upon receiving a link-state advertisement that indicates the failure of communication link  14 M, each of the source routers may determine destinations that are affected by the failure of communication link  14 M, such as destination router  12 K. For instance, source router  12 A determines that path  30  to destination router  12 K has been affected by the failure of communication link  14 M. Responsive to this determination, source router  12 A computes a label stack with a first node label that corresponds to router  12 B along path  30  and a second node label that corresponds to NPLR router  12 F. Each source router configures its forwarding state to apply its respective label stack to each network packet injected into network  10  that is destined for destination router  12 K. At the expiration of timer T 3 , all of the non-PLR routers converge onto the new network topology. 
     Upon expiration of timer T 2  in timers  76 , NPLR router  12 F updates the forwarding state of all the corresponding node segments in its global segment block for the remote PLR as per the new forwarding topology. For instance, kernel  70  may receive information from failover module  80  to configure FIB  72  to update entry 3001→102, 1001: Fwd R4 from  FIG. 2D  to 3001→2001: Fwd R4 in  FIG. 2E . Master microprocessor  52  using kernel  70  may configure one or more of ASICs  74  with the updated FIB  72 . Accordingly, ASICs  74 , when receiving a network packet with node label 3001, applies a node label 2001 corresponding to router  12 H and forwards the network packet to router  12 H using the interface indicated by FIB  72 . Similarly, as shown in  FIG. 2E , kernel  70  receives information from FM  80  to update entry 3004→102: Fwd R4 from  FIG. 2D  to 3004→2004: Fwd R4 in FIB  72 . Master microprocessor  52  using kernel  70  updates ASICs  74  accordingly. In this way, ASICs  74 , when receiving a network packet with node label 3004, applies a node label 2004 corresponding to router  12 H and forwards the network packet to router  12 H using the interface indicated by FIB  72 . Thus, after router  12 F updates and converges the node segment of FPLR  12 J as per new the topology that does not include communication link  14 M, NPLR  12 F uses node labels, rather than the previously used adjacency labels, to forward network to destination router  12 K. 
     As described in  FIG. 2 , upon expiration of timers T 2  at source routers  12 A,  12 C,  12 E, and  12 I, each of the source routers updates its respective forwarding information to forward network packets to destination  12 K according to the new network topology. To illustrate, source router  12 A configures its forwarding state  32 G to update entry LSP-to-D: Push 6005, 3004, 1001: Fwd R1 in  FIG. 2D  to LSP-to-D: Push 6001: Fwd R1. Accordingly, source router  12 A, when injecting a network packet into network  10  that is destined for destination router  12 K, applies a node label 6001 corresponding to router  12 H and forwards the network packet to router  12 B. Router  12 B, which updated its forwarding information  12 B in  FIG. 2D  to include the entry 6001→7001: Fwd R3, pushes label on the label stack of the network packet and forwards the network packet to router  12 G. In other words, the network packet sent by source router  12 A to destination router  12 K traverses path  34  in  FIG. 2E  rather than sub-paths  30 A,  30 D and  30 C in original and temporary network topologies of  FIGS. 2B-2E . 
     The architecture of router  51  illustrated in  FIG. 3  is shown for exemplary purposes only. This disclosure is not limited to this architecture. In other examples, router  51  may be configured in a variety of ways. In one example, some of the functionally of control unit  50  may be distributed within IFCs  56 . Control unit  82  may be implemented solely in software, or hardware, or may be implemented as a combination of software, hardware, or firmware. For example, control unit  50  may comprise one or more of a processor, a programmable processor, a general purpose processor, an integrated circuit, an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA), or any type of hardware unit capable of implementing the techniques described herein. Control unit  50  may further include one or more processors which execute software instructions stored on a computer readable storage medium, such as 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. In some instances, the computer-readable storage medium may include instructions that cause a programmable processor to perform the techniques described herein. 
       FIG. 4  is a flowchart that illustrates example operations of a router of  FIG. 1  that implements techniques for reducing or otherwise preventing micro-loops in an Internet Protocol (IP)/Multiprotocol Label Switching (MPLS) network using Source Packet Routing in Networking (SPRING), in accordance with techniques of this disclosure. For purposes of illustration only, the example operations are described below within the context of router  12 F and router  51 , as shown in  FIGS. 1-3 . In some examples, FM module  80  of  FIG. 3  may perform one or more of the techniques of  FIG. 4 . 
     Router  12 F, which may be a PLR router, may initially exchange node labels, adjacency labels, and timer intervals as described in  FIGS. 1-3  ( 100 ). In particular, router  12 F may advertise a node label range that is uniquely associated with router  12 F. Router  12 F may also advertise one or more adjacency labels that correspond to communication links directly coupled to router  12 F. In addition, router  12 F may receive timer intervals corresponding to MAX_FLOODING_DELAY and MAX_CONVERGENCE_DELAY advertised by another router in the SR domain and store this information for later use. Alternatively, router  12 F may determine MAX_FLOODING_DELAY and MAX_CONVERGENCE_DELAY as previously stored values and advertise the values to the other routers in the SR domain. 
     Router  12 F may configure its forwarding state to forward network packets using node labels as described in  FIGS. 1-3  ( 101 ). For instance, router  12 F may determine one or more routes through network  10  to destination router  12 K. Router  12 F may configure its forwarding state to forward network packets destined for destination router  12 K using node labels as described in  FIGS. 1-3 . At a later time, router  12 F may detect a link failure at communication link  14 M ( 102 ). Responsive to detecting the link failure, router  12 F may advertise the link failure to other routers in the SR domain ( 104 ). For instance, router  12 F may send link state advertisements that indicate the link that has failed. In response to detecting the link failure, router  12 F may also start a timer ( 106 ) with an interval that is equal to:
 
MAX_FLOODING_DELAY+2*MAX_CONVERGENCE_DELAY
 
     In accordance with techniques of the disclosure, responsive to detecting the link failure, router  12 F may also determine a backup sub-path from router  12 F (an NPLR router) to the FPLR router (e.g., FPLR router  12 J) that circumvents the failed link. Router  12 F may determine a list of adjacency labels for each link of the backup path from router  12 F to router  12 J. Based on determining the backup sub-path, router  12 F may update its forwarding state to apply the list of adjacency labels as a label stack to each network packet destined to destination router  12 K ( 108 ). 
     Upon configuring its forwarding state, router  12 F may forward any network packets destined for destination router  12 K using the list of adjacency labels ( 110 ). By applying the list of adjacency labels rather than node labels, techniques of the disclosure implemented by router  12 F may prevent or reduce micro-loops. While router  12 F is forwarding network packets to destination router  12 K using adjacency labels, the other routers of network  10  (excluding FPLR router  12 J) update their respective forwarding states based on the failure of communication link  14 M; however, the other routers do not converge onto a new network topology that does not include communication link  14 M until an interval of MAX_CONVERGENCE_DELAY has passed. By waiting until an interval of MAX_CONVERGENCE_DELAY has passed until the non-PLR routers converge, techniques of the disclosure may prevent or reduce micro-loops in the event of link failure. 
     Router  12 F may determine whether its timer (with an interval of MAX_FLOODING_DELAY+2*MAX_CONVERGENCE_DELAY) has expired ( 112 ). If the timer has not expired ( 116 ), router  12 F continues to forward network packets to destination router  12 K using the list of adjacency labels as described above ( 110 ). If, however, the timer at router  12 F has expired, router  12 F may update its forwarding state to apply node labels according to the new network topology that does not include the failed communication link ( 118 ). In other words, router  12 F may not use the list of adjacency labels that correspond to the backup sub-path to forward network packets to destination router  12 J after the timer has expired. In some examples, router  12 F may apply one or more node labels that correspond to one or more next hop routers to forward network packets to destination router  12 K. In some examples, the one or more next hop routers are the routers in the backup sub-path, which are now used as the primary path for network packets forwarded by router  12 F and destined for destination router  12 K. 
       FIG. 5  is a flowchart that illustrates example operations of a non-PLR router and a PLR router of  FIGS. 1-4 , that implement techniques for reducing or otherwise preventing micro-loops in an Internet Protocol (IP)/Multiprotocol Label Switching (MPLS) network using Source Packet Routing in Networking (SPRING), in accordance with techniques of this disclosure. For example purposes only, the techniques of  FIG. 5  are described with respect to NPLR router  12 F (e.g., PLR router) and source router  12 A (e.g., non-PLR router). Router  12 F and non-PLR router  12 A may initially exchange node labels, adjacency labels, and timer intervals as described in  FIGS. 1-4  ( 200 ). In particular, router  12 F may advertise a node label range that is uniquely associated with router  12 F. Router  12 F may also advertise one or more adjacency labels that correspond to communication links directly coupled to router  12 F. In addition, router  12 F may receive timer intervals corresponding to MAX_FLOODING_DELAY and MAX_CONVERGENCE_DELAY advertised by another router in the SR domain and store this information for later use. Alternatively, router  12 F may determine MAX_FLOODING_DELAY and MAX_CONVERGENCE_DELAY as previously stored values and advertise the values to the other routers in the SR domain. Non-PLR router  12 A may perform similar action as described with respect to PLR router  12 F. 
     Router  12 F and non-PLR router  12 A may each configure its respective forwarding state to forward network packets using node labels as described in  FIGS. 1-4  ( 202 ). For instance, each of router  12 F router non-PLR router  12 A may determine one or more routes through network  10  to destination router  12 K. Router  12 F and router  12 A may each configure its forwarding state to forward network packets destined for destination router  12 K using node labels as described in  FIGS. 1-4 . A 
     At a later time, router  12 F may detect a link failure at communication link  14 M ( 204 ). Responsive to detecting the link failure, router  12 F may initiate timers T 1  and T 2  as described in  FIGS. 2-4  ( 206 ). Timer T 1  may have a duration of MAX_FLOODING_DELAY and timer T 2  may have a duration of MAX_FLOODING_DELAY+2*MAX_CONVERGENCE_DELAY. Router  12 F may advertise the link failure to other routers in the SR domain until T 1  expires, e.g., for a duration of MAX_FLOODING_DELAY ( 208 ). For instance, router  12 F may send link state advertisements that indicate the link that has failed. 
     Responsive to detecting the link failure, router  12 F may also determine a backup sub-path from router  12 F (an NPLR router) to the FPLR router (e.g., FPLR router  12 J) that circumvents the failed link. Router  12 F may determine a list of adjacency labels for each link of the backup path from router  12 F to router  12 J. Based on determining the backup sub-path, router  12 F may update its forwarding state to apply the list of adjacency labels as a label stack to each network packet destined to destination router  12 K. Upon configuring its forwarding state, router  12 F may forward any network packets destined for destination router  12 K using the list of adjacency labels ( 210 ). By applying the list of adjacency labels rather than node labels, techniques of the disclosure implemented by router  12 F may prevent or reduce micro-loops. 
     Router  12 A, may receive a link-state advertisement that indicates the failed link, as router  12 F is flooding the link down event ( 212 ). Responsive to receiving the link-state advertisement, router  12 A initiates a timer T 3  that is equal to MAX_CONVERGENCE_DELAY ( 214 ). Router  12 A updates its forwarding state based on the failure of communication link  14 M to apply node labels for a new network topology that does not include the failed link ( 216 ). However, router  12 A does not converge onto the new network topology until timer T 3  has expired. In other words, router  12 A continues to forward network traffic to destination router  12 K using a temporary network topology that includes the backup sub-path with adjacency labels applied by router  12 F ( 218 ). Specifically, router  12 A may, as described in  FIG. 2 , apply a node label stack that includes (1) a first node label that corresponds to NPLR router  12 F; and (2) a second node label that corresponds to a next hop router on a path to reach NPLR router  12 F. By waiting until an interval of MAX_CONVERGENCE_DELAY has passed until router  12 A converges, techniques of the disclosure may prevent or reduce micro-loops in the event of link failure. 
     Router  12 A subsequently determines that timer T 3  has expired, i.e., a duration of MAX_CONVERGENCE_DELAY has occurred ( 220 ). Upon expiration of timer T 3 , router  12 A begins forwarding traffic using the new topology that does not include the failed communication link ( 222 ). In other words, although router  12 A previously updated its forwarding state to forward network packets using node labels for the new topology, router  12 A does not converge until the expiration of timer T 3 . By waiting until an interval of MAX_CONVERGENCE_DELAY has passed until the non-PLR routers converge, techniques of the disclosure may prevent or reduce micro-loops in the event of link failure. 
     Router  12 F, continues to forward network traffic along the backup sub-path using the list of adjacency labels until the expiration of timer T 2  ( 224 ). Upon determining that timer T 2  has expired, router  12 F converges to the new network topology and begins forwarding network packets to destination router  12 K using node labels rather than the adjacency labels used for the temporary network topology ( 226 ). 
     Techniques of the present disclosure using SPRING to avoid or otherwise prevent micro-loops may provide certain advantages over using other techniques such as T-LDP. For instance, using T-LDP for micro-loop free convergence may have certain disadvantages. As an example, if a router procures T-LDP labels on ad-hoc basis (i.e. on receiving the IGP link-state event from an NPLR), it will need to first setup T-LDP sessions with the NPLR, and then procure the desired labels. As T-LDP sessions formation and learning labels may need some time, the traffic may be sent on an older forwarding path for so long as still susceptible to transient micro-loops. To illustrate another disadvantage with T-LDP, if a router decides to procure T-LDP labels in advance, it will essentially have to setup T-LDP sessions to each node in the network (considering any link in the network can go down at any point of time) and learn labels for all possible destination nodes. This approach can pose some scalability overheads as compared to SPRING (e.g. in real practical deployments the maximum number of incoming T-LDP sessions a single node can handle may be in the order of few hundreds). 
     As described above, implementing nearside tunneling mechanism using T-LDP (targeted LDP) to ensure loop-free convergence may bear some convergence and scalability issues. For instance, while setting up targeted-LDP session to an NPLR and learning T-LDP labels on demand (i.e after learning link-down event from NPLR) may elongate the duration of traffic loss (and possibly also cause micro loops). On the other, if T-LDP labels are to be learnt from each router for each of its link and each of the destination affected by the link before the failure event it will amount to each source initiating as many T-LDP sessions as the total number of routers in the network, which may pose scalability issues introduced by T-LDP depending on the number of nodes in the network. 
     Accordingly, techniques of the disclosure use of SPRING segments distributed by link-state IGP protocols (e.g. OSPF and ISIS) as tunnel segments to prevent micro-loops. Since the tunnels required to setup by near-side PLR are available before-hand, the global convergence may be faster compared to other tunneling mechanisms. In some examples, each router may exchange all of its adjacency and node labels/label ranges at initial configuration and startup when the router becomes a part of the network. Accordingly, in some examples each router can determine all tunnels based on the node and adjacency labels for paths in the network. Therefore, in some examples, techniques of the disclosure allow the routers implementing SPRING to determine backup paths before a link failure occurs. Moreover, such techniques may not be subject to the scalability limitations of T-LDP as the total number of routers grows. Furthermore, there may be no additional overhead of setting up tunnels before-hand (as is the case with targeted LDP sessions) because SPRING provides ready-made tunnels. 
     The techniques described in this disclosure may be implemented, at least in part, in hardware, software, firmware, or any combination thereof. For example, various aspects of the described techniques may be implemented within one or more processors, including one or more microprocessors, digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), or any other equivalent integrated or discrete logic circuitry, as well as any combinations of such components. The term “processor” or “processing circuitry” may generally refer to any of the foregoing logic circuitry, alone or in combination with other logic circuitry, or any other equivalent circuitry. A control unit including hardware may also perform one or more of the techniques of this disclosure. 
     Such hardware, software, and firmware may be implemented within the same device or within separate devices to support the various techniques described in this disclosure. In addition, any of the described units, modules or components may be implemented together or separately as discrete but interoperable logic devices. Depiction of different features as modules or units is intended to highlight different functional aspects and does not necessarily imply that such modules or units must be realized by separate hardware, firmware, or software components. Rather, functionality associated with one or more modules or units may be performed by separate hardware, firmware, or software components, or integrated within common or separate hardware, firmware, or software components. 
     The techniques described in this disclosure may also be embodied or encoded in an article of manufacture including a computer-readable medium encoded with instructions. Instructions embedded or encoded in an article of manufacture including a computer-readable medium encoded, may cause one or more programmable processors, or other processors, to implement one or more of the techniques described herein, such as when instructions included or encoded in the computer-readable medium are executed by the one or more processors. 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), flash memory, a hard disk, a compact disc ROM (CD-ROM), a floppy disk, a cassette, magnetic media, optical media, or other computer readable media. In some examples, an article of manufacture may include one or more computer-readable storage media. In some examples, a computer-readable storage media may include non-transitory media. The term “non-transitory” may indicate that the storage medium is not embodied in a carrier wave or a propagated signal. In certain examples, a non-transitory storage medium may store data that can, over time, change (e.g., in RAM or cache). 
     It is to be recognized that depending on the embodiment, certain acts or events of any of the methods described herein can be performed in a different sequence, may be added, merged, or left out altogether (e.g., not all described acts or events are necessary for the practice of the method). Moreover, in certain embodiments, acts or events may be performed concurrently, e.g., through multi-threaded processing, interrupt processing, or multiple processors, rather than sequentially. 
     Various embodiments of the invention have been described. These and other embodiments are within the scope of the following claims.