Hi Colin,
Sorry for taking so long to respond - as you can see this email got a
bit out of hand. :-)
As you mentioned I'm working on congestion control and load balancing
this summer. Here's a quick overview of what I'll be doing.
First, the problems.
1. Congestion control - a node can send packets to a peer more quickly
than the link can deliver them, causing packet loss.
2. Load control - a node can send requests to a peer more quickly than
the peer can process and/or forward them.
3. Load balancing - a node can use more than its equal share of the
network's resources; flooding attacks are an extreme example.
4. Resource contribution - a node can use more resources than it
contributes to the network.
Second, the (possible) solutions.
1. Congestion control - retransmitting lost packets without reducing the
transmission rate would lead to congestion collapse, so we need to slow
down when the link is congested. However, sharp changes in the
transmission rate should be avoided because they could have knock-on
effects for other nodes. I'm going to use the omnet++ network simulator
to investigate an AIMD (additive increase, multiplicative decrease)
congestion control algorithm similar to the one used by TCP. The
increase and decrease parameters should be chosen to compete fairly with
TCP while giving a smoother transmission rate.
2. Load control - at the moment we wait for a peer to become overloaded
and start rejecting requests, then we back off for a while. I think we
can avoid rejecting requests in most circumstances by using an explicit
receiver window as in TCP (the receiver window is distinct from the
congestion window mentioned above, and doesn't use AIMD).
Each peer tells us how many more requests it's willing to accept based
on the rate at which it's currently able to process requests. The window
sizes specified by our peers tell us roughly how many requests we can
forward. We can take this into account when calculating our own window
sizes, thus propagating load information upstream before it becomes
necessary to reject requests.
3. Load balancing - this is a complicated problem, partly because it's
political as well as technical. I suggest tackling the problem in two
stages: first we define the ideal policy for allocating resources, and
then we look for mechanisms to implement that policy.
To get things started, here's the policy I think we should adopt:
* When there are enough resources to handle all requests, handle all
requests, no matter how unequal the load distribution
* When there are not enough resources to handle all requests, give each
peer an equal share of the resources
* Give local clients priority over peers
The last point is open to debate - it's supposed to reduce the incentive
for people to modify their nodes in order to get better performance. An
alternative would be to lump all local clients together and treat them
as a single peer, but then the amount of resources given to local
clients would depend on the number of peers, which seems wrong.
Here's a mechanism that implements the policy above:
* Keep a token bucket for each peer
* Before handling a request from a peer, remove a token from its bucket
* If the bucket is empty, reject the request
* After processing a request from a peer, add a token to the bucket of a
random peer
* Tokens are created at the same rate requests are processed (see
load control above)
* All peers get an equal number of tokens
* If the chosen bucket is full, add the token to the emptiest
bucket instead (excess resources are distributed to whoever needs them)
* After adding a token to a bucket, inform the peer of the number of
tokens in its bucket (this is the receiver window size - see load
control above)
I'm open to suggestions for other policies and mechanisms that implement
them, but without wishing to stifle debate, I'm not particularly
interested in suggestions for mechanisms that don't implement
well-defined and widely agreed policies. The simulator code will be in
SVN if anyone want to simulate their own mechanism and see what policy
it implements. ;-)
The mechanism above leaves one thorny problem unanswered: if a request
can't be forwarded to the best peer because of congestion control or
load control, should we send it to the next-best peer instead, or should
we reject it? Both solutions have the potential to waste bandwidth;
routing to the next-best peer might solve the problem of slow nodes
occupying large portions of the key space. Hopefully simulations will
settle this question.
4. Resource contribution - it might be a good idea to give users an
incentive to contribute resources to the network. A few quick points:
* Free riding might not be such an urgent problem in friend-to-friend
networks as it is in open networks
* People might be reluctant to short-change their friends
* We can probably achieve a lot through peer pressure (ouch)
* Maybe put a few statistics on fproxy's darknet page
* Percentage of time each peer is online
* Number of requests sent/received
* _Not_ number of responses sent/received (see below)
* On the other hand, resource contribution is also a security issue - an
attacker who can use resources without contributing might be able to DoS
the network
* Incentive mechanisms can go wrong in a couple of ways:
* Reward apparent good behaviour without hard evidence
* Creates an incentive to lie
* Honest nodes are punished for being honest
* Reward the subset of good behaviour that can be verified
* Creates an incentive to prioritise verifiable behaviours
With regard to the last point, I'd like to investigate the effect of
prioritising requests (which have verifiable responses) over inserts
(which don't). This will tell us whether an incentive mechanism based on
the number of requests each peer answers could harm the network. But
this is a late addition to the SoC work, and the other jobs (congestion
control, load control, load balancing) will take priority.
Anyway, I hope this gives you a better idea of what I'll be working on
this summer. My current task is to implement the freenet protocol
(including backoff, swapping and routing) in a discrete event-based
simulator, with realistic values for node bandwidth, link latency, etc.
I also need a realistic load model, which will probably involve digging
through a lot of frost logs. :-) Once I'm happy with the simulated
network, I'll use it as a testbed to evaluate the new mechanisms.
Cheers,
Michael
_______________________________________________
Devl mailing list
[email protected]
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
