Network topologies for energy efficient networks

Patent metadata

Field	Value
Publication number	US-9413636-B2
Application number	US-201414243510-A
Country	US
Kind code	B2
Filing date	Apr 2, 2014
Priority date	Feb 1, 2011
Publication date	Aug 9, 2016
Grant date	Aug 9, 2016

Abstract

One embodiment identifies all one-hop neighbor nodes and two-hop neighbor nodes of a node; determines an active set of one-hop neighbor nodes for the node, comprising: includes in the active set each one-hop neighbor node that is either an edge node or connected with at least one two-hop neighbor node with which no other one-hop neighbor nodes are connected; and if the active set is not yet complete, then: determine all combinations of one-hop neighbor nodes that are not already in the active set; and tests each combination in order of each combination's total-energy value to determine whether a specific combination is able to complete the active set; if no combination is able to complete the active set, then including all one-hop neighbor nodes in the active set; and communicates a message to each one-hop neighbor node in the active set indicating that it is in the active set.

First claim

What is claimed is:

1. A method comprising: by one or more computing devices,
identifying all one-hop neighbor nodes and two-hop neighbor nodes of a node;
determining an active set of one-hop neighbor nodes for the node, comprising:
including in the active set all one-hop neighbor nodes that are edge nodes and all one-hop neighbor nodes that are connected with at least one two-hop neighbor node with which no other one-hop neighbor nodes are connected; and
when any two-hop neighbor node is not connected with at least one one-hop neighbor node in the active set, or a bandwidth of the active set is less than a baseline bandwidth, or a number of paths of the active set is less than a minimum number of paths, then:
determining all combinations of one-hop neighbor nodes that are not already in the active set;
for each combination determining whether the combination is able to complete the active set; and
when no combination is able to complete the active set, then including all one-hop neighbor nodes in the active set; and

communicating a message to each one-hop neighbor node in the active set.

2. The method of claim 1 , wherein the node, the one-hop neighbor nodes, and the two-hop neighbor nodes are routers.

3. The method of claim 1 , wherein an edge node is a node directly connected to one or user devices.

4. An apparatus comprising:
a memory comprising instructions executable by one or more processors; and
the one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to:
identify all one-hop neighbor nodes and two-hop neighbor nodes of a node;
determine an active set of one-hop neighbor nodes for the node, comprising:
including in the active set all one-hop neighbor nodes that are edge nodes and all one-hop neighbor nodes that are connected with at least one two-hop neighbor node with which no other one-hop neighbor nodes are connected; and
determining that at least one of the following conditions exists:
(i) any two-hop neighbor node is not connected with at least one one-hop neighbor node in the active set, (ii) a bandwidth of the active set is less than a baseline bandwidth, and (iii) a number of paths of the active set is less than a minimum number of paths;
in response to determining that at least one of the conditions exists, then:
determining all combinations of one-hop neighbor nodes that are not already in the active set;
for each determined combination determining whether the combination is able to complete the active set;
when no combination is able to complete the active set, then including all one-hop neighbor nodes in the active set; and

communicating a message to each one-hop neighbor node in the active set indicating that it is in the active set.

5. The apparatus of claim 4 , wherein the node, the one-hop neighbor nodes, and the two-hop neighbor nodes are routers.

6. The apparatus of claim 4 , wherein an edge node is a node directly connected to one or user devices.

7. One or more computer-readable non-transitory storage media embodying software operable when executed by one or more computer systems to:
identify all one-hop neighbor nodes and two-hop neighbor nodes of a node;
determine an active set of one-hop neighbor nodes for the node, comprising:
including in the active set each one-hop neighbor node that is either an edge node or connected with at least one two-hop neighbor node with which no other one-hop neighbor nodes are connected; and
when any two-hop neighbor node is not connected with at least one one-hop neighbor node in the active set, or a bandwidth of the active set is less than a baseline bandwidth, or a number of paths of the active set is less than a minimum number of paths, then:
determining all combinations of one-hop neighbor nodes that are not already in the active set;
testing each combination to determine whether a specific combination is able to complete the active set; and
when no combination is able to complete the active set, then including all one-hop neighbor nodes in the active set; and

communicating a message to each one-hop neighbor node in the active set indicating that it is in the active set.

8. The media of claim 7 , wherein the node, the one-hop neighbor nodes, and the two-hop neighbor nodes are routers.

9. The media of claim 7 , wherein an edge node is a node directly connected to one or user devices.

Assignees

• Cisco Tech Inc

Inventors

• Retana Alvaro E
• Barnes Michael
• White Russell I
• Sheridan Alan Patrick
• Ratliff Stanley M

Classifications

• H04L41/12 Primary

  Discovery or management of network topologies · CPC title

• H04L45/123 Primary

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title

• Y02B60/50

  Cross-Sectional Technologies · mapped topic

• H04W40/246

  Connectivity information discovery · CPC title

• H04L45/125

  based on throughput or bandwidth · CPC title