From ed6b45c02fabd040f25c6ea3e7c5d1e03c9725e8 Mon Sep 17 00:00:00 2001
From: Florian Dold <florian.dold@gmail.com>
Date: Wed, 26 Sep 2018 17:34:51 +0200
Subject: randomized exponential backoff

---
 src/util/time.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 54 insertions(+)

(limited to 'src/util/time.c')

diff --git a/src/util/time.c b/src/util/time.c
index ee90eb8ae..0c177c381 100644
--- a/src/util/time.c
+++ b/src/util/time.c
@@ -443,6 +443,39 @@ GNUNET_TIME_relative_multiply (struct GNUNET_TIME_Relative rel,
 }
 
 
+/**
+ * Multiply relative time by a given floating-point factor.  The factor must be
+ * positive.
+ *
+ * @return FOREVER if rel=FOREVER or on overflow; otherwise rel*factor
+ */
+struct GNUNET_TIME_Relative
+relative_multiply_double (struct GNUNET_TIME_Relative rel,
+                          double factor)
+{
+  struct GNUNET_TIME_Relative out;
+  double m;
+
+  GNUNET_assert (0 <= factor);
+
+  if (0 == factor)
+    return GNUNET_TIME_UNIT_ZERO;
+  if (rel.rel_value_us == GNUNET_TIME_UNIT_FOREVER_REL.rel_value_us)
+    return GNUNET_TIME_UNIT_FOREVER_REL;
+
+  m = ((double) rel.rel_value_us) * factor;
+
+  if (m >= (double) (GNUNET_TIME_UNIT_FOREVER_REL).rel_value_us)
+  {
+    GNUNET_break (0);
+    return GNUNET_TIME_UNIT_FOREVER_REL;
+  }
+
+  out.rel_value_us = (uint64_t) m;
+  return out;
+}
+
+
 /**
  * Saturating multiply relative time by a given factor.
  *
@@ -701,5 +734,26 @@ GNUNET_TIME_year_to_time (unsigned int year)
 }
 
 
+/**
+ * Randomized exponential back-off, starting at 1 ms
+ * and going up by a factor of 2+r, where 0 <= r <= 0.5, up
+ * to a maximum of 15 m.
+ *
+ * @param r current backoff time, initially zero
+ * @return the next backoff time
+ */
+struct GNUNET_TIME_Relative
+GNUNET_TIME_randomized_backoff(struct GNUNET_TIME_Relative rt)
+{
+  double r = (rand() % 500) / 1000.0;
+  struct GNUNET_TIME_Relative t;
+
+  t = relative_multiply_double (GNUNET_TIME_relative_max (GNUNET_TIME_UNIT_MILLISECONDS,
+                                                          rt),
+                                2 + r);
+  return GNUNET_TIME_relative_min (GNUNET_TIME_STD_EXPONENTIAL_BACKOFF_THRESHOLD,
+                                   t);
+}
+
 
 /* end of time.c */
-- 
cgit v1.2.3