Alex R. Mosteo wrote: > 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,
I'm going to read too the "Using the Small-World Model to Improve Freenet Performance" paper. Sorry for the premature sending. I was saying that I have a more or less intuitive idea of how this work to locate a given [node]-id in that artificial circumference. But when a node stores multiple ids (the keys in its datastore), how this works? Is this related to specialization? There's some hints in Ian's slides but I don't get it. If I'm not mistaken, in a Kademlia type network is at the moment of publication that the data reference is placed in the corresponding node. I.e. there's a convergence between publishing and searching at the node placed in the proximity of the key. In freenet this is not doable for security concerns, because the reference to the node must not be harvestable. So here I'm lacking half of the picture. I see how we can locate a key, supposing that the key is where it should be. I don't see how a node key is dissociated from its data keys. I don't think this is really new to the new routing, it was already a characteristic of the 0.5 network, right? So I suppose docs from 0.5 could instruct me about this? Another non-related idea I had yesterday: Someone was worried that in a hybrid network, the darknet data could be, even if expensively, flooded out by malicious nodes. What about a datastore with reserved space for darknet data? Say 50%. This would prevent that someone that has harvested open nodes could flood the data received from trusted links. >>>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]
