On Thursday 11 November 2010 21:06:37 Gerard Krol wrote: > Hello everyone, > > I've spent some nights trying to understand the way Freenet builds and > maintains its opennet topology. The goal is to obtain a small world > network (without hubs).
Right, a small world network that is not a scale free network. > The small average path (hop) length is good > for performance, It's *essential* for performance. > while the large degree of clustering makes it easy to > find the node that has the exactly key we are looking for. Not sure exactly what clustering means, but having a few long links and lots of short links means we can traverse large distances quickly and then approach the ideal node (moving over short distances) quickly without having to bounce around endlessly. A Kleinberg-style routable small world network, which can be routed with greedy routing, requires that the probability of a connection between two peers is inversely proportional to the distance between their locations. > > The current system, as I understand it, has a chance to short circuit > a path. This is called "path folding". When any data is sent a node > will attach a noderef if it is interested in more peers. The data and > noderef will be routed across the network to the same location as the > data until it reaches a node that wants to have more peers and that > rolls success on the "path folding dice". If so, the nodes will > connect to each other and a shorter path is formed. You have this backwards. When the data is found, a noderef is returned from the data source, which is routed back to the request originator, but it can be intercepted along the way at random (security feature) or by other nodes that need the peers (for performance, subject of some debate). > > I think this behavior will cause us to connect to *clusters* of peers. > This is due to the path folding request traveling over already > established routes. How does this follow? > If those peers are close to us its not a problem, > but we might end up with a few connections to a cluster of peers far > away from our own location. Take a look at your "Peer Location > Distribution" now and tell me if that is the case. Why is that a problem? As long as most of our incoming requests are close to our specialisation, which is mostly true in practice, most of our peers will be close to our location. Also, IMHO peer clumps near other locations could very well be the result of FOAF. If the graph shows peers-of-peers the same as it shows direct peers, for instance, it entirely expected. Even if you are sure there is a cluster of direct peers of your node around a different location, it could still be influenced by FOAF, because if one of your peers is at that location, you will have a secondary specialisation in your incoming requests. > > My proposal is to change the way path folding works and make it less > "path folding" and more "peer finding". If we need a connection we > send our noderef to a random location chosen with chance proportional > to 1/d, where d is the distance between us and the chosen location. If > the final node on that location wants more peers we connect. This will > force an 1/d distribution of our peers, which should be enough to > obtain a small world network. You have detailed simulations and proof bordering on mathematical theorems? Oskar does, for the current algorithm. You have a mechanism that is essentially self-regulating, that takes performance into account without needing to explicitly balance reliability against speed against location? Path folding does. Everything suggests path folding works well. Anything we deploy in its place would need to work better, and the fact that it works better would need to be rigorously demonstrated. In any case, opennet is not the big issue IMHO. Opennet will be gone in a few years, because it is easy to attack, on every level, from cheaply locating an individual data source (a regular poster on the chat systems, or somebody careless enough to reinsert stuff or insert predictable data to CHKs) to relatively cheaply surveilling all traffic or blocking all nodes. Note that announcement actually does something somewhat similar to your proposal, but it returns multiple connections, some of which are hopefully "long links". > > The current peer disconnection algorithm looks OK to me. It will every > once in a while drop the peer for who it is the longest ago that it > was successful in fetching a key for us. > > Regards, > > Gerard -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 197 bytes Desc: This is a digitally signed message part. URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20101112/a3393acc/attachment.pgp>
