ROUTING USING CACHED SOURCE ROUTES FROM MESSAGE HEADERS

• US 20140029445A1
• Filed: 07/30/2012
• Published: 01/30/2014
• Est. Priority Date: 07/30/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, Thubert, Pascal, Wetterwald, Patrick
• Granted Patent: US 9,485,174 B2
• Time in Patent Office: Days
• US Class Current: 370/248
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof

Abstract

In one embodiment, an intermediate node of a computer network can receive a message intended for a destination. The message can include a header indicating a source route. The intermediate node can determine a routing entry for a routing entry for the destination associated with a next hop based on the source route and cache the routing entry. The intermediate node can further receive a second message intended for the destination that does not indicate the next hop, and transmit the second message according to the cached routing entry.

Claims

1. A method, comprising:

receiving, at an intermediate node of a computer network, a message intended for a destination, the message having a header indicating a source route;

determining a routing entry for the destination associated with a next hop of the intermediate node based on the source route;

caching the routing entry at the intermediate node;

receiving a second message intended for the destination at the intermediate node, wherein the second message does not indicate the next hop; and

transmitting the second message according to the cached routing entry to the next hop associated with the destination.

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

determining a second routing entry for the destination associated with a next-next hop of the next hop the intermediate node;

caching the second routing entry for the destination at the intermediate node; and

s transmitting the second message according to one of the first cached routing entry or the second cached routing entry based on an availability of the next hop and the next-next hop.

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

generating a control message to a root node of the computer network when the next hop or the next-next hop is unavailable.

4. The method as in claim 1, wherein the routing entry is cached at the intermediate node for a time period, the method further comprising:

determining reachability of the next hop via probing a link to the next hop;

determining that the next hop is no longer reachable based on the determined reachability; and

transmitting a control message to a root node to indicate a broken link based on the determined reachability.

5. The method as in claim 1, wherein determining the routing entry for the destination comprises determining a subset path of the source route to reach the destination;

wherein caching the routing entry comprises caching the subset of the source route at the intermediate node;

wherein transmitting the second message comprises transmitting the second message according to the subset path, the method further comprising;

updating a header of the second message to include the subset path in the source route.

6. The method as in claim 1, wherein source route of the message comprises a tag, and wherein determining the routing entry for the destination further comprises determining a routing entry for the destination associated with a plurality of next hops of the intermediate node based on the tag.

7. The method as in claim 1, wherein the routing entry is cached at the intermediate node for a time period based on historical data related to a path stability to the next hop.

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

receiving the time period that the routing entry is cached at the intermediate node from a root node of the computer network.

9. The method as in claim 1, wherein caching the routing entry at the intermediate node is in response to a route cache indicator within the message.

10. The method as in claim 9, wherein the route cache indicator is a flag in the message.

11. The method as in claim 9, wherein the route cache indicator is a timer parameter in the message indicating how long to cache the route entry.

12. A method, comprising:

transmitting, via a root node, a first message intended for a destination to one or more intermediate nodes, the first message having a header indicating a source route; and

transmitting a second message intended for the destination to the one or more intermediate nodes having a header with a subset of the source route for the destination based on one or more cached routing states of the one or more intermediate nodes.

13. The method as in claim 12, further comprising:

receiving the cached routing state from the one or more intermediate nodes at the root node; and

determining, via the root node, the header with the subset of the source route for the second message based on the cached routing state of the one or more intermediate nodes.

14. The method as in claim 12, further comprising:

determining that at least one of the one or more intermediate nodes is a relay node, wherein the relay node caches a routing entry having a subset path of the source route of the first message, wherein the second message is transmitted to the relay node and causes the relay node to distribute the second message with an updated header having the at least part of the cached source route.

15. The method as in claim 14, wherein the updated header indicates a subsequent relay node.

16. The method as in claim 13, wherein each cached routing state of each intermediate node is a tag that is associated with a plurality of next hops of the intermediate node.

17. The method as in claim 13, further comprising:

receiving available resource information from the one or more intermediate nodes;

determining a number of routing entries the one or more intermediate nodes can cache according to the available resource information; and

transmitting a message having a route cache indicator to the one or more intermediate nodes to cause the one or more intermediate nodes to cache the number of routing entries.

18. The method as in claim 17, further comprising:

receiving link reliability information from the one or more intermediate nodes, wherein determining a number of routing entries further comprises determining the number of routing entries one or more intermediate nodes can cache according to the available resource information and the link reliability information.

19. The method as in claim 12, wherein the first message includes a route cache timer that causes the one or more intermediate nodes to cache a routing entry associated with at least part of the source route for a specified period of time.

20. An apparatus, comprising:

one or more network interfaces of an intermediate node that communicates in a 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;

receive a message intended for a destination, the message having a header indicating a source route;

determine a routing entry for the destination associated with a next hop of the intermediate node based on the source route;

cache the routing entry at the intermediate node;

receive a second message intended for the destination at the intermediate node, wherein the second message does not indicate the next hop; and

transmit the second message according to the cached routing entry to the next hop associated with the destination.

21. An apparatus, comprising:

one or more network interfaces of a root node that communicates in a 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;

transmit a first message intended for a destination, the message having a header indicating a source route; and

transmit a second message intended for the destination to one or more intermediate nodes having a header with a subset of the source route for the destination based on one or more cached routing states of the one or more intermediate nodes.