New backtracking proposal, half ian's: - At present, we never route to a node which is further away from the target than we are. If we can't go anywhere short of breaking this rule, we backtrack (reject the query, the sender routes again with lower HTL). - The result of this is that most of the "extra" hops - the hops where the request is not getting closer to the key - are towards the beginning of the request i.e. the places furthest away from the key. - But what we want is to find the "ideal" node, and then wander around its nearest neighbours for a while, on the chance that the data we want is close by. It might have swapped. Although with the 6 hop swaps we use at present, that's unlikely - this needs to be looked into.
So, an improved backtracking algorithm is: - HTL starts at X, say 10, and is probabilistically decremented as now. - On the request, we record the location of the node closest to the key. This is dubious re anonymity for the first hop or first few hops, however, if you trust your neighbours it's not a problem, and if you don't, you'll have to use (slow) multi-neighbour premix routing, which will be implemented in 0.7.1. - If we route to a node whose location is closer to the key than the current record, we don't decrement the HTL. If we route to a node which is further away, we decrement the HTL. Thus, we route towards the ideal node. Then we wander around its immediate neighbours for 10 hops. Perfect, no? The anonymity cost is a bit of a concern, though. It would be very difficult to prevent the location giving away the request to the first node. However, it's pretty easy for the first node to identify the request anyway, with a correlation attack, or with fake premix topology, or many other attacks... But not setting the location on the first hop crosses the line from "they can easily bust you" to "they can trivially bust you". Setting it to a neighbour node's loc which is further away from the target than you or the node you're routing to will maybe move it back into "they can easily bust you". -- Matthew J Toseland - toad at amphibian.dyndns.org Freenet Project Official Codemonkey - http://freenetproject.org/ ICTHUS - Nothing is impossible. Our Boss says so. -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 189 bytes Desc: Digital signature URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20050902/d8406586/attachment.pgp>
