Selecting aggregation nodes in a network

• US 7,936,732 B2
• Filed: 09/27/2007
• Issued: 05/03/2011
• Est. Priority Date: 09/27/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Ho, Kah Kin, Vasseur, Jean-Philippe
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): Ho; Chuong T
• Application Number:
  US11/862,713
• Publication Number:
  US 20090086663A1
• Time in Patent Office: 1,314 Days
• Field of Search: 370/392, 370400-411, 370254-258, 370/328, 370/338, 370229-235, 370/335, 370/336
• US Class Current: 370/338
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership

Abstract

In one embodiment, a method includes determining, at a local node in a network of multiple nodes, a first neighbor node of one or more neighbor nodes with which the local node is in direct communication based on a first number of nodes with which the first neighbor node is in direct communication. The first neighbor node is selected as an aggregation node for information about the local node. The aggregation node outputs data that is a combination of data received from multiple different nodes. The method allows wireless routers in mobile ad hoc networks to automatically determine their own aggregation nodes for routing information and thus automatically enables routing protocols to scale for many thousands of mobile wireless nodes.

Claims

1. A method comprising:

determining, at a local node in a network that comprises a plurality of nodes, a first neighbor node of one or more neighbor nodes with which the local node is in direct communication based on a first number of nodes with which the first neighbor node is in direct communication; and

selecting the first neighbor node as an aggregation node for information about the local node,

wherein the aggregation node outputs data that is a combination of data received from a plurality of different nodes and a number of neighbor nodes with which the local node is in direct communication is called a local number, wherein determining the first neighbor node further comprises determining that the first number of nodes is greater than the local number, and that no other neighbor node of the local node is in direct communication with more nodes than the first number of nodes.

2. A method as recited in claim 1, wherein the direct communication between neighbors is a wireless communication between neighbors and the network is a mobile ad hoc network (MANET).

3. A method as recited in claim 1, wherein the information is routing information about network addresses of one or more devices connected to the local node.

4. A method as recited in claim 1, said step of determining the first neighbor node further comprising:

transmitting from the local node a message that includes local count data that indicates the local number of neighbor nodes;

receiving from each neighbor node a message that includes corresponding neighbor count data that indicates a corresponding number of one or more nodes with which the corresponding neighbor node is in direct communication; and

in response to receiving the message from every neighbor node, determining the first neighbor node.

5. A method as recited in claim 1, said step of selecting the first neighbor node as the aggregation node further comprising:

sending to the first neighbor node a register message that includes registration data that indicates the first neighbor node is the aggregation node for the local node; and

sending to the first neighbor node, an update message that includes information about the local node.

6. A method as recited in claim 5, said step of sending the update message further comprising sending the update message prior to receiving a request message from the first neighbor node for information.

7. A method as recited in claim 1, said step of determining the first neighbor node further comprising determining whether the local node received from the first neighbor node a message that includes aggregation advertising data that indicates the first neighbor node is an aggregation node for at least one node in direct communication with the first neighbor node.

8. A method as recited in claim 1, further comprising:

receiving from a second neighbor node a register message that includes registration data that indicates the local node is the aggregation node for the second neighbor node; and

in response to receiving the register message, transmitting from the local node a message that includes aggregation data that indicates the local node is an aggregation node for at least one neighbor node.

9. A method as recited in claim 8, further comprising receiving from the second neighbor node, an update message that includes information about the second neighbor node.

10. A method as recited in claim 8, said step of transmitting from the local node a message that includes aggregations data further comprising:

determining that the second node remains in direct communication with the local node for a minimum time; and

if it is determined that the second node remains in direct communication with the local node for a minimum time, then transmitting from the local node the message that includes aggregations data that indicates the local node is an aggregation node for at least one neighbor node.

11. A method as recited in claim 8, said step of transmitting from the local node a message that includes aggregations data further comprising transmitting from the local node the message that includes aggregations data that indicates the local node is an aggregation node and node identification data that indicates the second neighbor node.

12. A method as recited in claim 1, further comprising:

determining that the local node is an aggregation node for at least one neighbor node;

determining, at the local node, a second node that is an aggregation node based on a second number of aggregation nodes in communication with the second neighbor node; and

selecting the second node as a higher level aggregation node for information about one or more aggregation nodes in communication with the second neighbor node.

13. An apparatus comprising:

means for determining, at a local node in a network that comprises a plurality of nodes, a first neighbor node of one or more neighbor nodes with which the local node is in direct communication based on a first number of nodes with which the first neighbor node is in direct communication; and

means for selecting the first neighbor node as an aggregation node for information about the local node,

wherein the aggregation node outputs data that is a combination of data received from a plurality of different nodes and a number of neighbor nodes with which the local node is in direct communication is called a local number, wherein determining the first neighbor node further comprises determining that the first number of nodes is greater than the local number, and that no other neighbor node of the local node is in direct communication with more nodes than the first number of nodes.

14. An apparatus comprising:

a network interface that is configured for communicating a data packet with a packet-switched network that comprises a plurality of node;

logic encoded in one or more tangible media for execution and, when executed, operable for;

determining a first neighbor node of one or more neighbor nodes with which the apparatus is in direct communication through the network interface, based on a first number of nodes with which the first neighbor node is in direct communication; and

selecting the first neighbor node as an aggregation node for information about the apparatus,

wherein the aggregation node outputs data that is a combination of data received from a plurality of different nodes and a number of neighbor nodes with which a local node is in direct communication is called a local number, wherein determining the first neighbor node further comprises determining that the first number of nodes is greater than the local number, and that no other neighbor node of the local node is in direct communication with more nodes than the first number of nodes.

15. An apparatus as recited in claim 14, wherein the network interface is a wireless interface and direct communication between neighbors is a wireless communication between neighbors and the network is a mobile ad hoc network (MANET).

16. An apparatus as recited in claim 14, wherein the information is routing information about network addresses of one or more devices connected to the apparatus.

17. An apparatus as recited in claim 14, said determining the first neighbor node further comprising:

sending through the network interface a message that includes local count data that indicates the local number of neighbor nodes;

receiving through the network interface from each neighbor node a message that includes corresponding neighbor count data that indicates a corresponding number of one or more nodes with which the corresponding neighbor node is in direct communication; and

in response to receiving the message from every neighbor node, determining the first neighbor node.

18. An apparatus as recited in claim 14, said selecting the first neighbor node as the aggregation node further comprising:

sending through the network interface to the first neighbor node a register message that includes registration data that indicates the first neighbor node is the aggregation node for the apparatus; and

sending to the first neighbor node, an update message that includes information about the apparatus.

19. An apparatus as recited in claim 18, said sending the update message further comprising sending the update message prior to receiving a request message from the first neighbor node for information.

20. An apparatus as recited in claim 14, said determining the first neighbor node further comprising determining whether the apparatus received through the network interface from the first neighbor node a message that includes aggregation advertising data that indicates the first neighbor node is an aggregation node for at least one node in direct communication with the first neighbor node.