Peer-to-peer overlay graph construction

• US 20080155520A1
• Filed: 10/26/2006
• Published: 06/26/2008
• Est. Priority Date: 10/26/2006
• Status: Active Grant

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Dimitrov, Stanko, Yajnik, Shalini, Bentley, Jon, Meloche, Jean, Mallows, Colin L., Krishnan, P.
• Granted Patent: US 9,026,654 B2
• Time in Patent Office: Days
• US Class Current: 717/157
• CPC Class Codes: H04L 41/06 Management of faults, events, alarms or notifications
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/0811 by checking connectivity

Abstract

Systems and methods for constructing and maintaining a peer-to-peer overlay graph are disclosed herein. The systems and methods include adding a node to the overlay graph. Adding the node includes choosing an edge that is not connected to the node, breaking the edge and connecting the node to broken edge nodes previously connected to the edge. The process is repeating if additional connections are need and node addition data is stored for the node.

Claims

1. A method for constructing a peer-to-peer overlay graph, comprising:

adding a node j to the overlay graph, where adding the node j includes;

choosing an edge that is not connected to the node j;

breaking the edge and connecting the node j to broken edge nodes previously connected to the edge; and

repeating the adding process if additional connections are needed.

2. The method of claim 1, wherein the method of adding further comprises:

connecting to a first node in the overlay graph, if the first node is degree deficient.

3. The method of claim 1, wherein the method of adding further comprises:

communicating with an introduction server that refers the node j to the edge or to a node in the overlay graph.

4. The method of claim 1, wherein additional connections are needed if a degree of the node j is less than d, where d is the degree of node j.

5. The method of claim 4, wherein d is the degree for all nodes in the overlay graph.

6. The method of claim 1, further comprising:

removing a node k from the overlay graph including;

if the node k is not a young node l, exchanging node k with the young node l;

removing the young node l and

reconnecting edges broken during the insertion of young node l into the graph.

7. The method of claim 6, further comprising:

determining node k is disconnected due to a failure;

transmitting a message to young node l indicating the identity of the failed node k; and

exchanging node k with young node l.

8. The method of claim 7, wherein at least one neighbor node to failed node k transmits the message to young node l.

9. The method of claim 6, wherein the edges broken during the insertion of the young node l to the graph is determined by retrieving node addition data for young node l.

10. The method of claim 6, wherein exchanging node k with the young node l includes:

inserting young node l into the graph in the location of node k;

establishing the same connections between young node l and neighbor nodes as was previously established for node k; and

identifying node k as young node l.

11. The method of claim 6, wherein young node l is a last node added to the graph.

12. The method of claim 6, wherein young node l is determined as a node that is connected only to ancestor nodes.

13. The method of claim 1, further comprising:

storing node addition data for the node j.

14. The method of claim 1, wherein the node addition data comprises at least one of:

a set of edges with node j as an endpoint;

a set of edges broken when node j was added;

a unique node identifier for node j;

a current last node in the graph;

or

identities of neighbor nodes along edges connected to node j.

15. An apparatus for constructing a peer-to-peer overlay graph, comprising:

logic configured to add a node j to the overlay graph, wherein the logic configured to add the node j includes;

logic configured to choose an edge that is not connected to the node j;

logic configured to break the edge and to connect the node j to broken edge nodes previously connected to the edge; and

logic configured to repeat the adding process if additional connections are needed.

16. The apparatus of claim 15, wherein the logic configured to add the node j further comprises:

logic configured to connect to a first node in the overlay graph, if the first node is degree deficient.

17. The apparatus of claim 15, wherein the logic configured to add the node j further comprises:

logic configured to communicate with an introduction server that refers the node j to the edge or to a node in the overlay graph.

18. The apparatus of claim 15, wherein additional connections are needed if a degree of the node j is less than d, where d is the degree of node j.

19. The apparatus of claim 18, wherein d is the degree for all nodes in the overlay graph.

20. The apparatus of claim 15, further comprising:

logic configured to remove a node k from the overlay graph, including;

logic configured to exchange node k with a young node l, if the node k is not young node l;

logic configured to remove young node l; and

logic configured to reconnect the edges broken during the insertion of young node l into the graph.

21. The apparatus of claim 20, further comprising:

logic configured to determine node k is disconnected due to a failure; and

logic configured to transmit a message to young node l indicating the identity of the failed node k; and

logic configured to exchange node k with young node l.

22. The apparatus of claim 21, wherein at least one neighbor node to failed node k transmits the message to young node l.

23. The apparatus of claim 20, wherein the edges broken during the insertion of the young node l to the graph is determined by retrieving node addition data for young node l.

24. The apparatus of claim 20, wherein the logic configured to exchange node k with young node l includes:

logic configured to insert young node l into the graph in the location of node k;

logic configured to establish the same connections between young node l and neighbor nodes as was previously established for node k; and

logic configured to identify node k as young node l.

25. The method of claim 20, wherein young node l is a last node added to the graph.

26. The method of claim 20, wherein young node l is determined as a node that is connected only to ancestor nodes.

27. The apparatus of claim 15, further comprising:

logic configured to storing node addition data for the node j.

28. The apparatus of claim 27, wherein the node addition data comprises at least one of:

a set of edges with node j as an endpoint;

a set of edges broken when node j was added;

a unique node identifier for node j;

a current last node in the graph;

or

identities of neighbor nodes along edges connected to node j.