Freenet is decentralized, so while it’s (intended to be) a small-world network and thus short routes exist between any two nodes, it can be difficult to have a routing algorithm which can find those routes using only local information. As far as I understand it, Jon Kleinberg’s work (brief, paper) forms the basis of Freenet’s networking model. We don’t have local connections, as they’re expensive to form and in empirical testing actually detrimental to performance, but apparently the model still holds. A core finding from this work is that if connections are distributed so that more-distant connections are less likely, an implicit structure forms which allows forwarding a message to the closest peer at each hop to form a shortpath. As Freenet uses 1-dimensional locations, this distribution is based on a probability which is proportional to the inverse of the distance. The ideal distribution is logarithmic, but from what I’ve gathered, Freenet’s distribution isn’t too close to it. Making the actual match the ideal is difficult – the network size is a factor in the distribution, but it cannot (practically) be known. Techniques by Oskar Sandberg (paper) are intended to produce this distribution without such knowledge, but Freenet’s implementation seems to not behave as intended. I hope to help discover why, and how to fix it.
Edit May 2, 2012: I replaced a rather dubious ideal distribution plot made with a quick Python script with a much better-looking one made with a real simulator. Here are both distributions on the same plot:
Edit August 1, 2012: Corrected Y axis label to refer to the percent of links, not nodes.
