Seamless multipath retransmission using source-routed tunnels

• US 9,154,370 B2
• Filed: 11/05/2012
• Issued: 10/06/2015
• Est. Priority Date: 11/05/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Vasseur, Jean-Philippe, Hong, Wei
• Primary Examiner(s): Harper, Kevin C
• Application Number:
  US13/669,210
• Publication Number:
  US 20140126354A1
• Time in Patent Office: 1,065 Days
• Field of Search: 370220-430, 709220-245
• US Class Current: 1/1
• CPC Class Codes: H04L 2212/00 Encapsulation of packets
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 61/2592 using tunnelling or encapsulation
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

In one embodiment, a device receives a destination unreachable message originated by a particular node along a first source route, the message carrying an encapsulated packet as received by the particular node. In response, the device may determine a failed link along the first source route based on a tunnel header and the particular node. Once determining an alternate source route without the failed link, the device may re-encapsulate and re-transmit the original packet on an alternate source route with a new tunnel header indicating the alternate source route (e.g., and a new hop limit count for the tunnel header and an adjusted hop limit count in the original packet).

Claims

1. A method, comprising:

encapsulating and transmitting an original packet toward a destination in a computer network, wherein the original packet is encapsulated with a tunnel header indicating a first source route toward the destination and a hop limit count related to a number of tunnel hops in the first source route and the original packet has an adjusted hop limit count set to an original hop limit count of the original packet less the hop limit count of the tunnel header;

receiving a destination unreachable message originated by a particular node along the first source route, the destination unreachable message carrying the encapsulated packet as received by the particular node, wherein the particular node operates in a non-storing mode in which the particular node does not store a routing path to the destination;

determining a failed link along the first source route based on the tunnel header and the particular node;

determining an alternate source route to the destination without the failed link; and

re-encapsulating and re-transmitting the original packet on an alternate source route, wherein the original packet is re-encapsulated with a new tunnel header indicating the alternate source route.

2. The method as in claim 1, further comprising:

restoring the original hop limit count of the original packet in response to the received destination unreachable message by adding the adjusted hop limit count of the original packet as found in the received destination unreachable message to the number of tunnel hops in the first source route; and

re-encapsulating and re-transmitting the original packet on the alternate source route, wherein the original packet is re-encapsulated with the new tunnel header having a new hop limit count related to a new number of tunnel hops in the alternate source route, the original packet having a new adjusted hop limit count set to the restored original hop limit count less the new hop limit count of the new tunnel header.

3. The method as in claim 1, wherein the destination unreachable message is an Internet Control Message Protocol version 6 (ICMPv6) destination unreachable message.

4. The method as in claim 1, wherein the encapsulation and re-encapsulation are based on an Internet Protocol version 6 (IPv6)-in-IPv6 tunneling protocol.

5. The method as in claim 1, further comprising:

determining that no alternate source route exists; and

in response, returning a second destination unreachable message to a source of the original packet, the second destination unreachable message carrying the original packet with the restored original hop limit count.

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

fragmenting the original packet based on a maximum transmission unit (MTU) in consideration of a destination unreachable message to ensure that the entire original packet plus the tunnel header plus the first source route fits within the MTU when returned in a destination unreachable message.

15. The method of claim 1, wherein the computer network is a constrained network.

7. An apparatus, comprising:

one or more network interfaces to communicate with a computer network;

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;

encapsulate and transmit an original packet toward a destination in a computer network, wherein the original packet is encapsulated with a tunnel header indicating a first source route toward the destination and a hop limit count related to a number of tunnel hops in the first source route and the original packet has an adjusted hop limit count set to an original hop limit count of the original packet less the hop limit count of the tunnel header;

receive a destination unreachable message originated by a particular node along the first source route, the destination unreachable message carrying the encapsulated packet as received by the particular node, wherein the particular node operates in a non-storing mode in which the particular node does not store a routing path to the destination;

determine a failed link along the first source route based on the tunnel header and the particular node;

determine an alternate source route to the destination without the failed link; and

re-encapsulate and re-transmit the original packet on an alternate source route, wherein the original packet is re-encapsulated with a new tunnel header indicating the alternate source route.

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

restore the original hop limit count of the original packet in response to the received destination unreachable message by adding the adjusted hop limit count of the original packet as found in the received destination unreachable message to the number of tunnel hops in the first source route; and

re-encapsulate and re-transmit the original packet on the alternate source route, wherein the original packet is re-encapsulated with the new tunnel header having a new hop limit count related to a new number of tunnel hops in the alternate source route, the original packet having a new adjusted hop limit count set to the restored original hop limit count less the new hop limit count of the new tunnel header.

9. The apparatus as in claim 7, wherein the destination unreachable message is an Internet Control Message Protocol version 6 (ICMPv6) destination unreachable message.

10. The apparatus as in claim 7, wherein the encapsulation and re-encapsulation are based on an Internet Protocol version 6 (IPv6)-in-IPv6 tunneling protocol.

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

determine that no alternate source route exists; and

in response, return a second destination unreachable message to a source of the original packet, the second destination unreachable message carrying the original packet with the restored original hop limit count.

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

fragment the original packet based on a maximum transmission unit (MTU) in consideration of a destination unreachable message to ensure that the entire original packet plus the tunnel header plus the first source route fits within the MTU when returned in a destination unreachable message.

13. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:

encapsulate and transmit an original packet toward a destination in a computer network, wherein the original packet is encapsulated with a tunnel header indicating a first source route toward the destination and a hop limit count related to a number of tunnel hops in the first source route and the original packet has an adjusted hop limit count set to an original hop limit count of the original packet less the hop limit count of the tunnel header;

receive a destination unreachable message originated by a particular node along the first source route, the destination unreachable message carrying the encapsulated packet as received by the particular node, wherein the particular node operates in a non-storing mode in which the particular node does not store a routing path to the destination;

determine a failed link along the first source route based on the tunnel header and the particular node;

determine an alternate source route to the destination without the failed link; and

re-encapsulate and re-transmit the original packet on an alternate source route, wherein the original packet is re-encapsulated with a new tunnel header indicating the alternate source route.

14. The computer-readable media as in claim 13, wherein the software when executed is further operable to:

restore the original hop limit count of the original packet in response to the received destination unreachable message by adding the adjusted hop limit count of the original packet as found in the received destination unreachable message to the number of tunnel hops in the first source route; and

re-encapsulate and re-transmit the original packet on the alternate source route, wherein the original packet is re-encapsulated with the new tunnel header having a new hop limit count related to a new number of tunnel hops in the alternate source route, the original packet having a new adjusted hop limit count set to the restored original hop limit count less the new hop limit count of the new tunnel header.