linux/net/ipv4/tcp_cdg.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * CAIA Delay-Gradient (CDG) congestion control
 *
 * This implementation is based on the paper:
 *   D.A. Hayes and G. Armitage. "Revisiting TCP congestion control using
 *   delay gradients." In IFIP Networking, pages 328-341. Springer, 2011.
 *
 * Scavenger traffic (Less-than-Best-Effort) should disable coexistence
 * heuristics using parameters use_shadow=0 and use_ineff=0.
 *
 * Parameters window, backoff_beta, and backoff_factor are crucial for
 * throughput and delay. Future work is needed to determine better defaults,
 * and to provide guidelines for use in different environments/contexts.
 *
 * Except for window, knobs are configured via /sys/module/tcp_cdg/parameters/.
 * Parameter window is only configurable when loading tcp_cdg as a module.
 *
 * Notable differences from paper/FreeBSD:
 *   o Using Hybrid Slow start and Proportional Rate Reduction.
 *   o Add toggle for shadow window mechanism. Suggested by David Hayes.
 *   o Add toggle for non-congestion loss tolerance.
 *   o Scaling parameter G is changed to a backoff factor;
 *     conversion is given by: backoff_factor = 1000/(G * window).
 *   o Limit shadow window to 2 * cwnd, or to cwnd when application limited.
 *   o More accurate e^-x.
 */
#include <linux/kernel.h>
#include <linux/random.h>
#include <linux/module.h>
#include <linux/sched/clock.h>

#include <net/tcp.h>

#define HYSTART_ACK_TRAIN …
#define HYSTART_DELAY …

static int window __read_mostly = …;
static unsigned int backoff_beta __read_mostly = …; /* sqrt 0.5 */
static unsigned int backoff_factor __read_mostly = …;
static unsigned int hystart_detect __read_mostly = …;
static unsigned int use_ineff __read_mostly = …;
static bool use_shadow __read_mostly = …;
static bool use_tolerance __read_mostly;

module_param(window, int, 0444);
MODULE_PARM_DESC(…) …;
module_param(backoff_beta, uint, 0644);
MODULE_PARM_DESC(…) …;
module_param(backoff_factor, uint, 0644);
MODULE_PARM_DESC(…) …;
module_param(hystart_detect, uint, 0644);
MODULE_PARM_DESC(…) …;
module_param(use_ineff, uint, 0644);
MODULE_PARM_DESC(…) …;
module_param(use_shadow, bool, 0644);
MODULE_PARM_DESC(…) …;
module_param(use_tolerance, bool, 0644);
MODULE_PARM_DESC(…) …;

struct cdg_minmax { … };

enum cdg_state { … };

struct cdg { … };

/**
 * nexp_u32 - negative base-e exponential
 * @ux: x in units of micro
 *
 * Returns exp(ux * -1e-6) * U32_MAX.
 */
static u32 __pure nexp_u32(u32 ux)
{ … }

/* Based on the HyStart algorithm (by Ha et al.) that is implemented in
 * tcp_cubic. Differences/experimental changes:
 *   o Using Hayes' delayed ACK filter.
 *   o Using a usec clock for the ACK train.
 *   o Reset ACK train when application limited.
 *   o Invoked at any cwnd (i.e. also when cwnd < 16).
 *   o Invoked only when cwnd < ssthresh (i.e. not when cwnd == ssthresh).
 */
static void tcp_cdg_hystart_update(struct sock *sk)
{ … }

static s32 tcp_cdg_grad(struct cdg *ca)
{ … }

static bool tcp_cdg_backoff(struct sock *sk, u32 grad)
{ … }

/* Not called in CWR or Recovery state. */
static void tcp_cdg_cong_avoid(struct sock *sk, u32 ack, u32 acked)
{ … }

static void tcp_cdg_acked(struct sock *sk, const struct ack_sample *sample)
{ … }

static u32 tcp_cdg_ssthresh(struct sock *sk)
{ … }

static void tcp_cdg_cwnd_event(struct sock *sk, const enum tcp_ca_event ev)
{ … }

static void tcp_cdg_init(struct sock *sk)
{ … }

static void tcp_cdg_release(struct sock *sk)
{ … }

static struct tcp_congestion_ops tcp_cdg __read_mostly = …;

static int __init tcp_cdg_register(void)
{ … }

static void __exit tcp_cdg_unregister(void)
{ … }

module_init(…) …;
module_exit(tcp_cdg_unregister);
MODULE_AUTHOR(…) …;
MODULE_LICENSE(…) …;
MODULE_DESCRIPTION(…) …;