[Iccrg] Re: Appropriate rate given corruption
lachlan.andrew at gmail.com
Mon Aug 27 18:59:57 BST 2007
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)
> 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
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
More information about the Iccrg