On Saturday 28 March 2009 19:29:42 you wrote: > Reading Proposed Changes to Load Balancing I have marked in text bold > possible useful tasks to do.
Ugh, html-mail. :| We should discuss this on the devl list, in public, so I have CC'ed that. Note that any accepted student will have to communicate mostly in public. > > - AIMD <http://citeseer.ist.psu.edu/floyd00comparison.html>∞ congestion > control on each outgoing link > - A token bucket <http://en.wikipedia.org/wiki/Token_bucket>∞ for flow > control on each incoming link > - Fill the buckets at equal rates to ensure fairness > - When a peer's bucket is empty, reject its requests > - When a peer's bucket is full (ie when an incoming link is underused), > add its tokens to another bucket instead > - Perhaps add them to the emptiest bucket (if there's excess > bandwidth, give it to whoever asks for it) > - Perhaps add them to the fullest bucket (giving peers an incentive to > ask for as little bandwidth as possible) > - * We probably need simulations to discover the knock-on effects of > both suggestions* > - When forwarding a RejectedOverload, possibly reduce the rate at which > the rejected peer's bucket is filled > - This provides a stronger incentive to conserve bandwidth, but could > adversely affect paths that share one or more links with the path of the > rejected request > - * Again, simulations are needed* The above is an old proposal, please have a look at the mailing list archives, search for "token passing" ... I am not certain that AIMD is needed, what we need to do is simply to estimate the node's capacity for requests, and send messages to nodes indicating that we might be willing to take a request from them. These would be piggybacked on other packets e.g. completing a request, so would cost very little. If more requests come in than we have slots for, we can reject the surplus requests. We can use per-peer token buckets to track fairness between accepting requests from different peers, and these could be biased by tit-for-tat, as well as the tradeoffs mentioned above about rewarding vs punishing flooding. Once we have accepted a request, we queue it until we can forward it, or until it is satisfied locally (e.g. by the data being found). When we get an offer allowing us to forward a request, we try to pick the best queued request to forward. After some period, requests may timeout (and fail) if they have not been forwarded, or alternatively they may persist, depending on the flags on the request. Our criteria for forwarding requests should include: * the location of the node offering the request, and the target location for the request: the closer the match the better, for routing's sake! * the age of the request, and any policy set on the request (e.g. requests may specify deadlines, or that they are more interested in speed, or more interested in good routing) * avoiding ubernodes - sending more than X% of our traffic to any single node is bad, even if it has much higher capacity than our other peers do * not looping - if we know a request has already been sent to a specific node, or has come from it, clearly we do not want to send it there! there are also other concerns, see PeerManager.closerPeer() for full details But there are lots of variations on the proposal. Essentially the goals of a new load management system are: - Propagate load back to its source. A node that starts flooding requests at a high rate should be automatically contained by the network. It should only be able to start its fair share of requests, and we may want to prefer other non-flooding nodes when we have a choice. - More broadly, ensure that no more requests are started than the network has the capacity to handle. - But also not over-throttle: the number of requests started should be close to the network's capacity, but not greater than it. Arguably the current system is inflexible especially on high speed darknet pockets: it works by estimating the capacity of the entire network based on feedback on how many outgoing requests are rejected, and adjusting the outgoing local request rate. - Deal gracefully with exceptionally slow nodes. If a node has limited capacity e.g. because of local network conditions, because it is on a slow link, because the user started playing a computer game, we should send it fewer requests - but not no requests. Our current mechanism is backoff, which is not very flexible either. - Not to break routing. Load management should work with routing, not cause large scale misrouting. Ultimately routing requests to nodes which are not appropriate routing-wise will just cause load to multiply, as happened constantly on 0.5. However, if the perfect node to route to has very limited capacity, we may need to route to another node which is close to the target but not as close as that one. Ideally, the lower the capacity of the node, the sharper its specialisation - only the requests that really closely match it should be forwarded to it. - Not give away which requests are locally originated by timing attacks; the current load management system has an AIMD on the originator node determining how fast to send local requests, this may be exploitable by timing attacks to help determine which requests are local requests. - Avoid ubernodes. We do not want to send more than some proportion of our outgoing requests to any given node, even if routing says we should (this can be influenced by e.g. FOAF routing). This can be turned off by setting a low network security level. - Have the possibility of adapting the system for tit-for-tat or other strategies to reward "good" peers e.g. by allowing them more requests. - Allow requests with the "fast" flag to complete quickly, with low total latency, but with less routing accuracy, and fewer such requests accepted. - Allow requests with the "bulk" flag to be routed accurately and take a long time, and be accepted in higher quantity. - Note that the problem here is that most requests fail, hence we need lots of them to get good average throughput, but this means if a bunch of requests succeed then transferring all the data can take some time. On the other hand, "fast" requests are used by e.g. fproxy (freesites) so they need to respond quickly, but there can be fewer of them since most requests are for big stuff. As you can see, we're asking for a lot! Any load management system likely won't accomplish all of these goals immediately, but it should be possible to address them without making drastic changes to it. > > To verify this proposals simulating the algorithm in the Freenet simulator > and with special interest on adding lots of new nodes (i.e. flash crowds). > Aslo a possible extension could be the swap of token buckets under some > conditions. Yes. Simulations of load management would be very welcome. You should investigate the existing simulators (particularly the event-based ones), which are in the SVN repository, I am hopeful that they can be adapted without massive effort. You will need to more or less reproduce the current load management system (AIMDs on the originator based on timeouts and rejections, plus backoff to deal with individual slow peers, documented on the wiki), and then simulate various proposals from the mailing lists for new systems.
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Devl mailing list [email protected] http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
