Babel: Revamp cost computation and run route selection when cost change

Also fix several minor bugs and add 'limit' option for k-out-of-j
link sensing strategy. Change default from 8-of-16 to 12-of-16.
Change IHU expiry factor from 1.5 to 3.5 (as in RFC 6126).

3 files changed, 137 insertions, 87 deletions

diff --git a/proto/babel/babel.c b/proto/babel/babel.c
index 0b7ab91b..07c82d91 100644
--- a/proto/babel/babel.c
+++ b/proto/babel/babel.c
@@ -57,6 +57,7 @@ static int  babel_cache_seqno_request(struct babel_proto *p, net_addr *n, u64 ro
 static void babel_trigger_iface_update(struct babel_iface *ifa);
 static void babel_trigger_update(struct babel_proto *p);
 static void babel_send_seqno_request(struct babel_entry *e);
+static void babel_update_cost(struct babel_neighbor *n);
 static inline void babel_kick_timer(struct babel_proto *p);
 static inline void babel_iface_kick_timer(struct babel_iface *ifa);
 
@@ -208,7 +209,7 @@ babel_expire_route(struct babel_route *r)
 
   if (r->metric < BABEL_INFINITY)
   {
-    r->metric = BABEL_INFINITY;
+    r->metric = r->advert_metric = BABEL_INFINITY;
     r->expires = current_time() + r->expiry_interval;
   }
   else
@@ -300,15 +301,20 @@ babel_find_neighbor(struct babel_iface *ifa, ip_addr addr)
 static struct babel_neighbor *
 babel_get_neighbor(struct babel_iface *ifa, ip_addr addr)
 {
+  struct babel_proto *p = ifa->proto;
   struct babel_neighbor *nbr = babel_find_neighbor(ifa, addr);
 
   if (nbr)
     return nbr;
 
+  TRACE(D_EVENTS, "New neighbor %I on %s", addr, ifa->iface->name);
+
   nbr = mb_allocz(ifa->pool, sizeof(struct babel_neighbor));
   nbr->ifa = ifa;
   nbr->addr = addr;
+  nbr->rxcost = BABEL_INFINITY;
   nbr->txcost = BABEL_INFINITY;
+  nbr->cost = BABEL_INFINITY;
   init_list(&nbr->routes);
   add_tail(&ifa->neigh_list, NODE nbr);
 
@@ -316,12 +322,11 @@ babel_get_neighbor(struct babel_iface *ifa, ip_addr addr)
 }
 
 static void
-babel_flush_neighbor(struct babel_neighbor *nbr)
+babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr)
 {
-  struct babel_proto *p = nbr->ifa->proto;
   node *n;
 
-  TRACE(D_EVENTS, "Flushing neighbor %I", nbr->addr);
+  TRACE(D_EVENTS, "Removing neighbor %I on %s", nbr->addr, nbr->ifa->iface->name);
 
   WALK_LIST_FIRST(n, nbr->routes)
   {
@@ -340,24 +345,33 @@ babel_flush_neighbor(struct babel_neighbor *nbr)
 }
 
 static void
-babel_expire_ihu(struct babel_neighbor *nbr)
+babel_expire_ihu(struct babel_proto *p, struct babel_neighbor *nbr)
 {
+  TRACE(D_EVENTS, "IHU from nbr %I on %s expired", nbr->addr, nbr->ifa->iface->name);
+
   nbr->txcost = BABEL_INFINITY;
   nbr->ihu_expiry = 0;
+  babel_update_cost(nbr);
 }
 
 static void
-babel_expire_hello(struct babel_neighbor *nbr)
+babel_expire_hello(struct babel_proto *p, struct babel_neighbor *nbr)
 {
   nbr->hello_map <<= 1;
 
   if (nbr->hello_cnt < 16)
     nbr->hello_cnt++;
 
+  TRACE(D_EVENTS, "Hello from nbr %I on %s expired, %d left",
+	nbr->addr, nbr->ifa->iface->name, u32_popcount(nbr->hello_map));
+
   if (nbr->hello_map)
+  {
     nbr->hello_expiry += nbr->last_hello_int;
+    babel_update_cost(nbr);
+  }
   else
-    babel_flush_neighbor(nbr);
+    babel_flush_neighbor(p, nbr);
 }
 
 static void
@@ -372,10 +386,10 @@ babel_expire_neighbors(struct babel_proto *p)
     WALK_LIST_DELSAFE(nbr, nbx, ifa->neigh_list)
     {
       if (nbr->ihu_expiry && nbr->ihu_expiry <= now_)
-        babel_expire_ihu(nbr);
+        babel_expire_ihu(p, nbr);
 
       if (nbr->hello_expiry && nbr->hello_expiry <= now_)
-        babel_expire_hello(nbr);
+        babel_expire_hello(p, nbr);
     }
   }
 }
