---------- Forwarded Message ---------- Subject: ULPRs and passive requests (Jacobson paper) was Re: Submitted Freenet paper Date: Tuesday 09 Mar 2010 From: Matthew Toseland <[email protected]> To: Vilhelm Verendel <[email protected]>
On Friday 19 February 2010 12:42:58 Vilhelm Verendel wrote: > Interesting paper: http://portal.acm.org/citation.cfm?id=1658941 Long-term, we need a better system for publish/subscribe (to a set of keys or to a stream), and for Delay Tolerant Networking. Reasons for this: - Chat systems, and most other WoT-based apps, need to subscribe to a vast number of keys. - Darknet with poor connectivity will often not have end to end connectivity from the requestor to the data source. - The data source may be offline. In the near future we will deal with this by increasing data redundancy, but it'd be good to be able to just wait for it to come back online without constantly spamming the network with requests we know are unlikely to succeed (as we do now!). The proposed solution so far has been passive requests. "Long-term requests" are passive requests with some DTN capability. Ultra-Lightweight Passive Requests are a feature we already have which is similar to passive requests but has some important deliberate limitations: - We remember who has requested a key, and who we have routed it to, for 1 hour after the fact. This is partly because it's all in RAM, and partly for security reasons (arguably excessively paranoid, if an attacker can compromise nodes at will he can do anything). - If we get the data during that period we offer it to all of them - those who asked for it and those we routed it to (because they are probably closer to the ideal than we are). - This applies automatically to all requests (or almost all requests), you do not need to ask for it explicitly. - We do *not*, at present, stop a request when it runs into a recent ULPR subscription. This has however been planned for some time. The last item throws up some big issues: - The main problem is loops: If you run into your own tail, or if two requests form a loop, you get stuck. In an ideal world this would only happen when we are close to the ideal location and so would be fine, but in the chaos of a real life Freenet network I wouldn't bet on it. - The other issue is the tradeoff between searching more widely for the data versus reducing load that isn't likely to be productive. At the moment, if we route a request for a key to one node, and then we get another request for the same key, we route it differently - hence the whole network will in theory get probed eventually, if nodes keep on trying to fetch the key. Which is in fact the default behaviour. - The easy solution for both issues is to allow some number of requests for a given key, over a given time period, and then to block further requests for a timeout period. After that things might have changed so we should allow a few more routes. We had planned to implement something more sophisticated, with subscriptions persisting indefinitely provided the downstream nodes still exist based on quotas, with them rerouted when subscriptions or (sometimes) connections are lost, and with enough data propagated to prevent loops from causing deadlock. This has several advantages: - On a low-uptime darknet, we could send all the requests for a big file at once, and have them return to us gradually, dealing gracefully both with the nodes with the data coming online and offline and the nodes along the path back to the requestor coming online and offline, and minimising exposure to attackers as no further requests are sent. However this sort of thing does not easily work on opennet because quotas depend on trust. - In general, filesharing would benefit: Data will be found when the nodes with it come back online, and we achieve this *without* constantly pulling CHKs that are unlikely to exist. - Rerouting when a node goes offline etc can be quite cheap as we can send a whole swathe of requests at once, avoiding a lot of overhead. - The overhead of most nodes subscribing to a large number of keys for chat channels etc can be *very* low as there is no need to resubscribe regularly. However it is rather complex: - Rerouting and dealing with loops requires we send enough state data back down the tree to be able to tell when we are eating our own tail. This could be relatively costly. - Requires a whole new load management system based on trust-based quotas, to deal with the fact that there *are* ongoing costs, however small, to every passive request. CCN, as described in the paper, is closer to ULPRs, without the timeout and assuming huge storage, and they claim it can work with Delay Tolerant Networking (although probably not as well as real DTN stuff like Haggle etc). They do not deal with loops at all - they immediately stop a request when it reaches them if they have already routed a similar request (they check for a single request looping on itself but two requests can still form a loop if routing is a little chaotic) - and they never reroute. This may be acceptable given large storage and reasonably good routing. But maybe we can get most of the functionality and efficiency benefits of passive requests just by extending ULPRs? - Remember routes for a much longer period for purposes of notifications. This would probably have to be on-disk, but that is not necessarily catastrophic; we won't get a hit if the request is "new", and we can have a bloom filter to minimise disk accesses. - Only remember routes if the originator wants us to - but they usually will. The really paranoid can turn this off. - If we've routed requests for a given key X times over the last Y period, quash the request. We will tell the sender when they should resend it. This is both request coalescing and minimising the impact of polling. - Rework the cooldown queue to integrate smoothly with this and minimise disk I/O.
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Devl mailing list [email protected] http://osprey.vm.bytemark.co.uk/cgi-bin/mailman/listinfo/devl
