Matthew Toseland wrote: > Path folding is essentially what freenet has done up to 0.5. When a > request succeeds, the node that sends the data sends back its noderef. > This is randomly reset by other nodes along the request chain. It is > (sometimes) added to the routing table. The least recently used node is > expelled to make way for it, if we have reached the limit on the number > of nodes connected. Oskar has done some work which strongly suggests > that LRU+path folding produces a kleinberg-assignable small world > topology, or something similar, such that routing can work.
Thanks for the explanation. > I assume you have read the defcon presentation? Apart from that, I have > the following: I've read it, short and long versions, so I have an intuitive idea. I'm still trying to understand how this relates to locating data. As I see it, >>From: Oskar Sandberg <[EMAIL PROTECTED]> >>Date: 15 June 2005 17:36:06 BDT >>To: Ian Clarke <[EMAIL PROTECTED]> >>Subject: The algorithm >> >> >> >>It is actually and application of the Metropolis-Hastings algorithm >>to the problem, though the application isn't completely obvious. >>Basically it works like this: >> >>Two nodes choose each other and decide to attempt a switch. They >>calculate the distance of all their edges currently (that is the >>distance between their currend ID and that of their neighbors), and >>multiply up all these values to get A. Then they calculate the >>distance to all their neighbors as it would be if they switched >>IDs, and multiply up these values to get B. >> >>If A > B then they switch. >> >>If A <= B, then calculate p = A^2 / B^2. They then switch with >>probability p (that is, switch if rand.nextFloat() < p). >> >> >>The only issue beyond this is how two nodes decide to attempt >>switch. It needs to be a decentralized algorithm, but from my >>simulations it seems it will not work if nodes only ever try to >>switch with their neighbors. If they also switch with neighbors >>neighbors (chosen randomly) it works better, take three steps and >>even better. The best is to pick completely randomly from the set >>of nodes, but that of course isn't decentralized. A couple of >>random walk steps should be enough (currently I'm using five). >> >>// oskar > > > On Wed, Sep 21, 2005 at 06:30:20PM +0200, Alex R. Mosteo wrote: > >>Matthew Toseland wrote: >> >> >>>The main outstanding issue is how frequently we should do path folding. >>>If it is too slow, it will take too long to converge. But if it is too >>>fast, then oskar's routing algorithm won't be able to keep up. Is there >>>any way to determine an optimal time short of alchemy? >> >>Is there some wiki/doc with further explanation of oskar's algorithm and >>path folding details? I would like to understand it properly. >> >> >>------------------------------------------------------------------------ >> >>_______________________________________________ >>Tech mailing list >>Tech@freenetproject.org >>http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/tech _______________________________________________ chat mailing list chat@freenetproject.org Archived: http://news.gmane.org/gmane.network.freenet.general Unsubscribe at http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/chat Or mailto:[EMAIL PROTECTED]
