On Thu, Apr 13, 2006 at 05:39:58PM +0100, Michael Rogers wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Matthew Toseland wrote:
> > I mean we won't get enough information to have a useful and accurate
> > rate for each pair.
>
> I see your point, but hopefully it won't be necessary to have a very
> accurate rate for pairs that don't communicate much. The rate only needs
> to adapt quickly if there's a large amount of traffic, doesn't it?
I suppose so...
>
> > This is not a serious problem, because we are not really dealing with a
> > point to point routed network here. The same proportion of requests from E
> > and from A will reach F. If D is overloaded, then everyone needs to slow
> > down, because *everyone* is talking to D. If they are further away they
> > probably talk to D less and so need to slow down less.
>
> But that doesn't solve the problem of pushing the load back to A. If A
> causes D to become overloaded and everyone else who's using D slows
> down, A has no incentive to slow down. By pushing the load back along
> the path of the request that triggered the overload, you can quench
> sources that trigger more than their fair share of overloads.
Are you saying that this won't push the load back along the path? I
believe above we are talking about this:
E F
| |
A---B---C---D
D is overloaded. A is sending far more requests than anyone else, many
of which end up at D.
C reduces its send rate to D.
Therefore, F and B reduce their send rates to C.
Therefore, E and A reduce their send rates to B.
The problem is that if we use a naive understanding of queue fairness,
C will reject the same proportion of both B's and F's requests. F's
requests are very few, so they should be given priority; the node
producing more requests should have the greater proportion of its
requests rejected, then the load will propagate back properly to its
source. We might also want to factor in the node's utility to us.
Is there a non-alchemical way to define such a queueing algorithm?
Actually, this IS easy. If we use simple round-robin queueing (as
opposed to some form of simulated queueing), we get exactly the desired
effect: We take a request from B, then a request from F, then a request
from B, then ... Obviously since F isn't producing many requests,
generally its requests will be accepted, and many of B's requests will
be rejected.
Now, how to do that with simulated queueing (which is necessary IMHO to
minimize latency) ? We want something that behaves exactly as above, but
which does not involve actually delaying the requests.
There must be some way to do this...
Target rate t
Rate from B b
Rate from F f
We know:
b + f > t (otherwise we don't need to drop any)
If b >> f, then we can simply allow through all F's requests and reject
(b+f-t) requests from B.
But in general:
Lets say b = 100, f = 3, t = 50.
