Reduced topology routing in shared media communication networks
First Claim
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 a cost increase, and also have a respective link metric from the particular node that is within a 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
24 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 a cost increase, and also have a respective link metric from the particular node that is within a 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
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 a cost increase, and also have a respective link metric from the apparatus that is within a 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. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23)
-
-
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 a cost increase, and also have a respective link metric from the particular node that is within a 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.
-
Specification