@@ -409,66 +423,81 @@ babel_is_feasible(struct babel_source *s, u16 seqno, u16 metric)
     ((seqno == s->seqno) && (metric < s->metric));
 }
 
-static u16
-babel_compute_rxcost(struct babel_neighbor *n)
+/* Simple additive metric - Appendix 3.1 in the RFC */
+static inline u16
+babel_compute_metric(struct babel_neighbor *n, uint metric)
 {
-  struct babel_iface *ifa = n->ifa;
-  u8 cnt, missed;
-  u16 map=n->hello_map;
-
-  if (!map) return BABEL_INFINITY;
-  cnt = u32_popcount(map); // number of bits set
-  missed = n->hello_cnt-cnt;
+  return MIN(metric + n->cost, BABEL_INFINITY);
+}
 
-  if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
-  {
-    /* ETX - Appendix 2.2 in the RFC.
+static void
+babel_update_cost(struct babel_neighbor *nbr)
+{
+  struct babel_proto *p = nbr->ifa->proto;
+  struct babel_iface_config *cf = nbr->ifa->cf;
+  uint rcv = u32_popcount(nbr->hello_map); // number of bits set
+  uint max = nbr->hello_cnt;
+  uint rxcost = BABEL_INFINITY;	/* Cost to announce in IHU */
+  uint txcost = BABEL_INFINITY;	/* Effective cost for route selection */
 
-       beta = prob. of successful transmission.
-       rxcost = BABEL_RXCOST_WIRELESS/beta
+  if (!rcv || !nbr->ifa->up)
+    goto done;
 
-       Since: beta = 1-missed/n->hello_cnt = cnt/n->hello_cnt
-       Then: rxcost = BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt
-   */
-    if (!cnt) return BABEL_INFINITY;
-    return BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt;
-  }
-  else
+  switch (cf->type)
   {
+  case BABEL_IFACE_TYPE_WIRED:
     /* k-out-of-j selection - Appendix 2.1 in the RFC. */
-    DBG("Babel: Missed %d hellos from %I\n", missed, n->addr);
-    /* Link is bad if more than half the expected hellos were lost */
-    return (missed > n->hello_cnt/2) ? BABEL_INFINITY : ifa->cf->rxcost;
-  }
-}
 
+    /* Link is bad if less than cf->limit/16 of expected hellos were received */
+    if (rcv * 16 < cf->limit * max)
+      break;
+
+    rxcost =  cf->rxcost;
+    txcost = nbr->txcost;
+    break;
+
+  case BABEL_IFACE_TYPE_WIRELESS:
+    /*
+     * ETX - Appendix 2.2 in the RFC.
+     *
+     * alpha  = prob. of successful transmission estimated by the neighbor
+     * beta   = prob. of successful transmission estimated by the router
+     * rxcost = nominal rxcost of the router / beta
+     * txcost = nominal rxcost of the neighbor / (alpha * beta)
+     *        = received txcost / beta
+     *
+     * Note that received txcost is just neighbor's rxcost. Beta is rcv/max,
+     * we use inverse values of beta (i.e. max/rcv) to stay in integers.
+     */
+    rxcost = MIN( cf->rxcost * max / rcv, BABEL_INFINITY);
+    txcost = MIN(nbr->txcost * max / rcv, BABEL_INFINITY);
+    break;
+  }
 
