jacobson_karels: New module

A straightforward implementation of the Jacobson/Karels algorithm for
estimating round-trip time on a network link.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff --git a/Makefile-ccan b/Makefile-ccan
index 1d17e26fa0d48dc2eccfb96ac2365ec8b016490d..41548de61db60c9dbed25b47a3df3e052a8f37f4 100644 (file)
--- a/Makefile-ccan
+++ b/Makefile-ccan
@@ -60,6 +60,7 @@ MODS_WITH_SRC := antithread \
        io \
        isaac \
        iscsi \
+       jacobson_karels \
        jmap \
        json \
        jset \

diff --git a/ccan/jacobson_karels/LICENSE b/ccan/jacobson_karels/LICENSE
new file mode 120000 (symlink)
index 0000000..dc314ec
--- /dev/null
+++ b/ccan/jacobson_karels/LICENSE
@@ -0,0 +1 @@
+../../licenses/LGPL-2.1
\ No newline at end of file

diff --git a/ccan/jacobson_karels/_info b/ccan/jacobson_karels/_info
new file mode 100644 (file)
index 0000000..9165470
--- /dev/null
+++ b/ccan/jacobson_karels/_info
@@ -0,0 +1,25 @@
+#include <string.h>
+#include "config.h"
+
+/**
+ * jacobson_karels - Jacobson/Karels Round Trip Time algorithm
+ *
+ * This implements the Jacobson/Karels algorithm for estimating round
+ * trip time and appropriate timeouts over a network link.
+ *
+ * Author: David Gibson <david@gibson.dropbear.id>
+ * License: LGPL (v2.1 or any later version)
+ */
+int main(int argc, char *argv[])
+{
+       /* Expect exactly one argument */
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/minmax\n");
+               return 0;
+       }
+
+       return 1;
+}

diff --git a/ccan/jacobson_karels/jacobson_karels.h b/ccan/jacobson_karels/jacobson_karels.h
new file mode 100644 (file)
index 0000000..0e9bc2d
--- /dev/null
+++ b/ccan/jacobson_karels/jacobson_karels.h
@@ -0,0 +1,35 @@
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
+#ifndef CCAN_JACOBSON_KARELS_H
+#define CCAN_JACOBSON_KARELS_H
+
+#include "config.h"
+
+#include <ccan/minmax/minmax.h>
+
+#define JACOBSON_KARELS(_name, _type, _a1, _a2, _b1, _b2, _g, _k) \
+       struct _name##_state { \
+               _type rtt, variance; \
+       }; \
+       static void _name##_init(struct _name##_state *s, \
+                                _type rtt0, _type var0)  \
+       { \
+               s->rtt = rtt0; \
+               s->variance = var0; \
+       } \
+       static void _name##_update(struct _name##_state *s, _type sample) \
+       { \
+               _type diff = sample - s->rtt; \
+               s->rtt += (_a2) * diff / ((_a1) + (_a2)); \
+               diff = (diff < 0) ? -diff : diff; \
+               s->variance = ((_b1)*s->variance + (_b2) * diff) \
+                       / ((_b1) + (_b2));                       \
+       } \
+       static _type _name##_timeout(struct _name##_state *s, \
+                                    _type tmin, _type tmax)  \
+       { \
+               return clamp((_g) * s->rtt + (_k)*s->variance, tmin, tmax); \
+       }
+
+JACOBSON_KARELS(jacobson_karels, unsigned long, 7, 1, 3, 1, 1, 4)
+
+#endif /* CCAN_JACOBSON_KARELS_H */

diff --git a/ccan/jacobson_karels/test/run.c b/ccan/jacobson_karels/test/run.c
new file mode 100644 (file)
index 0000000..374345f
--- /dev/null
+++ b/ccan/jacobson_karels/test/run.c
@@ -0,0 +1,23 @@
+#include <ccan/jacobson_karels/jacobson_karels.h>
+#include <ccan/tap/tap.h>
+
+static void first_test(void)
+{
+       struct jacobson_karels_state s;
+
+       jacobson_karels_init(&s, 0, 0);
+       jacobson_karels_update(&s, 200);
+
+       ok1(jacobson_karels_timeout(&s, 2, 1000) == 225);
+}
+
+int main(void)
+{
+       /* This is how many tests you plan to run */
+       plan_tests(1);
+
+       first_test();
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}