Dominating set identification for path computation based on directed acyclic graph membership

• US 9,344,256 B2
• Filed: 09/18/2013
• Issued: 05/17/2016
• Est. Priority Date: 09/18/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Thubert, Pascal, Vasseur, Jean-Philippe, Wetterwald, Patrick
• Primary Examiner(s): Zhu, Alvin
• Application Number:
  US14/030,949
• Publication Number:
  US 20150078204A1
• Time in Patent Office: 972 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 5/0067 Allocation algorithms which involve graph matching
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In one embodiment, a method comprises a path computation device receiving device information from member network devices, each member network device belonging to a directed acyclic graph to a destination in a low power lossy network; and the path computation device classifying each member network device belonging to a directed acyclic graph as belonging to a dominating set, for generation of optimized routes distinct from any directed acyclic graph, for reaching any one of the member network devices of the dominating set.

Claims

1. A method comprising:

a path computation device receiving device information from member network devices, each member network device belonging to a directed acyclic graph to a destination in a low power lossy network; and

the path computation device classifying each member network device belonging to any directed acyclic graph as belonging to a dominating set, for generation of optimized routes distinct from any directed acyclic graph, for reaching any one of the member network devices of the dominating set.

2. The method of claim 1, further comprising the path computation device excluding from the dominating set any network device identified as not having any attached child network devices for reaching a directed acyclic graph in the network.

3. The method of claim 2, wherein each network device excluded from the dominating set is a leaf network device one hop away from one of the members of the dominating set.

4. The method of claim 1, wherein the classifying includes the path computation device classifying into the dominating set member network devices from distinct directed acyclic graphs, at least one of the optimized routes including member network devices from distinct directed acyclic graphs.

5. The method of claim 1, wherein the device information from a member network device includes a unique device identifier and device link information, the device link information including identification of any neighboring network devices of the member network device.

6. The method of claim 5, wherein the device link information further includes link quality information for each device link used by the corresponding member network device.

7. The method of claim 5, wherein each neighboring network device is identified in the device information as one of a member network device or a leaf network device that does not have any attached child network device for reaching a directed acyclic graph.

8. The method of claim 7, wherein:

the classifying includes the path computation device selectively adding one of the leaf network devices to the dominating set for addition to one or more of the optimized routes between two member network devices of the dominating set;

the method further comprising the path computation device selectively deleting from the dominating set any network device that is not used in any of the optimized routes.

9. The method of claim 1, further comprising generating the optimized routes as time-slotted channel mapped routes for execution by the member network devices.

10. An apparatus comprising:

a network interface circuit configured for receiving device information from member network devices, each member network device belonging to a directed acyclic graph to a destination in a low power lossy network; and

a processor circuit configured for classifying each member network device belonging to any directed acyclic graph as belonging to a dominating set, for generation of optimized routes distinct from any directed acyclic graph, for reaching any one of the member network devices of the dominating set.

11. The apparatus of claim 10, wherein the processor circuit is configured excluding from the dominating set any network device identified as not having any attached child network devices for reaching a directed acyclic graph in the network.

12. The apparatus of claim 10, wherein the processor circuit is configured generating the optimized routes as time-slotted channel mapped routes for execution by the member network devices.

13. Logic encoded in one or more non-transitory tangible media for execution and when executed by a machine operable for:

a path computation device receiving device information from member network devices, each member network device belonging to a directed acyclic graph to a destination in a low power lossy network; and

the path computation device classifying each member network device belonging to any directed acyclic graph as belonging to a dominating set, for generation of optimized routes distinct from any directed acyclic graph, for reaching any one of the member network devices of the dominating set.

14. The logic of claim 13, further operable for generating the optimized routes as time-slotted channel mapped routes for execution by the member network devices.

15. A method comprising:

a network device in a low power lossy network joining a directed acyclic graph to a destination; and

the network device sending device information to a path computation device in response to joining the directed acyclic graph, enabling the path computation device to add the network device to a dominating set of network devices based on membership in the directed acyclic graph, for generation by the path computation device of optimized routes for reaching any network device in the lower power lossy network via one or more of the network devices in the dominating set, the optimized routes distinct from any directed acyclic graph.

16. The method of claim 15, wherein the device information includes a unique device identifier and device link information, the device link information including identification of any neighboring network devices of the network device.

17. The method of claim 16, wherein the device link information further includes link quality information for each device link used by the corresponding network device, each neighboring network device identified in the device information as one of a member network device belonging to a directed acyclic graph or a leaf network device that does not have any attached child network device for reaching a directed acyclic graph.

18. The method of claim 15, further comprising the network device receiving from the path computation device one or more optimized routes as time-slotted channel mapped routes for reaching respective destinations in the low power lossy network.

19. Logic encoded in one or more non-transitory tangible media for execution and when executed by a machine operable for:

a network device in a low power lossy network joining a directed acyclic graph to a destination; and

the network device sending device information to a path computation device in response to joining the directed acyclic graph, enabling the path computation device to add the network device to a dominating set of network devices based on membership in the directed acyclic graph, for generation by the path computation device of optimized routes for reaching any network device in the lower power lossy network via one or more of the network devices in the dominating set, the optimized routes distinct from any directed acyclic graph.

20. The logic of claim 19, further operable for the network device receiving from the path computation device one or more optimized routes as time-slotted channel mapped routes for reaching respective destinations in the low power lossy network.