gateway: always select a new gateway when threshold != 0
[olsrd.git] / src / gateway_default_handler.c
index ef68935..3957b3a 100644 (file)
  *  Created on: Jan 29, 2010
  *      Author: rogge
  */
+#ifdef __linux__
+
+#include "gateway_default_handler.h"
 
 #include "defs.h"
 #include "gateway.h"
-#include "gateway_default_handler.h"
-#include "scheduler.h"
-#include "tc_set.h"
-#include "log.h"
 #include "lq_plugin.h"
 
-#include "assert.h"
-
-#ifdef linux
-static uint32_t gw_def_nodecount, gw_def_stablecount;
-static bool gw_def_finished_ipv4, gw_def_finished_ipv6;
-
+static uint32_t gw_def_nodecount;
+static uint32_t gw_def_stablecount;
+static bool gw_def_choose_new_ipv4_gw;
+static bool gw_def_choose_new_ipv6_gw;
 static struct timer_entry *gw_def_timer;
 
+/* forward declarations */
+static void gw_default_init(void);
+static void gw_default_cleanup(void);
 static void gw_default_startup_handler(void);
+static uint64_t gw_default_getcosts(struct gateway_entry *gw);
 static void gw_default_choosegw_handler(bool ipv4, bool ipv6);
 static void gw_default_update_handler(struct gateway_entry *);
 static void gw_default_delete_handler(struct gateway_entry *);
 
