Current Freenet 0.7 algorithms for load management, congestion control etc
The current deployed algorithms for limiting and balancing load and preventing congestion: (This was originally modelled on TCP over Ethernet, but I'm not convinced that's a useful metaphor at this point)
- Encryption, retransmission, etc. Lowest layer. New design: http://wiki.freenetproject.org/NewPacketFormat (not finished)
The current packet encryption is adequate, but has higher overhead than the proposed design. The retransmission layer is not adequate as it has various arbitrary parameters and limits (e.g. we always allow up to 256 and no more than 256 packets in flight).
freenet/node/FNPPacketMangler, KeyTracker, PeerNode etc
- Congestion control. Middle layer. New design: http://wiki.freenetproject.org/NewTransportLayer (not finished)
Current: Per-link AIMD, similar to TCP, only applies to data blocks. Parameters are probably too slow or too fast.
freenet/io/comm/PacketThrottle etc
- High-level load limiting. Also in urgent need of a redesign.
Current:
1) Load balancing: Backoff (exponential randomised backoff a la ethernet, triggered when a request times out or we get a RejectedOverload { local = true } [ when it is passed on we reset this to false ]).
Objective of backoff is to prevent slow nodes from pulling down the entire network via load limiting.
2) Load limiting: Client nodes have a global AIMD window, and a per-request-type (CHK|SSK req|ins) RTT. This was performing really badly (far less traffic being sent than should be), and we were working on a completely new algorithm, and the metaphor of "TCP over ethernet" is IMHO broken anyway, so around xmas we decided to divide the interval from the AIMD by the number of connections (this is somewhat alchemical although maybe it can be defended on the grounds that we have multiple links).
- Pre-emptive rejection: Nodes decide how many requests they can handle and reject the rest. This then interacts with load balancing and load limiting. Perhaps not very well. :|
This did increase traffic significantly, but it looks like it may just be routing load rather than routing requests - at least sometimes. The underlying problem may well be an issue with routing, which *might* be caused by the (apparent and not really verified) location clustering issue. In any case it *may* be caused by a degenerate topology resulting from the lack of opennet - but IMHO we should investigate further first. Another big issue that needs further work is simply local performance - if nodes are constantly running out of memory, running constant garbage collections for ages, and then restarting, this could easily mess up the network as a whole. Yet another possibility is that an interaction between the above and PreemptiveRejection breaks something. :|
See also: LoadBalancing
