[p2p-hackers] Node counting algorithm

[Michael Parker]

Interestingly enough, the topology of some DHTs makes this not too 
difficult to calculate. In Pastry/Bamboo, for example:

If your leaf set overlaps, it's just the number of entries in your leaf set.
If your leaf set does not overlap, divide the size of the ring (e.g. 
2^128, 2^160) by the span of your leaf set (i.e., the farthest clockwise 
node minus the farthest counterclockwise node, modulo the ring size), 
and multiply by the size of your leaf set. Basically, what this means is 
if your leaf set is size L, and it spans a percentage x of the node 
identifier space, the size of the network is approximately L * x^-1. To 
improve accuracy, ask the two farthest nodes in your leaf set and ask 
them for their leaf sets, merging them into yours before calculating. 
That way, you have a larger effective L.

The same can be done for Chord using its successor list and predecessor. 
Alternatively, in these two networks, since the number of nodes in your 
routing table is log_2 N, you can estimate the size of your network as 
2^k, where k is the number of filled rows in your routing table. 
Finally, although I'm no Kademlia expert, I think you can estimate the 
size of the network by 2^k, where k is the number of buckets in your 
routing table.

- Michael Parker


Gwenchlan wrote:

> Le mercredi 23 février 2005 à 06:33 -0800, Daniel Stutzbach a écrit :
>
>> On Wed, Feb 23, 2005 at 03:23:21PM +0100, Gwenchlan wrote:
>>
>>> i am looking for papers or informations about node counting on 
>>> overlays, but currently without success.
>>> In a distributed fashion, a node would be able to start a process to 
>>> estimate the overlay size.
>>> Do someone here have seen something like this recently?
>>> Any clues about that?
>>> I think i will have to use random walkers.
>>
>>
>> Are you looking for an algorithm that will estimate the overlay size
>> for use by the overlay, or are you looking for measurement techniques?
>>  
>>
> Hi Daniel,
> probably the first option, in order to launch "on demand" mesurement 
> for overlay maintenance (by the overlay itself) for exemple..
> The request initiator would be waiting for a more or less precise 
> estimation, due to dynamicity, response time expected..
> _______________________________________________
> p2p-hackers mailing list
> p2p-hackers at zgp.org
> http://zgp.org/mailman/listinfo/p2p-hackers
> _______________________________________________
> Here is a web page listing P2P Conferences:
> http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences
>