ENABLING DYNAMIC ROUTING TOPOLOGIES IN SUPPORT OF REAL-TIME DELAY TRAFFIC

• US 20140126423A1
• Filed: 11/05/2012
• Published: 05/08/2014
• 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: Vasseur, Jean-Philippe, Hui, Jonathan W.
• Granted Patent: US 9,306,841 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

In one embodiment, a device determines a set of sources and used destinations for traffic in a computer network, where nodes of the network are configured to send all traffic to the used destinations through a root node of the computer network according to a directed acyclic graph (DAG). The device may then also determine a set of capable nodes as common ancestors to source-destination pairs that provide a more optimal path between the source-destination pairs than traversing the root node, and instructs the set of capable nodes to store downward routes to forward traffic for one or more of the used destinations according to the stored downward route rather than through the root node.

Claims

1. A method, comprising:

determining a set of sources and used destinations for traffic in a computer network, wherein nodes of the network are configured to send all traffic to the used destinations through a root node of the computer network according to a directed acyclic graph (DAG);

determining a set of capable nodes as common ancestors to source-destination pairs that provide a more optimal path between the source-destination pairs than traversing the root node; and

instructing the set of capable nodes to store downward routes to forward traffic for one or more of the used destinations according to the stored downward route rather than through the root node.

2. The method as in claim 1, wherein determining the set of sources and used destinations for traffic comprises:

inspecting packets received at the root node.

3. The method as in claim 1, wherein determining the set of sources and used destinations for traffic comprises:

receiving an explicit notification from at least one of either a source or a destination of traffic.

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

determining all nodes capable of storing downward routes from which to determine the set of capable nodes as common ancestors to source-destination pairs.

5. The method as in claim 4, wherein determining all nodes capable of storing downward routes comprises:

determining at least one of either a distinct capability or a level of available resources of the nodes in the computer network.

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

instructing one or more nodes of the computer network to select new DAG parents based on the set of capable nodes instructed to store downward routes.

7. The method as in claim 6, wherein the one or more nodes of the computer network are instructed to select new DAG parents based on the set of capable nodes instructed to store downward routes for only one or more of the used destinations.

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

determining that a particular node of the set of capable nodes instructed to store downward routes is no longer capable; and

in response,

determining a new set of capable nodes as common ancestors to source-destination pairs that provide a more optimal path between the source-destination pairs than traversing the root node, the new set not including the particular node.

9. The method as in claim 1, wherein providing a more optimal path between the source-destination pairs than traversing the root node comprises providing a path that meets a particular delay requirement.

10. The method as in claim 1, wherein the traffic for which the set of sources and used destinations is determined and for which the set of capable nodes are instructed to store downward routes is a certain type of traffic only.

11. An apparatus, comprising:

one or more network interfaces to communicate in 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;

determine a set of sources and used destinations for traffic in a computer network, wherein nodes of the network are configured to send all traffic to the used destinations through a root node of the computer network according to a directed acyclic graph (DAG);

determine a set of capable nodes as common ancestors to source-destination pairs that provide a more optimal path between the source-destination pairs than traversing the root node; and

instruct the set of capable nodes to store downward routes to forward traffic for one or more of the used destinations according to the stored downward route rather than through the root node.

12. The apparatus as in claim 11, wherein the process when executed to determine the set of sources and used destinations for traffic is further operable to:

inspect packets received at the root node.

13. The apparatus as in claim 11, wherein the process when executed to determine the set of sources and used destinations for traffic is further operable to:

receive an explicit notification from at least one of either a source or a destination of traffic.

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

determine all nodes capable of storing downward routes from which to determine the set of capable nodes as common ancestors to source-destination pairs.

15. The apparatus as in claim 14, wherein the process when executed to determine all nodes capable of storing downward routes is further operable to:

determine at least one of either a distinct capability or a level of available resources of the nodes in the computer network.

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

instruct one or more nodes of the computer network to select new DAG parents based on the set of capable nodes instructed to store downward routes.

17. The apparatus as in claim 16, wherein the one or more nodes of the computer network are instructed to select new DAG parents based on the set of capable nodes instructed to store downward routes for only one or more of the used destinations.

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

determine that a particular node of the set of capable nodes instructed to store downward routes is no longer capable; and

in response,

determine a new set of capable nodes as common ancestors to source-destination pairs that provide a more optimal path between the source-destination pairs than traversing the root node, the new set not including the particular node.

19. The apparatus as in claim 11, wherein providing a more optimal path between the source-destination pairs than traversing the root node comprises providing a path that meets a particular delay requirement.

20. The apparatus as in claim 11, wherein the traffic for which the set of sources and used destinations is determined and for which the set of capable nodes are instructed to store downward routes is a certain type of traffic only.

21. A method, comprising:

operating as a node in non-storing mode in a directed acyclic graph (DAG) where all traffic is sent through a root node according to the DAG;

indicating a capability to operate in storing mode;

s receiving instructions to operate in storing mode to store downward routes to forward traffic for one or more particular destinations according to the stored downward route rather than through the root node of the DAG;

receiving traffic for a specific destination of the particular destinations; and

, in response,

using a corresponding stored downward route to forward the traffic toward the specific destination.

22. The method as in claim 21, wherein the traffic for which the node is instructed to store downward routes is a certain type of traffic only.

23. The method as in claim 21, wherein indicating the capability to operate in storing mode comprises:

indicating at least one of either a distinct capability or a level of available resources of the node.

24. An apparatus, comprising:

one or more network interfaces to communicate in 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;

operate in non-storing mode in a directed acyclic graph (DAG) where all traffic is sent through a root node according to the DAG;

indicate a capability to operate in storing mode;

receive instructions to operate in storing mode to store downward routes to forward traffic for one or more particular destinations according to the stored downward route rather than through the root node of the DAG;

receive traffic for a specific destination of the particular destinations; and

, in response,

use a corresponding stored downward route to forward the traffic toward the specific destination.

25. The apparatus as in claim 24, wherein the traffic for which the apparatus is instructed to store downward routes is a certain type of traffic only.