summaryrefslogtreecommitdiff
path: root/src/ipcpd/unicast/ca/mb-ecn.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/ipcpd/unicast/ca/mb-ecn.c')
-rw-r--r--src/ipcpd/unicast/ca/mb-ecn.c296
1 files changed, 296 insertions, 0 deletions
diff --git a/src/ipcpd/unicast/ca/mb-ecn.c b/src/ipcpd/unicast/ca/mb-ecn.c
new file mode 100644
index 00000000..38305a39
--- /dev/null
+++ b/src/ipcpd/unicast/ca/mb-ecn.c
@@ -0,0 +1,296 @@
+/*
+ * Ouroboros - Copyright (C) 2016 - 2021
+ *
+ * Multi-bit ECN Congestion Avoidance
+ *
+ * Dimitri Staessens <dimitri@ouroboros.rocks>
+ * Sander Vrijders <sander@ouroboros.rocks>
+ *
+ * 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 "mb-ecn.h"
+
+#include <inttypes.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+/* congestion avoidance constants */
+#define CA_SHFT 5 /* Average over 32 pkts */
+#define CA_WND (1 << CA_SHFT) /* 32 pkts receiver wnd */
+#define CA_UPD (1 << (CA_SHFT - 2)) /* Update snd every 8 pkt */
+#define CA_SLOT 24 /* Initial slot = 16 ms */
+#define CA_INC 1UL << 16 /* ~4MiB/s^2 additive inc */
+#define CA_IWL 1UL << 16 /* Initial limit ~4MiB/s */
+#define CA_MINPS 8 /* Mimimum pkts / slot */
+#define CA_MAXPS 64 /* Maximum pkts / slot */
+#define ECN_Q_SHFT 4
+#define ts_to_ns(ts) ((size_t) 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_wbc; /* Window byte count */
+ size_t tx_wpc; /* Window packet count */
+ size_t tx_wbl; /* Window byte limit */
+ bool tx_cav; /* Congestion avoidance */
+ size_t tx_mul; /* Slot size multiplier */
+ size_t tx_inc; /* Additive increase */
+ size_t tx_slot;
+};
+
+struct 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,
+ .print_stats = mb_ecn_print_stats
+};
+
+void * mb_ecn_ctx_create(void)
+{
+ struct timespec now;
+ struct mb_ecn_ctx * ctx;
+
+ ctx = malloc(sizeof(*ctx));
+ if (ctx == NULL)
+ return NULL;
+
+ clock_gettime(PTHREAD_COND_CLOCK, &now);
+
+ memset(ctx, 0, sizeof(*ctx));
+
+ ctx->tx_mul = CA_SLOT;
+ ctx->tx_wbl = CA_IWL;
+ ctx->tx_inc = CA_INC;
+ ctx->tx_slot = ts_to_ns(now) >> ctx->tx_mul;
+
+ return (void *) ctx;
+}
+
+void mb_ecn_ctx_destroy(void * ctx)
+{
+ free(ctx);
+}
+
+#define _slot_after(new, old) ((int64_t) (old - new) < 0)
+
+ca_wnd_t mb_ecn_ctx_update_snd(void * _ctx,
+ size_t len)
+{
+ struct timespec now;
+ size_t slot;
+ ca_wnd_t wnd;
+ struct mb_ecn_ctx * ctx = _ctx;
+
+ clock_gettime(PTHREAD_COND_CLOCK, &now);
+
+ slot = ts_to_ns(now) >> ctx->tx_mul;
+
+ ctx->tx_ctr++;
+ ctx->tx_wpc++;
+ ctx->tx_wbc += len;
+
+ if (ctx->tx_ctr > CA_WND)
+ ctx->tx_ece = 0;
+
+ if (_slot_after(slot, ctx->tx_slot)) {
+ bool carry = false; /* may carry over if window increases */
+
+ ctx->tx_slot = slot;
+
+ if (!ctx->tx_cav) { /* Slow start */
+ if (ctx->tx_wbc > ctx->tx_wbl)
+ ctx->tx_wbl <<= 1;
+ } else {
+ if (ctx->tx_ece) /* Mult. Decrease */
+ ctx->tx_wbl -= (ctx->tx_wbl * ctx->tx_ece)
+ >> (CA_SHFT + 8);
+ else /* Add. Increase */
+ ctx->tx_wbl = ctx->tx_wbc + ctx->tx_inc;
+ }
+
+ /* Window scaling */
+ if (ctx->tx_wpc < CA_MINPS) {
+ size_t fact = 0; /* factor to scale the window up */
+ size_t pkts = ctx->tx_wpc;
+ while (pkts < CA_MINPS) {
+ pkts <<= 1;
+ fact++;
+ }
+ ctx->tx_mul += fact;
+ ctx->tx_slot >>= fact;
+ if ((ctx->tx_slot & ((1 << fact) - 1)) == 0) {
+ carry = true;
+ ctx->tx_slot += 1;
+ }
+ ctx->tx_wbl <<= fact;
+ ctx->tx_inc <<= fact;
+ } else if (ctx->tx_wpc > CA_MAXPS) {
+ size_t fact = 0; /* factor to scale the window down */
+ size_t pkts = ctx->tx_wpc;
+ while (pkts > CA_MAXPS) {
+ pkts >>= 1;
+ fact++;
+ }
+ ctx->tx_mul -= fact;
+ ctx->tx_slot <<= fact;
+ ctx->tx_wbl >>= fact;
+ ctx->tx_inc >>= fact;
+ } else {
+ ctx->tx_slot = slot;
+ }
+
+ if (!carry) {
+ ctx->tx_wbc = 0;
+ ctx->tx_wpc = 0;
+ }
+ }
+
+ if (ctx->tx_wbc > ctx->tx_wbl)
+ wnd.wait = ((ctx->tx_slot + 1) << ctx->tx_mul) - ts_to_ns(now);
+ else
+ wnd.wait = 0;
+
+ 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 < 1s */
+ 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;
+}
+
+int mb_ecn_calc_ecn(int fd,
+ uint8_t * ecn,
+ qoscube_t qc,
+ size_t len)
+{
+ size_t q;
+
+ (void) len;
+ (void) qc;
+
+ q = ipcp_flow_queued(fd);
+
+ *ecn |= (uint8_t) (q >> ECN_Q_SHFT);
+
+ return 0;
+}
+
+ssize_t mb_ecn_print_stats(void * _ctx,
+ char * buf,
+ size_t len)
+{
+ struct mb_ecn_ctx* ctx = _ctx;
+ char * regime;
+
+ if (len < 1024)
+ return 0;
+
+ if (!ctx->tx_cav)
+ regime = "Slow start";
+ else if (ctx->tx_ece)
+ regime = "Multiplicative dec";
+ else
+ regime = "Additive inc";
+
+ sprintf(buf,
+ "Congestion avoidance algorithm: %20s\n"
+ "Upstream congestion level: %20u\n"
+ "Upstream packet counter: %20zu\n"
+ "Downstream congestion level: %20u\n"
+ "Downstream packet counter: %20zu\n"
+ "Congestion window size (ns): %20" PRIu64 "\n"
+ "Packets in this window: %20zu\n"
+ "Bytes in this window: %20zu\n"
+ "Max bytes in this window: %20zu\n"
+ "Current congestion regime: %20s\n",
+ "Multi-bit ECN",
+ ctx->tx_ece, ctx->tx_ctr,
+ ctx->rx_ece, ctx->rx_ctr, (uint64_t) (1ULL << ctx->tx_mul),
+ ctx->tx_wpc, ctx->tx_wbc, ctx->tx_wbl,
+ regime);
+
+ return strlen(buf);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-23 04:14:01 +0000