SOURCE ROUTING CONVERGENCE IN CONSTRAINED COMPUTER NETWORKS

• US 20120307629A1
• Filed: 06/01/2011
• Published: 12/06/2012
• Est. Priority Date: 06/01/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Hui, Jonathan W.
• Granted Patent: US 8,837,277 B2
• Time in Patent Office: Days
• US Class Current: 370/228
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

In one embodiment, a source routing device (e.g., root device) pre-computes diverse source-routed paths to one or more nodes in a computer network. Upon receiving a particular packet, the device forwards the particular packet on a source-routed first path of the pre-computed diverse paths. In the event the device implicitly detects failure of the first path, then it forwards a copy of the particular packet on a source-routed second path of the pre-computed diverse paths in response. In one embodiment, implicit failure detection comprises seeing a second (repeated) packet with the same identification within a certain time since the first packet, and the second packet is forwarded on the second path. In another embodiment, implicit failure detection comprises not seeing a link-layer acknowledgment returned or receiving an error notification from a node along the broken path, and a stored copy of the particular packet is forwarded on the second path.

Claims

1. A method, comprising:

pre-computing diverse source-routed paths to one or more nodes in a computer network by a source routing device;

receiving a particular packet at the device;

forwarding the particular packet on a source-routed first path of the pre-computed diverse paths;

implicitly detecting failure of the first path by the device; and

forwarding a copy of the particular packet on a source-routed second path of the pre-computed diverse paths in response to the implicitly detected failure of the first path.

2. The method as in claim 1, wherein implicitly detecting failure comprises:

determining a packet identification of the particular packet by the device;

initiating a timer upon receipt of the particular packet; and

determining that a second packet is received at the device that has the same packet identification as the particular packet prior to expiration of the timer; and

wherein the method further comprises;

forwarding the second packet as the copy of the particular packet on the source-routed second path in response to determining that the second packet received at the device has the same packet identification as the particular packet prior to expiration of the timer.

3. The method as in claim 2, wherein the packet identification is selected from a group consisting of:

an explicit packet identifier value; and

a computed identification of the packet, the computed identification further selected from a second group consisting of;

a hash result of the packet;

a checksum of the packet; and

a direct comparison between the received particular packet and the previously received packet.

4. The method as in claim 1, wherein implicitly detecting failure comprises:

determining, by the device, that there is no returned link-layer acknowledgment for the particular packet from a destination of the particular packet; and

wherein the method further comprises;

storing the particular packet at the device as the copy of the particular packet; and

forwarding the stored copy of the particular packet on the source-routed second path in response to determining that there is no returned link-layer acknowledgment for the particular packet from the destination of the particular packet.

5. The method as in claim 4, wherein determining that there is no returned link-layer acknowledgment for the particular packet from a destination of the particular packet comprises:

receiving an Internet control message protocol (ICMP) error from a downstream node along the first path.

6. The method as in claim 1, wherein the computer network is configured as a directed acyclic graph (DAG).

7. The method as in claim 6, further comprising:

determining, during the pre-computing, that diverse paths do not exist to at least one particular node of the one or more nodes; and

in response, adjusting an objective function (OF) of the DAG to increase a possibility of pre-computing diverse paths to the at least one particular node.

8. The method as in claim 7, wherein adjusting the OF comprises:

increasing a number of parent nodes for each node of the DAG to select.

9. The method as in claim 6, further comprising:

monitoring upward traffic within the DAG toward a root device of the DAG;

determining that the upward traffic is unbalanced within the DAG; and

in response, adjusting an objective function (OF) of the DAG to increase load-balancing of the upward traffic within the DAG.

10. The method as in claim 6, wherein the device is a root of the DAG.

11. The method as in claim 1, wherein the one or more nodes in the computer network consist of all of the nodes in the computer network.

12. The method as in claim 1, wherein the source-routed first and second paths are label-switched paths.

