gnunet

commit ed6b45c02fabd040f25c6ea3e7c5d1e03c9725e8
parent e67f1331d12caef3731a41700deb89bd44f1cf3d
Author: Florian Dold <florian.dold@gmail.com>
Date:   Wed, 26 Sep 2018 17:34:51 +0200

randomized exponential backoff

Diffstat:
M
src/include/gnunet_time_lib.h
 | 
13
+++++++++++++
M
src/util/time.c
 | 
54
++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 67 insertions(+), 0 deletions(-)
diff --git a/src/include/gnunet_time_lib.h b/src/include/gnunet_time_lib.h
@@ -173,6 +173,19 @@ GNUNET_NETWORK_STRUCT_END
 #define GNUNET_TIME_STD_BACKOFF(r) GNUNET_TIME_relative_min (GNUNET_TIME_STD_EXPONENTIAL_BACKOFF_THRESHOLD, \
    GNUNET_TIME_relative_multiply (GNUNET_TIME_relative_max (GNUNET_TIME_UNIT_MILLISECONDS, (r)), 2));
 
+
+/**
+ * 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);
+
+
 /**
  * Return relative time of 0ms.
  */
diff --git a/src/util/time.c b/src/util/time.c
@@ -444,6 +444,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.
  *
  * @param rel some duration
@@ -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 */