March 8, 2011

Grenville Armitage has provided a summary of the completed TCP Congestion Control Algorithms project:

Background

TCP is a crucial part of any modern operating system. FreeBSD’s standard “NewReno” congestion control (CC) is not able to fully utilize the high capacity links available today. A range of newer CC algorithms have emerged (and continue to emerge) from the networking research community over the past 15+ years. These include traditional loss-based algorithms (where packet losses indicate network congestion) and delay-based algorithms (where changes in Round Trip Time, RTT, are used to infer network congestion).

However, to date FreeBSD’s TCP stack has not had an easy-to-use mechanism for introducing new CC algorithms. In recent years the Centre for Advanced Internet Architectures (CAIA) at Swinburne University of Technology has (with the support of the Cisco University Research Program Fund at Community Foundation Silicon Valley) been developing a range of extensions to the FreeBSD TCP stack. These included a modular framework for adding new CC algorithms and new modular implementations of the existing NewReno algorithm, four other algorithms from the literature (H-TCP, CUBIC, Vegas and HD) and a novel algorithm developed at CAIA (CHD). In mid-2010 the FreeBSD Foundation funded CAIA to complete, tidy up and commit a number of these key enhancements to the FreeBSD TCP stack.

Delivered

Our project, “Five New TCP Congestion Control Algorithms for FreeBSD”, has delivered the following enhancements to FreeBSD’s TCP stack:

  • Modular congestion control framework.
  • Khelp (Kernel Helper) and Hhook (Helper Hook) frameworks.
  • Basic Khelp/Hhook (Kernel help/hook) integration with the TCP stack.
  • ERTT (Enhanced Round Trip Time) Khelp module for delay-based TCP algorithms.
  • Modularised implementations of NewReno, CUBIC and HTCP loss-based TCP CC algorithms.
  • Modularised implementations of Vegas, “HD” and “CHD” delay-based TCP CC algorithms.
  • Technical report comparing the computational overhead associated with TCP before and after integrating the new frameworks and modularised NewReno algorithm

Benefits

Each congestion control algorithm is implemented as a loadable kernel module. Algorithms can be selected to suit the application/network characteristics and requirements of the host’s installation. The modular CC framework also makes it much easier for developers to implement new algorithms, allowing FreeBSD’s TCP to be at the forefront of advancements in this area, while still maintaining the stability of its network stack.

CUBIC and HTCP are variants of TCP that provide significant performance improvements (relative to NewReno) over high bandwidth, high latency paths. Vegas, HD, and CHD utilise RTT fluctuations to provide a more timely indication of network congestion — by not forcing network queues to overflow, delay-based CC algorithms can help to keep queuing delays low along a network path. CHD is also tolerant of packet losses that are unrelated to congestion (such as can occur over wireless links).

In addition, the Khelp/Hhook frameworks provide useful kernel infrastructure which are not specific to the TCP stack and we anticipate they will be used elsewhere in the kernel in the future to provide other unrelated enhancements to FreeBSD.

Participants

Code development, testing, and documentation: David Hayes and Lawrence Stewart

Editorial review of code and documentation: Rui Paulo and Bjoern Zeeb

Project supervision: Grenville Armitage

Project URL: http://caia.swin.edu.au/freebsd/5cc/