Congestion Control for High Bandwidth-Delay Product Networks

Summary
The title of this paper is a bit misleading. What this paper really does is propose a new protocol for congestion avoidance in the network, one that would replace TCP. The authors argue that TCP performs poorly in networks with a high bandwidth-delay product (hence the title), and argue that these types of networks are becoming more common in today's Internet.

The primary change that the eXplicit Control Protocol (XCP) makes to TCP is that it adds a congestion header that provides explicit notification of congestion to endpoints rather than relying on dropped packets to tacitly signal congestion like TCP does. This modification allows routers to be more clever about their policies, and interestingly allows routing with almost no dropped packets (in their simulations, which have all well-behaved receivers).

The protocol (at the endpoints) works roughly as follows:
Sender: set my current congestion window size and round trip time estimate in the header of each packet. ACKs to these packets will have a computed requested delta in my congestion window in there, adjust accordingly.
Receiver: Simply copy the delta that's been computed along the way from the sent packet into the ACK header.

Routers along the packet's path compute the delta. Each router can overwrite the header so the bottleneck should end up being the delta in the packet. Fairness and utilization deltas are computed separately allowing different policies to be used for each one. The authors test a multiplicative increase, multiplicative decrease for utilization with an additive increase, multiplicative decrease for fairness.

There are a number of simulations that show that XCP outperforms TCP in a variety of environments.

XCP does not deal with misbehaving senders any better than TCP, however, it is much easier to identify misbehaving senders with XCP. An edge router can send a delta ACK asking for a congestion window decrease. If the sender does not respond by decreasing to the new window, it is misbehaving and can be punished appropriately.

Thoughts
This was an interesting paper. Having to use dropped packets as a signal for congestion really limits the performance of TCP, especially in situations where the packet wasn't really dropped but was only assumed dropped, as can be the case in high bandwidth-delay product networks. This will also be true in things like wireless networks where dropped packets are not due to delay but due to a crummy link.

XCP seems to solve many of TCPs weaknesses quite well. There are a few concerns I have however.

Firstly, how to deal with a misbehaving router along the path of a packet. It seems this router could overwrite the congestion header and upset the whole algorithm. TCP will have problems with misbehaving routers as well, but XCP seems like it could suffer from more insidious problems here where, say, only one source has it's congestion headers bumped up, leading to unfairness.

Secondly, per flow state is still needed for identification of misbehaving receivers. This may be unavoidable, but it is still unfortunate. Moving this computation to edge routers could alleviate the problem somewhat, as will increasing raw power in routers.

Finally, adoption seems difficult here. Although the authors suggest a way to have XCP and TCP co-exist fairly, it still requires software upgrades in a huge number of points, and only one hop on the path not supporting XCP means the whole connection needs to fall back to TCP. This path seems difficult to go down, but perhaps as bandwidth-delay products keep rising the switch will become essential.