TCP Laminar

What is Laminar?

Laminar is a new framework for TCP congestion control that separates transmission scheduling, which determines precisely when data is sent, from pure Congestion Control, which determines the total amount of data sent during each RTT.

The default algorithm for transmission scheduling is a strict implementation of Van Jacobson's packet conservation principle [Jacobson88]. Data arriving at the receiver cause ACKs which in turn cause the sender to transmit an equivalent quantity of data back into the network. The primary state variable is implicit in the quantity of data and ACKs circulating in the network. This state is observed through an improved tcp_packets_in_flight() estimator (aka total_pipe). The total_pipe is based on "pipe" as described in RFC 3517 but also includes the quantity of data reported by the current ACK and pending transmissions that have passed congestion control but are waiting for other events such as TSO.

A new variable, CCwin, is the primary congestion control state variable. The congestion control algorithms adjust CCwin to regulate the overall congestion level along the path. Although CCwin resembles cwnd, cwnd is overloaded and used by multiple algorithms (such as burst suppression) with different and sometimes conflicting goals.

Any time total_pipe is different from CCwin the transmission scheduling algorithm slightly adjusts the number of segments sent in response to each ACK. Slow start and Proportional Rate Reduction [PRR] (a replacement for rate-halving) are both embedded in the transmission scheduling algorithm.

The primary advantage of the Laminar framework is that by partitioning congestion control and transmission scheduling into separate subsystems, each is subject to far simpler design constraints, making it easier to develop many new algorithms that are not feasible with the previous organization of the code.

The Laminar framework changes the underlying design philosophy of TCP congestion control and potentially has broad implications, beyond the patch itself. This patch is intended to permit people to experiment with the code, comment and help discover any corner cases that might have been overlooked. Furthermore the patch is incomplete in the sense that a number of algorithms are still missing, specifically: congestion control algorithms other than CUBIC and Reno; cwnd validation; destination metrics; etc. It would be really great if people could help refactoring some of these other algorithms.

The Laminar framework and its motivation are more thoroughly described in an Internet Draft, draft-mathis-tcpm-tcp-laminar.

Please send comments and suggestions to mattmathis@google.com.

This project is part of Google's efforts to Make the Web Faster through protocol improvements.

Implementation Notes

Laminar is primarily implemented in 3 functions (tcp_input.c):

Tcp_cong_avoid() and tcp_mult_decr() perform AIMD congestion control using the CCwin state variable. Except for undo, these two functions are the only places where CCwin changes. (Both functions invoke congestion module specific handlers).

Tcp_laminar_schedule() determines how much data to send in response to each ACK. It implements Van Jacobson packet conservation, adjusted up or down slightly to make tcp_packets_in_flight() converge to CCwin.

There are important changes to the tcp_packets_in_flight() estimator to make it invariant across most protocol events. Application stalls, the adjustments in tcp_laminar_schedule(), and actual packet losses change tcp_packets_in_flight(), as they must. ACK processing, TSO and most other events do not. Note that when there are losses, the actual number of packets in flight changes immediately, but is not reflected in tcp_packets_in_flight() estimator until the retransmission machinery marks them as lost and increments lost_out.

Get the patch

This patch is against Dave Miller's net-next, and applies cleanly to 3.5-rc2.
NB: Congestion control modules other that Reno and CUBIC have not been updated and will not compile. If your configuration builds other congestion control modules, such as vegas, scalable, highspeed, etc they must be disabled first.