-static u16
-babel_compute_cost(struct babel_neighbor *n)
-{
-  struct babel_iface *ifa = n->ifa;
-  u16 rxcost = babel_compute_rxcost(n);
-  if (rxcost == BABEL_INFINITY) return rxcost;
-  else if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
+done:
+  /* If RX cost changed, send IHU with next Hello */
+  if (rxcost != nbr->rxcost)
   {
-    /* ETX - Appendix 2.2 in the RFC */
-    return (MAX(n->txcost, BABEL_RXCOST_WIRELESS) * rxcost)/BABEL_RXCOST_WIRELESS;
+    nbr->rxcost = rxcost;
+    nbr->ihu_cnt = 0;
   }
-  else
+
+  /* If link cost changed, run route selection */
+  if (txcost != nbr->cost)
   {
-    /* k-out-of-j selection - Appendix 2.1 in the RFC. */
-    return n->txcost;
-  }
-}
+    TRACE(D_EVENTS, "Cost of nbr %I on %s changed from %u to %u",
+	  nbr->addr, nbr->ifa->iface->name, nbr->cost, txcost);
 
-/* Simple additive metric - Appendix 3.1 in the RFC */
-static u16
-babel_compute_metric(struct babel_neighbor *n, uint metric)
-{
-  metric += babel_compute_cost(n);
-  return MIN(metric, BABEL_INFINITY);
-}
+    nbr->cost = txcost;
 
+    struct babel_route *r; node *n;
+    WALK_LIST2(r, n, nbr->routes, neigh_route)
+    {
+      r->metric = babel_compute_metric(nbr, r->advert_metric);
+      babel_select_route(r->e);
+    }
+  }
+}
 
 /**
  * babel_announce_rte - announce selected route to the core
@@ -506,6 +535,7 @@ babel_announce_rte(struct babel_proto *p, struct babel_entry *e)
     rte->u.babel.router_id = r->router_id;
     rte->pflags = 0;
 
+    r->old_metric = r->metric;
     rte_update2(c, e->n.addr, rte, p->p.main_source);
   }
   else
@@ -535,7 +565,7 @@ static void
 babel_select_route(struct babel_entry *e)
 {
   struct babel_proto *p = e->proto;
-  struct babel_route *r, *cur = e->selected_in;
+  struct babel_route *r, *cur = e->selected_in, *best = e->selected_in;
 
   /* try to find the best feasible route */
   WALK_LIST(r, e->routes)
@@ -544,12 +574,12 @@ babel_select_route(struct babel_entry *e)
         babel_is_feasible(babel_find_source(e, r->router_id), r->seqno, r->advert_metric))
       cur = r;
 
