babeld: babelz merge.

Babelz is the last version of the stand-alone babel daemon. In
particular, it use multiple channels to diminuate
interferences. Please refer to this one for more details.

15 files changed, 792 insertions, 317 deletions

diff --git a/babeld/babel_interface.c b/babeld/babel_interface.c
index e403cce0..1c8c8868 100644
--- a/babeld/babel_interface.c
+++ b/babeld/babel_interface.c
@@ -456,6 +456,30 @@ interface_idle(babel_interface_nfo *babel_ifp)
             babel_ifp->activity_time < babel_now.tv_sec - idle_time);
 }
 
+int
+update_hello_interval(struct interface *ifp)
+{
+    int rc = 0;
+    unsigned short interval;
+    struct babel_interface *babel_ifp = babel_get_if_nfo(ifp);
+
+    if(interface_idle(babel_ifp))
+        interval = idle_hello_interval;
+    else if(IF_CONF(ifp, hello_interval) > 0)
+        interval = IF_CONF(ifp, hello_interval);
+    else if((ifp->flags & BABEL_IF_WIRED))
+        interval = wired_hello_interval;
+    else
+        interval = wireless_hello_interval;
+
+    if(babel_ifp->hello_interval != interval) {
+        babel_ifp->hello_interval = interval;
+        rc = 1;
+    }
+
+    return rc;
+}
+
 /* This should be no more than half the hello interval, so that hellos
    aren't sent late.  The result is in milliseconds. */
 unsigned
@@ -560,10 +584,11 @@ interface_recalculate(struct interface *ifp)
     update_interface_metric(ifp);
 
     debugf(BABEL_DEBUG_COMMON,
-           "Upped network %s (%s, cost=%d%s).",
+           "Upped interface %s (%s, cost=%d, channel=%d%s).",
            ifp->name,
            (babel_ifp->flags & BABEL_IF_WIRED) ? "wired" : "wireless",
            babel_ifp->cost,
+           babel_ifp->channel,
            babel_ifp->ipv4 ? ", IPv4" : "");
 
     if(rc > 0)
@@ -777,19 +802,41 @@ DEFUN (show_babel_neighbour,
 }
 
 static void
-show_babel_routes_sub (struct vty *vty, struct babel_route *route)
+show_babel_routes_sub (struct babel_route *route, void *closure)
 {
+    struct vty *vty = (struct vty*) closure;
     const unsigned char *nexthop =
         memcmp(route->nexthop, route->neigh->address, 16) == 0 ?
         NULL : route->nexthop;
+    char channels[100];
+
+    if(route->channels[0] == 0)
+        channels[0] = '\0';
+    else {
+        int k, j = 0;
+        snprintf(channels, 100, " chan (");
+        j = strlen(channels);
+        for(k = 0; k < DIVERSITY_HOPS; k++) {
+            if(route->channels[k] == 0)
+                break;
+            if(k > 0)
+                channels[j++] = ',';
+            snprintf(channels + j, 100 - j, "%d", route->channels[k]);
+            j = strlen(channels);
+        }
+        snprintf(channels + j, 100 - j, ")");
+        if(k == 0)
+            channels[0] = '\0';
+    }
 
     vty_out(vty,
-            "%s metric %d refmetric %d id %s seqno %d age %d "
+            "%s metric %d refmetric %d id %s seqno %d%s age %d "
             "via %s neigh %s%s%s%s%s",
             format_prefix(route->src->prefix, route->src->plen),
             route_metric(route), route->refmetric,
             format_eui64(route->src->id),
             (int)route->seqno,
+            channels,
             (int)(babel_now.tv_sec - route->time),
             route->neigh->ifp->name,
             format_address(route->neigh->address),
@@ -801,11 +848,12 @@ show_babel_routes_sub (struct vty *vty, struct babel_route *route)
 }
 
 static void
-show_babel_xroutes_sub (struct vty *vty, struct xroute *xroute)
+show_babel_xroutes_sub (struct xroute *xroute, void *closure)
 {
+    struct vty *vty = (struct vty *) closure;
     vty_out(vty, "%s metric %d (exported)%s",
-            format_prefix(xroutes->prefix, xroute->plen),
-            xroutes->metric,
+            format_prefix(xroute->prefix, xroute->plen),
+            xroute->metric,
             VTY_NEWLINE);
 }
 
@@ -818,15 +866,8 @@ DEFUN (show_babel_database,
        "Database information\n"
        "No attributes\n")
 {
-    int i;
-
-    for(i = 0; i < numroutes; i++) {
-        show_babel_routes_sub(vty, &routes[i]);
-    }
-    for(i = 0; i < numxroutes; i++) {
-        show_babel_xroutes_sub(vty, &xroutes[i]);
-    }
-
+    for_all_routes(show_babel_routes_sub, vty);
+    for_all_xroutes(show_babel_xroutes_sub, vty);
     return CMD_SUCCESS;
 }
 
@@ -950,6 +991,7 @@ babel_interface_allocate (void)
     babel_ifp->bucket = BUCKET_TOKENS_MAX;
     babel_ifp->hello_seqno = (random() & 0xFFFF);
     babel_ifp->hello_interval = BABELD_DEFAULT_HELLO_INTERVAL;
+    babel_ifp->channel = BABEL_IF_CHANNEL_INTERFERING;
 
     return babel_ifp;
 }
diff --git a/babeld/babel_interface.h b/babeld/babel_interface.h
index d9fb9a4a..5b551fbe 100644
--- a/babeld/babel_interface.h
+++ b/babeld/babel_interface.h
@@ -42,10 +42,15 @@ THE SOFTWARE.
 #include <zebra.h>
 #include "zclient.h"
 
