Tech and Media Labs
This site uses cookies to improve the user experience.




Finding Peers in a P2P Network

Jakob Jenkov
Last update: 2014-05-23

Peers in a P2P network should be able to communicate directly with any other peer in the network. A peer can of course easily communicate directly with the peers it has in its routing table. But what about the peers it does not have in its routing table? These peers must first be located before the peer can communicate with them.

Finding a peer in a P2P network is done via the peer routing tables. It is done using the following iterative process:

  1. Find closest peer (GUID) to target peer (GUID) in own routing table.
  2. If closest peer is not target peer, contact closest peer and ask for closest peer to target peer.
  3. If closest peer returned from contacted peer is not target peer, repeat from 2, by contacting the currently closest peer and ask for the closest peer to target peer.

The process is illustrated in the diagram below. The diagram assumes that Kademlia routing tables are used, but the principle is the same using Choord routing tables.

Peer 0 finds peer 15 in a Kademlia network.
Peer 0 finds peer 15 in a Kademlia network.

Peer 0 is trying to find peer 15, which it does not have a reference to.

Peer 0 first looks in its own routing table. The closest peer to peer 15 it has in its routing table, is peer 8.

Peer 0 then contacts peer 8 and asks for the closest peer to peer 15. The closest peer to 15 that peer 8 has in its routing table, is peer 12. So, peer 8 returns peer 12 to peer 0.

Peer 0 now contacts peer 12, and asks for the closest peer to peer 15. The closest peer that peer 12 has in its routing table, is peer 14. So, peer 12 returns peer 14 to peer 0.

Peer 0 now contacts peer 14, and asks for the closest peer to peer 15. Peer 14 actually has a reference to peer 15, so peer 14 returns that reference to peer 0.

Peer 0 has now found peer 15.

If peer 15 had not been online in the network, peer 14 would have returned the closest GUID it knew to 15, which was itself (14). When peer 14 returns 14, peer 0 would know that it could not get any closer, and that peer 15 thus could not be found.

The lookup process is also illustrated in this flow diagram:

Flow diagram of the peer lookup process.
Flow diagram of the peer lookup process.

And, finally, here is the lookup process in pseudo code:

targetPeer      = 14;     // or some other number.
closestPeer     = routingTable.findClosest(targetGUID);
prevClosestPeer = null;

    
while(    closestPeer != targetPeer
       && closestPeer != prevClosestPeer ) {
    
    prevClosestPeer = closestPeer;
    closestPeer     = askForClosestPeer(closestPeer, targetPeer);
}

if(closestPeer == targetPeer) {
      // found
} else {
      // not found, closestPeer = prevClosestPeer
}


Logarithmic Lookup Speed

If you look at the ring diagram again, you may notice that for each step in the lookup process, the distance between peer 0 and peer 15 was cut in half. First the distance was 15. After finding peer 8 in its own routing table, the distance was now 7 (15 - 8). After contacting peer 8 and getting a reference to peer 12, the distance was 3 (15 - 12). After contacting peer 12 and getting a reference to peer 14 the distance was now 1 (15-14).

This characteristic of the peer lookup process is caused by the exponentiel distances of the peers kept in each peers routing table.

This characteristic of the peer lookup process means, that the O notation for the lookup process is

O( log(n) )

where n is the number of nodes in the network.

For instance, if a P2P network uses 64 bit GUID's, and thus has space for 264 peers in the ring, then any peer in the network can be found by at most log( 264 ) = 64 steps. If you double the number of peers in the network to 265, then it only takes at most 1 more step to find any peer, namely 65.

In other words, as n (the number of peers in the network) grows, the time it takes to lookup a peer in the network only grows with log(n). This means that the loopkup process scales reasonably well, even for very large networks.

Jakob Jenkov




Copyright  Jenkov Aps
Close TOC