[xcp] Why use positive feedback and negative feedback at the same time?

[Ted Faber]

On Tue, Nov 22, 2005 at 05:43:41PM -0800, Leon Martin wrote:
> Hi all,
> 
> It looks to me that the two feedbacks are used
> simultaneously for a given packet at a given time. In
> other words, both the positive feedback and the
> negative feedback can be non-zero at the same time.
> This is clear in Lines 13 and 14 in 4.2.2. of the
> following document:
> 
> http://www.isi.edu/isi-xcp/docs/draft-falk-xcp-spec-01.html
> 
> What is the rationale behind this?

The two feedback pools make the shuffling algorithm used for fairness
work.  Dina's (and Mark's and Charlie's, but I think of it as Dina's)
sigcomm paper explains how the positive and negative feedback is
allocated - and they're each done differently.  All hosts get the smae
amount of positive feedback per control interval (linear increase), but
the amount of negative feedback depends on the current sending rate
(multiplicative decrease).  You have to keep track of how much of each
you've allocated to stay in the high utilization region.

I find it helpful to consider the case here there's one source that's
sending as close as possible to full utilization.  At this point the
total feedback (phi) is 0, but there's actually equal quantities of
positive and negative feedback allocated.  Over the control interval,
the single source will recieve all the positive and all the negative
feedback, and its long term rate will be the same - that of the full
outgoing link.  Keeping track of the negative feedback in this case
keeps the router from reducing the single source more than it was
increased, which would result in a net utilization decrease.  Because
the router doesn't remember per-flow state, it can't keep track of this
for each flow.

The question I had at that point is "why hand out any feedback at all in
this case?" When another source joins, it's going to need positive
feedback to speed up and negative feedback to slow the outher source
down.  Because there's no per-flow state at the routers with which to
detect a new flow, the routers are always handing out a bit of each to
nudge sources toward fairness.  Without per-flow state routers don't
know when to stop shuffling capacity like this, so they don't stop.

Does that make sense?


-- 
Ted Faber
http://www.isi.edu/~faber           PGP: http://www.isi.edu/~faber/pubkeys.asc
Unexpected attachment on this mail? See http://www.isi.edu/~faber/FAQ.html#SIG
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 187 bytes
Desc: not available
Url : http://mailman.isi.edu/pipermail/xcp/attachments/20051122/311f7f90/attachment.bin