REDUCED TOPOLOGY ROUTING IN SHARED MEDIA COMMUNICATION NETWORKS

• US 20130028143A1
• Filed: 07/27/2011
• Published: 01/31/2013
• Est. Priority Date: 07/27/2011
• 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 8,654,649 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In one embodiment, a particular node in a shared communication network determines a current path cost in a routing topology from itself to a root node via a current parent node. The particular node also determines a respective path cost from each reachable potential parent node of the particular node to the root node via each potential parent and a respective link metric to each potential parent node. A set of acceptable parent nodes are determined from the potential parent nodes that have a respective path cost that is less than the current path cost plus an acceptable cost increase, and also have a respective link metric that is within an acceptable range. By determining a respective number of child nodes for each acceptable parent node, the particular node may then select a new parent node based on giving preference to those having a greater respective number of child nodes.

Claims

1. A method, comprising:

determining a current path cost in a routing topology from a particular node in a shared media communication network to a root node of the routing topology via a current parent node;

determining, for each reachable potential parent node of the particular node, a respective path cost from the particular node to the root node via each potential parent and a respective link metric from the particular node to each potential parent node;

determining a set of acceptable parent nodes selected from the potential parent nodes, wherein acceptable parent nodes have a respective path cost that is less than the current path cost plus an acceptable cost increase, and also have a respective link metric from the particular node that is within an acceptable link metric range;

determining, for each acceptable parent node of the set, a respective number of child nodes of the corresponding acceptable parent node; and

selecting a new parent node for the particular node in the routing topology based on giving preference to acceptable parent nodes having a greater respective number of child nodes.

2. The method as in claim 1, wherein selecting the new parent node comprises:

selecting an acceptable parent node having the greatest number of child nodes.

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

iteratively updating parent node selection based on updates to the routing topology.

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

initializing the routing topology using the link metric without regard to numbers of child nodes; and

updating parent node selection by the selecting of the new parent node for the particular node in the routing topology based on giving preference to acceptable parent nodes having a greater respective number of child nodes.

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

determining at least one of either the acceptable cost increase and the acceptable link metric range from a centralized management device.

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

determining at least one of either the acceptable cost increase and the acceptable link metric range locally and dynamically by the particular node.

7. The method as in claim 6, wherein determining the acceptable cost increase locally and dynamically comprises:

determining the acceptable cost increase based on one or more factors selected form a group consisting of;

a number of neighbors of the particular node;

a number of children of the particular node; and

dynamic link characteristics of the particular node.

8. The method as in claim 1, wherein the link metric is selected from a group consisting of:

expected transmission count (ETX);

delay; and

packet loss.

9. The method as in claim 1, wherein a respective number of child nodes of a particular corresponding acceptable parent node is based on phantom nodes to weight the preference of the particular acceptable parent node.

10. The method as in claim 1, wherein selecting the new parent node comprises:

giving preference to acceptable parent nodes based on one or more capabilities of the acceptable parent nodes.

11. The method as in claim 10, wherein the one or more capabilities are selected from a group consisting of:

being powered by main-power;

having sufficient battery power remaining;

being capable of performing data aggregation;

having sufficient processing capacity; and

having sufficient available memory.

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

notifying one or more child nodes of the particular node of a new path cost associated with the selected new parent node to reach the root node; and

in response to receiving more than a threshold amount of replies from the child nodes indicating that the new path cost is unacceptable, canceling the selection of the new parent node.

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

determining that the particular node can reach only host nodes in the routing topology; and

in response to determining that the particular node can reach only host nodes in the routing topology, requesting that one or more host nodes activate operation as routers.

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

receiving a plurality of notifications from a plurality of the host nodes that they are requested to operate as a router, the notifications timed inversely proportional to a corresponding distance to the root node from the respective host node; and

in response, selecting a particular host node from which a particular one of the notifications is received first as the new parent node.

15. An apparatus, comprising:

one or more network interfaces to communicate within a shared media communication 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 current path cost in a routing topology from the apparatus to a root node of the routing topology via a current parent node;

determine, for each reachable potential parent node of the apparatus, a respective path cost from the apparatus to the root node via each potential parent and a respective link metric from the apparatus to each potential parent node;

determine a set of acceptable parent nodes selected from the potential parent nodes, wherein acceptable parent nodes have a respective path cost that is less than the current path cost plus an acceptable cost increase, and also have a respective link metric from the apparatus that is within an acceptable link metric range;

determine, for each acceptable parent node of the set, a respective number of child nodes of the corresponding acceptable parent node; and

select a new parent node for the apparatus in the routing topology based on giving preference to acceptable parent nodes having a greater respective number of child nodes.

16. The apparatus as in claim 15, wherein the process when executed to select the new parent node is further operable to:

select an acceptable parent node having the greatest number of child nodes.

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

initialize the routing topology using the link metric without regard to numbers of child nodes; and

update parent node selection by the selection of the new parent node for the apparatus in the routing topology based on giving preference to acceptable parent nodes having a greater respective number of child nodes.

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

determine at least one of either the acceptable cost increase and the acceptable link metric range from a centralized management device.

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

determine at least one of either the acceptable cost increase and the acceptable link metric range locally and dynamically.

20. The apparatus as in claim 15, wherein the link metric is selected from a group consisting of:

expected transmission count (ETX);

delay; and

packet loss.

21. The apparatus as in claim 15, wherein the process when executed to select the new parent node is further operable to:

give preference to acceptable parent nodes based on one or more capabilities of the acceptable parent nodes.

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

notify one or more child nodes of the apparatus of a new path cost associated with the selected new parent node to reach the root node; and

in response to receiving more than a threshold amount of replies from the child nodes indicating that the new path cost is unacceptable, cancel the selection of the new parent node.

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

determine that the apparatus can reach only host nodes in the routing topology; and

in response to determining that the apparatus can reach only host nodes in the routing topology, request that one or more host nodes activate operation as routers.

24. A tangible, non-transitory, computer-readable media having software encoded thereon, the software, when executed by a processor on a particular node in a shared media communication network, operable to:

determine a current path cost in a routing topology from the particular node to a root node of the routing topology via a current parent node;

determine, for each reachable potential parent node of the particular node, a respective path cost from the particular node to the root node via each potential parent and a respective link metric from the particular node to each potential parent node;

determine a set of acceptable parent nodes selected from the potential parent nodes, wherein acceptable parent nodes have a respective path cost that is less than the current path cost plus an acceptable cost increase, and also have a respective link metric from the particular node that is within an acceptable link metric range;

determine, for each acceptable parent node of the set, a respective number of child nodes of the corresponding acceptable parent node; and

select a new parent node for the particular node in the routing topology based on giving preference to acceptable parent nodes having a greater respective number of child nodes.