-  if (cur && !OUR_ROUTE(cur) &&
-      ((!e->selected_in && cur->metric < BABEL_INFINITY) ||
-       (e->selected_in && cur->metric < e->selected_in->metric)))
+  if (cur && !OUR_ROUTE(cur) && (cur->metric < BABEL_INFINITY) &&
+      (!best || (cur->metric < best->metric) || ((cur == best) && (cur->metric != cur->old_metric))))
   {
-    TRACE(D_EVENTS, "Picked new route for prefix %N: router id %lR metric %d",
-	  e->n.addr, cur->router_id, cur->metric);
+    if (cur != best)
+      TRACE(D_EVENTS, "Picked new route for prefix %N: router id %lR metric %d",
+	    e->n.addr, cur->router_id, cur->metric);
 
     e->selected_in = cur;
     e->updated = current_time();
@@ -564,10 +594,9 @@ babel_select_route(struct babel_entry *e)
        babel_build_rte() will set the unreachable flag if the metric is BABEL_INFINITY.*/
     if (e->selected_in)
     {
-      TRACE(D_EVENTS, "Lost feasible route for prefix %N",
-	    e->n.addr);
+      TRACE(D_EVENTS, "Lost feasible route for prefix %N", e->n.addr);
 
-      e->selected_in->metric = BABEL_INFINITY;
+      e->selected_in->metric = e->selected_in->advert_metric = BABEL_INFINITY;
       e->updated = current_time();
 
       babel_send_seqno_request(e);
@@ -583,7 +612,7 @@ babel_select_route(struct babel_entry *e)
       /* No route currently selected, and no new one selected; this means we
 	 don't have a route to this destination anymore (and were probably
 	 called from an expiry timer). Remove the route from the nest. */
-      TRACE(D_EVENTS, "Flushing route for prefix %N", e->n.addr);
+      // TRACE(D_EVENTS, "Flushing route for prefix %N", e->n.addr);
 
       e->selected_in = NULL;
       e->updated = current_time();
@@ -617,7 +646,7 @@ babel_build_ihu(union babel_msg *msg, struct babel_iface *ifa, struct babel_neig
 
   msg->type = BABEL_TLV_IHU;
   msg->ihu.addr = n->addr;
-  msg->ihu.rxcost = babel_compute_rxcost(n);
+  msg->ihu.rxcost = n->rxcost;
   msg->ihu.interval = ifa->cf->ihu_interval;
 
   TRACE(D_PACKETS, "Sending IHU for %I with rxcost %d interval %t",
@@ -630,6 +659,7 @@ babel_send_ihu(struct babel_iface *ifa, struct babel_neighbor *n)
   union babel_msg msg = {};
   babel_build_ihu(&msg, ifa, n);
   babel_send_unicast(&msg, ifa, n->addr);
+  n->ihu_cnt = BABEL_IHU_INTERVAL_FACTOR;
 }
 
 static void
@@ -638,14 +668,18 @@ babel_send_ihus(struct babel_iface *ifa)
   struct babel_neighbor *n;
   WALK_LIST(n, ifa->neigh_list)
   {
-    union babel_msg msg = {};
-    babel_build_ihu(&msg, ifa, n);
-    babel_enqueue(&msg, ifa);
+    if (n->hello_cnt && (--n->ihu_cnt <= 0))
+    {
+      union babel_msg msg = {};
+      babel_build_ihu(&msg, ifa, n);
+      babel_enqueue(&msg, ifa);
+      n->ihu_cnt = BABEL_IHU_INTERVAL_FACTOR;
+    }
   }
 }
 
 static void
-babel_send_hello(struct babel_iface *ifa, u8 send_ihu)
+babel_send_hello(struct babel_iface *ifa)
 {
   struct babel_proto *p = ifa->proto;
   union babel_msg msg = {};
@@ -659,8 +693,7 @@ babel_send_hello(struct babel_iface *ifa, u8 send_ihu)
 
   babel_enqueue(&msg, ifa);
 
-  if (send_ihu)
-    babel_send_ihus(ifa);
+  babel_send_ihus(ifa);
 }
 
 static void
@@ -907,7 +940,7 @@ babel_update_hello_history(struct babel_neighbor *n, u16 seqno, uint interval)
 
   u16 delta = ((uint) seqno - (uint) n->next_hello_seqno);
 
-  if (delta == 0)
+  if ((delta == 0) || (n->hello_cnt == 0))
   {
     /* Do nothing */
   }
@@ -934,6 +967,8 @@ babel_update_hello_history(struct babel_neighbor *n, u16 seqno, uint interval)
   n->hello_map = (n->hello_map << 1) | 1;
   n->next_hello_seqno = seqno+1;
   if (n->hello_cnt < 16) n->hello_cnt++;
+
+  /* Update expiration */
   n->hello_expiry = current_time() + BABEL_HELLO_EXPIRY_FACTOR(interval);
   n->last_hello_int = interval;
 }
@@ -1041,8 +1076,13 @@ babel_handle_hello(union babel_msg *m, struct babel_iface *ifa)
 	msg->seqno, (btime) msg->interval);
 
   struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
