Source routing convergence in constrained computer networks

• US 8,837,277 B2
• Filed: 06/01/2011
• Issued: 09/16/2014
• 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.
• Primary Examiner(s): Chriss, Andrew
• Assistant Examiner(s): FAYED, RASHA K
• Application Number:
  US13/151,109
• Publication Number:
  US 20120307629A1
• Time in Patent Office: 1,203 Days
• Field of Search: 370/256, 370/351, 370/408, 370/228, 370/394, 709/238, 709/252
• 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;

determining an identification of the particular packet;

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 by detecting a second packet with a same identification as the particular packet that has been received at the source routing device after the particular packet has already been received at the device and prior to expiration of a timer, wherein the detecting of the same identification indicates that the second packet is a repeated packet and has already been forwarded from the source routing device along the first path and should not again be forwarded along the first path; 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 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 the computer network is configured as a directed acyclic graph (DAG).

5. The method as in claim 4, 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.

6. The method as in claim 5, wherein adjusting the OF comprises:

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

7. The method as in claim 4, 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.

8. The method as in claim 4, wherein the device is a root of the DAG.

9. 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.

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

11. 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.

12. 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;

determine an identification of the 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 by the device by detecting a second packet with a same identification as the particular packet that has been received at the source routing device after the particular packet has already been received at the device and prior to expiration of a timer, wherein the detecting of the same identification indicates that the second packet is a repeated packet and has already been forwarded from the source routing device along the first path and should not again be forwarded along 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.

13. The apparatus as in claim 12,

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.

14. The apparatus as in claim 12, 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.

15. The apparatus as in claim 14, 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.

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

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

18. 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;

determine an identification of the 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 by the device by detecting a second packet with a same identification as the particular packet that has been received at the source routing device after the particular packet has already been received at the device and prior to expiration of a timer, wherein the detecting of the same identification indicates that the second packet is a repeated packet and has already been forwarded from the source routing device along the first path and should not again be forwarded along 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.

19. The computer-readable media as in claim 18,

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.

20. The computer-readable media as in claim 18, 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.