Connecting to a Graph
When initially connecting to a graph, a peer node connects to a node that is already connected to the graph. The peer node determines the address of the peer node connected to the graph through any method to resolve the IP address of a graph node, such as DNS or the peer discovery and name resolution methods as described in the "Peer Discovery and Name Resolution with PNRP" section of this white paper.
If the selected peer node has less than the maximum allowable number of graph connections to neighbors, it will send an accept response. If it has already reached the maximum number, it will send a rejection response. In the rejection response is a referral list, a list of other nodes in the graph. The peer node attempting to connect to the graph that receives the rejection response picks at random a peer graph node in the referral list, and tries to connect to it.
The process to pick a new neighbor after connecting to the graph is the same. The reject message from the tentative new neighbor contains a referral list. The peer node attempting to connect to a new neighbor that receives the rejection response picks at random a peer graph node in the referral list, and tries to connect to it.
Disconnecting from a Graph
When a node disconnects from a graph, it sends a disconnect message. This can potentially create a graph partition. The disconnect message carries a referral list, which includes all neighbors except the node being disconnected from. When a node receives a disconnect message from a neighbor, it should try to reconnect to peer in the referral list.
Detecting and Repairing a Graph Partition
As nodes connect and disconnect from graphs, partitions in the graph may occur. For each graph there is a graph signature and one or more contacts. The number of contacts for the graph is proportional to the size of the graph. Peers can belong to multiple graphs. The contact and graph signature information is flooded to all the nodes of the graph. The contact and graph signature information is refreshed periodically. If the contact and graph signature information becomes stale, a partition has occurred. When this is detected, an attempt to communicate with the contact node is made. If successful, an attempt is made to reconnect the graph.
Graph Partition Repair Example
To provide an example of a graph partition, let's build a graph and then examine the information that is exchanged to detect the partition and to repair it.
Building an Example Graph
The following process describes how a graph is built:
| • |
We start our graph (Graph X) with a single node, Node A. Node A has the node ID 2. Node A creates a Signature record for the Graph X with graph signature of 2. Node A also creates a Contact record for Graph X/Node A with graph signature of 2. |
| • |
Node B joins the graph. Node B has node ID 1 and connects to Graph X via Node A. Node B gets Node A's record database, which consists of the Signature record for the graph and the Contact record for Node A. |
| • |
Node B notices that the graph signature for Graph X is higher than its own node ID. The graph signature for Graph X should be 1, rather than 2. |
| • |
Node B floods a new Signature record for Graph X with graph signature of 1 to Node A. Node A updates its record database with the new Signature record from Node B. |
| • |
Node A checks its own Contact record. Node A notices that its own Contact record has a graph signature set to 2, when it should be set to 1, the new graph signature for Graph X. |
| • |
Node A changes the graph signature of its own Contact record to 1 and floods a new copy of its Contact record to Node B. |
| • |
Node B updates its Contact record for A with the new graph signature of 1. |
Note: Graph records contain a digital signature and cannot be altered. However, they can be replaced. Therefore, the use of the term "update" in this discussion refers to the replacement of a record with a record containing a higher version number, rather than the changing of the record's contents.
At this point, the graph records have been synchronized and the graph topology has converged. Both Node A and Node B have the same information in their record databases for the graph: a Signature record with the graph signature set to 1 and a Contact record for Node A with the graph signature set to 1.
Node C, with the node ID of 5, connects to Graph X via Node B. After connecting to Node B, Node C gets Node B's record database, consisting of the Signature record and the Contact record for Node A. Once again, the graph has converged: Node A, Node B, and Node C have the same information in their record databases for Graph X.
Over time, separate graph connection forms between Node C and Node A to form a fully interconnected graph.
Let's jump ahead to Graph X with 6 nodes as shown in Figure 7.
Graph X consists of Node A (node ID 2), Node B (node ID 1), Node C (node ID 5), Node D (node ID 7), Node E (node ID 8), and Node F (node ID 9), with Node A and Node D as contacts.
The graph topology has converged. All the nodes have the same record database: a Signature record with graph signature of 1, a Contact record for Node A with graph signature of 1, and a Contact record for Node D with graph signature of 1. The Signature record has a valid lifetime of 5 minutes and is periodically refreshed (within 5 minutes) by Node B. The Contact records also have valid lifetimes and are periodically refreshed.