Dijjer and Freenet (RE: [p2p-hackers] clustering)

Oskar Sandberg ossa at math.chalmers.se
Sat Mar 18 13:24:25 UTC 2006

Ian Clarke wrote:
> On 3/12/06, Serguei Osokine <osokin at osokin.com> wrote:
>>        By the way, as a practical matter, does Dijjer grow its routing
>>tables with network size?
> I will take this as Oskar isn't really familiar with the details of
> Dijjer (I think he is much more interested in the mathematics rather
> than the practicalities of implementation).  Dijjer does not scale its
> routing tables with the log of the network size, basically it tries to
> make the routing tables as big as possible within a given constraint
> (I think the default is 20 connections).  While this means that it
> doesn't have log(N) scalability, in practice it doesn't really make
> much difference and it means that we don't need to try to calculate
> the total network size.

To put actual numbers to this, I did simulations of point to point 
routes using the same algorithm that I think is being used in Dijjer 
(the one described in my thesis, with 20 shortcuts, but without using 
"local" links):

1000    4.4446
2000    5.066
4000    5.7604
8000    6.546755
16000   7.476
32000   8.34637
64000   9.434343
128000  10.747675
256000  12.572815
512000  15.743066

Success-rates were above 99% for all levels. These are just the lengths 
of routes, and do not take things like caching into account (off hand, 
you could probably see each cached document as an extra shortcut, since 
having the document required is the same thing as having an edge to its 

So at least up to 150,000 nodes or so you should have no problems with 
20 neighbors. Above that one might want to consider having more.

// oskar

More information about the P2p-hackers mailing list