Methods and Apparatus for Membership Management of Network Nodes

• US 20080104218A1
• Filed: 08/14/2007
• Published: 05/01/2008
• Est. Priority Date: 10/31/2006
• Status: Active Grant

• Current Assignee: Hulu LLC (The Walt Disney Company)
• Original Assignee: International Business Machines Corporation
• Inventors: Liang, Jin, Spreitzer, Michael Joseph, Steinder, Malgorzata, Tang, Chunqiang
• Granted Patent: US 8,094,585 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 41/0677 Localisation of faults
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1089 Hierarchical topologies

Abstract

Techniques for managing membership of a network of nodes are provided. Nodes of the network are organized into a tree structure having a plurality of vertices. Each vertex of the tree structure comprises a group having a plurality of nodes. Membership information is maintained at each node. The membership information for a given node comprises information about a group to which the given node belongs and child groups of the group to which the given node belongs in the tree structure.

Claims

1. A method of managing membership of a network of nodes, comprising the steps of:

organizing nodes of the network into a tree structure having a plurality of vertices, wherein each vertex of the tree structure comprises a group having a plurality of nodes; and

maintaining membership information at each node, wherein the membership information for a given node comprises information about a group to which the given node belongs and child groups of the group to which the given node belongs in the tree structure.

2. The method of claim 1, wherein the step of organizing nodes of the network comprises the step of assigning an id to each group in accordance with a level within the tree structure and a sequence of groups on the level of the tree structure.

3. The method of claim 1, wherein the step of organizing nodes of the network comprises the step of maintaining a size of each group at a target size.

4. The method of claim 3, wherein the step of maintaining a size of each group comprises the step of recruiting nodes from a child group of the given group if the given group is below the target size and the given group has at least one child group.

5. The method of claim 3, wherein the step of maintaining a size of each group comprises the step of migrating nodes of the given group down from the given group to a child group of the given group if the given group is above the target size.

6. The method of claim 3, further comprising the step of joining a node to the network of nodes, wherein the step of joining a node comprises the steps of:

sending a join request to one or more known nodes in the network;

checking size of each group of the one or more known nodes; and

accepting the join request at a given group having a given known node if a size of the given group is smaller than the target size.

7. The method of claim 1, wherein the step of maintaining membership information comprises the step of removing information about the given node from other nodes that are members of the group to which the given node belongs when the given node has stopped responding to messages for a specified period of time.

8. The method of claim 1, wherein the step of organizing nodes of the network comprises the steps of:

assigning a random id to each node of each group; and

organizing nodes in each group in a ring in accordance with the random id of each node.

9. The method of claim 1, further comprising the step of detecting a failure of a node in the network.

10. The method of claim 9, wherein the step of detecting a failure comprises the step of:

periodically sending a message from each node to a neighbor of each node for failure detection; and

if the given node is unresponsive to a defined number of messages, reporting a node failure to other nodes in the group to which the given node belongs.

11. The method of claim 10, wherein, in the step of periodically sending a message from each node, the nodes of a group are organized in a ring and the message is sent to a right neighbor of each node.

12. The method of claim 1, wherein the step of maintaining membership information at each node comprises the step of maintaining an age at each node for every other node in the same group.

13. The method of claim 12, wherein, in the step of maintaining an age, the age of a node comprises a time period from which it was last known that the node was live.

14. The method of claim 1, wherein the step of maintaining membership information at each node comprises the step of exchanging membership information with other nodes.

15. The method of claim 14, wherein the step of exchanging membership information comprises at least one of:

periodically sending a message from each node to a neighbor of each node;

selecting a random member from the group to which the given node belongs for membership exchange with the given node; and

selecting a random member from a child group of the group to which the given node belongs for membership exchange with the given node.

16. The method of claim 1, further comprising the step of performing data aggregation on the network of nodes.

17. The method of claim 16, wherein the step of performing data aggregation comprises the steps of:

randomly selecting a plurality of nodes in a root group of the tree structure;

propagating an aggregation request to the plurality of nodes;

selecting a random node in each child group of the root group by each of the plurality of nodes;

propagating the aggregation request to the random nodes in each child group;

propagating the aggregation request to each node in the root group from each of the plurality of nodes.

18. The method of claim 17, wherein the steps of selecting a random node in each child group, propagating the aggregation request to the random nodes in each child group, and propagating the aggregation request to each node in the root group are repeated until there are no child groups left, wherein random nodes in each child group in a previous iteration become the plurality of nodes in a current iteration.

19. The method of claim 17, wherein the step of selecting a random node in each child group comprises the steps of:

dividing nodes of each child group into segments based on node id;

selecting a segment based on rank of nodes in the root group, by each of the plurality of nodes; and

selecting a node from the selected segment in the child group by each of the plurality of nodes.

20. The method of claim 19, wherein the step of selecting a node from the selected segment, comprises the step of selecting the node from the selected segment with the smallest age.

21. Apparatus for managing membership of a network of nodes, comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) organize nodes of the network into a tree structure having a plurality of vertices, wherein each vertex of the tree structure comprises a group having a plurality of nodes; and

(ii) maintain membership information at each node, wherein the membership information for a given node comprises information about a group to which the given node belongs and child groups of the group to which the given node belongs in the tree structure.

22. A method for making a computer implemented process to managing membership of a network of nodes, the method comprising the steps of instantiating first computer instructions onto a computer readable medium, the first computer instructions configured to organize nodes of the network into a tree structure having a plurality of vertices, wherein each vertex of the tree structure comprises a group having a plurality of nodes;

and

instantiating second computer instructions onto a computer readable medium, the second computer instructions configured to maintain membership information at each node, wherein the membership information for a given node comprises information about a group to which the given node belongs and child groups of the group to which the given node belongs in the tree structure.