13. The method as in claim 1, wherein implicitly detecting failure is performed in response to determining that the particular packet is classified as a packet to protect.

14. An apparatus, comprising:

one or more network interfaces to communicate in computer network using source routing;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

pre-compute diverse source-routed paths to one or more nodes in the computer network;

receive a particular packet;

forward the particular packet on a source-routed first path of the pre-computed diverse paths;

implicitly detect failure of the first path; and

forward a copy of the particular packet on a source-routed second path of the pre-computed diverse paths in response to the implicitly detected failure of the first path.

15. The apparatus as in claim 14, wherein the process when executed to implicitly detect failure is operable to:

determine a packet identification of the particular packet;

initiate a timer upon receipt of the particular packet; and

determine that a second packet is received at the apparatus that has the same packet identification as the particular packet prior to expiration of the timer; and

wherein the process when executed to forward the copy of the particular packet is operable to;

forward the second packet as the copy of the particular packet on the source-routed second path in response to determining that the second packet received at the apparatus has the same packet identification as the particular packet prior to expiration of the timer.

16. The apparatus as in claim 14, wherein the process when executed is further operable to:

store the particular packet at the device as the copy of the particular packet;

implicitly detect failure by determining that there is no returned link-layer acknowledgment for the particular packet from a destination of the particular packet; and

forward the stored copy of the particular packet on the source-routed second path in response to determining that there is no returned link-layer acknowledgment for the particular packet from the destination of the particular packet.

17. The apparatus as in claim 14, wherein the computer network is configured as a directed acyclic graph (DAG), and wherein the process when executed is further operable to:

determine, during pre-computing, that diverse paths do not exist to at least one particular node of the one or more nodes; and

in response, adjust an objective function (OF) of the DAG to increase a possibility of pre-computing diverse paths to the at least one particular node.

18. The apparatus as in claim 17, wherein the process when executed to adjust the OF is operable to:

increase a number of parent nodes for each node of the DAG to select.

19. The apparatus as in claim 14, wherein the apparatus is a root device of a directed acyclic graph (DAG).

20. The apparatus as in claim 14, wherein the one or more nodes in the computer network consist of all of the nodes in the computer network.

21. A tangible, non-transitory, computer-readable media having software instructions thereon, the software instructions, when executed by a processor on a device in a computer network, operable to:

pre-compute diverse source-routed paths to one or more nodes in the computer network;

receive a particular packet;

forward the particular packet on a source-routed first path of the pre-computed diverse paths;

implicitly detect failure of the first path; and

forward a copy of the particular packet on a source-routed second path of the pre-computed diverse paths in response to the implicitly detected failure of the first path.

22. The computer-readable media as in claim 21, wherein the software instructions when executed to implicitly detect failure are operable to:

determine a packet identification of the particular packet;

initiate a timer upon receipt of the particular packet; and

determine that a second packet is received at the device that has the same packet identification as the particular packet prior to expiration of the timer; and

wherein the software instructions when executed to forward the copy of the particular packet are operable to;

forward the second packet as the copy of the particular packet on the source-routed second path in response to determining that the second packet received at the device has the same packet identification as the particular packet prior to expiration of the timer.

23. The computer-readable media as in claim 21, wherein the software instructions when executed are further operable to:

store the particular packet at the device as the copy of the particular packet;

implicitly detect failure by determining that there is no returned link-layer acknowledgment for the particular packet from a destination of the particular packet; and

forward the stored copy of the particular packet on the source-routed second path in response to determining that there is no returned link-layer acknowledgment for the particular packet from the destination of the particular packet.

24. The computer-readable media as in claim 21, wherein the computer network is configured as a directed acyclic graph (DAG), and wherein the software instructions when executed are further operable to:

determine, during pre-computing, that diverse paths do not exist to at least one particular node of the one or more nodes; and

in response, adjust an objective function (OF) of the DAG to increase a possibility of pre-computing diverse paths to the at least one particular node.