[e2e] Why do we need congestion control?

Srinivasan Keshav keshav at uwaterloo.ca
Wed Mar 6 05:57:42 PST 2013

To make sure that we're all on the same page, I assume that by a rateless code you mean a code where a source that wants to send S bytes actually sends a potentially infinite number of bytes, but the receiver can decode the source as long as it successfully receives aS bytes, where a > 1 [1].  Rateless erasure codes allow a receiver to recover from packet losses due to transient congestion because it can decode the transmitted information despite losses. Thus, these codes provide an alternative to buffers, allowing us to trade (buffer) space for (link) time.

When source rates are not reduced in response to overload of a shared resource, then congestion is persistent and the packet loss rate is high (and equal to the difference between the sum of the source rates and the resource capacity). In this situation, I think that fountain codes are not a sufficient solution, because in order to receive aS bytes, a source may need to send a potentially unbounded number of bytes. Moreover, this excess load can cause overloads elsewhere in the network. Thus, the network is not carrying retransmissions, as you correctly observe, but it is still not a healthy situation.

To fix ideas, consider a link whose carrying capacity is 1 unit, and whose average load over some period of time is 4 units. Then, 3 units of packets must be dropped at the link. Assuming that losses are shared perfectly evenly, a source that wants to send S bytes through this link would need to send (3+a)S bytes; the receiver would then still receive aS bytes and decode the source. This appears to be a reasonable solution, in that the receiver is able to decode the source despite overload, but note that every link prior to the congested link on the path from the source to the receiver is carrying 3S worth of traffic that is destined to be dropped. If such a link is on the path from some other source to some other destination, this can cause other paths to also be overloaded, raising the overall load on the network. Moreover, if the response of a source to overload is to send *more* data, to allow the receiver to decode traffic, this quickly leads to widespread collapse.

Incidentally, Bob Braden's remarks on legislating TCP-friendliness become very clear in this context. If source A were to drop its source rate in response to congestion, but source B uses a fountain code and does not reduce its source rate, then source B's packets will dominate the shared resource, shutting out source A. Thus, it is individually rational for each source to use a fountain code, but the overall system suffers if each source acts in its own selfish self interest. This is well understood. Solutions range from careful sharing of the resource that allocates packet losses in proportion to source rates (for example by means of fair queueing) to legislating the use of TCP-friendly sources. From time to time researchers discover that 'selfish' transport protocols do better than TCP, the recent report from Fujtsu being one more in a long line of offenders. We can only hope that these efforts are not widely successful; otherwise costly in-network control mechanisms will need to be invoked.


[1] http://en.wikipedia.org/wiki/Fountain_code

On 2013-03-06, at 7:29 AM, shun cai wrote:

As discussed in chapter 1 of your PhD thesis,  when network is congested, retransmission dominate the traffic and effective throughput diminshes rapidly, leading to a deteriorating situation. This can be illustrated in the well known figure with two turning points Knee and Cliff.

     I wonder, however, does the situation the same if rateless erasure code (say fountain codes) is used?  As with erasure code, no ACK and retransmission is needed except when the whole file is completed. So even heavy loaded, the network is still busy with effective data packet, right?  Although queueing delay will increase, I believe that  the network throughput  will not  suffer the plunge as un-coded network.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.postel.org/pipermail/end2end-interest/attachments/20130306/000305a7/attachment.html

More information about the end2end-interest mailing list