-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Matthew Toseland wrote: > Is there a non-alchemical way to define such a queueing algorithm?
Yup, see my message from the following morning about token buckets. I guess from the flood of messages that you've just dealt with a week's worth of mail. :-) > Target rate t > Rate from B b > Rate from F f > > We know: > b + f > t (otherwise we don't need to drop any) Exactly - when capacity exceeds traffic, give everyone as much as they ask for; enforcing fairness when there's excess bandwidth would be cutting off our nose to spite our face. > If b >> f, then we can simply allow through all F's requests and reject > (b+f-t) requests from B. This is what a token bucket achieves. Each neighbour's bucket is filled with tokens at the same rate. (The bucket is actually just implemented as a counter, where the 'size' of the bucket is the upper limit of the counter.) Each token allows the neighbour to send a certain number of bytes. When a neighbour's bucket is empty, its requests are rejected. *But* to avoid wasting bandwidth by enforcing fairness when there's excess capacity, tokens from overflowing buckets spill over into the emptiest bucket. So the bandwidth is distributed according to demand when there's enough to go round, and fairly when there isn't. There's no queueing delay, and the buckets allow for bursty traffic (larger buckets allow larger bursts, enforcing fairness over a longer timescale). > And we don't need to track stats per-path. Agreed. However, there should be an AIMD rate limit on each link, which again can be implemented with a token bucket to allow bursts of traffic, giving two buckets per neighbour: one for incoming traffic (fairness) and one for outgoing traffic (rate control). Add sliding window flow control to the links and it should be possible to prevent overload rather than using ping time to detect it. I'm planning to do some proper work on this after the p2p2006 deadline on the 1st of May... maybe Google will even pay me to work on it. ;-) Cheers, Michael -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.2.2 (GNU/Linux) iD8DBQFESUnsyua14OQlJ3sRAmbnAJ9vUJAI013vqRQdGuBAjmmOWBy5XwCg/ZTy UU+Q1qwc30gc76/+mkOx1Y4= =Fepy -----END PGP SIGNATURE----- _______________________________________________ Devl mailing list Devl@freenetproject.org http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
