From 2fff8c8cbf820abf45c4963a8356410ecfdba878 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Marek=20Vavrus=CC=8Ca?= <marek.vavrusa@nic.cz>
Date: Tue, 2 Jun 2015 10:34:38 +0200
Subject: [PATCH] lib/nsrep: probabilistic NS probing strategy
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

simplified bee foraging strategy, by default each query goes to the most rewarding NS
however with a chance proportional to the NS RTT, a server may be probed even if it isn’t the most rewarding
---
 lib/nsrep.c   | 51 +++++++++++++++++++++++++++++++++++++--------------
 lib/nsrep.h   |  5 +++--
 lib/zonecut.c |  5 +++++
 3 files changed, 45 insertions(+), 16 deletions(-)

diff --git a/lib/nsrep.c b/lib/nsrep.c
index 45b0be770..9e7e99090 100644
--- a/lib/nsrep.c
+++ b/lib/nsrep.c
@@ -24,6 +24,9 @@
 #include "lib/defines.h"
 #include "lib/generic/pack.h"
 
+/** Some built-in unfairness ... */
+#define FAVOUR_IPV6 20 /* 20ms bonus for v6 */
+
 /** @internal Macro to set address structure. */
 #define ADDR_SET(sa, family, addr, len) do {\
     	memcpy(&sa ## _addr, (addr), (len)); \
@@ -54,35 +57,55 @@ static void update_nsrep(struct kr_nsrep *ns, const knot_dname_t *name, uint8_t
 
 #undef ADDR_SET
 
-static int eval_nsrep(const char *k, void *v, void *baton)
+static unsigned eval_addr_set(pack_t *addr_set, kr_nsrep_lru_t *rttcache, unsigned score, uint8_t **addr)
 {
-	struct kr_nsrep *ns = baton;
-	unsigned score = ns->score;
-	pack_t *addr_set = v;
-	uint8_t *addr = NULL;
-
 	/* Name server is better candidate if it has address record. */
 	uint8_t *it = pack_head(*addr_set);
 	while (it != pack_tail(*addr_set)) {
 		void *val = pack_obj_val(it);
 		size_t len = pack_obj_len(it);
-		unsigned *cached = lru_get(ns->repcache, val, len);
+		/* Get RTT for this address (if known) */
+		unsigned *cached = rttcache ? lru_get(rttcache, val, len) : NULL;
 		unsigned addr_score = (cached) ? *cached : KR_NS_UNKNOWN / 2;
-		/** @todo Favorize IPv6 */
-		if (addr_score <= score) {
-			addr = it;
+		/* Give v6 a head start */
+		unsigned favour = (len == sizeof(struct in6_addr)) ? FAVOUR_IPV6 : 0;
+		if (addr_score < score + favour) {
+			*addr = it;
 			score = addr_score;
 		}
 		it = pack_obj_next(it);
 	}
-	/* No known address */
-	if (!addr) {
+	return score;
+}
+
+static int eval_nsrep(const char *k, void *v, void *baton)
+{
+	struct kr_nsrep *ns = baton;
+	unsigned score = KR_NS_MAX_SCORE;
+	uint8_t *addr = NULL;
+
+	/* Favour nameservers with unknown addresses to probe them,
+	 * otherwise discover the current best address for the NS. */
+	pack_t *addr_set = (pack_t *)v;
+	if (addr_set->len == 0) {
 		score = KR_NS_UNKNOWN;
+	} else {
+		score = eval_addr_set(addr_set, ns->repcache, score, &addr);
 	}
 
-	/* Update best scoring nameserver. */
-	if (score < ns->score) {
+	/* Probabilistic bee foraging strategy (naive).
+	 * The fastest NS is preferred by workers until it is depleted (timeouts or degrades),
+	 * at the same time long distance scouts probe other sources (low probability).
+	 * Servers on TIMEOUT (depleted) can be probed by the dice roll only */
+	if (score < ns->score && score < KR_NS_TIMEOUT) {
 		update_nsrep(ns, (const knot_dname_t *)k, addr, score);
+	} else {
+		/* With 5% chance, probe server with a probability given by its RTT / MAX_RTT */
+		unsigned roll = rand() % KR_NS_MAX_SCORE;
+		if ((roll % 100 < 5) && (roll >= score)) {
+			update_nsrep(ns, (const knot_dname_t *)k, addr, score);
+			return 1; /* Stop evaluation */
+		}
 	}
 
 	return kr_ok();
diff --git a/lib/nsrep.h b/lib/nsrep.h
index 11dbc7e40..eeda40b72 100644
--- a/lib/nsrep.h
+++ b/lib/nsrep.h
@@ -20,6 +20,7 @@
 #include <libknot/dname.h>
 #include <limits.h>
 
+#include "lib/defines.h"
 #include "lib/generic/map.h"
 #include "lib/generic/lru.h"
 
@@ -27,8 +28,8 @@
   * Special values for nameserver score (RTT in miliseconds)
   */
 enum kr_ns_score {
-	KR_NS_MAX_SCORE = 10 * 1000,
-	KR_NS_TIMEOUT   = KR_NS_MAX_SCORE,
+	KR_NS_MAX_SCORE = KR_CONN_RTT_MAX,
+	KR_NS_TIMEOUT   = (90 * KR_NS_MAX_SCORE) / 100,
 	KR_NS_UNKNOWN   = 10
 };
 
diff --git a/lib/zonecut.c b/lib/zonecut.c
index 0fb3dfb91..ec150fe0b 100644
--- a/lib/zonecut.c
+++ b/lib/zonecut.c
@@ -210,6 +210,11 @@ static int fetch_ns(struct kr_zonecut *cut, const knot_dname_t *name, struct kr_
 		kr_zonecut_add(cut, ns_name, NULL);
 	}
 
+	/* Always keep SBELT as a backup for root */
+	if (name[0] == '\0') {
+		kr_zonecut_set_sbelt(cut);
+	}
+
 	return kr_ok();
 }
 
-- 
2.47.3