+#define CONFIG_DEFAULT 0
+#define CONFIG_NO 1
+#define CONFIG_YES 2
+
 /* babeld interface informations */
 struct babel_interface {
     unsigned short flags;                     /* see below */
     unsigned short cost;
+    int channel;
     struct timeval hello_timeout;
     struct timeval update_timeout;
     struct timeval flush_timeout;
@@ -67,6 +72,7 @@ struct babel_interface {
     time_t bucket_time;
     unsigned int bucket;
     time_t activity_time;
+    time_t last_update_time;
     unsigned short hello_seqno;
     unsigned hello_interval;
     unsigned update_interval;
@@ -85,12 +91,20 @@ static inline babel_interface_nfo* babel_get_if_nfo(struct interface *ifp)
     return ((babel_interface_nfo*) ifp->info);
 }
 
+#define IF_CONF(_ifp, _field) babel_get_if_nfo(_ifp)->_field
+
 /* babel_interface_nfo flags */
+#define BABEL_IF_IS_UP         (1 << 0)
 #define BABEL_IF_WIRED         (1 << 1)
 #define BABEL_IF_SPLIT_HORIZON (1 << 2)
 #define BABEL_IF_LQ            (1 << 3)
-#define BABEL_IF_IS_ENABLE     (1 << 4)
-#define BABEL_IF_IS_UP         (1 << 5)
+#define BABEL_IF_FARAWAY       (1 << 4)
+#define BABEL_IF_IS_ENABLE     (1 << 7)
+
+/* Only INTERFERING can appear on the wire. */
+#define BABEL_IF_CHANNEL_UNKNOWN 0
+#define BABEL_IF_CHANNEL_INTERFERING 255
+#define BABEL_IF_CHANNEL_NONINTERFERING -2
 
 static inline int
 if_up(struct interface *ifp)
@@ -133,6 +147,7 @@ int babel_interface_address_delete (int, struct zclient *, zebra_size_t);
 
 /* others functions */
 int interface_idle(babel_interface_nfo *);
+int update_hello_interval(struct interface *ifp);
 unsigned jitter(babel_interface_nfo *, int);
 unsigned update_jitter(babel_interface_nfo *babel_ifp, int urgent);
 /* return "true" if "address" is one of our ipv6 addresses */
diff --git a/babeld/babel_main.c b/babeld/babel_main.c
index 159ba656..4d6f60eb 100644
--- a/babeld/babel_main.c
+++ b/babeld/babel_main.c
@@ -482,7 +482,7 @@ babel_exit_properly(void)
 
     /* Uninstall and flush all routes. */
     debugf(BABEL_DEBUG_COMMON, "Uninstall routes.");
-    babel_uninstall_all_routes();
+    flush_all_routes();
     babel_interface_close_all();
     babel_zebra_close_connexion();
     babel_save_state_file();
diff --git a/babeld/babeld.c b/babeld/babeld.c
index 0cf8c8a1..d69662c0 100644
--- a/babeld/babeld.c
+++ b/babeld/babeld.c
@@ -269,7 +269,7 @@ babel_initial_noise(void)
 static void
 babel_clean_routing_process()
 {
-    babel_uninstall_all_routes();
+    flush_all_routes();
     babel_interface_close_all();
 
     /* cancel threads */
diff --git a/babeld/message.c b/babeld/message.c
index 92c416b9..8cd1db63 100644
--- a/babeld/message.c
+++ b/babeld/message.c
@@ -69,6 +69,8 @@ struct timeval unicast_flush_timeout = {0, 0};
 static const unsigned char v4prefix[16] =
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0, 0, 0, 0 };
 
+/* Parse a network prefix, encoded in the somewhat baroque compressed
+   representation used by Babel.  Return the number of bytes parsed. */
 static int
 network_prefix(int ae, int plen, unsigned int omitted,
                const unsigned char *p, const unsigned char *dp,
@@ -76,6 +78,7 @@ network_prefix(int ae, int plen, unsigned int omitted,
 {
     unsigned pb;
     unsigned char prefix[16];
+    int ret = -1;
 
     if(plen >= 0)
         pb = (plen + 7) / 8;
@@ -90,7 +93,9 @@ network_prefix(int ae, int plen, unsigned int omitted,
     memset(prefix, 0, 16);
 
     switch(ae) {
-    case 0: break;
+    case 0:
+        ret = 0;
+        break;
     case 1:
         if(omitted > 4 || pb > 4 || (pb > omitted && len < pb - omitted))
             return -1;
@@ -100,6 +105,7 @@ network_prefix(int ae, int plen, unsigned int omitted,
             memcpy(prefix, dp, 12 + omitted);
         }
         if(pb > omitted) memcpy(prefix + 12 + omitted, p, pb - omitted);
+        ret = pb - omitted;
         break;
     case 2:
         if(omitted > 16 || (pb > omitted && len < pb - omitted)) return -1;
@@ -108,19 +114,68 @@ network_prefix(int ae, int plen, unsigned int omitted,
             memcpy(prefix, dp, omitted);
         }
         if(pb > omitted) memcpy(prefix + omitted, p, pb - omitted);
+        ret = pb - omitted;
         break;
     case 3:
         if(pb > 8 && len < pb - 8) return -1;
         prefix[0] = 0xfe;
         prefix[1] = 0x80;
         if(pb > 8) memcpy(prefix + 8, p, pb - 8);
+        ret = pb - 8;
         break;
     default:
         return -1;
     }
 
     mask_prefix(p_r, prefix, plen < 0 ? 128 : ae == 1 ? plen + 96 : plen);
-    return 1;
+    return ret;
+}
+
+static void
+parse_route_attributes(const unsigned char *a, int alen,
+                       unsigned char *channels)
+{
+    int type, len, i = 0;
+
+    while(i < alen) {
+        type = a[i];
+        if(type == 0) {
+            i++;
+            continue;
+        }
+
+        if(i + 1 > alen) {
+            fprintf(stderr, "Received truncated attributes.\n");
+            return;
+        }
+        len = a[i + 1];
+        if(i + len > alen) {
+            fprintf(stderr, "Received truncated attributes.\n");
+            return;
+        }
+
+        if(type == 1) {
+            /* Nothing. */
+        } else if(type == 2) {
+            if(len > DIVERSITY_HOPS) {
+                fprintf(stderr,
+                        "Received overlong channel information (%d > %d).\n",
+                        len, DIVERSITY_HOPS);
+                len = DIVERSITY_HOPS;
+            }
+            if(memchr(a + i + 2, 0, len) != NULL) {
+                /* 0 is reserved. */
+                fprintf(stderr, "Channel information contains 0!");
+                return;
+            }
+            memset(channels, 0, DIVERSITY_HOPS);
+            memcpy(channels, a + i + 2, len);
+        } else {
+            fprintf(stderr, "Received unknown route attribute %d.\n", type);
+        }
+
+        i += len + 2;
+    }
 }
 
 static int
@@ -130,6 +185,13 @@ network_address(int ae, const unsigned char *a, unsigned int len,
     return network_prefix(ae, -1, 0, a, NULL, len, a_r);
 }
 
+static int
+channels_len(unsigned char *channels)
+{
+    unsigned char *p = memchr(channels, 0, DIVERSITY_HOPS);
+    return p ? (p - channels) : DIVERSITY_HOPS;
+}
+
 void
 parse_packet(const unsigned char *from, struct interface *ifp,
              const unsigned char *packet, int packetlen)
@@ -284,8 +346,9 @@ parse_packet(const unsigned char *from, struct interface *ifp,
         } else if(type == MESSAGE_UPDATE) {
             unsigned char prefix[16], *nh;
             unsigned char plen;
+            unsigned char channels[DIVERSITY_HOPS];
             unsigned short interval, seqno, metric;
-            int rc;
+            int rc, parsed_len;
             if(len < 10) {
                 if(len < 2 || message[3] & 0x80)
                     have_v4_prefix = have_v6_prefix = 0;
@@ -307,6 +370,7 @@ parse_packet(const unsigned char *from, struct interface *ifp,
                     have_v4_prefix = have_v6_prefix = 0;
                 goto fail;
             }
+            parsed_len = 10 + rc;
 
             plen = message[4] + (message[2] == 1 ? 96 : 0);
 
@@ -360,8 +424,27 @@ parse_packet(const unsigned char *from, struct interface *ifp,
                     goto done;
             }
 
+            if((ifp->flags & BABEL_IF_FARAWAY)) {
+                channels[0] = 0;
+            } else {
+                /* This will be overwritten by parse_route_attributes below. */
+                if(metric < 256) {
+                    /* Assume non-interfering (wired) link. */
+                    channels[0] = 0;
+                } else {
+                    /* Assume interfering. */
+                    channels[0] = BABEL_IF_CHANNEL_INTERFERING;
+                    channels[1] = 0;
+                }
+
+                if(parsed_len < len)
+                    parse_route_attributes(message + 2 + parsed_len,
+                                           len - parsed_len, channels);
+            }
+
             update_route(router_id, prefix, plen, seqno, metric, interval,
-                         neigh, nh);
+                         neigh, nh,
+                         channels, channels_len(channels));
         } else if(type == MESSAGE_REQUEST) {
             unsigned char prefix[16], plen;
             int rc;
@@ -374,10 +457,17 @@ parse_packet(const unsigned char *from, struct interface *ifp,
                    message[2] == 0 ? "any" : format_prefix(prefix, plen),
                    format_address(from), ifp->name);
             if(message[2] == 0) {
+                struct babel_interface *babel_ifp =babel_get_if_nfo(neigh->ifp);
                 /* If a neighbour is requesting a full route dump from us,
                    we might as well send it an IHU. */
                 send_ihu(neigh, NULL);
-                send_update(neigh->ifp, 0, NULL, 0);
+                /* Since nodes send wildcard requests on boot, booting
+                   a large number of nodes at the same time may cause an
+                   update storm.  Ignore a wildcard request that happens
+                   shortly after we sent a full update. */
+                if(babel_ifp->last_update_time <
+                   babel_now.tv_sec - MAX(babel_ifp->hello_interval / 100, 1))
+                    send_update(neigh->ifp, 0, NULL, 0);
             } else {
                 send_update(neigh->ifp, 0, prefix, plen);
             }
@@ -665,10 +755,12 @@ send_hello_noupdate(struct interface *ifp, unsigned interval)
 void
 send_hello(struct interface *ifp)
 {
+    int changed;
+    changed = update_hello_interval(ifp);
     babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
     send_hello_noupdate(ifp, (babel_ifp->hello_interval + 9) / 10);
     /* Send full IHU every 3 hellos, and marginal IHU each time */
-    if(babel_ifp->hello_seqno % 3 == 0)
+    if(changed || babel_ifp->hello_seqno % 3 == 0)
         send_ihu(NULL, ifp);
     else
         send_marginal_ihu(ifp);
@@ -724,12 +816,19 @@ static void
 really_send_update(struct interface *ifp,
                    const unsigned char *id,
                    const unsigned char *prefix, unsigned char plen,
-                   unsigned short seqno, unsigned short metric)
+                   unsigned short seqno, unsigned short metric,
+                   unsigned char *channels, int channels_len)
 {
     babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
     int add_metric, v4, real_plen, omit = 0;
     const unsigned char *real_prefix;
     unsigned short flags = 0;
+    int channels_size;
+
+    if(diversity_kind != DIVERSITY_CHANNEL)
+        channels_len = -1;
+
+    channels_size = channels_len >= 0 ? channels_len + 2 : 0;
 
     if(!if_up(ifp))
         return;
@@ -786,7 +885,8 @@ really_send_update(struct interface *ifp,
         babel_ifp->have_buffered_id = 1;
     }
 
-    start_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit);
+    start_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit +
+                  channels_size);
     accumulate_byte(ifp, v4 ? 1 : 2);
     accumulate_byte(ifp, flags);
     accumulate_byte(ifp, real_plen);
@@ -795,7 +895,14 @@ really_send_update(struct interface *ifp,
     accumulate_short(ifp, seqno);
     accumulate_short(ifp, metric);
     accumulate_bytes(ifp, real_prefix + omit, (real_plen + 7) / 8 - omit);
-    end_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit);
+    /* Note that an empty channels TLV is different from no such TLV. */
+    if(channels_len >= 0) {
+        accumulate_byte(ifp, 2);
+        accumulate_byte(ifp, channels_len);
+        accumulate_bytes(ifp, channels, channels_len);
+    }
+    end_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit +
+                channels_size);
 
     if(flags & 0x80) {
         memcpy(babel_ifp->buffered_prefix, prefix, 16);
@@ -884,9 +991,6 @@ flushupdates(struct interface *ifp)
         qsort(b, n, sizeof(struct buffered_update), compare_buffered_updates);
 
         for(i = 0; i < n; i++) {
-            unsigned short seqno;
-            unsigned short metric;
-
             /* The same update may be scheduled multiple times before it is
                sent out.  Since our buffer is now sorted, it is enough to
                compare with the previous update. */
@@ -903,22 +1007,51 @@ flushupdates(struct interface *ifp)
             if(xroute && (!route || xroute->metric <= kernel_metric)) {
                 really_send_update(ifp, myid,
                                    xroute->prefix, xroute->plen,
-                                   myseqno, xroute->metric);
+                                   myseqno, xroute->metric,
+                                   NULL, 0);
                 last_prefix = xroute->prefix;
                 last_plen = xroute->plen;
             } else if(route) {
+                unsigned char channels[DIVERSITY_HOPS];
+                int chlen;
+                struct interface *route_ifp = route->neigh->ifp;
+                struct babel_interface *babel_route_ifp = NULL;
+                unsigned short metric;
+                unsigned short seqno;
+
                 seqno = route->seqno;
-                metric = route_metric(route);
+                metric =
+                    route_interferes(route, ifp) ?
+                    route_metric(route) :
+                    route_metric_noninterfering(route);
+
                 if(metric < INFINITY)
                     satisfy_request(route->src->prefix, route->src->plen,
                                     seqno, route->src->id, ifp);
                 if((babel_ifp->flags & BABEL_IF_SPLIT_HORIZON) &&
                    route->neigh->ifp == ifp)
                     continue;
+
+                babel_route_ifp = babel_get_if_nfo(route_ifp);
+                if(babel_route_ifp->channel ==BABEL_IF_CHANNEL_NONINTERFERING) {
+                    memcpy(channels, route->channels, DIVERSITY_HOPS);
+                } else {
+                    if(babel_route_ifp->channel == BABEL_IF_CHANNEL_UNKNOWN)
+                        channels[0] = BABEL_IF_CHANNEL_INTERFERING;
+                    else {
+                        assert(babel_route_ifp->channel > 0 &&
+                               babel_route_ifp->channel <= 255);
+                        channels[0] = babel_route_ifp->channel;
+                    }
+                    memcpy(channels + 1, route->channels, DIVERSITY_HOPS - 1);
+                }
+
+                chlen = channels_len(channels);
                 really_send_update(ifp, route->src->id,
                                    route->src->prefix,
                                    route->src->plen,
-                                   seqno, metric);
+                                   seqno, metric,
+                                   channels, chlen);
                 update_source(route->src, seqno, metric);
                 last_prefix = route->src->prefix;
                 last_plen = route->src->plen;
@@ -926,7 +1059,7 @@ flushupdates(struct interface *ifp)
             /* There's no route for this prefix.  This can happen shortly
                after an xroute has been retracted, so send a retraction. */
                 really_send_update(ifp, myid, b[i].prefix, b[i].plen,
-                                   myseqno, INFINITY);
+                                   myseqno, INFINITY, NULL, -1);
             }
         }
         schedule_flush_now(ifp);
@@ -961,12 +1094,17 @@ buffer_update(struct interface *ifp,
     if(babel_ifp->update_bufsize == 0) {
         int n;
         assert(babel_ifp->buffered_updates == NULL);
-        n = MAX(babel_ifp->bufsize / 16, 4);
+        /* Allocate enough space to hold a full update.  Since the
+           number of installed routes will grow over time, make sure we
+           have enough space to send a full-ish frame. */
+        n = installed_routes_estimate() + xroutes_estimate() + 4;
+        n = MAX(n, babel_ifp->bufsize / 16);
     again:
         babel_ifp->buffered_updates = malloc(n *sizeof(struct buffered_update));
         if(babel_ifp->buffered_updates == NULL) {
             zlog_err("malloc(buffered_updates): %s", safe_strerror(errno));
             if(n > 4) {
+                /* Try again with a tiny buffer. */
                 n = 4;
                 goto again;
             }
@@ -982,12 +1120,18 @@ buffer_update(struct interface *ifp,
     babel_ifp->num_buffered_updates++;
 }
 
+static void
+buffer_update_callback(struct babel_route *route, void *closure)
+{
+    buffer_update((struct interface*)closure,
+                  route->src->prefix, route->src->plen);
+}
+
 void
 send_update(struct interface *ifp, int urgent,
             const unsigned char *prefix, unsigned char plen)
 {
     babel_interface_nfo *babel_ifp = NULL;
-    int i;
 
     if(ifp == NULL) {
       struct interface *ifp_aux;
@@ -1020,15 +1164,13 @@ send_update(struct interface *ifp, int urgent,
         if(!interface_idle(babel_ifp)) {
             send_self_update(ifp);
             if(!parasitic) {
-                debugf(BABEL_DEBUG_COMMON,"Sending update to %s for any.", ifp->name);
-                for(i = 0; i < numroutes; i++)
-                    if(routes[i].installed)
-                        buffer_update(ifp,
-                                      routes[i].src->prefix,
-                                      routes[i].src->plen);
+                debugf(BABEL_DEBUG_COMMON,"Sending update to %s for any.",
+                       ifp->name);
+                for_all_installed_routes(buffer_update_callback, ifp);
             }
         }
         set_timeout(&babel_ifp->update_timeout, babel_ifp->update_interval);
+        babel_ifp->last_update_time = babel_now.tv_sec;
     }
     schedule_update_flush(ifp, urgent);
 }
@@ -1086,11 +1228,16 @@ update_myseqno()
     seqno_time = babel_now;
 }
 
+static void
+send_xroute_update_callback(struct xroute *xroute, void *closure)
+{
+    struct interface *ifp = (struct interface*)closure;
+    send_update(ifp, 0, xroute->prefix, xroute->plen);
+}
+
 void
 send_self_update(struct interface *ifp)
 {
-    int i;
-
     if(ifp == NULL) {
       struct interface *ifp_aux;
       struct listnode *linklist_node = NULL;
@@ -1104,8 +1251,7 @@ send_self_update(struct interface *ifp)
 
     if(!interface_idle(babel_get_if_nfo(ifp))) {
         debugf(BABEL_DEBUG_COMMON,"Sending self update to %s.", ifp->name);
-        for(i = 0; i < numxroutes; i++)
-            send_update(ifp, 0, xroutes[i].prefix, xroutes[i].plen);
+        for_all_xroutes(send_xroute_update_callback, ifp);
     }
 }
 
diff --git a/babeld/neighbour.c b/babeld/neighbour.c
index f360b891..5a327dfe 100644
--- a/babeld/neighbour.c
+++ b/babeld/neighbour.c
@@ -122,7 +122,8 @@ find_neighbour(const unsigned char *address, struct interface *ifp)
     return neigh;
 }
 
-/* Recompute a neighbour's rxcost.  Return true if anything changed. */
+/* Recompute a neighbour's rxcost.  Return true if anything changed.
+   This does not call local_notify_neighbour, see update_neighbour_metric. */
 int
 update_neighbour(struct neighbour *neigh, int hello, int hello_interval)
 {
@@ -327,7 +328,7 @@ neighbour_cost(struct neighbour *neigh)
         return INFINITY;
 
     if(!(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ)
-       || (a <= 256 && b <= 256)) {
+       || (a < 256 && b < 256)) {
         return a;
     } else {
         /* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
diff --git a/babeld/net.c b/babeld/net.c
index eaed51d2..5e0200b0 100644
--- a/babeld/net.c
+++ b/babeld/net.c
@@ -58,6 +58,7 @@ babel_socket(int port)
     int s, rc;
     int saved_errno;
     int one = 1, zero = 0;
+    const int ds = 0xc0;        /* CS6 - Network Control */
 
     s = socket(PF_INET6, SOCK_DGRAM, 0);
     if(s < 0)
@@ -86,6 +87,15 @@ babel_socket(int port)
     if(rc < 0)
         goto fail;
 
+#ifdef IPV6_TCLASS
+    rc = setsockopt(s, IPPROTO_IPV6, IPV6_TCLASS, &ds, sizeof(ds));
+#else
+    rc = -1;
+    errno = ENOSYS;
+#endif
+    if(rc < 0)
+        perror("Couldn't set traffic class");
+
     rc = fcntl(s, F_GETFL, 0);
     if(rc < 0)
         goto fail;
diff --git a/babeld/route.c b/babeld/route.c
index aadf80f2..a9ffc5d9 100644
--- a/babeld/route.c
+++ b/babeld/route.c
@@ -53,36 +53,161 @@ THE SOFTWARE.
 
 static void consider_route(struct babel_route *route);
 
-struct babel_route *routes = NULL;
-int numroutes = 0, maxroutes = 0;
+struct babel_route **routes = NULL;
+static int route_slots = 0, max_route_slots = 0;
 int kernel_metric = 0;
 int allow_duplicates = -1;
+int diversity_kind = DIVERSITY_NONE;
+int diversity_factor = 256;     /* in units of 1/256 */
+int keep_unfeasible = 0;
+
+/* We maintain a list of "slots", ordered by prefix.  Every slot
+   contains a linked list of the routes to this prefix, with the
+   installed route, if any, at the head of the list. */
+
+static int
+route_compare(const unsigned char *prefix, unsigned char plen,
+               struct babel_route *route)
+{
+    int i = memcmp(prefix, route->src->prefix, 16);
+    if(i != 0)
+        return i;
+
+    if(plen < route->src->plen)
+        return -1;
+    else if(plen > route->src->plen)
+        return 1;
+    else
+        return 0;
+}
+
+/* Performs binary search, returns -1 in case of failure.  In the latter
+   case, new_return is the place where to insert the new element. */
+
+static int
+find_route_slot(const unsigned char *prefix, unsigned char plen,
+                int *new_return)
+{
+    int p, m, g, c;
+
+    if(route_slots < 1) {
+        if(new_return)
+            *new_return = 0;
+        return -1;
+    }
+
+    p = 0; g = route_slots - 1;
+
+    do {
+        m = (p + g) / 2;
+        c = route_compare(prefix, plen, routes[m]);
+        if(c == 0)
+            return m;
+        else if(c < 0)
+            g = m - 1;
+        else
+            p = m + 1;
+    } while(p <= g);
+
+    if(new_return)
+        *new_return = p;
+
+    return -1;
+}
 
 struct babel_route *
 find_route(const unsigned char *prefix, unsigned char plen,
            struct neighbour *neigh, const unsigned char *nexthop)
 {
-    int i;
-    for(i = 0; i < numroutes; i++) {
-        if(routes[i].neigh == neigh &&
-           memcmp(routes[i].nexthop, nexthop, 16) == 0 &&
-           source_match(routes[i].src, prefix, plen))
-            return &routes[i];
+    struct babel_route *route;
+    int i = find_route_slot(prefix, plen, NULL);
+
+    if(i < 0)
+        return NULL;
+
+    route = routes[i];
+
+    while(route) {
+        if(route->neigh == neigh && memcmp(route->nexthop, nexthop, 16) == 0)
+            return route;
+        route = route->next;
     }
+
     return NULL;
 }
 
 struct babel_route *
 find_installed_route(const unsigned char *prefix, unsigned char plen)
 {
-    int i;
-    for(i = 0; i < numroutes; i++) {
-        if(routes[i].installed && source_match(routes[i].src, prefix, plen))
-            return &routes[i];
-    }
+    int i = find_route_slot(prefix, plen, NULL);
+
+    if(i >= 0 && routes[i]->installed)
+        return routes[i];
+
     return NULL;
 }
 
+/* Returns an overestimate of the number of installed routes. */
+int
+installed_routes_estimate(void)
+{
+    return route_slots;
+}
+
+static int
+resize_route_table(int new_slots)
+{
+    struct babel_route **new_routes;
+    assert(new_slots >= route_slots);
+
+    if(new_slots == 0) {
+        new_routes = NULL;
+        free(routes);
+    } else {
+        new_routes = realloc(routes, new_slots * sizeof(struct babel_route*));
+        if(new_routes == NULL)
+            return -1;
+    }
+
+    max_route_slots = new_slots;
+    routes = new_routes;
+    return 1;
+}
+
+/* Insert a route into the table.  If successful, retains the route.
+   On failure, caller must free the route. */
+static struct babel_route *
+insert_route(struct babel_route *route)
+{
+    int i, n;
+
+    assert(!route->installed);
+
+    i = find_route_slot(route->src->prefix, route->src->plen, &n);
+
+    if(i < 0) {
+        if(route_slots >= max_route_slots)
+            resize_route_table(max_route_slots < 1 ? 8 : 2 * max_route_slots);
+        if(route_slots >= max_route_slots)
+            return NULL;
+        route->next = NULL;
+        if(n < route_slots)
+            memmove(routes + n + 1, routes + n,
+                    (route_slots - n) * sizeof(struct babel_route*));
+        route_slots++;
+        routes[n] = route;
+    } else {
+        struct babel_route *r;
+        r = routes[i];
+        while(r->next)
+            r = r->next;
+        r->next = route;
+        route->next = NULL;
+    }
+
+    return route;
+}
+
 void
 flush_route(struct babel_route *route)
 {
@@ -91,39 +216,67 @@ flush_route(struct babel_route *route)
     unsigned oldmetric;
     int lost = 0;
 
-    i = route - routes;
-    assert(i >= 0 && i < numroutes);
-
     oldmetric = route_metric(route);
+    src = route->src;
 
     if(route->installed) {
         uninstall_route(route);
         lost = 1;
     }
 
-    src = route->src;
+    i = find_route_slot(route->src->prefix, route->src->plen, NULL);
+    assert(i >= 0 && i < route_slots);
 
-    if(i != numroutes - 1)
-        memcpy(routes + i, routes + numroutes - 1, sizeof(struct babel_route));
-    numroutes--;
-    VALGRIND_MAKE_MEM_UNDEFINED(routes + numroutes, sizeof(struct babel_route));
+    if(route == routes[i]) {
+        routes[i] = route->next;
+        route->next = NULL;
+        free(route);
 
-    if(numroutes == 0) {
-        free(routes);
-        routes = NULL;
-        maxroutes = 0;
-    } else if(maxroutes > 8 && numroutes < maxroutes / 4) {
-        struct babel_route *new_routes;
-        int n = maxroutes / 2;
-        new_routes = realloc(routes, n * sizeof(struct babel_route));
-        if(new_routes != NULL) {
-            routes = new_routes;
-            maxroutes = n;
+        if(routes[i] == NULL) {
+            if(i < route_slots - 1)
+                memmove(routes + i, routes + i + 1,
+                        (route_slots - i - 1) * sizeof(struct babel_route*));
+            routes[route_slots - 1] = NULL;
+            route_slots--;
         }
+
+        if(route_slots == 0)
+            resize_route_table(0);
+        else if(max_route_slots > 8 && route_slots < max_route_slots / 4)
+            resize_route_table(max_route_slots / 2);
+    } else {
+        struct babel_route *r = routes[i];
+        while(r->next != route)
+            r = r->next;
+        r->next = route->next;
+        route->next = NULL;
+        free(route);
     }
 
     if(lost)
         route_lost(src, oldmetric);
+
+    release_source(src);
+}
+
+void
+flush_all_routes()
+{
+    int i;
+
+    /* Start from the end, to avoid shifting the table. */
+    i = route_slots - 1;
+    while(i >= 0) {
+        while(i < route_slots) {
+        /* Uninstall first, to avoid calling route_lost. */
+            if(routes[i]->installed)
+                uninstall_route(routes[0]);
+            flush_route(routes[i]);
+        }
+        i--;
+    }
+
+    check_sources_released();
 }
 
 void
@@ -132,12 +285,19 @@ flush_neighbour_routes(struct neighbour *neigh)
     int i;
 
     i = 0;
-    while(i < numroutes) {
-        if(routes[i].neigh == neigh) {
-            flush_route(&routes[i]);
-            continue;
+    while(i < route_slots) {
+        struct babel_route *r;
+        r = routes[i];
+        while(r) {
+            if(r->neigh == neigh) {
+                flush_route(r);
+                goto again;
+            }
+            r = r->next;
         }
         i++;
+    again:
+        ;
     }
 }
 
@@ -147,13 +307,46 @@ flush_interface_routes(struct interface *ifp, int v4only)
     int i;
 
     i = 0;
-    while(i < numroutes) {
-        if(routes[i].neigh->ifp == ifp &&
-           (!v4only || v4mapped(routes[i].nexthop))) {
-           flush_route(&routes[i]);
-           continue;
+    while(i < route_slots) {
+        struct babel_route *r;
+        r = routes[i];
+        while(r) {
+            if(r->neigh->ifp == ifp &&
+               (!v4only || v4mapped(r->nexthop))) {
+                flush_route(r);
+                goto again;
+            }
+            r = r->next;
         }
         i++;
+    again:
+        ;
+    }
+}
+
+/* Iterate a function over all routes. */
+void
+for_all_routes(void (*f)(struct babel_route*, void*), void *closure)
+{
+    int i;
+
+    for(i = 0; i < route_slots; i++) {
+        struct babel_route *r = routes[i];
+        while(r) {
+            (*f)(r, closure);
+            r = r->next;
+        }
+    }
+}
+
+void
+for_all_installed_routes(void (*f)(struct babel_route*, void*), void *closure)
+{
+    int i;
+
+    for(i = 0; i < route_slots; i++) {
+        if(routes[i]->installed)
+            (*f)(routes[i], closure);
     }
 }
 
@@ -163,10 +356,28 @@ metric_to_kernel(int metric)
     return metric < INFINITY ? kernel_metric : KERNEL_INFINITY;
 }
 
+/* This is used to maintain the invariant that the installed route is at
+   the head of the list. */
+static void
+move_installed_route(struct babel_route *route, int i)
+{
+    assert(i >= 0 && i < route_slots);
+    assert(route->installed);
+
+    if(route != routes[i]) {
+        struct babel_route *r = routes[i];
+        while(r->next != route)
+            r = r->next;
+        r->next = route->next;
+        route->next = routes[i];
+        routes[i] = route;
+    }
+}
+
 void
 install_route(struct babel_route *route)
 {
-    int rc;
+    int i, rc;
 
     if(route->installed)
         return;
@@ -175,6 +386,15 @@ install_route(struct babel_route *route)
         zlog_err("WARNING: installing unfeasible route "
                  "(this shouldn't happen).");
 
+    i = find_route_slot(route->src->prefix, route->src->plen, NULL);
+    assert(i >= 0 && i < route_slots);
+
+    if(routes[i] != route && routes[i]->installed) {
+        fprintf(stderr, "WARNING: attempting to install duplicate route "
+                "(this shouldn't happen).");
+        return;
+    }
+
     rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen,
                       route->nexthop,
                       route->neigh->ifp->ifindex,
@@ -186,6 +406,8 @@ install_route(struct babel_route *route)
             return;
     }
     route->installed = 1;
+    move_installed_route(route, i);
+
 }
 
 void
@@ -239,15 +461,16 @@ switch_routes(struct babel_route *old, struct babel_route *new)
 
     old->installed = 0;
     new->installed = 1;
+    move_installed_route(new, find_route_slot(new->src->prefix, new->src->plen,
+                                              NULL));
 }
 
 static void
-change_route_metric(struct babel_route *route, unsigned newmetric)
+change_route_metric(struct babel_route *route,
+                    unsigned refmetric, unsigned cost, unsigned add)
 {
     int old, new;
-
-    if(route_metric(route) == newmetric)
-        return;
+    int newmetric = MIN(refmetric + cost + add, INFINITY);
 
     old = metric_to_kernel(route_metric(route));
     new = metric_to_kernel(newmetric);
@@ -265,14 +488,15 @@ change_route_metric(struct babel_route *route, unsigned newmetric)
         }
     }
 
-    route->metric = newmetric;
+    route->refmetric = refmetric;
+    route->cost = cost;
+    route->add_metric = add;
 }
 
 static void
 retract_route(struct babel_route *route)
 {
-    route->refmetric = INFINITY;
-    change_route_metric(route, INFINITY);
+    change_route_metric(route, INFINITY, INFINITY, 0);
 }
 
 int
@@ -293,6 +517,51 @@ route_expired(struct babel_route *route)
     return route->time < babel_now.tv_sec - route->hold_time;
 }
 
+static int
+channels_interfere(int ch1, int ch2)
+{
+    if(ch1 == BABEL_IF_CHANNEL_NONINTERFERING
+       || ch2 == BABEL_IF_CHANNEL_NONINTERFERING)
+        return 0;
+    if(ch1 == BABEL_IF_CHANNEL_INTERFERING
+       || ch2 == BABEL_IF_CHANNEL_INTERFERING)
+        return 1;
+    return ch1 == ch2;
+}
+
+int
+route_interferes(struct babel_route *route, struct interface *ifp)
+{
+    struct babel_interface *babel_ifp = NULL;
+    switch(diversity_kind) {
+    case DIVERSITY_NONE:
+        return 1;
+    case DIVERSITY_INTERFACE_1:
+        return route->neigh->ifp == ifp;
+    case DIVERSITY_CHANNEL_1:
+    case DIVERSITY_CHANNEL:
+        if(route->neigh->ifp == ifp)
+            return 1;
+        babel_ifp = babel_get_if_nfo(ifp);
+        if(channels_interfere(babel_ifp->channel,
+                              babel_get_if_nfo(route->neigh->ifp)->channel))
+            return 1;
+        if(diversity_kind == DIVERSITY_CHANNEL) {
+            int i;
+            for(i = 0; i < DIVERSITY_HOPS; i++) {
+                if(route->channels[i] == 0)
+                    break;
+                if(channels_interfere(babel_ifp->channel, route->channels[i]))
+                    return 1;
+            }
+        }
+        return 0;
+    default:
+        fprintf(stderr, "Unknown kind of diversity.\n");
+        return 1;
+    }
+}
+
 int
 update_feasible(struct source *src,
                 unsigned short seqno, unsigned short refmetric)
@@ -317,21 +586,22 @@ struct babel_route *
 find_best_route(const unsigned char *prefix, unsigned char plen, int feasible,
                 struct neighbour *exclude)
 {
-    struct babel_route *route = NULL;
-    int i;
+    struct babel_route *route = NULL, *r = NULL;
+    int i = find_route_slot(prefix, plen, NULL);
+
+    if(i < 0)
+        return NULL;
+
+    route = routes[i];
 
-    for(i = 0; i < numroutes; i++) {
-        if(!source_match(routes[i].src, prefix, plen))
-            continue;
-        if(route_expired(&routes[i]))
-            continue;
-        if(feasible && !route_feasible(&routes[i]))
-            continue;
-        if(exclude && routes[i].neigh == exclude)
-            continue;
-        if(route && route_metric(route) <= route_metric(&routes[i]))
-            continue;
-        route = &routes[i];
+    r = route->next;
+    while(r) {
+        if(!route_expired(r) &&
+           (!feasible || route_feasible(r)) &&
+           (!exclude || r->neigh != exclude) &&
+           (route_metric(r) < route_metric(route)))
+            route = r;
+        r = r->next;
     }
     return route;
 }
@@ -354,31 +624,29 @@ update_route_metric(struct babel_route *route)
                                       route->src->prefix, route->src->plen,
                                       neigh->address,
                                       neigh->ifp->ifindex);
-        int newmetric = MIN(route->refmetric +
-                            add_metric +
-                            neighbour_cost(route->neigh),
-                            INFINITY);
-
-        if(newmetric != oldmetric) {
-            change_route_metric(route, newmetric);
+        change_route_metric(route, route->refmetric,
+                            neighbour_cost(route->neigh), add_metric);
+        if(route_metric(route) != oldmetric)
             route_changed(route, route->src, oldmetric);
-        }
     }
 }
 
 /* Called whenever a neighbour's cost changes, to update the metric of
- all routes through that neighbour. */
+   all routes through that neighbour.  Calls local_notify_neighbour. */
 void
 update_neighbour_metric(struct neighbour *neigh, int changed)
 {
+
     if(changed) {
         int i;
 
-        i = 0;
-        while(i < numroutes) {
-            if(routes[i].neigh == neigh)
-                update_route_metric(&routes[i]);
-            i++;
+        for(i = 0; i < route_slots; i++) {
+            struct babel_route *r = routes[i];
+            while(r) {
+                if(r->neigh == neigh)
+                    update_route_metric(r);
+                r = r->next;
+            }
         }
     }
 }
@@ -388,11 +656,13 @@ update_interface_metric(struct interface *ifp)
 {
     int i;
 
-    i = 0;
-    while(i < numroutes) {
-        if(routes[i].neigh->ifp == ifp)
-            update_route_metric(&routes[i]);
-        i++;
+    for(i = 0; i < route_slots; i++) {
+        struct babel_route *r = routes[i];
+        while(r) {
+            if(r->neigh->ifp == ifp)
+                update_route_metric(r);
+            r = r->next;
+        }
     }
 }
 
@@ -402,7 +672,8 @@ update_route(const unsigned char *router_id,
              const unsigned char *prefix, unsigned char plen,
              unsigned short seqno, unsigned short refmetric,
              unsigned short interval,
-             struct neighbour *neigh, const unsigned char *nexthop)
+             struct neighbour *neigh, const unsigned char *nexthop,
+             const unsigned char *channels, int channels_len)
 {
     struct babel_route *route;
     struct source *src;
@@ -424,12 +695,18 @@ update_route(const unsigned char *router_id,
     if(add_metric >= INFINITY)
         return NULL;
 
-    src = find_source(router_id, prefix, plen, 1, seqno);
+    route = find_route(prefix, plen, neigh, nexthop);
+
+    if(route && memcmp(route->src->id, router_id, 8) == 0)
+        /* Avoid scanning the source table. */
+        src = route->src;
+    else
+        src = find_source(router_id, prefix, plen, 1, seqno);
+
     if(src == NULL)
         return NULL;
 
     feasible = update_feasible(src, seqno, refmetric);
-    route = find_route(prefix, plen, neigh, nexthop);
     metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY);
 
     if(route) {
@@ -457,12 +734,12 @@ update_route(const unsigned char *router_id,
             }
         }
 
-        route->src = src;
-        if(feasible && refmetric < INFINITY)
+        route->src = retain_source(src);
+        if((feasible || keep_unfeasible) && refmetric < INFINITY)
             route->time = babel_now.tv_sec;
         route->seqno = seqno;
-        route->refmetric = refmetric;
-        change_route_metric(route, metric);
+        change_route_metric(route,
+                            refmetric, neighbour_cost(neigh), add_metric);
         route->hold_time = hold_time;
 
         route_changed(route, oldsrc, oldmetric);
@@ -472,36 +749,46 @@ update_route(const unsigned char *router_id,
         if(!feasible)
             send_unfeasible_request(neigh, route->installed && route_old(route),
                                     seqno, metric, src);
+        release_source(oldsrc);
     } else {
+        struct babel_route *new_route;
+
         if(refmetric >= INFINITY)
             /* Somebody's retracting a route we never saw. */
             return NULL;
         if(!feasible) {
             send_unfeasible_request(neigh, 0, seqno, metric, src);
-            return NULL;
-        }
-        if(numroutes >= maxroutes) {
-            struct babel_route *new_routes;
-            int n = maxroutes < 1 ? 8 : 2 * maxroutes;
-            new_routes = routes == NULL ?
-                malloc(n * sizeof(struct babel_route)) :
-                realloc(routes, n * sizeof(struct babel_route));
-            if(new_routes == NULL)
+            if(!keep_unfeasible)
                 return NULL;
-            maxroutes = n;
-            routes = new_routes;
         }
-        route = &routes[numroutes];
-        route->src = src;
+
+        route = malloc(sizeof(struct babel_route));
+        if(route == NULL) {
+            perror("malloc(route)");
+            return NULL;
+        }
+
+        route->src = retain_source(src);
         route->refmetric = refmetric;
+        route->cost = neighbour_cost(neigh);
+        route->add_metric = add_metric;
         route->seqno = seqno;
-        route->metric = metric;
         route->neigh = neigh;
         memcpy(route->nexthop, nexthop, 16);
         route->time = babel_now.tv_sec;
         route->hold_time = hold_time;
         route->installed = 0;
-        numroutes++;
+        memset(&route->channels, 0, sizeof(route->channels));
+        if(channels_len > 0)
+            memcpy(&route->channels, channels,
+                   MIN(channels_len, DIVERSITY_HOPS));
+        route->next = NULL;
+        new_route = insert_route(route);
+        if(new_route == NULL) {
+            fprintf(stderr, "Couldn't insert route.\n");
+            free(route);
+            return NULL;
+        }
         consider_route(route);
     }
     return route;
@@ -558,13 +845,6 @@ consider_route(struct babel_route *route)
     if(route_metric(installed) >= INFINITY)
         goto install;
 
-    if(route_metric(installed) >= route_metric(route) + 192)
-        goto install;
-
-    /* Avoid switching sources */
-    if(installed->src != route->src)
-        return;
-
     if(route_metric(installed) >= route_metric(route) + 64)
         goto install;
 
@@ -584,15 +864,18 @@ retract_neighbour_routes(struct neighbour *neigh)
 {
     int i;
 
-    i = 0;
-    while(i < numroutes) {
-        if(routes[i].neigh == neigh) {
-            if(routes[i].refmetric != INFINITY) {
-                unsigned short oldmetric = route_metric(&routes[i]);
-                    retract_route(&routes[i]);
+    for(i = 0; i < route_slots; i++) {
+        struct babel_route *r = routes[i];
+        while(r) {
+            if(r->neigh == neigh) {
+                if(r->refmetric != INFINITY) {
+                    unsigned short oldmetric = route_metric(r);
+                    retract_route(r);
                     if(oldmetric != INFINITY)
-                        route_changed(&routes[i], routes[i].src, oldmetric);
+                        route_changed(r, r->src, oldmetric);
+                }
             }
+            r = r->next;
         }
         i++;
     }
@@ -699,51 +982,38 @@ route_lost(struct source *src, unsigned oldmetric)
     }
 }
 
+/* This is called periodically to flush old routes.  It will also send
+   requests for routes that are about to expire. */
 void
 expire_routes(void)
 {
+    struct babel_route *r;
     int i;
 
     debugf(BABEL_DEBUG_COMMON,"Expiring old routes.");
 
     i = 0;
-    while(i < numroutes) {
-        struct babel_route *route = &routes[i];
-
-        if(route->time > babel_now.tv_sec || /* clock stepped */
-           route_old(route)) {
-            flush_route(route);
-            continue;
-        }
+    while(i < route_slots) {
+        r = routes[i];
+        while(r) {
+            /* Protect against clock being stepped. */
+            if(r->time > babel_now.tv_sec || route_old(r)) {
+                flush_route(r);
+                goto again;
+            }
 
-        update_route_metric(route);
+            update_route_metric(r);
 
-        if(route->installed && route->refmetric < INFINITY) {
-            if(route_old(route))
-                send_unicast_request(route->neigh,
-                                     route->src->prefix, route->src->plen);
+            if(r->installed && r->refmetric < INFINITY) {
+                if(route_old(r))
+                    /* Route about to expire, send a request. */
+                    send_unicast_request(r->neigh,
+                                         r->src->prefix, r->src->plen);
+            }
+            r = r->next;
         }
         i++;
+    again:
+        ;
     }
 }
-
-void
-babel_uninstall_all_routes(void)
-{
-    while(numroutes > 0) {
-        uninstall_route(&routes[0]);
-        /* We need to flush the route so network_up won't reinstall it */
-        flush_route(&routes[0]);
-    }
-}
-
-struct babel_route *
-babel_route_get_by_source(struct source *src)
-{
-    int i;
-    for(i = 0; i < numroutes; i++) {
-        if(routes[i].src == src)
-            return &routes[i];
-    }
-    return NULL;
-}
diff --git a/babeld/route.h b/babeld/route.h
index c08332a6..b6d2d294 100644
--- a/babeld/route.h
+++ b/babeld/route.h
@@ -43,41 +43,69 @@ THE SOFTWARE.
 #include "babel_interface.h"
 #include "source.h"
 
+#define DIVERSITY_NONE 0
+#define DIVERSITY_INTERFACE_1 1
+#define DIVERSITY_CHANNEL_1 2
+#define DIVERSITY_CHANNEL 3
+
+#define DIVERSITY_HOPS 8
+
 struct babel_route {
     struct source *src;
-    unsigned short metric;
     unsigned short refmetric;
+    unsigned short cost;
+    unsigned short add_metric;
     unsigned short seqno;
     struct neighbour *neigh;
     unsigned char nexthop[16];
     time_t time;
     unsigned short hold_time;    /* in seconds */
     short installed;
+    unsigned char channels[DIVERSITY_HOPS];
+    struct babel_route *next;
 };
 
-static inline unsigned short
+extern struct babel_route **routes;
+extern int kernel_metric, allow_duplicates;
+extern int diversity_kind, diversity_factor;
+extern int keep_unfeasible;
+
+static inline int
 route_metric(const struct babel_route *route)
 {
-    return route->metric;
+    int m = (int)route->refmetric + route->cost + route->add_metric;
+    return MIN(m, INFINITY);
 }
 
-extern struct babel_route *routes;
-extern int numroutes, maxroutes;
-extern int kernel_metric, allow_duplicates;
+static inline int
+route_metric_noninterfering(const struct babel_route *route)
+{
+    int m =
+        (int)route->refmetric +
+        (diversity_factor * route->cost + 128) / 256 +
+        route->add_metric;
+    m = MAX(m, route->refmetric + 1);
+    return MIN(m, INFINITY);
+}
 
 struct babel_route *find_route(const unsigned char *prefix, unsigned char plen,
                          struct neighbour *neigh, const unsigned char *nexthop);
 struct babel_route *find_installed_route(const unsigned char *prefix,
                                    unsigned char plen);
+int installed_routes_estimate(void);
 void flush_route(struct babel_route *route);
+void flush_all_routes(void);
 void flush_neighbour_routes(struct neighbour *neigh);
 void flush_interface_routes(struct interface *ifp, int v4only);
+void for_all_routes(void (*f)(struct babel_route*, void*), void *closure);
+void for_all_installed_routes(void (*f)(struct babel_route*, void*), void *closure);
 void install_route(struct babel_route *route);
 void uninstall_route(struct babel_route *route);
 void switch_route(struct babel_route *old, struct babel_route *new);
 int route_feasible(struct babel_route *route);
 int route_old(struct babel_route *route);
 int route_expired(struct babel_route *route);
+int route_interferes(struct babel_route *route, struct interface *ifp);
 int update_feasible(struct source *src,
                     unsigned short seqno, unsigned short refmetric);
 struct babel_route *find_best_route(const unsigned char *prefix, unsigned char plen,
@@ -87,11 +115,12 @@ struct babel_route *install_best_route(const unsigned char prefix[16],
 void update_neighbour_metric(struct neighbour *neigh, int change);
 void update_interface_metric(struct interface *ifp);
 void update_route_metric(struct babel_route *route);
-struct babel_route *update_route(const unsigned char *a,
-                           const unsigned char *p, unsigned char plen,
+struct babel_route *update_route(const unsigned char *id,
+                           const unsigned char *prefix, unsigned char plen,
                            unsigned short seqno, unsigned short refmetric,
                            unsigned short interval, struct neighbour *neigh,
-                           const unsigned char *nexthop);
+                           const unsigned char *nexthop,
+                           const unsigned char *channels, int channels_len);
 void retract_neighbour_routes(struct neighbour *neigh);
 void send_unfeasible_request(struct neighbour *neigh, int force,
                              unsigned short seqno, unsigned short metric,
@@ -103,7 +132,4 @@ void route_changed(struct babel_route *route,
 void route_lost(struct source *src, unsigned oldmetric);
 void expire_routes(void);
 
-void babel_uninstall_all_routes(void);
-struct babel_route *babel_route_get_by_source(struct source *src);
-
 #endif
diff --git a/babeld/source.c b/babeld/source.c
index cc4ed445..772112d4 100644
--- a/babeld/source.c
+++ b/babeld/source.c
@@ -63,8 +63,10 @@ find_source(const unsigned char *id, const unsigned char *p, unsigned char plen,
             continue;
         if(memcmp(src->id, id, 8) != 0)
             continue;
-        if(source_match(src, p, plen))
-           return src;
+        if(src->plen != plen)
+            continue;
+        if(memcmp(src->prefix, p, 16) == 0)
+            return src;
     }
 
     if(!create)
@@ -82,18 +84,32 @@ find_source(const unsigned char *id, const unsigned char *p, unsigned char plen,
     src->seqno = seqno;
     src->metric = INFINITY;
     src->time = babel_now.tv_sec;
+    src->route_count = 0;
     src->next = srcs;
     srcs = src;
     return src;
 }
 
+struct source *
+retain_source(struct source *src)
+{
+    assert(src->route_count < 0xffff);
+    src->route_count++;
+    return src;
+}
+
+void
+release_source(struct source *src)
+{
+    assert(src->route_count > 0);
+    src->route_count--;
+}
+
 int
 flush_source(struct source *src)
 {
-    /* This is absolutely horrible -- it makes expire_sources quadratic.
-       But it's not called very often. */
-
-    if (babel_route_get_by_source(src) != NULL)
+    if(src->route_count > 0)
+        /* The source is in use by a route. */
         return 0;
 
     if(srcs == src) {
@@ -109,19 +125,6 @@ flush_source(struct source *src)
     return 1;
 }
 
-int
-source_match(struct source *src,
-             const unsigned char *p, unsigned char plen)
-{
-    if(src->plen != plen)
-        return 0;
-    if(src->prefix[15] != p[15])
-        return 0;
-    if(memcmp(src->prefix, p, 16) != 0)
-        return 0;
-    return 1;
-}
-
 void
 update_source(struct source *src,
               unsigned short seqno, unsigned short metric)
@@ -129,6 +132,10 @@ update_source(struct source *src,
     if(metric >= INFINITY)
         return;
 
+    /* If a source is expired, pretend that it doesn't exist and update
+       it unconditionally.  This makes ensures that old data will
+       eventually be overridden, and prevents us from getting stuck if
+       a router loses its sequence number. */
     if(src->time < babel_now.tv_sec - SOURCE_GC_TIME ||
        seqno_compare(src->seqno, seqno) < 0 ||
        (src->seqno == seqno && src->metric > metric)) {
@@ -157,3 +164,17 @@ expire_sources()
         src = src->next;
     }
 }
+
+void
+check_sources_released(void)
+{
+    struct source *src;
+
+    for(src = srcs; src; src = src->next) {
+        if(src->route_count != 0)
+            fprintf(stderr, "Warning: source %s %s has refcount %d.\n",
+                    format_eui64(src->id),
+                    format_prefix(src->prefix, src->plen),
+                    (int)src->route_count);
+    }
+}
diff --git a/babeld/source.h b/babeld/source.h
index 38d3c004..62a7e1ee 100644
--- a/babeld/source.h
+++ b/babeld/source.h
@@ -48,19 +48,20 @@ struct source {
     unsigned char plen;
     unsigned short seqno;
     unsigned short metric;
+    unsigned short route_count;
     time_t time;
 };
 
-int source_match(struct source *src,
-                 const unsigned char *p, unsigned char plen);
 struct source *find_source(const unsigned char *id,
                            const unsigned char *p,
                            unsigned char plen,
                            int create, unsigned short seqno);
+struct source *retain_source(struct source *src);
+void release_source(struct source *src);
 int flush_source(struct source *src);
 void update_source(struct source *src,
                    unsigned short seqno, unsigned short metric);
 void expire_sources(void);
-
+void check_sources_released(void);
 
 #endif
diff --git a/babeld/util.c b/babeld/util.c
index 514e0ff3..011f3824 100644
--- a/babeld/util.c
+++ b/babeld/util.c
@@ -200,17 +200,6 @@ parse_msec(const char *string)
     return -1;
 }
 
-void
-do_debugf(const char *format, ...)
-{
-    va_list args;
-    va_start(args, format);
-    vfprintf(stderr, format, args);
-    fprintf(stderr, "\n");
-    fflush(stderr);
-    va_end(args);
-}
-
 int
 in_prefix(const unsigned char *restrict address,
           const unsigned char *restrict prefix, unsigned char plen)
@@ -328,63 +317,6 @@ parse_address(const char *address, unsigned char *addr_r, int *af_r)
 }
 
 int
-parse_net(const char *net, unsigned char *prefix_r, unsigned char *plen_r,
-          int *af_r)
-{
-    char buf[INET6_ADDRSTRLEN];
-    char *slash, *end;
-    unsigned char prefix[16];
-    long plen;
-    int af;
-    struct in_addr ina;
-    struct in6_addr ina6;
-    int rc;
-
-    if(strcmp(net, "default") == 0) {
-        memset(prefix, 0, 16);
-        plen = 0;
-    } else {
-        slash = strchr(net, '/');
-        if(slash == NULL) {
-            rc = parse_address(net, prefix, &af);
-            if(rc < 0)
-                return rc;
-            plen = 128;
-        } else {
-            if(slash - net >= INET6_ADDRSTRLEN)
-                return -1;
-            memcpy(buf, net, slash - net);
-            buf[slash - net] = '\0';
-            rc = inet_pton(AF_INET, buf, &ina);
-            if(rc > 0) {
-                memcpy(prefix, v4prefix, 12);
-                memcpy(prefix + 12, &ina, 4);
-                plen = strtol(slash + 1, &end, 0);
-                if(*end != '\0' || plen < 0 || plen > 32)
-                    return -1;
-                plen += 96;
-                af = AF_INET;
-            } else {
-                rc = inet_pton(AF_INET6, buf, &ina6);
-                if(rc > 0) {
-                    memcpy(prefix, &ina6, 16);
-                    plen = strtol(slash + 1, &end, 0);
-                    if(*end != '\0' || plen < 0 || plen > 128)
-                        return -1;
-                    af = AF_INET6;
-                } else {
-                    return -1;
-                }
-            }
-        }
-    }
-    mask_prefix(prefix_r, prefix, plen);
-    *plen_r = plen;
-    if(af_r) *af_r = af;
-    return 0;
-}
-
-int
 parse_eui64(const char *eui, unsigned char *eui_r)
 {
     int n;
diff --git a/babeld/util.h b/babeld/util.h
index 376b967f..5d9d2f5d 100644
--- a/babeld/util.h
+++ b/babeld/util.h
@@ -100,8 +100,6 @@ int timeval_compare(const struct timeval *s1, const struct timeval *s2)
 void timeval_min(struct timeval *d, const struct timeval *s);
 void timeval_min_sec(struct timeval *d, time_t secs);
 int parse_msec(const char *string) ATTRIBUTE ((pure));
-void do_debugf(const char *format, ...)
-    ATTRIBUTE ((format (printf, 1, 2))) COLD;
 int in_prefix(const unsigned char *restrict address,
               const unsigned char *restrict prefix, unsigned char plen)
     ATTRIBUTE ((pure));
@@ -113,8 +111,6 @@ const char *format_prefix(const unsigned char *address, unsigned char prefix);
 const char *format_eui64(const unsigned char *eui);
 const char *format_bool(const int b);
 int parse_address(const char *address, unsigned char *addr_r, int *af_r);
-int parse_net(const char *ifp, unsigned char *prefix_r, unsigned char *plen_r,
-              int *af_r);
 int parse_eui64(const char *eui, unsigned char *eui_r);
 int wait_for_fd(int direction, int fd, int msecs);
 int martian_prefix(const unsigned char *prefix, int plen) ATTRIBUTE ((pure));
diff --git a/babeld/xroute.c b/babeld/xroute.c
index 8330b492..80651671 100644
--- a/babeld/xroute.c
+++ b/babeld/xroute.c
@@ -50,9 +50,12 @@ THE SOFTWARE.
 #include "util.h"
 #include "babel_interface.h"
 
-struct xroute *xroutes;
-int numxroutes = 0;
-int maxxroutes = 0;
+static int xroute_add_new_route(unsigned char prefix[16], unsigned char plen,
+                                unsigned short metric, unsigned int ifindex,
+                                int proto, int send_updates);
+
+static struct xroute *xroutes;
+static int numxroutes = 0, maxxroutes = 0;
 
 /* Add redistributed route to Babel table. */
 int
@@ -189,8 +192,24 @@ add_xroute(unsigned char prefix[16], unsigned char plen,
     return 1;
 }
 
-/* add an xroute, verifying some conditions; return 0 if there is no changes */
+/* Returns an overestimate of the number of xroutes. */
 int
+xroutes_estimate()
+{
+    return numxroutes;
+}
+
+void
+for_all_xroutes(void (*f)(struct xroute*, void*), void *closure)
+{
+    int i;
+
+    for(i = 0; i < numxroutes; i++)
+        (*f)(&xroutes[i], closure);
+}
+
+/* add an xroute, verifying some conditions; return 0 if there is no changes */
+static int
 xroute_add_new_route(unsigned char prefix[16], unsigned char plen,
                      unsigned short metric, unsigned int ifindex,
                      int proto, int send_updates)
diff --git a/babeld/xroute.h b/babeld/xroute.h
index c9a4f85f..4d4ab99d 100644
--- a/babeld/xroute.h
+++ b/babeld/xroute.h
@@ -45,14 +45,8 @@ struct xroute {
     int proto;
 };
 
-extern struct xroute *xroutes;
-extern int numxroutes;
-
 struct xroute *find_xroute(const unsigned char *prefix, unsigned char plen);
 void flush_xroute(struct xroute *xroute);
-int xroute_add_new_route(unsigned char prefix[16], unsigned char plen,
-                         unsigned short metric, unsigned int ifindex,
-                         int proto, int send_updates);
 int babel_ipv4_route_add (struct zapi_ipv4 *api, struct prefix_ipv4 *prefix,
                           unsigned int ifindex, struct in_addr *nexthop);
 int babel_ipv4_route_delete (struct zapi_ipv4 *api, struct prefix_ipv4 *prefix,
@@ -61,3 +55,5 @@ int babel_ipv6_route_add (struct zapi_ipv6 *api, struct prefix_ipv6 *prefix,
                           unsigned int ifindex, struct in6_addr *nexthop);
 int babel_ipv6_route_delete (struct zapi_ipv6 *api, struct prefix_ipv6 *prefix,
                              unsigned int ifindex);
+int xroutes_estimate(void);
+void for_all_xroutes(void (*f)(struct xroute*, void*), void *closure);