Congestion Control

Timeout Prevention by Pre-emptive Rejection

LoadBalancing is a critical component described elsewhere. All we need to know here is that it is necessary to have as few requests time out as possible, because not only do timeouts make requests suck, even worse they can't usually be traced to a specific peer. So what we want is to reject requests pre-emptively when we are overloaded. We do that by two main mechanisms:

1. Round-trip time.
We record the average round-trip time per peer. This is the time it takes for a packet to be acknowledged. Note that we don't send an explicit acknowledgement, unless we are sending a packet anyway, for 200ms after receiving it, so we shouldn't expect the round trip time to be much below this.

If the geometric mean of the round-trip times of all connected peers is less than 500ms, we accept all requests. If it is over 1000ms, we accept no requests. If it is between the two then we accept requests randomly proportional to the round-trip time.

2. Bandwidth limiter delay.
Data-carrying packets are subject to bandwidth limiting. We record the average time between when we wanted to send a data packet, and when it was actually sent.

If this is less than 1000ms, we accept all requests. If it is more than 2000ms, we accept no requests (actually we accept one every 10 seconds anyway just to ensure that we don't get "stuck" with too high an old average). If it's in between we accept some requests, as above.

Data Transfers

Additionally, data transfers (32kB blocks divided into 1kB packets) are limited using the same AIMD algorithm described in LoadBalancing.