[Iccrg] Re: Appropriate rate given corruption

[Lachlan Andrew]

Greetings Michael,

On 26/08/07, Michael Welzl <michael.welzl at uibk.ac.at> wrote:
> On Sun, 2007-08-26 at 16:16 -0700, Lachlan Andrew wrote:
> > Do you agree that
>
> > 2. On a path with multiple bottlenecks, with loss rates  p_i,  the
> > total loss rate is slightly    less   than the sum of the p_i.   That
> > is,  p = 1-product(1-p_i) < (sum p_i)
>
> No.
>
> I don't understand why the total loss rate of
> the path would be slightly less than the sum of the p_i
> and not precisely that sum.

*grin*  Last thread, I made the approximation that  p = sum p_i, and
you correctly pointed out that, strictly,
    p = 1 - product(1-p_i)
because the probability a packet gets through is the probability it
gets through on the first link *and* the second *and* the third, ...

If you're happy with the approximation  p = sum p_i,  we can go with
that and it will (greatly) simplify my later arguments.

However, if you want to more precise and go with  p = 1 -
product(1-p_i)  then we'll need to use the fact that
    1 - product(1-p_i)  <=  sum  p_i
This follows immediately by induction.  We don't need the inequality
to be strict.

> The way I think about it, there is only one
> bottleneck along a path per definition (so the p_i's will
> all be close to zero except for one of them, which
> represents the bottleneck).

OK.  In the optimization flow control literature, the term
"bottleneck" is used to mean any link which has non-zero p_i.  That
means that a link which is a bottleneck for *any* flow using that link
will be a "bottleneck" for all flows using that link.

Do you agree that,
   If one flow loses packets at a link due to congestion (non-zero p_i)
   then that congestion will cause all flows to lose some packets on
   that link eventually (not necessarily all in the same "congestion event")?
That is the basis behind AIMD giving fairness.

It isn't important for my arguments how *common* it is in the real
internet for a flow to have multiple links with non-zero  p_i; just
how TCP would respond if it did happen.

If you like, we can just try to agree on the weaker statement:
2a. The total loss rate is   not greater   than the sum of the p_i.


> > 3. As a result, TCP gives slightly  higher  rate to multi-hop flows
> > than a hypothetical scheme which gave a rate  K/sqrt(sum p_i) <=
> > K/sqrt(p)
>
> No because this is based on 2, which I disagree with.

Again, we can try for a slightly weaker statement, based on 2a:
3a. TCP gives   no smaller   rate to multi-hop flows
      than would a hypothetical scheme which gave a rate
      K/sqrt(sum p_i) <= K/sqrt(p)

If you are happy with the approximation that  p = sum p_i  then  3a
follows immediately.

Cheers,
Lachlan

-- 
Lachlan Andrew  Dept of Computer Science, Caltech
1200 E California Blvd, Mail Code 256-80, Pasadena CA 91125, USA
Phone: +1 (626) 395-8820    Fax: +1 (626) 568-3603