From: David Gibson <david@gibson.dropbear.id.au>
Date: Sun, 1 Jun 2014 14:03:09 +0000 (+1000)
Subject: jacobson_karels: New module
X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=59208d61ceac29b28bd2a15cc0f3ebad524d9b6a;ds=sidebyside

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 1d17e26f..41548de6 100644
--- 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
index 00000000..dc314eca
--- /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
index 00000000..91654703
--- /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
index 00000000..0e9bc2db
--- /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
index 00000000..374345f2
--- /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();
+}