+  int first_hello = !n->hello_cnt;
+
   babel_update_hello_history(n, msg->seqno, msg->interval);
-  if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
+  babel_update_cost(n);
+
+  /* Speed up session establishment by sending IHU immediately */
+  if (first_hello)
     babel_send_ihu(ifa, n);
 }
 
@@ -1062,6 +1102,7 @@ babel_handle_ihu(union babel_msg *m, struct babel_iface *ifa)
   struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
   n->txcost = msg->rxcost;
   n->ihu_expiry = current_time() + BABEL_IHU_EXPIRY_FACTOR(msg->interval);
+  babel_update_cost(n);
 }
 
 /**
@@ -1159,7 +1200,7 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa)
       WALK_LIST(n, nbr->routes)
       {
 	r = SKIP_BACK(struct babel_route, neigh_route, n);
-	r->metric = BABEL_INFINITY;
+	r->metric = r->advert_metric = BABEL_INFINITY;
 	babel_select_route(r->e);
       }
     }
@@ -1176,7 +1217,7 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa)
       if (!r)
 	return;
 
-      r->metric = BABEL_INFINITY;
+      r->metric = r->advert_metric = BABEL_INFINITY;
       babel_select_route(e);
     }
 
@@ -1215,7 +1256,7 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa)
       return;
 
     /* Treat as retraction */
-    r->metric = BABEL_INFINITY;
+    r->metric = r->advert_metric = BABEL_INFINITY;
   }
   else
   {
@@ -1347,8 +1388,7 @@ babel_iface_timer(timer *t)
 
   if (now_ >= ifa->next_hello)
   {
-    babel_send_hello(ifa, (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS ||
-                           ifa->hello_seqno % BABEL_IHU_INTERVAL_FACTOR == 0));
+    babel_send_hello(ifa);
     ifa->next_hello += hello_period * (1 + (now_ - ifa->next_hello) / hello_period);
   }
 
@@ -1395,7 +1435,7 @@ babel_iface_start(struct babel_iface *ifa)
   tm2_start(ifa->timer, 100 MS);
   ifa->up = 1;
 
-  babel_send_hello(ifa, 0);
+  babel_send_hello(ifa);
   babel_send_wildcard_retraction(ifa);
   babel_send_wildcard_request(ifa);
   babel_send_update(ifa, 0);	/* Full update */
@@ -1422,9 +1462,11 @@ babel_iface_stop(struct babel_iface *ifa)
     WALK_LIST(n, nbr->routes)
     {
       r = SKIP_BACK(struct babel_route, neigh_route, n);
-      r->metric = BABEL_INFINITY;
+      r->metric = r->advert_metric = BABEL_INFINITY;
       r->expires = now_ + r->expiry_interval;
-      babel_select_route(r->e);
+
+      if (r == r->e->selected_in)
+	babel_select_route(r->e);
     }
   }
 
@@ -1551,7 +1593,7 @@ babel_remove_iface(struct babel_proto *p, struct babel_iface *ifa)
 
   struct babel_neighbor *n;
   WALK_LIST_FIRST(n, ifa->neigh_list)
-    babel_flush_neighbor(n);
+    babel_flush_neighbor(p, n);
 
   rem_node(NODE ifa);
 
@@ -1871,7 +1913,7 @@ babel_show_neighbors(struct proto *P, char *iff)
       uint hellos = u32_popcount(n->hello_map);
       btime timer = n->hello_expiry - current_time();
       cli_msg(-1024, "%-25I %-10s %6u %6u %6u %7t",
-	      n->addr, ifa->iface->name, n->txcost, rts, hellos, MAX(timer, 0));
+	      n->addr, ifa->iface->name, n->cost, rts, hellos, MAX(timer, 0));
     }
   }
 
