Method of aggregate statistic computation

• US 7,738,404 B2
• Filed: 01/23/2007
• Issued: 06/15/2010
• Est. Priority Date: 01/23/2007
• Status: Active Grant

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Rastogi, Rajeev, K V M, Naidu, Deb, Supratim, Srinivasan, Anand, Kashyap, Srinivas
• Primary Examiner(s): Kumar, Pankaj
• Assistant Examiner(s): EBRAHIM, ANEZ C
• Application Number:
  US11/656,465
• Publication Number:
  US 20080175169A1
• Time in Patent Office: 1,239 Days
• Field of Search: 370/241.235, 370/238, 370/256, 370/396, 370/408, 370/235, 370/241, 370/338, 370/403, 370/425, 370/445, 709208-211, 709/233, 709/201, 709/224, 709/225, 709/226, 709/230, 707/3, 707/10, 707/205
• US Class Current: 370/255
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1051 Group master selection mechanisms
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks

Abstract

A method of grouping nodes within a distributed network is provided. The example method includes performing a leader node self determination operation by which each node within the distributed network determines whether to become a leader node or a non-leader node, each leader node being the leader of a group including at least one node. Next, requests are sent, from each leader node, requesting at least one non-leader node to join the group associated with the leader node. First received requests are accepted, at each non-leader node, such that accepting non-leader nodes transition from a non-leader node to a dependent node dependent upon the requesting leader node. A next set of requests are sent, from each remaining non-leader node, requesting to join the group associated with at least one leader node. A determination is made, at each requested leader node, as to whether to accept the non-leader node into the group associated with the requested leader node. Based on the determination, at each requested leader node, the non-leader node is either accepted into the group associated with the requested leader node, or is alternatively rejected from the group.

Claims

1. A method of grouping nodes within a distributed network, comprising:

performing a leader node self determination operation, without interacting with other nodes within the distributed network, by which each node within the distributed network determines whether to become a leader node or a non-leader node, each leader node being the leader of a group including at least one node;

sending requests, from each leader node, requesting at least one non-leader node to join the group associated with the leader node, the at least one non-leader node initially being unassociated with the leader node sending the requests;

accepting, at each non-leader node, a request from a first requesting leader node, such that accepting non-leader nodes transition from a non-leader node to a dependent node dependent upon the requesting leader node;

sending requests, from each remaining non-leader node, requesting to join the group associated with at least one leader node;

determining, at each requested leader node, whether to accept the non-leader node into the group associated with the requested leader node; and

accepting, at each requested leader node, the non-leader node into the group associated with the requested leader node based on the determining step.

2. The method of claim 1, wherein the leader node self determination operation comprises:

determining, at each of the nodes within the distributed network, whether to transition to a leader node such that each node within the distributed has a probability (1/log n) of becoming a leader node, where n is a total number of nodes within the distributed network; and

transitioning approximately (n/log n) of the n nodes into leader nodes.

3. The method of claim 1, wherein the sending step performed at each leader node comprises:

selecting one of a plurality of nodes within the distributed network; and

sending a group join request requesting the selected node to join an associated group.

4. The method of claim 3, wherein the sending step performed at each leader node further comprises:

repeating the selecting and sending a group join request steps until a number of iterations of the selecting and sending a group join request steps exceeds a threshold.

5. The method of claim 4, wherein the leader node and the selected node exchange data if the selected node accepts the group join request.

6. The method of claim 3, wherein the selecting step randomly selects one of the plurality of nodes.

7. The method of claim 1, wherein transitioning from a non-leader node to a dependent node includes exchanging data between the dependent node and the associated leader node.

8. The method of claim 1, wherein the accepting step performed at each non-leader node accepts the request from the first requesting leader node if the request is received within a time threshold.

9. The method of claim 8, wherein the time threshold is a given number of rounds, each round being a synchronized interval within which leader nodes send a single request to join the group of the leader node.

10. The method of claim 1, wherein sending step performed by each remaining non-leader node comprises:

selecting one of a plurality of nodes within the distributed network;

determining whether the selected node is a leader node;

sending a group join request to the selected node if the determining step indicates that the selected node is a leader node; and

receiving contact information for a leader node of the group associated with the selected node if the determining step indicates that the selected node is not a leader node.

11. The method of claim 10, wherein sending step performed by each remaining non-leader node further comprises:

repeating the selecting, determining, sending a group join request and receiving steps until either (i) a leader node accepts the group join request or (ii) the number of iterations of the selecting, determining, sending a group join request and receiving steps exceeds a threshold.

12. The method of claim 10, wherein sending step performed by each remaining non-leader node further comprises:

repeating the sending a group join request step for the leader node of the group associated with the selected node if the determining step indicates that the selected node is not a leader node.

13. The method of claim 1, wherein the determining step determines to accept the non-leader node into the group associated with the requested leader node if (i) a number of nodes within the group associated with the requested leader node does not exceed a first threshold or (ii) a number of nodes joining the group associated with the requested leader node in response to requests sent by the remaining non-leader nodes does not exceed a second threshold.

14. The method of claim 1, further comprising:

performing an aggregate statistic computation, the leader nodes configured to operate in accordance with a first set of protocols during the aggregate statistic computation and the dependent nodes configured to operate in accordance with a second set of protocols during the aggregate statistic computation.

15. The method of claim 14, wherein the aggregate statistic computation is based upon local data of a given data type stored independently at each of the nodes within the distributed network.

16. The method of claim 15, wherein the aggregate statistic computation is one of (i) calculating a maximum of the local data among all of the nodes within the distributed network, (ii) calculating a sum of the local data among all of the nodes within the distributed network, (iii) calculating an average of the local data among all of the nodes within the distributed network, (iv) calculating a group average of the local data among all of the groups within the distributed network, (v) calculating a rank of the local data among all of the nodes within the distributed network and (vi) calculating a minimum of the local data among all of the nodes within the distributed network.