SEARCH - Better Slow Start for TCP and QUIC

SEARCH is an enhancement to TCP and QUIC to exit the slow start phase after the congestion point is reached but before inducing unnecessary packet loss.

Overview

The Transmission Control Protocol's (TCP) slow start is designed to ramp up to the network congestion point quickly, doubling the congestion window each round-trip time until the congestion point is reached, whereupon TCP exits the slow start phase. Unfortunately, the default Linux TCP slow start implementation - TCP Cubic with HyStart - can cause premature exit from slow start, but without HyStart, TCP exits too late, causing unnecessary packet loss.

To improve TCP performance during slow start, we developed the Slow start Exit At Right CHokepoint (SEARCH) algorithm where the congestion point is determined based on bytes delivered compared to the expected bytes delivered, smoothed to account for link latency variation and normalized to accommodate link capacities.

Extensive evaluation of SEARCH over 4G LTE, low earth orbit (LEO), geosynchronous (GEO) satellite and Wi-Fi links shows SEARCH reliably exits from slow after the congestion point is reached but before inducing packet loss, increasing link utilization compared to TCP HyStart on and decreasing packet loss compared to TCP HyStart off.

Versions

Versions of the SEARCH Algorithm:

SEARCH 1.0 [5]

• uses sent and delivered bytes
• bin values based on delta from previous

SEARCH 2.0 [1, 2, 3, 4]

• uses only delivered bytes
• bin values based on delta from previous

SEARCH 3.0

• uses only delivered bytes
• bin values based on cumulative delivered bytes
• reduces bits in bin array with scale factor

Search options

• do not use interpolation if previous window between bins
• upon exit, lower cwnd to value 2 RTTs prior
• adjust the window size if there are insufficient bins

Documentation

[1] Jae Chung, Maryam Ataei Kachooei, Feng Li, and Mark Claypool. "SEARCH - a New Slow Start Algorithm for TCP and QUIC", IETF Internet-Draft draft-chung-ccwg-search-00, July 2024. https://datatracker.ietf.org/doc/draft-chung-ccwg-search/ (SEARCH 2.0) (slides: 2024-jul-24 2024-nov-05)

Code

• Linux Kernel Module Implementations (SEARCH 2.0)

  • 5.13.x series kernel: https://github.com/Project-Faster/tcp_ss_search.git (main branch)

  • 6.10rc2 based: https://github.com/Project-Faster/tcp_ss_search/tree/net-next-6.10rc2 (net-next-6.10rc2 branch)

• QUIC implementation for H2O/Quicly (SEARCH 2.0)

  • https://github.com/Project-Faster/quicly/tree/generic-slowstart (generic-slowstart branch)

Publications

[2] Amber Cronin, Maryam Ataei Kachooei, Jae Chung, Feng Li, Benjamin Peters, and Mark Claypool. "Improving QUIC Slow Start Behavior in Wireless Networks with SEARCH", In Proceedings of the IEEE International Symposium on Local and Metropolitan Area Networks (LANMAN), Boston, Massachusetts, USA, July 2024. https://web.cs.wpi.edu/~claypool/papers/quic-search-lanman-24/

[3] Maryam Ataei Kachooei, Joshua Chung, Amber Cronin, Benjamin Peters, Feng Li, Jae Won Chung, and Mark Claypool. "Implementation of the SEARCH Slow Start Algorithm in the Linux Kernel", In Proceedings of the 0x18 NetDev Conference, Santa Clara, California, USA, July 2024. http://www.cs.wpi.edu/~claypool/papers/search-netdev-24/

[4] Maryam Ataei Kachooei, Jae Chung, Feng Li, Benjamin Peters, Josh Chung, and Mark Claypool. "Improving TCP Slow Start Performance in Wireless Networks with SEARCH", In Proceedings of the IEEE World of Wireless, Mobile and Multimedia Networks (WoWMoM), Perth, Australia, June 2024. https://web.cs.wpi.edu/~claypool/papers/search-wowmom-24/

[5] Maryam Ataei Kachooei, Jae Chung, Feng Li, Benjamin Peters, and Mark Claypool. "SEARCH: Robust TCP Slow Start Performance over Satellite Networks", In Proceedings of the 48th IEEE Conference on Local Computer Networks (LCN), Daytona Beach, Florida, USA, October 1-5, 2023. https://web.cs.wpi.edu/~claypool/papers/search-lcn-23/