diff --git a/proto/babel/babel.h b/proto/babel/babel.h
index d0c159f9..78841254 100644
--- a/proto/babel/babel.h
+++ b/proto/babel/babel.h
@@ -34,9 +34,10 @@
 
 #define BABEL_HELLO_INTERVAL_WIRED	(4 S_)	/* Default hello intervals in seconds */
 #define BABEL_HELLO_INTERVAL_WIRELESS	(4 S_)
+#define BABEL_HELLO_LIMIT		12
 #define BABEL_UPDATE_INTERVAL_FACTOR	4
 #define BABEL_IHU_INTERVAL_FACTOR	3
-#define BABEL_IHU_EXPIRY_FACTOR(X)	((btime)(X)*3/2)	/* 1.5 */
+#define BABEL_IHU_EXPIRY_FACTOR(X)	((btime)(X)*7/2)	/* 3.5 */
 #define BABEL_HELLO_EXPIRY_FACTOR(X)	((btime)(X)*3/2)	/* 1.5 */
 #define BABEL_ROUTE_EXPIRY_FACTOR(X)	((btime)(X)*7/2)	/* 3.5 */
 #define BABEL_ROUTE_REFRESH_INTERVAL	(2 S_)	/* Time before route expiry to send route request */
@@ -112,6 +113,7 @@ struct babel_iface_config {
 
   u16 rxcost;
   u8 type;
+  u8 limit;				/* Minimum number of Hellos to keep link up */
   u8 check_link;
   uint port;
   uint hello_interval;			/* Hello interval, in us */
@@ -188,7 +190,10 @@ struct babel_neighbor {
   struct babel_iface *ifa;
 
   ip_addr addr;
-  u16 txcost;
+  u16 rxcost;				/* Sent in last IHU */
+  u16 txcost;				/* Received in last IHU */
+  u16 cost;				/* Computed neighbor cost */
+  s8 ihu_cnt;				/* IHU countdown, 0 to send it */
   u8 hello_cnt;
   u16 hello_map;
   u16 next_hello_seqno;
@@ -218,6 +223,7 @@ struct babel_route {
   u16 seqno;
   u16 advert_metric;
   u16 metric;
+  u16 old_metric;
   u64 router_id;
   ip_addr next_hop;
   btime refresh_time;
diff --git a/proto/babel/config.Y b/proto/babel/config.Y
index 27c50676..c72c00a3 100644
--- a/proto/babel/config.Y
+++ b/proto/babel/config.Y
@@ -56,6 +56,7 @@ babel_iface_start:
   init_list(&this_ipatt->ipn_list);
   BABEL_IFACE->port = BABEL_PORT;
   BABEL_IFACE->type = BABEL_IFACE_TYPE_WIRED;
+  BABEL_IFACE->limit = BABEL_HELLO_LIMIT;
   BABEL_IFACE->tx_tos = IP_PREC_INTERNET_CONTROL;
   BABEL_IFACE->tx_priority = sk_priority_control;
   BABEL_IFACE->check_link = 1;
@@ -89,6 +90,7 @@ babel_iface_finish:
 babel_iface_item:
  | PORT expr { BABEL_IFACE->port = $2; if (($2<1) || ($2>65535)) cf_error("Invalid port number"); }
  | RXCOST expr { BABEL_IFACE->rxcost = $2; if (($2<1) || ($2>65535)) cf_error("Invalid rxcost"); }
+ | LIMIT expr { BABEL_IFACE->limit = $2; if (($2<1) || ($2>16)) cf_error("Limit must be in range 1-16"); }
  | TYPE WIRED { BABEL_IFACE->type = BABEL_IFACE_TYPE_WIRED; }
  | TYPE WIRELESS { BABEL_IFACE->type = BABEL_IFACE_TYPE_WIRELESS; }
  | HELLO INTERVAL expr_us { BABEL_IFACE->hello_interval = $3; if (($3<BABEL_MIN_INTERVAL) || ($3>BABEL_MAX_INTERVAL)) cf_error("Hello interval must be in range 10 ms - 655 s"); }