diff options
Diffstat (limited to 'src/ipcpd/unicast/pol/ca-mb-ecn.c')
| -rw-r--r-- | src/ipcpd/unicast/pol/ca-mb-ecn.c | 216 |
1 files changed, 216 insertions, 0 deletions
diff --git a/src/ipcpd/unicast/pol/ca-mb-ecn.c b/src/ipcpd/unicast/pol/ca-mb-ecn.c new file mode 100644 index 00000000..2de8f8e7 --- /dev/null +++ b/src/ipcpd/unicast/pol/ca-mb-ecn.c @@ -0,0 +1,216 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2020 + * + * Multi-bit ECN Congestion Avoidance + * + * Dimitri Staessens <[email protected]> + * Sander Vrijders <[email protected]> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., http://www.fsf.org/about/contact/. + */ + +#if defined(__linux__) || defined(__CYGWIN__) +#define _DEFAULT_SOURCE +#else +#define _POSIX_C_SOURCE 200809L +#endif + +#include "config.h" + +#include <ouroboros/ipcp-dev.h> +#include <ouroboros/time_utils.h> + +#include "ca-mb-ecn.h" + +#include <stdlib.h> +#include <string.h> + +/* congestion avoidance constants */ +#define CA_SHFT 5 +#define CA_WND (1 << CA_SHFT) +#define CA_UPD (1 << (CA_SHFT - 3)) +#define CA_SLOT 18 +#define CA_AI 20000 +#define ECN_Q_SHFT 5 +#define ts_to_ns(ts) (ts.tv_sec * BILLION + ts.tv_nsec) + +struct mb_ecn_ctx { + uint16_t rx_ece; /* level of congestion (upstream) */ + size_t rx_ctr; /* receiver side packet counter */ + + uint16_t tx_ece; /* level of congestion (downstream) */ + size_t tx_ctr; /* sender side packet counter */ + size_t tx_aps; /* average packet size */ + time_t tx_wnd; /* tgt time to send packets (ns) */ + bool tx_cav; /* Congestion avoidance */ + size_t tx_slot; + + struct timespec t_sent; /* last sent packet */ +}; + +struct pol_ca_ops mb_ecn_ca_ops = { + .ctx_create = mb_ecn_ctx_create, + .ctx_destroy = mb_ecn_ctx_destroy, + .ctx_update_snd = mb_ecn_ctx_update_snd, + .ctx_update_rcv = mb_ecn_ctx_update_rcv, + .ctx_update_ece = mb_ecn_ctx_update_ece, + .wnd_wait = mb_ecn_wnd_wait, + .calc_ecn = mb_ecn_calc_ecn +}; + +void * mb_ecn_ctx_create(void) +{ + + struct mb_ecn_ctx * ctx; + + ctx = malloc(sizeof(*ctx)); + if (ctx == NULL) + return NULL; + + memset(ctx, 0, sizeof(*ctx)); + + return (void *) ctx; +} + +void mb_ecn_ctx_destroy(void * ctx) +{ + free(ctx); +} + +ca_wnd_t mb_ecn_ctx_update_snd(void * _ctx, + size_t len) +{ + struct timespec now; + size_t slot; + time_t gap; + ca_wnd_t wnd; + + struct mb_ecn_ctx * ctx = _ctx; + + clock_gettime(PTHREAD_COND_CLOCK, &now); + + if (ctx->tx_wnd == 0) { /* 10 ms initial window estimate */ + ctx->tx_wnd = 10 * MILLION; + gap = ctx->tx_wnd >> CA_SHFT; + ctx->tx_aps = len >> CA_SHFT; + ctx->tx_slot = ts_to_ns(now) >> CA_SLOT; + } else { + gap = ts_diff_ns(&ctx->t_sent, &now); + ctx->tx_aps -= ctx->tx_aps >> CA_SHFT; + ctx->tx_aps += len; + } + + ctx->t_sent = now; + + slot = ts_to_ns(now) >> CA_SLOT; + + ctx->tx_ctr++; + + if (slot - ctx->tx_slot > 0) { + ctx->tx_slot = slot; + + if (ctx->tx_ctr > CA_WND) + ctx->tx_ece = 0; + + /* Slow start */ + if (!ctx->tx_cav) { + ctx->tx_wnd >>= 1; + /* Multiplicative Decrease */ + } else if (ctx->tx_ece) { /* MD */ + ctx->tx_wnd += (ctx->tx_wnd * ctx->tx_ece) + >> (CA_SHFT + 8); + /* Additive Increase */ + } else { + size_t bw = ctx->tx_aps * BILLION / ctx->tx_wnd; + bw += CA_AI; + ctx->tx_wnd = ctx->tx_aps * BILLION / bw; + } + } + + wnd.wait = (ctx->tx_wnd >> CA_SHFT) - gap; + + return wnd; +} + +void mb_ecn_wnd_wait(ca_wnd_t wnd) +{ + if (wnd.wait > 0) { + struct timespec s = {0, 0}; + if (wnd.wait > BILLION) /* Don't care throttling < 1pps */ + s.tv_sec = 1; + else + s.tv_nsec = wnd.wait; + + nanosleep(&s, NULL); + } +} + +bool mb_ecn_ctx_update_rcv(void * _ctx, + size_t len, + uint8_t ecn, + uint16_t * ece) +{ + struct mb_ecn_ctx* ctx = _ctx; + bool update; + + (void) len; + + if ((ctx->rx_ece | ecn) == 0) + return false; + + if (ecn == 0) { + /* end of congestion */ + ctx->rx_ece >>= 2; + update = ctx->rx_ece == 0; + } else { + if (ctx->rx_ece == 0) { + /* start of congestion */ + ctx->rx_ece = ecn; + ctx->rx_ctr = 0; + update = true; + } else { + /* congestion update */ + ctx->rx_ece -= ctx->rx_ece >> CA_SHFT; + ctx->rx_ece += ecn; + update = (ctx->rx_ctr++ & (CA_UPD - 1)) == true; + } + } + + *ece = ctx->rx_ece; + + return update; +} + + +void mb_ecn_ctx_update_ece(void * _ctx, + uint16_t ece) +{ + struct mb_ecn_ctx* ctx = _ctx; + + ctx->tx_ece = ece; + ctx->tx_ctr = 0; + ctx->tx_cav = true; +} + +uint8_t mb_ecn_calc_ecn(int fd, + size_t len) +{ + size_t q; + + (void) len; + + q = ipcp_flow_queued(fd); + + return (uint8_t) (q >> ECN_Q_SHFT); +} |