Micro-loop prevention using source packet routing

• US 9,838,246 B1
• Filed: 09/30/2014
• Issued: 12/05/2017
• Est. Priority Date: 09/30/2014
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Hegde, Shraddha, Sarkar, Pushpasis, Gredler, Hannes
• Primary Examiner(s): Orgad, Edan
• Assistant Examiner(s): Latorre, Ivan O
• Application Number:
  US14/502,469
• Time in Patent Office: 1,162 Days
• Field of Search: 370216-228
• CPC Class Codes: H04L 41/0659 by isolating or reconfiguring faulty entities
• CPC Class Codes: H04L 41/0668 by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/507 Label distribution
• CPC Class Codes: H04L 45/72 Routing based on the source address

Abstract

In general, techniques are described for reducing or otherwise preventing micro-loops in network using Source Packet Routing in Networking (SPRING). In some examples, a method includes detecting a failure of a communication by a network device that implements a Source Packet Routing in Networking (SPRING) protocol to forward network packets using node labels according to an initial network topology. Responsive to detecting the failure of the communication link, the network device may apply, for a defined time duration, one or more adjacency labels to network packets to define a set of one-hop tunnels corresponding to a backup sub-path that circumvents the failed communication link. Upon expiration of the defined time duration, the network device may 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.

Claims

1. A method comprising:

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, wherein the NPLR, the FPLR, and any of the other network devices operating in accordance with the SPRING protocol exchange the node labels using at least one link-state interior gateway protocol (IGP);

responsive to detecting the failure of the communication link, applying, by the NPLR and for a defined time duration, one or more adjacency labels in accordance with the SPRING protocol 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.

2. The method of claim 1, further comprising:

before detecting, by the NPLR, the failure of the communication link;

receiving, by the NPLR, the one or more adjacency labels from one or more of the plurality of other network devices;

pre-computing, by the NPLR, the backup sub-path that does not include the communication link; and

after detecting, by the NPLR, the failure of the communication link;

configuring, by the NPLR and 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.

3. The method of claim 1, wherein the defined time duration is a first defined time duration, the method further comprising:

responsive to detecting the failure of the communication link;

initiating, by the NPLR, a first timer with the first defined time duration;

initiating, by the NPLR, a second timer with a second time duration; and

sending, by the NPLR and while the second timer has not expired, a plurality of link state advertisements to the plurality of other network devices.

4. The method of claim 1, further comprising:

before detecting, by the NPLR, the failure of the communication link;

receiving, by the NPLR, 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 the NPLR, FPLR and the plurality of other network devices; and

configuring, by the NPLR, a forwarding state of the NPLR 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.

5. The method of claim 1, wherein forwarding, 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, further comprises:

applying, by the NPLR, at least one node label or range of node labels that uniquely identifies one of the plurality of other network devices to network packets destined for the destination network device, wherein the one of the plurality of other network devices was included in the backup sub-path.

6. The method of claim 1, wherein the backup sub-path comprises a portion of an overall network path through the network between a source network device and a destination network device.

7. The method of claim 1, further comprising:

receiving, by one of the plurality of other network devices that is not the NPLR or the FPLR, a link state advertisement that the communication link has failed;

responsive to receiving the link state advertisement, initiating, by the one of the plurality of other network devices that is not the NPLR or the FPLR, a timer;

configuring, before the timer has expired, a forwarding state of the one of the plurality of other network devices that is not the NPLR or the FPLR, to forward network packets according to the new network topology; and

forwarding, while the timer has not expired and by the one of the plurality of other network devices that is not the NPLR or the FPLR, network packets destined for the destination network device according to the temporary network topology.

8. The method of claim 7, wherein forwarding, while the timer has not expired, network packets destined for the destination network device according to the temporary network topology further comprises:

responsive to determining the network packets are destined for the destination network device, applying, by the one of the plurality of other network devices that is not the NPLR or the FPLR, a label stack to each of the network packets, wherein the label stack comprises;

a first node label that corresponds to a next hop router on a path to reach the NPLR; and

a second node label that corresponds to destination.

9. The method of claim 7, further comprising:

