Seamless multipath retransmission using source-routed tunnels

• US 9,413,643 B2
• Filed: 09/01/2015
• Issued: 08/09/2016
• 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:
  US14/842,240
• Publication Number:
  US 20150372903A1
• Time in Patent Office: 343 Days
• Field of Search: None
• 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;

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;

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;

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.

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

encapsulating and transmitting the original packet toward the destination with the tunnel header additionally having a hop limit count related to a number of tunnel hops in the first source route, the original packet having 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;

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, wherein the destination unreachable message is limited to information required to determine the failed link and the original packet.

6. The method as in claim 5, wherein the information required to determine the failed link is one of either a) the tunnel header and the first source route;

or b) an explicit indication of the failed link.

7. The method as in claim 5, wherein the destination unreachable message is limited in response to the encapsulated packet not fitting within a maximum transmission unit (MTU) when carried within the destination unreachable message.

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

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

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;

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;

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.

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

encapsulate and transmit the original packet toward the destination with the tunnel header additionally having a hop limit count related to a number of tunnel hops in the first source route, the original packet having 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;

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.

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

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

13. The apparatus as in claim 9, wherein the destination unreachable message is limited to information required to determine the failed link and the original packet.

14. The apparatus as in claim 9, wherein the information required to determine the failed link is one of either a) the tunnel header and the first source route;

or b) an explicit indication of the failed link.

15. The apparatus as in claim 14, wherein the destination unreachable message is limited in response to the encapsulated packet not fitting within a maximum transmission unit (MTU) when carried within the destination unreachable message.

16. The apparatus as in claim 9, 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.

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

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;

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;

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.

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

encapsulate and transmit the original packet toward the destination with the tunnel header additionally having a hop limit count related to a number of tunnel hops in the first source route, the original packet having 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;

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.