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.
I assume you have read the defcon presentation? Apart from that, I have the following: >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. -- Matthew J Toseland - [EMAIL PROTECTED] Freenet Project Official Codemonkey - http://freenetproject.org/ ICTHUS - Nothing is impossible. Our Boss says so.
signature.asc
Description: Digital signature
_______________________________________________ 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]
