“Congestion Control for High Bandwidth-Delay Product Networks”

Most of the papers we’ve read on improving congestion behavior have an “incremental” flavor: they begin with traditional TCP and router behavior, and then suggest a conservative change that addresses some particular problem (e.g. slow start, better RTO estimation, fast retransmit, fair queueing, etc.). In contrast, this paper takes a “clean slate” approach:

Our initial objective is to step back and rethink Internet congestion control without caring about backward compatibility or deployment. If we were to build a new congestion control architecture from scratch, what might it look like?

Efficiency and fairness

In TCP, efficiency and fairness are coupled, because TCP uses a single procedure (“additive increase, multiplicative decrease“) to try to achieve both goals. The paper argues that these goals should really be treated separately: efficiency describes how close the link’s aggregate throughput approaches the link capacity, whereas fairness concerns how the current link throughput is distributed among the flows passing through a link.

Therefore, XCP separates these two goals: an efficiency controller is responsible for deciding whether to increase or decrease the link’s aggregate throughput, and a fairness controller is tasked with translating that aggregate feedback into per-flow feedback in order to achieve or maintain fairness. Separating these two components makes it easier to analyze their behavior (e.g. the efficiency controller doesn’t need to account for the number of flows), and allows new component designs to be considered in isolation.

The paper proposes using a multiplicative-increase, multiplicative-decrease (MIMD) for the efficiency controller, and a traditional additive-increase, multiplicative decrease (AIMD) scheme for the fairness controller. The paper argues that using MIMD for efficiency is important, because the AIMD policy traditionally used by TCP takes a long time to reach full capacity on links with a high bandwidth-delay product.

Explicit congestion signals

XCP moves away from packet drops as an implicit signal of network conditions, for a few pretty convincing reasons:

  • Congestion is not the only source of loss, so clients cannot distinguish between losses due to errors and losses due to congestion.
  • Detecting packet loss requires waiting for the RTO timeout, duplicate ACKs, or similar — the extra delay incurred makes clients respond more slowly to congestion signals, which makes the network more unstable. This also means clients must be more conservative when probing for network capacity, because the penalty for “overshooting” is more severe.
  • Packet loss is a binary signal; an explicit congestion notification can carry more information about the state of the network.

That makes a lot of sense, but it seems quite obvious and not really novel: ECN for IP has been around for a long time, and DECNet did something very similar years before this paper was written. I would guess the slow deployment of ECN is mostly related to pragmatism (e.g. support for ECN in IP stacks and routers), which developing a completely new transport protocol would only exacerbate.

Implementation

In XCP, senders attach a “congestion header” to each outgoing packet. This contains the sender’s current congestion window size, RTT estimate, and the sender’s desired window size increase (“H_feedback”). H_feedback is modified by XCP routers, and the updated value is returned in the ACK for a sent packet. The feedback value instructs senders to either increase or decrease their congestion windows.

In an XCP router, the efficiency controller first tries to adjust the aggregate link throughput to approach full utilization. The output of the efficiency controller is then fed to the fairness controller, which translates the global increase/decrease signal into feedback for individual senders, in such a way that fairness is increased or maintained.

Comments

The feasibility of separating fairness and efficiency hinges on whether these two goals really are independent: in practice, can the efficiency controller be replaced without any consideration of the fairness controller, and vice versa? I was initially skeptical that such a clean separation would be possible, but I think the paper’s scheme is pretty compelling.

Part of the paper’s motivation is the idea that networks with high bandwidth-delay will become increasingly common in the future. If we ignore special-cases like satellite links, then high-bandwidth networks are a certainty, but is it true that latency improvements won’t match bandwidth? I suppose latency is fundamentally limited by the speed of light in a way that bandwidth is not. “Latency lags bandwidth” is an interesting paper from Dave Patterson that examines this trend in general, and argues that latency will continue to lag bandwidth in the future.

Given the enormous administrative cost of deploying a new transport protocol, one wonders if the goals identified by this paper can’t be reached more easily by incremental changes to TCP, rather than a clean-slate redesign. XCP just doesn’t seem fundamentally different enough to warrant throwing out TCP.

Advertisements

1 Comment

Filed under Paper Summaries

One response to ““Congestion Control for High Bandwidth-Delay Product Networks”

  1. Nice review and comments Neil.

    I also found the separation of EC and FC quite interesting. It looks like that older algorithms could have done something similar as well but it was not particularly useful for them since they would have ended up with heavy per flow processing if their goal was fairness anyway. The nice thing about XCP seems to be that because of special XCP sender calculating certain parameters, FC needs to do very little processing per flow…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s