-static struct olsr_gw_handler gw_def_handler = {
-  &gw_default_startup_handler,
-  &gw_default_choosegw_handler,
-  &gw_default_update_handler,
-  &gw_default_delete_handler
+/**
+ * Callback list for the gateway (default) handler
+ */
+struct olsr_gw_handler gw_def_handler = {
+    &gw_default_init,
+    &gw_default_cleanup,
+    &gw_default_startup_handler,
+    &gw_default_getcosts,
+    &gw_default_choosegw_handler,
+    &gw_default_update_handler,
+    &gw_default_delete_handler
 };
 
+/*
+ * Helper functions
+ */
+
+/**
+ * Calculate the threshold path cost.
+ *
+ * @param path_cost the path cost
+ * @return the threshold path cost
+ */
+static inline uint64_t gw_default_calc_threshold(uint64_t path_cost) {
+  if (olsr_cnf->smart_gw_thresh == 0) {
+    return path_cost;
+  }
+
+  return ((path_cost * (uint64_t) olsr_cnf->smart_gw_thresh) + (uint64_t) 50) / (uint64_t) 100;
+}
+
+/**
+ * Weigh the path costs and the gateway bandwidth.
+ *
+ * If the ETX divider is zero, then no weighing is performed and only the path
+ * costs are considered (classic behaviour).
+ *
+ * If either of the uplink or downlink bandwidths is zero, then UINT64_MAX is
+ * returned.
+ *
+ * @param path_cost the (ETX) path cost to the gateway
+ * @param exitUk the gateway exit link uplink bandwidth (in kbps)
+ * @param exitDk the gateway exit link downlink bandwidth (in kbps)
+ * @return the weighed path cost
+ */
+static inline uint64_t gw_default_weigh_costs(uint64_t path_cost, uint32_t exitUk, uint32_t exitDk) {
+  uint8_t WexitU = olsr_cnf->smart_gw_weight_exitlink_up;
+  uint8_t WexitD = olsr_cnf->smart_gw_weight_exitlink_down;
+  uint8_t Wetx = olsr_cnf->smart_gw_weight_etx;
+  uint8_t Detx = olsr_cnf->smart_gw_divider_etx;
+  uint64_t costU;
+  uint64_t costD;
+  uint64_t costE;
+
+  if (!Detx) {
+    /* only consider path costs (classic behaviour) */
+    return path_cost;
+  }
+
+  if (!exitUk || !exitDk) {
+    /* zero bandwidth */
+    return UINT64_MAX;
+  }
+
+  /*
+   * Weighing of the path costs:
+   *
+   * exitUm = the gateway exit link uplink   bandwidth, in Mbps
+   * exitDm = the gateway exit link downlink bandwidth, in Mbps
+   * WexitU = the gateway exit link uplink   bandwidth weight   (configured)
+   * WexitD = the gateway exit link downlink bandwidth weight   (configured)
+   * Wetx   = the ETX path cost weight                          (configured)
+   * Detx   = the ETX path cost divider                         (configured)
+   *
+   *                     WexitU   WexitD   Wetx
+   * path_cost_weight =  ------ + ------ + ---- * path_cost
+   *                     exitUm   exitDm   Detx
+   *
+   * Since the gateway exit link bandwidths are in Kbps, the following formula
+   * is used to convert them to the desired Mbps:
+   *
+   *       bwK
+   * bwM = ----       bwK = bandwidth in Kbps
+   *       1000       bwM = bandwidth in Mbps
+   *
+   * exitUk = the gateway exit link uplink   bandwidth, in Kbps
+   * exitDk = the gateway exit link downlink bandwidth, in Kbps
+   *
+   *                     1000 * WexitU   1000 * WexitD   Wetx
+   * path_cost_weight =  ------------- + ------------- + ---- * path_cost
+   *                         exitUk          exitDk      Detx
+   *
+   *
+   * Analysis of the required bit width of the result:
+   *
+   * exitUk    = [1,   320,000,000] = 29 bits
+   * exitDk    = [1,   320,000,000] = 29 bits
+   * WexitU    = [1,           255] =  8 bits
+   * WexitD    = [1,           255] =  8 bits
+   * Wetx      = [1,           255] =  8 bits
+   * Detx      = [1,           255] =  8 bits
+   * path_cost = [1, 4,294,967,295] = 32 bits
+   *
+   *                         1000 * 255   1000 * 255   255
+   * path_cost_weight(max) = ---------- + ---------- + --- * 4,294,967,295
+   *                              1             1       1
+   *
+   * path_cost_weight(max) = 0x3E418    + 0x3E418    + 0xFEFFFFFF01
+   * path_cost_weight(max) = 0xFF0007C731
+   *
+   * Because we can multiply 0xFF0007C731 by 2^24 without overflowing a
+   * 64 bits number, we do this to increase accuracy.
+   */
+
+  costU = (((uint64_t) (1000 * WexitU)) << 24) / exitUk;
+  costD = (((uint64_t) (1000 * WexitD)) << 24) / exitDk;
+  costE = (((uint64_t) (Wetx * path_cost)) << 24) / Detx;
+
+  return (costU + costD + costE);
+}
+
 /**
  * Look through the gateway list and select the best gateway
  * depending on the distance to this router
  */
 static void gw_default_choose_gateway(void) {
-  struct tc_entry *tc;
-  struct gateway_entry *inet_ipv4, *inet_ipv6;
-  olsr_linkcost cost_ipv4, cost_ipv6;
+  uint64_t cost_ipv4_threshold = UINT64_MAX;
+  uint64_t cost_ipv6_threshold = UINT64_MAX;
+  bool cost_ipv4_threshold_valid = false;
+  bool cost_ipv6_threshold_valid = false;
+  struct gateway_entry *chosen_gw_ipv4 = NULL;
+  struct gateway_entry *chosen_gw_ipv6 = NULL;
+  uint64_t chosen_gw_ipv4_costs = UINT64_MAX;
+  uint64_t chosen_gw_ipv6_costs = UINT64_MAX;
   struct gateway_entry *gw;
-  bool dual;
-  olsr_linkcost path_cost_times_threshold;
+  bool dual = false;
 
-  cost_ipv4 = ROUTE_COST_BROKEN;
-  cost_ipv6 = ROUTE_COST_BROKEN;
+  if (olsr_cnf->smart_gw_thresh) {
+    /* determine the path cost thresholds */
 
-  inet_ipv4 = NULL;
-  inet_ipv6 = NULL;
+    uint64_t cost = gw_default_getcosts(olsr_get_inet_gateway(false));
+    if (cost != UINT64_MAX) {
+      cost_ipv4_threshold = gw_default_calc_threshold(cost);
+      cost_ipv4_threshold_valid = true;
+    }
+
+    cost = gw_default_getcosts(olsr_get_inet_gateway(true));
+    if (cost != UINT64_MAX) {
+      cost_ipv6_threshold = gw_default_calc_threshold(cost);
+      cost_ipv6_threshold_valid = true;
+    }
+  }
 
   OLSR_FOR_ALL_GATEWAY_ENTRIES(gw) {
-    /* gateways should not exist without tc entry */
-    if ((tc = olsr_lookup_tc_entry(&gw->originator)) == NULL) {
+    uint64_t gw_cost = gw_default_getcosts(gw);
+
+    if (gw_cost == UINT64_MAX) {
+      /* never select a node with infinite costs */
       continue;
     }
 
-    if (olsr_cnf->smart_gw_thresh == 0) {
-      path_cost_times_threshold = tc->path_cost;
-    } else {
-      path_cost_times_threshold = ((long long)tc->path_cost * (long long)olsr_cnf->smart_gw_thresh + 50LL) / 100LL;
+    if (gw_def_choose_new_ipv4_gw) {
+      bool gw_eligible_v4 = gw->ipv4
+          /* && (olsr_cnf->ip_version == AF_INET || olsr_cnf->use_niit) *//* contained in gw_def_choose_new_ipv4_gw */
+          && (olsr_cnf->smart_gw_allow_nat || !gw->ipv4nat);
+      if (gw_eligible_v4 && gw_cost < chosen_gw_ipv4_costs
+          && (!cost_ipv4_threshold_valid || (gw_cost < cost_ipv4_threshold))) {
+        chosen_gw_ipv4 = gw;
+        chosen_gw_ipv4_costs = gw_cost;
+      }
     }
-    if (!gw_def_finished_ipv4 && gw->ipv4 && gw->ipv4nat == olsr_cnf->smart_gw_allow_nat && path_cost_times_threshold < cost_ipv4) {
-      inet_ipv4 = gw;
-      cost_ipv4 = path_cost_times_threshold;
-    }
-    if (!gw_def_finished_ipv6 && gw->ipv6 && path_cost_times_threshold < cost_ipv6) {
-      inet_ipv6 = gw;
-      cost_ipv6 = path_cost_times_threshold;
+
+    if (gw_def_choose_new_ipv6_gw) {
+      bool gw_eligible_v6 = gw->ipv6
+          /* && olsr_cnf->ip_version == AF_INET6 *//* contained in gw_def_choose_new_ipv6_gw */;
+      if (gw_eligible_v6 && gw_cost < chosen_gw_ipv6_costs
+          && (!cost_ipv6_threshold_valid || (gw_cost < cost_ipv6_threshold))) {
+        chosen_gw_ipv6 = gw;
+        chosen_gw_ipv6_costs = gw_cost;
+      }
     }
   } OLSR_FOR_ALL_GATEWAY_ENTRIES_END(gw)
 
-  /* found an IPv4 gateway ? */
-  gw_def_finished_ipv4 |= inet_ipv4 != NULL;
-  gw_def_finished_ipv6 |= inet_ipv6 != NULL;
-  dual = inet_ipv4 == inet_ipv6;
-  if (inet_ipv4) {
-    olsr_set_inet_gateway(&inet_ipv4->originator, true, dual, false);
+  /* determine if we should keep looking for IPv4 and/or IPv6 gateways */
+  gw_def_choose_new_ipv4_gw = gw_def_choose_new_ipv4_gw && (chosen_gw_ipv4 == NULL);
+  gw_def_choose_new_ipv6_gw = gw_def_choose_new_ipv6_gw && (chosen_gw_ipv6 == NULL);
+
+  /* determine if we are dealing with a dual stack gateway */
+  dual = chosen_gw_ipv4 && (chosen_gw_ipv4 == chosen_gw_ipv6);
+
+  if (chosen_gw_ipv4) {
+    /* we are dealing with an IPv4 or dual stack gateway */
+    olsr_set_inet_gateway(&chosen_gw_ipv4->originator, chosen_gw_ipv4_costs, true, dual);
   }
-  if (inet_ipv6 && !dual) {
-    olsr_set_inet_gateway(&inet_ipv6->originator, false, true, false);
+  if (chosen_gw_ipv6 && !dual) {
+    /* we are dealing with an IPv6-only gateway */
+    olsr_set_inet_gateway(&chosen_gw_ipv6->originator, chosen_gw_ipv6_costs, false, true);
   }
 
-  /* finished ? */
-  if ((olsr_cnf->smart_gw_thresh == 0) && gw_def_finished_ipv4 && gw_def_finished_ipv6) {
+  if ((olsr_cnf->smart_gw_thresh == 0) && !gw_def_choose_new_ipv4_gw && !gw_def_choose_new_ipv6_gw) {
+    /* stop looking for a better gateway */
     olsr_stop_timer(gw_def_timer);
     gw_def_timer = NULL;
   }
@@ -97,16 +240,17 @@ static void gw_default_choose_gateway(void) {
  */
 static void gw_default_timer(void *unused __attribute__ ((unused))) {
   /* accept a 10% increase/decrease in the number of gateway nodes without triggering a stablecount reset */
-  if (((tc_tree.count * 10) <= (gw_def_nodecount * 11)) ||
-      ((tc_tree.count * 10) >= (gw_def_nodecount *  9))) {
+  unsigned int tree100percent = tc_tree.count * 10;
+  uint32_t nodecount090percent = gw_def_nodecount * 9;
+  uint32_t nodecount110percent = gw_def_nodecount * 11;
+  if ((tree100percent >= nodecount090percent) && (tree100percent <= nodecount110percent)) {
     gw_def_nodecount = tc_tree.count;
   }
 
   if (tc_tree.count == gw_def_nodecount) {
     /* the number of gateway nodes is 'stable' */
     gw_def_stablecount++;
-  }
-  else {
+  } else {
     /* there was a significant change in the number of gateway nodes */
     gw_def_nodecount = tc_tree.count;
     gw_def_stablecount = 0;
@@ -118,91 +262,147 @@ static void gw_default_timer(void *unused __attribute__ ((unused))) {
   }
 }
 
-/* gateway handler callbacks */
+/**
+ * Lookup a new gateway
+ *
+ * @param ipv4 lookup new v4 gateway
+ * @param ipv6 lookup new v6 gateway
+ */
+static void gw_default_lookup_gateway(bool ipv4, bool ipv6) {
+  if (ipv4) {
+    /* get a new IPv4 gateway if we use OLSRv4 or NIIT */
+    gw_def_choose_new_ipv4_gw = (olsr_cnf->ip_version == AF_INET) || olsr_cnf->use_niit;
+  }
+  if (ipv6) {
+    /* get a new IPv6 gateway if we use OLSRv6 */
+    gw_def_choose_new_ipv6_gw = olsr_cnf->ip_version == AF_INET6;
+  }
+
+  if (gw_def_choose_new_ipv4_gw || gw_def_choose_new_ipv6_gw) {
+    gw_default_choose_gateway();
+  }
+}
+
+/*
+ * Exported functions
+ */
+
+/*
+ * Handler functions
+ */
+
+/**
+ * initialization of default gateway handler
+ */
+static void gw_default_init(void) {
+  /* initialize values */
+  gw_def_nodecount = 0;
+  gw_def_stablecount = 0;
+  gw_def_choose_new_ipv4_gw = true;
+  gw_def_choose_new_ipv6_gw = true;
+  gw_def_timer = NULL;
+}
+
+/**
+ * Cleanup default gateway handler
+ */
+static void gw_default_cleanup(void) {
+}
+
+/**
+ * Handle gateway startup
+ */
 static void gw_default_startup_handler(void) {
   /* reset node count */
   gw_def_nodecount = tc_tree.count;
   gw_def_stablecount = 0;
 
-  /* get new ipv4 GW if we use OLSRv4 or NIIT */
-  gw_def_finished_ipv4 = !(olsr_cnf->ip_version == AF_INET || olsr_cnf->use_niit);
+  /* get a new IPv4 gateway if we use OLSRv4 or NIIT */
+  gw_def_choose_new_ipv4_gw = (olsr_cnf->ip_version == AF_INET) || olsr_cnf->use_niit;
 
-  /* get new ipv6 GW if we use OLSRv6 */
-  gw_def_finished_ipv6 = !(olsr_cnf->ip_version == AF_INET6);
+  /* get a new IPv6 gateway if we use OLSRv6 */
+  gw_def_choose_new_ipv6_gw = olsr_cnf->ip_version == AF_INET6;
 
   /* keep in mind we might be a gateway ourself */
-  gw_def_finished_ipv4 |= olsr_cnf->has_ipv4_gateway;
-  gw_def_finished_ipv6 |= olsr_cnf->has_ipv6_gateway;
+  gw_def_choose_new_ipv4_gw = gw_def_choose_new_ipv4_gw && !olsr_cnf->has_ipv4_gateway;
+  gw_def_choose_new_ipv6_gw = gw_def_choose_new_ipv6_gw && !olsr_cnf->has_ipv6_gateway;
 
-  /* start gateway selection timer */
+  /* (re)start gateway lazy selection timer */
   olsr_set_timer(&gw_def_timer, olsr_cnf->smart_gw_period, 0, true, &gw_default_timer, NULL, 0);
 }
 
-static void gw_default_update_handler(struct gateway_entry *gw) {
-  bool v4changed, v6changed;
-
-  v4changed = (gw == olsr_get_ipv4_inet_gateway(NULL))
-      && (!gw->ipv4 || (gw->ipv4nat && !olsr_cnf->smart_gw_allow_nat));
-  v6changed = (gw == olsr_get_ipv6_inet_gateway(NULL)) && !gw->ipv6;
+/**
+ * Called when the costs of a gateway must be determined.
+ *
+ * @param gw the gateway
+ * @return the costs, or UINT64_MAX in case the gateway is null or has inifinite costs
+ */
+static uint64_t gw_default_getcosts(struct gateway_entry *gw) {
+  struct tc_entry* tc;
 
-  if (v4changed || v6changed) {
-    olsr_gw_default_lookup_gateway(v4changed, v6changed);
+  if (!gw) {
+    return UINT64_MAX;
   }
-}
-
-static void gw_default_delete_handler(struct gateway_entry *gw) {
-  bool isv4, isv6;
 
-  isv4 = gw == olsr_get_ipv4_inet_gateway(NULL);
-  isv6 = gw == olsr_get_ipv6_inet_gateway(NULL);
+  tc = olsr_lookup_tc_entry(&gw->originator);
 
-  if (gw != NULL && (isv4 || isv6)) {
-    olsr_gw_default_lookup_gateway(isv4, isv6);
+  if (!tc || (tc->path_cost == ROUTE_COST_BROKEN) || (!gw->uplink || !gw->downlink)) {
+    /* gateways should not exist without tc entry */
+    /* do not consider nodes with an infinite ETX */
+    /* do not consider nodes without bandwidth or with a uni-directional link */
+    return UINT64_MAX;
   }
+
+  /* determine the path cost */
+  return gw_default_weigh_costs(tc->path_cost, gw->uplink, gw->downlink);
 }
 
+/**
+ * Choose a new gateway
+ *
+ * @param ipv4 lookup new v4 gateway
+ * @param ipv6 lookup new v6 gateway
+ */
 static void gw_default_choosegw_handler(bool ipv4, bool ipv6) {
-  olsr_gw_default_lookup_gateway(ipv4, ipv6);
+  gw_default_lookup_gateway(ipv4, ipv6);
 
-  if (!(gw_def_finished_ipv4 && gw_def_finished_ipv6)) {
+  if (gw_def_choose_new_ipv4_gw || gw_def_choose_new_ipv6_gw) {
     gw_default_startup_handler();
   }
 }
 
 /**
- * initialization of default gateway handler
+ * Update a gateway entry
+ *
+ * @param gw the gateway entry
  */
-void olsr_gw_default_init(void) {
-  /* initialize values */
-  gw_def_timer = NULL;
-  gw_def_finished_ipv4 = false;
-  gw_def_finished_ipv6 = false;
-  gw_def_nodecount = 0;
-  gw_def_stablecount = 0;
-  gw_def_timer = NULL;
-
-  /* setup default handler */
-  olsr_set_inetgw_handler(&gw_def_handler);
+static void gw_default_update_handler(struct gateway_entry *gw) {
+  if (olsr_cnf->smart_gw_thresh == 0) {
+    /* classical behaviour: stick with the chosen gateway unless it changes */
+    bool v4changed = gw && (gw == olsr_get_inet_gateway(false))
+        && (!gw->ipv4 || (gw->ipv4nat && !olsr_cnf->smart_gw_allow_nat));
+    bool v6changed = gw && (gw == olsr_get_inet_gateway(true)) && !gw->ipv6;
+
+    if (v4changed || v6changed) {
+      gw_default_lookup_gateway(v4changed, v6changed);
+    }
+  } else {
+    /* new behaviour: always pick a new gateway */
+    gw_default_lookup_gateway(true, true);
+  }
 }
 
 /**
- * Lookup a new gateway based on distance metric
+ * Remove a gateway entry
  *
- * @param ipv4 lookup new v4 gateway
- * @param ipv6 lookup new v6 gateway
+ * @param gw the gateway entry
  */
-void olsr_gw_default_lookup_gateway(bool ipv4, bool ipv6) {
-  if (ipv4) {
-    /* get new ipv4 GW if we use OLSRv4 or NIIT */
-    gw_def_finished_ipv4 = !(olsr_cnf->ip_version == AF_INET || olsr_cnf->use_niit);
-  }
-  if (ipv6) {
-    /* get new ipv6 GW if we use OLSRv6 */
-    gw_def_finished_ipv6 = !(olsr_cnf->ip_version == AF_INET6);
-  }
+static void gw_default_delete_handler(struct gateway_entry *gw) {
+  bool isv4 = gw && (gw == olsr_get_inet_gateway(false));
+  bool isv6 = gw && (gw == olsr_get_inet_gateway(true));
 
-  if (!(gw_def_finished_ipv4 && gw_def_finished_ipv6)) {
-    gw_default_choose_gateway();
+  if (isv4 || isv6) {
+    gw_default_lookup_gateway(isv4, isv6);
   }
 }
-#endif
+#endif /* __linux__ */