-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
>> AIMD for congestion control,
>> token buckets for flow control and load balancing, and load propagated
>> back to the sender by (1) giving each peer a fair share of your
>> resources, (2) calculating how many requests you can accept and filling
>> the token buckets at appropriate rates, and (3) telling each peer how
>> many tokens are in its bucket, so it can send at an appropriate rate?
>
> I don't understand (3), that's straying into MRI territory... I thought
> we were going to simply let it work it out based on how many are
> rejected? This fits better with a minimal- or no- misrouting model...
Even if you're not going to route around overloaded nodes, you can save
some bandwidth by not sending a request if you know it's going to be
rejected. Also, knowing how many requests each of your peers is willing
to accept allows you to calculate how many requests /you/ can accept, so
information about load is propagated upstream without wasting any
bandwidth on rejected requests.
> (2) is determined by AIMD, yes?
Partly - the minimum of the AIMD congestion window and the receiver
window tells you how many requests you can forward on each link. You
also need to work out the approximate relationship between the number of
incoming requests and the number of outgoing requests - some incoming
requests will be answered locally, and some outgoing requests will be
generated locally. If you keep a running average requestsInOverOut then
you can calculate (2) as follows:
double totalOutgoing = 0.0;
for (int i = 0; i < peers.length; i++)
totalOutgoing += Math.min (peers[i].cwindow, peers[i].rwindow);
totalIncoming = totalOutgoing / requestsInOverOut;
> You seemed to be leaving out a chunk... weren't we using two separate
> token buckets last time?
At one stage we were using a token bucket for each outgoing link, but
that function's now performed by the receiver window (which just tells
you the number of tokens in the bucket at the other end of the link,
removing the need for a duplicate bucket at your end).
I did forget the bandwidth limiter, though... I'll have a think about
how to incorporate it into the calculation above, so we can ask our
peers to slow down before we run into the bandwidth limiter and have to
reject requests.
> We'd need to drop the HTL by something like 5 to make that safe. I
> accept that temporary overload should be routed around, but generally
> misrouting is a REALLY REALLY BAD THING, because it *causes more load*.
OK, but rejecting requests that have already travelled several hops also
causes more load.
Here's how I look at it: having a slow peer on a dialup link is
somewhere between having a fast peer and having no peer at all.
Sometimes you can take advantage of the slow peer, but most of the time
you have to act as if it isn't there. If it wasn't there and you got a
request for its portion of the keyspace, would you reject the request?
No, you'd route to the best available peer.
Essentially all I'm saying is that "available" should mean "connected
and able to accept requests" rather than just "connected". Apart from
that I'm not suggesting any changes in routing: we still always route to
the best available peer.
Here's another way of looking at it: a friend with a dialup connection
wants to become your peer. Your friend's connection is only fast enough
to accept one in every ten requests: the rest will be rejected. With the
current behaviour, nine out of ten requests that fall into your friend's
portion of the keyspace will be rejected: from your point of view, the
slow peer will have created a hole in the keyspace. You're better off
saying no. On the other hand if you send one out of ten requests to the
slow peer and the other nine to the best available peer (ie whichever of
your current peers is closest to the key in question), the slow peer is
doing useful work by reducing the load on your other peers, and you're
better off saying yes.
> Our current algorithm propagates load back to the source.
Does it? I thought backoff was only triggered by local rejections,
meaning that only the neighbour of the overloaded node changes its
behaviour. The only way for this to propagate load back to the source
would be for every node along the path to become overloaded. Or are you
talking about well-behaved senders slowing down when their requests get
rejected?
Cheers,
Michael
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)
iD8DBQFEiAilyua14OQlJ3sRAno6AJsFmvmM2xEMNQCXR4ypXaWI97/9pQCePhQ8
HbefJcnBn2zY2LXZAukQWCk=
=z4fa
-----END PGP SIGNATURE-----
