Neighborhood maintenance in the federation

• US 8,417,775 B2
• Filed: 02/27/2008
• Issued: 04/09/2013
• Est. Priority Date: 02/27/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kakivaya, Gopala Krishna Reddy, Xun, Lu
• Primary Examiner(s): Lazaro, David
• Assistant Examiner(s): KOROBOV, VITALI A
• Application Number:
  US12/038,363
• Publication Number:
  US 20090213757A1
• Time in Patent Office: 1,868 Days
• Field of Search: 709/204, 709/223, 709/238, 709/243, 709/250, 709/251, 370/254, 370/400
• US Class Current: 709/204
• CPC Class Codes: H04L 63/126 the source of the received data
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053

Abstract

Systems and methods that provide for joining a node to a federation. A link component facilitates joining such node thru three phases of join, introduce and advise. A plurality of messages and replies are exchanged between nodes in form of introduce, advise, and response messages. Such messages contain the sending node'"'"'s full neighborhood.

Claims

1. A computer-implemented system comprising at least one processor coupled to at least one machine-readable medium storing instructions executable by the at least one processor to implement:

a link component configured to introduce an introducing node to a neighborhood of nodes of a communications network, at least in part by sending an introduce message to the neighborhood of nodes, the introduce message identifying a current view of neighboring nodes of the introducing node, the neighborhood of nodes including a predetermined number of nodes closest to the introducing node,

wherein the link component is further configured to cause the introducing node to become an introduced node based on the current view becoming a stable view of the neighboring nodes of the introducing node, wherein in the stable view the current view does not change after responses to the introduce message are received; and

a set of rules for controlling extending the neighborhood of nodes, the set of rules including a rule requiring that, for an extending node to extend an edge of a neighborhood of the extending node from a first introduced node to a second introduced node, the extending node has no entries in a routing table of the extending node of any introduced node between the first introduced node and the second introduced node.

2. The computer-implemented system of claim 1, the link component further comprising a join component configured to implement a join phase including sending, by a joining node, a join message to an identifier of the joining node.

3. The computer-implemented system of claim 2, wherein the link component is further configured to, if neighboring nodes of the introducing node go down, implement the join phase for the introducing node.

4. The computer-implemented system of claim 1, the link component further comprising an advisory component configured to send an advise message to an introduced node in the neighborhood of nodes, the advise message prompting a response identifying neighboring nodes of a responding node.

5. The computer-implemented system of claim 1, wherein a response to the introduce message includes an identification of neighboring nodes of a responding node.

6. The computer-implemented system of claim 1, wherein the predetermined number of nodes comprises an edge node in each of successor and predecessor node directions.

7. The computer-implemented system of claim 1, wherein the rule requires that, for the extending node to extend the edge of the neighborhood of the extending node from the first introduced node to the second introduced node, the extending node has no entries in the routing table of the extending node of any introduced node.

8. A computer-readable storage medium, the computer-readable storage medium being hardware and storing instructions, the instructions if executed by a computing device causing the computing device to perform operations comprising:

by an introducing node, sending an introduce message to a neighborhood of nodes in a communications network, the introduce message identifying a current view of neighboring nodes of the introducing node;

receiving a response from at least one node of the neighborhood of nodes, the response identifying neighboring nodes of the at least one node; and

based on the current view being unchanged by the response, becoming an introduced node of the neighborhood of nodes in accordance with a set of rules for controlling extending the neighborhood of nodes, the set of rules including a rule requiring that, for an extending node to extend an edge of a neighborhood of the extending node from a first introduced node to a second introduced node, the extending node lacks entries in a routing table of the extending node of any introduced node between the first introduced node and the second introduced node.

9. The computer-readable storage medium of claim 8, the operations further comprising:

adding the introduced node to the neighborhood of nodes.

10. The computer-readable storage medium of claim 8, the operations further comprising:

by a joining node, targeting a join message to an identifier of the joining node.

11. The computer-readable storage medium of claim 10, the operations further comprising:

by a neighboring node of the joining node closest to the joining node, receiving the join message.

12. The computer-readable storage medium of claim 11, the operations further comprising:

by the neighboring node of the joining node closest to the joining node, responding to the join message with an identification of neighbors of the neighboring node closest to the joining node.

13. The computer-readable storage medium of claim 10, the operations further comprising:

removing a shut-down node from the neighborhood of nodes.

14. The computer-readable storage medium of claim 8, wherein the rule requires that, for the extending node to extend the edge of the neighborhood of the extending node from the first introduced node to the second introduced node, the extending node lacks entries in the routing table of the extending node of any introduced node.

15. A method comprising:

by a new node in a communications network, sending an introduce message to a plurality of neighboring nodes;

receiving responses from the plurality of neighboring nodes, the responses identifying respective neighborhoods of the plurality of neighboring nodes; and

becoming an introduced node to the plurality of neighboring nodes if after receiving the responses the current view is unchanged, in accordance with a set of rules for controlling extending the plurality of neighboring nodes, the set of rules including a rule requiring that, for an extending node to extend an edge of a neighborhood of the extending node from a first introduced node to a second introduced node, the extending node lacks entries in a routing table of the extending node of any introduced node between the first introduced node and the second introduced node.

16. The method of claim 15, further comprising:

by the new node, targeting a join message to an identifier of the new node.

17. The method of claim 16, further comprising:

by a closest neighboring node of the new node, receiving the join message.

18. The method of claim 17, further comprising:

by the closest neighboring node of the new node, responding to the join message with an identification of neighbors of the closest neighboring node of the new node.

19. The method of claim 15, further comprising:

by the introduced node, based on recognizing that a neighboring node is shut down, sending a message to another neighboring node containing information about the shut-down node; and

extending an edge of the plurality of neighboring nodes to a predecessor node of the shut-down node.

20. The method of claim 19, further comprising:

identifying the plurality of neighboring nodes in terms of a sorted list joined in a ring.