[Iccrg] Re: Appropriate rate given corruption

[Lachlan Andrew]

Greetings Michael,

Good.  It seems we're coming to a common understanding.  I'll try to
be more explicit about the assumptions...

Next I claim that:

5. If we use a "tcp friendly" flow control without unnecessary
saw-tooth oscillation (like TFRC) then  p_i = 0  if the link isn't
overloaded (sum of rates < capacity), and  p_i  increases as the
amount of overload increases.

6. Define  U(x) = -(K^2)/x  as a "utility function".    Then  the
response function of TCP is
    D(p) = K/sqrt(p) =  (U')^{-1}(x),
namely the inverse of the derivative of the utility.  (As an aside, if
 x  is the receive rate, this is proportional to how long it takes to
download a file of a given size, and negated since we get more benefit
from shorter download times.)

Combining 1, 2, 5 and 6 gives

7. TFRC solves Kelly's "utility maximization" problem, with the above
utility function, if "utility" is assumed to be derived from the
send   rate, rather than the    receive    rate.

For reference, that utility maximization problem is
    max sum_i U(x_i)    over all rates  x_i  for each flow  i
subject to
    R x <= c
where
   x=(x_i)  is a vector of rates (one per flow)
   c=(c_l) is a vector of capacities (one per link)
   R=(r_{il})  is a "routing matrix", where  r_{il}  is the amount of
traffic flowing over link  l  for each unit of traffic in flow  i.
Without any loss,  r_{il} = 1 if the link is on the path, or 0
otherwise.  If there is loss upstream, then  r_{il}  will be slightly
less than 1 if the link is on the path, but for a givne amount of
loss, there will still be a well-defined "r_{il}" value.

Unless you're familiar with the Kelly/Low framework, it isn't
"obvious" that  7.  is true.  However, checking  Low and Lapsely '99
shows that  6.  is the basic relation that has to hold.

Do you accept all (any :)  of these claims?

Cheers,
Lachlan


For reference, the things we agreed on were:

1. TCP responds with a rate approximately   K/sqrt(p)  where  K  is a
constant dependent on such things as RTT and packet size,  and  p  is
the total loss probability

2. On a path with multiple bottlenecks, with loss rates  p_i,  the
total loss rate is approximately (and not more than) the sum of the p_i.

3. As a result, TCP gives at least the same rate to multi-hop flows
than a hypothetical scheme which gave a rate  K/sqrt(sum p_i) <=
K/sqrt(p)

4. Consider a network only one link  l_0 which
corrupts packets, which transmits fraction  r  of the packets it
receives.  Then each received packet on a flow traversing  l_0
creates as much additional congestion as a flow in a modified network
such that
  (a) there is no loss
  (b) each link  l_i  upstream of  l_0  is replaced by "1/r" links,
each with the same amount of congestion as  l_i  had in the original
network.


-- 
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