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
"home").
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