responsive to the expiration of the timer, forwarding, by the one of the plurality of other network devices that is not the NPLR or the FPLR, network packets destined for the destination network device according to the new network topology.

10. The method of claim 9, wherein forwarding network packets destined for the destination network device according to the new network topology further comprises:

applying to a first network packet destined for the destination network device, by the one of the plurality of other network devices that is not the NPLR or the FPLR, 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, wherein the second network packet was destined for the destination network device.

11. A network device, wherein the network device is a first point of local failure (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, wherein the first PLR, the second PLR, and any of the other network devices operating in accordance with the SPRING protocol exchange the node labels using at least one link-state interior gateway protocol (IGP);

responsive to detecting the failure of the communication link, apply, for a defined time duration, one or more adjacency labels in accordance with the SPRING protocol 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.

12. The network device of claim 11, wherein the at least one module is operable by the at least one processor to:

before detecting the failure of the communication link;

receive the one or more adjacency labels from one or more of the plurality of other network devices;

pre-compute the backup sub-path that does not include the communication link; and

after detecting the failure of the communication link;

configure, based on the pre-computing of the backup sub-path, a forwarding state of the first PLR to apply the one or more adjacency labels to network packets destined for the destination network device.

13. The network device of claim 11, wherein the at least one module is operable by the at least one processor to:

responsive to detecting the failure of the communication link;

initiate a first timer with the first defined time duration;

initiate a second timer with a second time duration; and

send, while the second timer has not expired, a plurality of link state advertisements to the plurality of other network devices.

14. The network device of claim 11, wherein the at least one module is operable by the at least one processor to:

before detecting the failure of the communication link;

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 the first PLR, the second PLR and the plurality of other network devices; and

configure a forwarding state of the first PLR 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.

15. The network device of claim 11, wherein the at least one module is operable by the at least one processor to:

apply at least one node label or range of node labels that uniquely identifies one of the plurality of other network devices to network packets destined for the destination network device, wherein the one of the plurality of other network devices was included in the backup sub-path.

16. The network device of claim 11, wherein the backup sub-path comprises a portion of an overall network path through the network between a source network device and a destination network device.

17. A method comprising:

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 non-PLR, 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 includes the plurality of network devices, wherein the non-PLR, the NPLR, the FPLR, and any of the other network devices operating in accordance with the SPRING protocol exchange the node labels using at least one link-state interior gateway protocol (IGP);

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 a destination network device according to a temporary network topology that is different than the new network topology, wherein the temporary network topology is based on one or more adjacency labels in accordance with the SPRING protocol that define a set of one-hop tunnels corresponding to a backup sub-path that circumvents the failed communication link between the NPLR and the FPLR.

18. The method of claim 17, wherein forwarding, while the timer has not expired, network packets destined for the destination network device according to the temporary network topology further comprises:

responsive to determining the network packets are destined for the destination network device, applying, by the non-PLR network device, a label stack to each of the network packets, wherein the label stack comprises;

a first node label that corresponds to a next hop router on a path to reach the NPLR; and

a second node label that corresponds to the destination network device.

19. The method of claim 17, further comprising:

responsive to the expiration of the timer, forwarding, by the non-PLR network device, network packets destined for the destination network device according to the new network topology.

20. A method comprising:

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 non-PLR, 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 includes the plurality of network devices, wherein the non-PLR, the NPLR, the FPLR, and any of the other network devices operating in accordance with the SPRING protocol exchange the node labels using at least one link-state interior gateway protocol (IGP);

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;

forwarding, while the timer has not expired and by the non-PLR network device, network packets destined for a destination network device according to a temporary network topology that is different than the new network topology, wherein the temporary network topology is based on one or more adjacency labels in accordance with the SPRING protocol that define a set of one-hop tunnels corresponding to a backup sub-path that circumvents the failed communication link between the NPLR and the FPLR; and

responsive to the expiration of the timer, forwarding, by the non-PLR network device, network packets destined for the destination network device according to the new network topology, wherein forwarding network packets destined for the destination network device according to the new network topology further comprises;

applying to a first network packet destined for the destination network device, by the non-PLR 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, wherein the second network packet was destined for the destination network device.