src/congestion_control/xqc_copa.c (417 lines of code) (raw):
/**
* @copyright Copyright (c) 2022, Alibaba Group Holding Limited
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <xquic/xquic.h>
#include "src/common/xqc_config.h"
#include "src/common/xqc_time.h"
#include "src/congestion_control/xqc_copa.h"
#include "src/transport/xqc_send_ctl.h"
#define XQC_COPA_MSS (XQC_MSS)
#define XQC_COPA_MIN_WIN (4 * XQC_COPA_MSS)
#define XQC_COPA_MAX_INIT_WIN (100 * XQC_COPA_MSS)
#define XQC_COPA_INIT_WIN (32 * XQC_COPA_MSS)
#define XQC_COPA_RTT_MIN_WINDOW (10000000) /* 10s */
#define XQC_COPA_RTT_MAX_WINDOW (4) /* 4 RTTs */
#define XQC_COPA_RTT_STA_WINDOW (0.5) /* 0.5 RTT */
/* mode switching threshold: 5 RTTs */
#define XQC_COPA_MS_THRESHOLD (5)
/* the default value recommended by Facebook */
#define XQC_COPA_DEFAULT_DELTA (0.05)
/* the upper bound of delta for the competitive mode */
#define XQC_COPA_DEFAULT_DELTA_MAX (0.5)
#define XQC_COPA_MAX_DELTA (1.0)
#define XQC_COPA_INF_U64 (~0ULL)
#define XQC_COPA_INIT_VELOCITY (1.0)
#define XQC_COPA_MAX_RATE (1.8E19)
#define XQC_COPA_USEC2SEC (1000000)
#define XQC_COPA_DEFAULT_DELTA_AI_UNIT (1.0)
#define XQC_COPA_LOG_STATE(comment_str, log_level) \
do { \
xqc_log(copa->ctl_ctx->ctl_conn->log, log_level, \
"|copa|"comment_str"|init_cwnd_bytes:%ui|cwnd_bytes:%ui|" \
"rtt_min:%ui|rtt_max:%ui|rtt_standing:%ui|delta:%.4f|" \
"velocity:%.4f|curr_dir:%d|prev_dir:%d|same_dir_cnt:%d|mode:%d|" \
"t_last_delay_min:%ui|slow_start:%d|pacing_rate:%ui|" \
"recovery_start_time:%ui|round_cnt:%ud|next_round_delivered:%ui|" \
"round_start:%d|delta_base:%.4f|delta_max:%.4f|" \
"last_round_cwnd_bytes:%ui|cwnd_adjustment_accumulated:%i|" \
"delta_ai_unit:%.4f|", \
copa->init_cwnd_bytes, copa->cwnd_bytes, \
xqc_win_filter_get(&copa->rtt_min), \
xqc_win_filter_get(&copa->rtt_max), \
xqc_win_filter_get(&copa->rtt_standing), \
copa->delta, copa->v, copa->curr_dir, copa->prev_dir, \
copa->same_dir_cnt, copa->mode, copa->t_last_delay_min, \
copa->in_slow_start, copa->pacing_rate, copa->recovery_start_time, \
copa->round_cnt, copa->next_round_delivered, \
copa->round_start, copa->delta_base, copa->delta_max, \
copa->last_round_cwnd_bytes, copa->cwnd_adjustment_accumulated, \
copa->delta_ai_unit); \
} while (0)
static void
xqc_copa_set_pacing_rate(xqc_copa_t *copa)
{
/* 2*cwnd / rtt_standing */
xqc_usec_t rtt_standing = xqc_win_filter_get(&copa->rtt_standing);
xqc_usec_t initial_rtt = copa->ctl_ctx->ctl_conn->conn_settings.initial_rtt;
if (rtt_standing == XQC_COPA_INF_U64) {
/* initialization */
rtt_standing = copa->ctl_ctx->ctl_srtt;
}
if (rtt_standing == 0) {
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_WARN,
"|copa|rtt_standing_error:%ui|", rtt_standing);
/* initialization */
rtt_standing = initial_rtt;
xqc_win_filter_reset(&copa->rtt_standing, 0, XQC_COPA_INF_U64);
}
copa->pacing_rate = ((copa->cwnd_bytes) * XQC_COPA_USEC2SEC) << 1;
copa->pacing_rate /= rtt_standing;
copa->pacing_rate = xqc_max(copa->pacing_rate, XQC_COPA_MSS);
}
static size_t
xqc_copa_size()
{
return sizeof(xqc_copa_t);
}
static void
xqc_copa_init(void *cong, xqc_send_ctl_t *ctl_ctx, xqc_cc_params_t cc_params)
{
xqc_copa_t *copa = (xqc_copa_t*)cong;
copa->init_cwnd_bytes = XQC_COPA_INIT_WIN;
copa->delta_base = XQC_COPA_DEFAULT_DELTA;
copa->delta_max = XQC_COPA_DEFAULT_DELTA_MAX;
copa->delta_ai_unit = XQC_COPA_DEFAULT_DELTA_AI_UNIT;
xqc_win_filter_reset(&copa->rtt_min, 0, XQC_COPA_INF_U64);
xqc_win_filter_reset(&copa->rtt_max, 0, 0);
xqc_win_filter_reset(&copa->rtt_standing, 0, XQC_COPA_INF_U64);
copa->v = XQC_COPA_INIT_VELOCITY;
copa->curr_dir = COPA_UNDEF; /* slow start */
copa->prev_dir = COPA_UNDEF;
copa->same_dir_cnt = 0;
copa->mode = COPA_DELAY_MODE;
copa->t_last_delay_min = 0;
copa->in_slow_start = XQC_TRUE;
copa->ctl_ctx = ctl_ctx;
if (cc_params.customize_on) {
copa->init_cwnd_bytes = xqc_clamp(cc_params.init_cwnd * XQC_COPA_MSS,
XQC_COPA_MIN_WIN,
XQC_COPA_MAX_INIT_WIN);
if (cc_params.copa_delta_base > 0) {
copa->delta_base = cc_params.copa_delta_base;
}
if (cc_params.copa_delta_max > 0) {
copa->delta_max = cc_params.copa_delta_max;
}
if (cc_params.copa_delta_ai_unit > 1.0) {
copa->delta_ai_unit = cc_params.copa_delta_ai_unit;
}
copa->delta_max = xqc_min(copa->delta_max, XQC_COPA_MAX_DELTA);
copa->delta_base = xqc_min(copa->delta_base, copa->delta_max);
}
copa->delta = copa->delta_base;
copa->cwnd_bytes = copa->init_cwnd_bytes;
copa->last_round_cwnd_bytes = 0;
xqc_copa_set_pacing_rate(copa);
copa->recovery_start_time = 0;
copa->next_round_delivered = 0;
copa->round_cnt = 0;
copa->round_start = XQC_FALSE;
copa->cwnd_adjustment_accumulated = 0;
XQC_COPA_LOG_STATE("initialization", XQC_LOG_DEBUG);
return;
}
static void
xqc_copa_on_lost(void *cong, xqc_usec_t lost_sent_time)
{
xqc_copa_t *copa = (xqc_copa_t*)cong;
/* already in recovery mode */
if (lost_sent_time < copa->recovery_start_time) {
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|loss_before_recovery|loss_sent_time:%ui|"
"recovery_start_time:%ui|",
lost_sent_time, copa->recovery_start_time);
} else {
/* start a new recovery epoch */
copa->recovery_start_time = xqc_monotonic_timestamp();
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|recovery_start_at:%ui|", copa->recovery_start_time);
if (copa->mode == COPA_COMPETITIVE_MODE) {
/*
* multiplicative decrease on 1 / delta,
* once per epoch (RTT) at most.
*/
copa->delta = xqc_min(copa->delta * 2, copa->delta_max);
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|MD_on_delta:%.4f|", copa->delta);
}
}
XQC_COPA_LOG_STATE("on_lost", XQC_LOG_DEBUG);
return;
}
static inline void
xqc_copa_handle_sudden_direction_change(xqc_copa_t *copa,
xqc_copa_direction_t new_dir)
{
copa->v = XQC_COPA_INIT_VELOCITY;
copa->same_dir_cnt = 0;
copa->last_round_cwnd_bytes = copa->cwnd_bytes;
copa->prev_dir = copa->curr_dir;
copa->curr_dir = new_dir;
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|handle_sudden_direction_change|cwnd_bytes:%ui|"
"last_round_cwnd_bytes:%ui|curr_dir:%d|prev_dir:%d|",
copa->cwnd_bytes, copa->last_round_cwnd_bytes,
copa->curr_dir, copa->prev_dir);
}
static void
xqc_copa_on_ack(void *cong, xqc_sample_t *sampler)
{
xqc_copa_t *copa = (xqc_copa_t*)cong;
xqc_usec_t largest_pkt_sent_time = sampler->po_sent_time;
uint32_t newly_acked_bytes = sampler->acked;
xqc_usec_t ack_recv_time = sampler->now;
xqc_usec_t latest_rtt = copa->ctl_ctx->ctl_latest_rtt;
xqc_usec_t srtt = copa->ctl_ctx->ctl_srtt;
xqc_usec_t rtt_min_win = XQC_COPA_RTT_MIN_WINDOW;
xqc_usec_t rtt_sta_win = XQC_COPA_RTT_STA_WINDOW * srtt;
xqc_usec_t rtt_max_win = XQC_COPA_RTT_MAX_WINDOW;
XQC_COPA_LOG_STATE("before_on_ack", XQC_LOG_DEBUG);
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG, "|copa|sampler|"
"ack_time:%ui|prior_delivered:%ui|delivered:%ud|acked:%ud|"
"bytes_inflight:%ud|prior_inflight:%ud|rtt:%ui|"
"is_applimit:%ud|srtt:%ui|loss:%ud|total_acked:%ui|",
sampler->now, sampler->prior_delivered, sampler->delivered,
sampler->acked, sampler->bytes_inflight, sampler->prior_inflight,
sampler->rtt, sampler->is_app_limited, sampler->srtt,
sampler->loss, sampler->total_acked);
/* check if we have recovered from losses */
if (copa->recovery_start_time > 0
&& largest_pkt_sent_time > copa->recovery_start_time)
{
copa->recovery_start_time = 0;
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|loss_recovered|sent_time:%ui|ack_time:%ui|",
largest_pkt_sent_time, ack_recv_time);
}
/*
* Copa does not care about if it is in recovery mode.
* It always adjusts cwnd with the AIAD law.
*/
copa->round_start = XQC_FALSE;
/* update packet-timed round trip counter */
if (sampler->prior_delivered >= copa->next_round_delivered) {
copa->round_cnt++;
copa->next_round_delivered = sampler->total_acked;
copa->round_start = XQC_TRUE;
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|round_cnt_advanced|round_cnt:%ud|"
"next_round_delivered:%ui|",
copa->round_cnt, copa->next_round_delivered);
}
/* update delta */
if (copa->mode == COPA_COMPETITIVE_MODE && copa->round_start) {
/*
* additive increase on 1 / delta.
* 1 / delta = 1 / delta + 1 = (delta + 1) / delta
*/
copa->delta = copa->delta / (copa->delta * copa->delta_ai_unit + 1);
}
/* Once we have a valid ack sample, rtt statistics must not be zero */
if (latest_rtt == 0) {
/* invalid latest_rtt */
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_WARN,
"|copa|invalid_latest_rtt:%ui|ack_time:%ui|",
ack_recv_time, latest_rtt);
goto on_ack_end;
}
/* update rtt statistics */
xqc_win_filter_min(&copa->rtt_min, rtt_min_win,
ack_recv_time, latest_rtt);
xqc_win_filter_min(&copa->rtt_standing, rtt_sta_win,
ack_recv_time, latest_rtt);
xqc_win_filter_max(&copa->rtt_max, rtt_max_win,
copa->round_cnt, latest_rtt);
/* calculate data */
double target_rate, current_rate;
xqc_usec_t rtt_standing, rtt_min, rtt_max, delay;
rtt_standing = xqc_win_filter_get(&copa->rtt_standing);
rtt_min = xqc_win_filter_get(&copa->rtt_min);
if (rtt_standing < rtt_min) {
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_WARN,
"|copa|negative_queuing_delay|srtt:%ui|"
"rtt_standing:%ui|rtt_min:%ui|",
srtt, rtt_standing, rtt_min);
goto on_ack_end;
}
delay = rtt_standing - rtt_min;
/* update the time when a low queuing delay is observed */
/* <= guarantees the update the timestamp when delay is zero */
if (delay <= ((xqc_win_filter_get(&copa->rtt_max) - rtt_min) / 10)) {
copa->t_last_delay_min = ack_recv_time;
if (copa->mode != COPA_DELAY_MODE) {
/* switch to delay mode and reset delta */
copa->mode = COPA_DELAY_MODE;
copa->delta = copa->delta_base;
}
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|low_delay_is_observed_at:%ui|mode:%d|",
ack_recv_time, copa->mode);
}
if (delay == 0) {
/* no queuing delay */
target_rate = XQC_COPA_MAX_RATE;
} else {
target_rate = XQC_COPA_MSS * 1.0
* XQC_COPA_USEC2SEC / (delay * copa->delta);
}
current_rate = copa->cwnd_bytes * 1.0 * XQC_COPA_USEC2SEC / rtt_standing;
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|rate_generated|target_rate:%.4f|current_rate:%.4f|"
"delay:%ui|",
target_rate, current_rate, delay);
/* slow start */
if (copa->in_slow_start) {
if (current_rate > target_rate) {
/* exit slow start */
copa->in_slow_start = 0;
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|slow_start_exit|");
/* @TODO: we may set Copa's direction to DOWN at here */
} else {
/*
* We make sure that cwnd must NOT increase by more than 2x
* at a time.
*/
if (newly_acked_bytes > copa->cwnd_bytes) {
copa->cwnd_bytes <<= 1;
} else {
copa->cwnd_bytes += newly_acked_bytes;
}
xqc_copa_set_pacing_rate(copa);
goto on_ack_end;
}
}
/* steady phase start */
/* check mode switching conditions at round start */
/* @TODO: may switch to packet-timed rounds for t_last_delay_min */
if (copa->round_start
&& copa->mode != COPA_COMPETITIVE_MODE
&& ((ack_recv_time - copa->t_last_delay_min)
>= (XQC_COPA_MS_THRESHOLD * srtt)))
{
copa->mode = COPA_COMPETITIVE_MODE;
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|switch_to_competitive_mode_at:%ui|"
"round_cnt:%ud|t_last_delay_min:%ui|",
ack_recv_time, copa->round_cnt, copa->t_last_delay_min);
}
/* check & update the direction for cwnd adjustment */
if (copa->round_start) {
xqc_copa_direction_t new_dir;
if (copa->cwnd_bytes > copa->last_round_cwnd_bytes) {
new_dir = COPA_UP;
} else {
new_dir = COPA_DOWN;
}
copa->last_round_cwnd_bytes = copa->cwnd_bytes;
if (new_dir != copa->curr_dir) {
copa->v = XQC_COPA_INIT_VELOCITY;
copa->same_dir_cnt = 0;
} else {
copa->same_dir_cnt++;
}
copa->prev_dir = copa->curr_dir;
copa->curr_dir = new_dir;
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|direction_update|curr_dir:%d|prev_dir:%d|"
"same_dir_cnt:%ud|velocity:%.4f|",
copa->curr_dir, copa->prev_dir, copa->same_dir_cnt, copa->v);
/*
* if cnt == 3, it means the direction remains the same for
* a bit less than 3 RTTs.
*/
if (copa->same_dir_cnt > 3) {
/*
* double v every RTT once the direction has remained the same
* for 3 RTTs.
*/
copa->v *= 2.0;
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|velocity_update|velocity:%.4f|", copa->v);
}
/*
* if v makes cwnd grow faster than slow start,
* we should reduce it
*/
if ((copa->v * XQC_COPA_MSS) >= (copa->delta * copa->cwnd_bytes)) {
copa->v /= 2.0;
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|velocity_too_large|velocity:%.4f|", copa->v);
}
/* but, we need to ensure v is at least XQC_COPA_INIT_VELOCITY */
copa->v = xqc_max(copa->v, XQC_COPA_INIT_VELOCITY);
}
int aiad_sign;
/* update cwnd */
if (current_rate > target_rate) {
/*
* According to Facebook's Copa implementation, they reset the velocity
* to 1.0, if the current direction indicates the opposite cwnd
* adjustment direction of what current_rate and target_rate indicate
* and the velocity is greater than XQC_COPA_INIT_VELOCITY.
*/
if (copa->curr_dir != COPA_DOWN && copa->v > XQC_COPA_INIT_VELOCITY) {
xqc_copa_handle_sudden_direction_change(copa, COPA_DOWN);
}
aiad_sign = -1;
} else {
if (copa->curr_dir != COPA_UP && copa->v > XQC_COPA_INIT_VELOCITY) {
xqc_copa_handle_sudden_direction_change(copa, COPA_UP);
}
aiad_sign = 1;
}
uint64_t numerator_bytes = (uint64_t)(copa->v * newly_acked_bytes
/ copa->delta);
/* v * delta should be always greater than 1.0 */
if (numerator_bytes == 0) {
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_WARN,
"|copa|acked_bytes_too_less|velocity:%.4f|delta:%.4f|"
"newly_acked_bytes:%ui|",
copa->v, copa->delta, newly_acked_bytes);
}
copa->cwnd_adjustment_accumulated += (aiad_sign * numerator_bytes);
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|aiad_bytes_accumulated|aiad_sign:%d|numertor_bytes:%ui|"
"cwnd_adjustment_accumulated:%i|",
aiad_sign, numerator_bytes, copa->cwnd_adjustment_accumulated);
if (copa->cwnd_adjustment_accumulated > 0
&& copa->cwnd_adjustment_accumulated >= copa->cwnd_bytes) {
int64_t d = copa->cwnd_adjustment_accumulated / copa->cwnd_bytes;
copa->cwnd_adjustment_accumulated -= (d * copa->cwnd_bytes);
copa->cwnd_bytes += (d * XQC_COPA_MSS);
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|aiad_bytes_applied|UP|cwnd_bytes:%ui|"
"cwnd_adjustment_accumulated:%i|",
copa->cwnd_bytes, copa->cwnd_adjustment_accumulated);
} else if (copa->cwnd_adjustment_accumulated < 0
&& copa->cwnd_adjustment_accumulated <= -copa->cwnd_bytes) {
int64_t d = -copa->cwnd_adjustment_accumulated / copa->cwnd_bytes;
copa->cwnd_adjustment_accumulated += (d * copa->cwnd_bytes);
/* avoid underflow */
d = d * XQC_COPA_MSS;
if (d <= copa->cwnd_bytes) {
copa->cwnd_bytes -= d;
} else {
copa->cwnd_bytes = 0;
}
xqc_log(copa->ctl_ctx->ctl_conn->log, XQC_LOG_DEBUG,
"|copa|aiad_bytes_applied|DOWN|cwnd_bytes:%ui|"
"cwnd_adjustment_accumulated:%i|",
copa->cwnd_bytes, copa->cwnd_adjustment_accumulated);
}
copa->cwnd_bytes = xqc_max(XQC_COPA_MIN_WIN, copa->cwnd_bytes);
xqc_copa_set_pacing_rate(copa);
on_ack_end:
XQC_COPA_LOG_STATE("after_on_ack", XQC_LOG_DEBUG);
return;
}
static uint64_t
xqc_copa_get_cwnd(void *cong)
{
xqc_copa_t *copa = (xqc_copa_t*)cong;
return copa->cwnd_bytes;
}
static void
xqc_copa_reset_cwnd(void *cong)
{
xqc_copa_t *copa = (xqc_copa_t*)cong;
/*
* @NOTE: We reinitialize Copa and do slow start again. After recovering
* from a persistent congestion event, the network path may have changed
* significantly. Therefore, the safest way to do congestion control is to
* cut the cwnd to the minimal value and re-probe the network path by
* slow start.
*/
xqc_win_filter_reset(&copa->rtt_min, 0, XQC_COPA_INF_U64);
xqc_win_filter_reset(&copa->rtt_max, 0, 0);
xqc_win_filter_reset(&copa->rtt_standing, 0, XQC_COPA_INF_U64);
copa->v = XQC_COPA_INIT_VELOCITY;
copa->curr_dir = COPA_UNDEF; /* slow start */
copa->prev_dir = COPA_UNDEF;
copa->same_dir_cnt = 0;
copa->mode = COPA_DELAY_MODE;
copa->t_last_delay_min = 0;
copa->in_slow_start = XQC_TRUE;
copa->delta = copa->delta_base;
copa->recovery_start_time = 0;
copa->cwnd_adjustment_accumulated = 0;
copa->cwnd_bytes = XQC_COPA_MIN_WIN;
xqc_copa_set_pacing_rate(copa);
XQC_COPA_LOG_STATE("persistent_congestion", XQC_LOG_DEBUG);
return;
}
static int
xqc_copa_in_slow_start(void *cong)
{
xqc_copa_t *copa = (xqc_copa_t*)cong;
return copa->in_slow_start;
}
static void
xqc_copa_restart_from_idle(void *cong, uint64_t arg)
{
/*
* @TODO: may do something here in the future,
* e.g. resetting congestion state and restarting from slow start.
*/
return;
}
static int
xqc_copa_in_recovery(void *cong)
{
xqc_copa_t *copa = (xqc_copa_t*)cong;
return copa->recovery_start_time > 0;
}
/* @TODO: use u64 for pacing rate all the time */
static uint32_t
xqc_copa_get_pacing_rate(void *cong)
{
xqc_copa_t *copa = (xqc_copa_t*)cong;
return copa->pacing_rate;
}
const xqc_cong_ctrl_callback_t xqc_copa_cb = {
.xqc_cong_ctl_size = xqc_copa_size,
.xqc_cong_ctl_init = xqc_copa_init,
.xqc_cong_ctl_on_lost = xqc_copa_on_lost,
/* @TODO: rename this callback interface */
.xqc_cong_ctl_on_ack_multiple_pkts = xqc_copa_on_ack,
.xqc_cong_ctl_get_cwnd = xqc_copa_get_cwnd,
.xqc_cong_ctl_reset_cwnd = xqc_copa_reset_cwnd,
.xqc_cong_ctl_in_slow_start = xqc_copa_in_slow_start,
.xqc_cong_ctl_restart_from_idle = xqc_copa_restart_from_idle,
.xqc_cong_ctl_in_recovery = xqc_copa_in_recovery,
.xqc_cong_ctl_get_pacing_rate = xqc_copa_get_pacing_rate,
};