[Iccrg] Re: Appropriate rate given corruption

[Shivkumar Kalyanaraman]

Lachlan, Michael,

When we designed LT-TCP, we viewed erasure loss
differently from congestion loss/ECN marks. An erasure loss essentially
reduces the capacity of the link. The process of adding FEC (whether at
the link layer to mask it or transport layer to add reliability) is a
"coding" function. So if the erasure rate of a channel with nominal bit
rate C is p, then the shannon capacity of that erasure channel is C(1-p).

Now think of a network with new links (indexed by j) where the link
capacities are replaced with Cj(1-pj). Kelly's theory can then be applied
to this revised network to define a notion of fairness. The special
case of TCP-friendliness would be the case when  all users
picked the same "TCP-friendly utility function" ...

However the TCP throughput formula could mix up matters.
By adding the aggregate loss rate (erasure + congestion) and using the TCP
formula leads to a significantly lower equilibrium rate for a flow on a
lossy channel -- since one would be mixing the effects of reliability &
congestion.

Fairness seems to be appropriate at the level of congestion control (i.e.
equilibrium rates relative to allowed utility functions). However, a
scheme that offers superior reliability due to better coding (eg: hybrid
ARQ/FEC) should not be considered unfair compared to a scheme that uses
all the same congestion detection/response mechanisms but uses a less
effective reliability strategy (eg: window ARQ/SACK etc).

We view this as a matter of disentangling the effects of congestion
control and reliability. TCP friendliness that includes the effect of
reliability would mean that TCP SACK would be unfriendly to TCP Reno
(just to make the point... granted that there are both congestion
control/reliability differences in these schemes).

best
-Shiv
===
Shivkumar Kalyanaraman
Professor, Dept of ECSE, Rensselaer Polytechnic Institute (RPI)
110, 8th Street, Room JEC 6003, Troy NY 12180-3590
Ph: 518 276 8979   Fax: 518 276 4403
WWW: http://www.ecse.rpi.edu/Homepages/shivkuma
Google: "Shiv RPI"


On Tue, 28 Aug 2007, Lachlan Andrew wrote:

> 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
>
> _______________________________________________
> Iccrg mailing list
> Iccrg at cs.ucl.ac.uk
> http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg
>