*: Initial Import of Babeld into FRR

This is a direct copy of:
https://github.com/boutier/quagga-merge

From the branch babel-merge

I copied the babeld directory into FRR and then fixed up everything to
compile.

Babeld at this point in time when run will more than likely crash and burn
in it's interfactions with zebra.

I might have messed up the cli, which will need to be looked at

extract.pl.in and vtysh.c need to be fixed up.  Additionally we probably
need to work on DEFUN_NOSH conversion in babeld as well

This code comes from:
Matthieu Boutier <boutier@irif.fr>
Juliusz Chroboczek <jch@irif.fr>

Signed-off-by: Donald Sharp <sharpd@cumulusnetworks.com>

1 files changed, 1802 insertions, 0 deletions

diff --git a/babeld/message.c b/babeld/message.c
new file mode 100644
index 000000000..5990373b6
--- /dev/null
+++ b/babeld/message.c
@@ -0,0 +1,1802 @@
+/*
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <zebra.h>
+#include "if.h"
+
+#include "babeld.h"
+#include "util.h"
+#include "net.h"
+#include "babel_interface.h"
+#include "source.h"
+#include "neighbour.h"
+#include "route.h"
+#include "xroute.h"
+#include "resend.h"
+#include "message.h"
+#include "kernel.h"
+#include "babel_main.h"
+
+static unsigned char packet_header[4] = {42, 2};
+
+int split_horizon = 1;
+
+unsigned short myseqno = 0;
+
+#define UNICAST_BUFSIZE 1024
+static int unicast_buffered = 0;
+static unsigned char *unicast_buffer = NULL;
+struct neighbour *unicast_neighbour = NULL;
+struct timeval unicast_flush_timeout = {0, 0};
+
+/* Minimum TLV _body_ length for TLVs of particular types (0 = no limit). */
+static const unsigned char tlv_min_length[MESSAGE_MAX + 1] =
+{
+    [ MESSAGE_PAD1       ] =  0,
+    [ MESSAGE_PADN       ] =  0,
+    [ MESSAGE_ACK_REQ    ] =  6,
+    [ MESSAGE_ACK        ] =  2,
+    [ MESSAGE_HELLO      ] =  6,
+    [ MESSAGE_IHU        ] =  6,
+    [ MESSAGE_ROUTER_ID  ] = 10,
+    [ MESSAGE_NH         ] =  2,
+    [ MESSAGE_UPDATE     ] = 10,
+    [ MESSAGE_REQUEST    ] =  2,
+    [ MESSAGE_MH_REQUEST ] = 14,
+};
+
+/* 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,
+               unsigned int len, unsigned char *p_r)
+{
+    unsigned pb;
+    unsigned char prefix[16];
+    int ret = -1;
+
+    if(plen >= 0)
+        pb = (plen + 7) / 8;
+    else if(ae == 1)
+        pb = 4;
+    else
+        pb = 16;
+
+    if(pb > 16)
+        return -1;
+
+    memset(prefix, 0, 16);
+
+    switch(ae) {
+    case 0:
+        ret = 0;
+        break;
+    case 1:
+        if(omitted > 4 || pb > 4 || (pb > omitted && len < pb - omitted))
+            return -1;
+        memcpy(prefix, v4prefix, 12);
+        if(omitted) {
+            if (dp == NULL || !v4mapped(dp)) return -1;
+            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;
+        if(omitted) {
+            if (dp == NULL || v4mapped(dp)) return -1;
+            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 ret;
+}
+
+static void
+parse_update_subtlv(const unsigned char *a, int alen,
+                    unsigned char *channels)
+{
+    int type, len, i = 0;
+
+    while(i < alen) {
+        type = a[i];
+        if(type == SUBTLV_PAD1) {
+            i++;
+            continue;
+        }
+
+        if(i + 1 > alen) {
+            zlog_err("Received truncated attributes.");
+            return;
+        }
+        len = a[i + 1];
+        if(i + len > alen) {
+            zlog_err("Received truncated attributes.");
+            return;
+        }
+
+        if(type == SUBTLV_PADN) {
+            /* Nothing. */
+        } else if(type == SUBTLV_DIVERSITY) {
+            if(len > DIVERSITY_HOPS) {
+                zlog_err("Received overlong channel information (%d > %d).n",
+                         len, DIVERSITY_HOPS);
+                len = DIVERSITY_HOPS;
+            }
+            if(memchr(a + i + 2, 0, len) != NULL) {
+                /* 0 is reserved. */
+                zlog_err("Channel information contains 0!");
+                return;
+            }
+            memset(channels, 0, DIVERSITY_HOPS);
+            memcpy(channels, a + i + 2, len);
+        } else {
+            debugf(BABEL_DEBUG_COMMON,
+                   "Received unknown route attribute %d.", type);
+        }
+
+        i += len + 2;
+    }
+}
+
+static int
+parse_hello_subtlv(const unsigned char *a, int alen,
+                   unsigned int *hello_send_us)
+{
+    int type, len, i = 0, ret = 0;
+
+    while(i < alen) {
+        type = a[0];
+        if(type == SUBTLV_PAD1) {
+            i++;
+            continue;
+        }
+
+        if(i + 1 > alen) {
+            zlog_err("Received truncated sub-TLV on Hello message.");
+            return -1;
+        }
+        len = a[i + 1];
+        if(i + len > alen) {
+            zlog_err("Received truncated sub-TLV on Hello message.");
+            return -1;
+        }
+
+        if(type == SUBTLV_PADN) {
+            /* Nothing to do. */
+        } else if(type == SUBTLV_TIMESTAMP) {
+            if(len >= 4) {
+                DO_NTOHL(*hello_send_us, a + i + 2);
+                ret = 1;
+            } else {
+                zlog_err("Received incorrect RTT sub-TLV on Hello message.");
+            }
+        } else {
+            debugf(BABEL_DEBUG_COMMON,
+                   "Received unknown Hello sub-TLV type %d.", type);
+        }
+
+        i += len + 2;
+    }
+    return ret;
+}
+
+static int
+parse_ihu_subtlv(const unsigned char *a, int alen,
+                 unsigned int *hello_send_us,
+                 unsigned int *hello_rtt_receive_time)
+{
+    int type, len, i = 0, ret = 0;
+
+    while(i < alen) {
+        type = a[0];
+        if(type == SUBTLV_PAD1) {
+            i++;
+            continue;
+        }
+
+        if(i + 1 > alen) {
+            zlog_err("Received truncated sub-TLV on IHU message.");
+            return -1;
+        }
+        len = a[i + 1];
+        if(i + len > alen) {
+            zlog_err("Received truncated sub-TLV on IHU message.");
+            return -1;
+        }
+
+        if(type == SUBTLV_PADN) {
+            /* Nothing to do. */
+        } else if(type == SUBTLV_TIMESTAMP) {
+            if(len >= 8) {
+                DO_NTOHL(*hello_send_us, a + i + 2);
+                DO_NTOHL(*hello_rtt_receive_time, a + i + 6);
+                ret = 1;
+            }
+            else {
+                zlog_err("Received incorrect RTT sub-TLV on IHU message.");
+            }
+        } else {
+            debugf(BABEL_DEBUG_COMMON,
+                   "Received unknown IHU sub-TLV type %d.", type);
+        }
+
+        i += len + 2;
+    }
+    return ret;
+}
+
+static int
+network_address(int ae, const unsigned char *a, unsigned int len,
+                unsigned char *a_r)
+{
+    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;
+}
+
+/* Check, that the provided frame consists of a valid Babel packet header
+   followed by a sequence of TLVs. TLVs of known types are also checked to meet
+   minimum length constraints defined for each. Return 0 for no errors. */
+static int
+babel_packet_examin(const unsigned char *packet, int packetlen)
+{
+    unsigned i = 0, bodylen;
+    const unsigned char *message;
+    unsigned char type, len;
+
+    if(packetlen < 4 || packet[0] != 42 || packet[1] != 2)
+        return 1;
+    DO_NTOHS(bodylen, packet + 2);
+    while (i < bodylen){
+        message = packet + 4 + i;
+        type = message[0];
+        if(type == MESSAGE_PAD1) {
+            i++;
+            continue;
+        }
+        if(i + 1 > bodylen) {
+            debugf(BABEL_DEBUG_COMMON,"Received truncated message.");
+            return 1;
+        }
+        len = message[1];
+        if(i + len > bodylen) {
+            debugf(BABEL_DEBUG_COMMON,"Received truncated message.");
+            return 1;
+        }
+        /* not Pad1 */
+        if(type <= MESSAGE_MAX && tlv_min_length[type] && len < tlv_min_length[type]) {
+            debugf(BABEL_DEBUG_COMMON,"Undersized %u TLV", type);
+            return 1;
+        }
+        i += len + 2;
+    }
+    return 0;
+}
+
+void
+parse_packet(const unsigned char *from, struct interface *ifp,
+             const unsigned char *packet, int packetlen)
+{
+    int i;
+    const unsigned char *message;
+    unsigned char type, len;
+    int bodylen;
+    struct neighbour *neigh;
+    int have_router_id = 0, have_v4_prefix = 0, have_v6_prefix = 0,
+        have_v4_nh = 0, have_v6_nh = 0;
+    unsigned char router_id[8], v4_prefix[16], v6_prefix[16],
+        v4_nh[16], v6_nh[16];
+    int have_hello_rtt = 0;
+    /* Content of the RTT sub-TLV on IHU messages. */
+    unsigned int hello_send_us = 0, hello_rtt_receive_time = 0;
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+
+    if(babel_ifp->flags & BABEL_IF_TIMESTAMPS) {
+        /* We want to track exactly when we received this packet. */
+        gettime(&babel_now);
+    }
+
+    if(!linklocal(from)) {
+        zlog_err("Received packet from non-local address %s.",
+                 format_address(from));
+        return;
+    }
+
+    if (babel_packet_examin (packet, packetlen)) {
+        zlog_err("Received malformed packet on %s from %s.",
+                 ifp->name, format_address(from));
+        return;
+    }
+
+    neigh = find_neighbour(from, ifp);
+    if(neigh == NULL) {
+        zlog_err("Couldn't allocate neighbour.");
+        return;
+    }
+
+    DO_NTOHS(bodylen, packet + 2);
+
+    if(bodylen + 4 > packetlen) {
+        zlog_err("Received truncated packet (%d + 4 > %d).",
+                 bodylen, packetlen);
+        bodylen = packetlen - 4;
+    }
+
+    i = 0;
+    while(i < bodylen) {
+        message = packet + 4 + i;
+        type = message[0];
+        if(type == MESSAGE_PAD1) {
+            debugf(BABEL_DEBUG_COMMON,"Received pad1 from %s on %s.",
+                   format_address(from), ifp->name);
+            i++;
+            continue;
+        }
+        len = message[1];
+
+        if(type == MESSAGE_PADN) {
+            debugf(BABEL_DEBUG_COMMON,"Received pad%d from %s on %s.",
+                   len, format_address(from), ifp->name);
+        } else if(type == MESSAGE_ACK_REQ) {
+            unsigned short nonce, interval;
+            DO_NTOHS(nonce, message + 4);
+            DO_NTOHS(interval, message + 6);
+            debugf(BABEL_DEBUG_COMMON,"Received ack-req (%04X %d) from %s on %s.",
+                   nonce, interval, format_address(from), ifp->name);
+            send_ack(neigh, nonce, interval);
+        } else if(type == MESSAGE_ACK) {
+            debugf(BABEL_DEBUG_COMMON,"Received ack from %s on %s.",
+                   format_address(from), ifp->name);
+            /* Nothing right now */
+        } else if(type == MESSAGE_HELLO) {
+            unsigned short seqno, interval;
+            int changed;
+            unsigned int timestamp;
+            DO_NTOHS(seqno, message + 4);
+            DO_NTOHS(interval, message + 6);
+            debugf(BABEL_DEBUG_COMMON,"Received hello %d (%d) from %s on %s.",
+                   seqno, interval,
+                   format_address(from), ifp->name);
+            changed = update_neighbour(neigh, seqno, interval);
+            update_neighbour_metric(neigh, changed);
+            if(interval > 0)
+                /* Multiply by 3/2 to allow hellos to expire. */
+                schedule_neighbours_check(interval * 15, 0);
+            /* Sub-TLV handling. */
+            if(len > 8) {
+                if(parse_hello_subtlv(message + 8, len - 6, &timestamp) > 0) {
+                    neigh->hello_send_us = timestamp;
+                    neigh->hello_rtt_receive_time = babel_now;
+                    have_hello_rtt = 1;
+                }
+            }
+        } else if(type == MESSAGE_IHU) {
+            unsigned short txcost, interval;
+            unsigned char address[16];
+            int rc;
+            DO_NTOHS(txcost, message + 4);
+            DO_NTOHS(interval, message + 6);
+            rc = network_address(message[2], message + 8, len - 6, address);
+            if(rc < 0) goto fail;
+            debugf(BABEL_DEBUG_COMMON,"Received ihu %d (%d) from %s on %s for %s.",
+                   txcost, interval,
+                   format_address(from), ifp->name,
+                   format_address(address));
+            if(message[2] == 0 || is_interface_ll_address(ifp, address)) {
+                int changed = txcost != neigh->txcost;
+                neigh->txcost = txcost;
+                neigh->ihu_time = babel_now;
+                neigh->ihu_interval = interval;
+                update_neighbour_metric(neigh, changed);
+                if(interval > 0)
+                    /* Multiply by 3/2 to allow neighbours to expire. */
+                    schedule_neighbours_check(interval * 45, 0);
+                /* RTT sub-TLV. */
+                if(len > 10 + rc)
+                    parse_ihu_subtlv(message + 8 + rc, len - 6 - rc,
+                                     &hello_send_us, &hello_rtt_receive_time);
+            }
+        } else if(type == MESSAGE_ROUTER_ID) {
+            memcpy(router_id, message + 4, 8);
+            have_router_id = 1;
+            debugf(BABEL_DEBUG_COMMON,"Received router-id %s from %s on %s.",
+                   format_eui64(router_id), format_address(from), ifp->name);
+        } else if(type == MESSAGE_NH) {
+            unsigned char nh[16];
+            int rc;
+            rc = network_address(message[2], message + 4, len - 2,
+                                 nh);
+            if(rc < 0) {
+                have_v4_nh = 0;
+                have_v6_nh = 0;
+                goto fail;
+            }
+            debugf(BABEL_DEBUG_COMMON,"Received nh %s (%d) from %s on %s.",
+                   format_address(nh), message[2],
+                   format_address(from), ifp->name);
+            if(message[2] == 1) {
+                memcpy(v4_nh, nh, 16);
+                have_v4_nh = 1;
+            } else {
+                memcpy(v6_nh, nh, 16);
+                have_v6_nh = 1;
+            }
+        } 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, parsed_len;
+            DO_NTOHS(interval, message + 6);
+            DO_NTOHS(seqno, message + 8);
+            DO_NTOHS(metric, message + 10);
+            if(message[5] == 0 ||
+               (message[2] == 1 ? have_v4_prefix : have_v6_prefix))
+                rc = network_prefix(message[2], message[4], message[5],
+                                    message + 12,
+                                    message[2] == 1 ? v4_prefix : v6_prefix,
+                                    len - 10, prefix);
+            else
+                rc = -1;
+            if(rc < 0) {
+                if(message[3] & 0x80)
+                    have_v4_prefix = have_v6_prefix = 0;
+                goto fail;
+            }
+            parsed_len = 10 + rc;
+
+            plen = message[4] + (message[2] == 1 ? 96 : 0);
+
+            if(message[3] & 0x80) {
+                if(message[2] == 1) {
+                    memcpy(v4_prefix, prefix, 16);
+                    have_v4_prefix = 1;
+                } else {
+                    memcpy(v6_prefix, prefix, 16);
+                    have_v6_prefix = 1;
+                }
+            }
+            if(message[3] & 0x40) {
+                if(message[2] == 1) {
+                    memset(router_id, 0, 4);
+                    memcpy(router_id + 4, prefix + 12, 4);
+                } else {
+                    memcpy(router_id, prefix + 8, 8);
+                }
+                have_router_id = 1;
+            }
+            if(!have_router_id && message[2] != 0) {
+                zlog_err("Received prefix with no router id.");
+                goto fail;
+            }
+            debugf(BABEL_DEBUG_COMMON,"Received update%s%s for %s from %s on %s.",
+                   (message[3] & 0x80) ? "/prefix" : "",
+                   (message[3] & 0x40) ? "/id" : "",
+                   format_prefix(prefix, plen),
+                   format_address(from), ifp->name);
+
+            if(message[2] == 0) {
+                if(metric < 0xFFFF) {
+                    zlog_err("Received wildcard update with finite metric.");
+                    goto done;
+                }
+                retract_neighbour_routes(neigh);
+                goto done;
+            } else if(message[2] == 1) {
+                if(!have_v4_nh)
+                    goto fail;
+                nh = v4_nh;
+            } else if(have_v6_nh) {
+                nh = v6_nh;
+            } else {
+                nh = neigh->address;
+            }
+
+            if(message[2] == 1) {
+                if(!babel_get_if_nfo(ifp)->ipv4)
+                    goto done;
+            }
+
+            if((babel_get_if_nfo(ifp)->flags & BABEL_IF_FARAWAY)) {
+                channels[0] = 0;
+            } else {
+                /* This will be overwritten by parse_update_subtlv 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_update_subtlv(message + 2 + parsed_len,
+                                        len - parsed_len, channels);
+            }
+
+            update_route(router_id, prefix, plen, seqno, metric, interval,
+                         neigh, nh,
+                         channels, channels_len(channels));
+        } else if(type == MESSAGE_REQUEST) {
+            unsigned char prefix[16], plen;
+            int rc;
+            rc = network_prefix(message[2], message[3], 0,
+                                message + 4, NULL, len - 2, prefix);
+            if(rc < 0) goto fail;
+            plen = message[3] + (message[2] == 1 ? 96 : 0);
+            debugf(BABEL_DEBUG_COMMON,"Received request for %s from %s on %s.",
+                   message[2] == 0 ? "any" : format_prefix(prefix, plen),
+                   format_address(from), ifp->name);
+            if(message[2] == 0) {
+                struct babel_interface *neigh_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);
+                /* 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(neigh_ifp->last_update_time <
+                   (time_t)(babel_now.tv_sec -
+                            MAX(neigh_ifp->hello_interval / 100, 1)))
+                    send_update(neigh->ifp, 0, NULL, 0);
+            } else {
+                send_update(neigh->ifp, 0, prefix, plen);
+            }
+        } else if(type == MESSAGE_MH_REQUEST) {
+            unsigned char prefix[16], plen;
+            unsigned short seqno;
+            int rc;
+            DO_NTOHS(seqno, message + 4);
+            rc = network_prefix(message[2], message[3], 0,
+                                message + 16, NULL, len - 14, prefix);
+            if(rc < 0) goto fail;
+            plen = message[3] + (message[2] == 1 ? 96 : 0);
+            debugf(BABEL_DEBUG_COMMON,"Received request (%d) for %s from %s on %s (%s, %d).",
+                   message[6],
+                   format_prefix(prefix, plen),
+                   format_address(from), ifp->name,
+                   format_eui64(message + 8), seqno);
+            handle_request(neigh, prefix, plen, message[6],
+                           seqno, message + 8);
+        } else {
+            debugf(BABEL_DEBUG_COMMON,"Received unknown packet type %d from %s on %s.",
+                   type, format_address(from), ifp->name);
+        }
+    done:
+        i += len + 2;
+        continue;
+
+    fail:
+        zlog_err("Couldn't parse packet (%d, %d) from %s on %s.",
+                 message[0], message[1], format_address(from), ifp->name);
+        goto done;
+    }
+
+    /* We can calculate the RTT to this neighbour. */
+    if(have_hello_rtt && hello_send_us && hello_rtt_receive_time) {
+        int remote_waiting_us, local_waiting_us;
+        unsigned int rtt, smoothed_rtt;
+        unsigned int old_rttcost;
+        int changed = 0;
+        remote_waiting_us = neigh->hello_send_us - hello_rtt_receive_time;
+        local_waiting_us = time_us(neigh->hello_rtt_receive_time) -
+            hello_send_us;
+
+        /* Sanity checks (validity window of 10 minutes). */
+        if(remote_waiting_us < 0 || local_waiting_us < 0 ||
+           remote_waiting_us > 600000000 || local_waiting_us > 600000000)
+            return;
+
+        rtt = MAX(0, local_waiting_us - remote_waiting_us);
+        debugf(BABEL_DEBUG_COMMON, "RTT to %s on %s sample result: %d us.\n",
+               format_address(from), ifp->name, rtt);
+
+        old_rttcost = neighbour_rttcost(neigh);
+        if (valid_rtt(neigh)) {
+            /* Running exponential average. */
+            smoothed_rtt = (babel_ifp->rtt_decay * rtt +
+			    (256 - babel_ifp->rtt_decay) * neigh->rtt);
+            /* Rounding (up or down) to get closer to the sample. */
+            neigh->rtt = (neigh->rtt >= rtt) ? smoothed_rtt / 256 :
+                (smoothed_rtt + 255) / 256;
+        } else {
+            /* We prefer to be conservative with new neighbours
+               (higher RTT) */
+            assert(rtt <= 0x7FFFFFFF);
+            neigh->rtt = 2*rtt;
+        }
+        changed = (neighbour_rttcost(neigh) == old_rttcost ? 0 : 1);
+        update_neighbour_metric(neigh, changed);
+        neigh->rtt_time = babel_now;
+    }
+    return;
+}
+
+/* Under normal circumstances, there are enough moderation mechanisms
+   elsewhere in the protocol to make sure that this last-ditch check
+   should never trigger.  But I'm superstitious. */
+
+static int
+check_bucket(struct interface *ifp)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    if(babel_ifp->bucket <= 0) {
+        int seconds = babel_now.tv_sec - babel_ifp->bucket_time;
+        if(seconds > 0) {
+            babel_ifp->bucket = MIN(BUCKET_TOKENS_MAX,
+                              seconds * BUCKET_TOKENS_PER_SEC);
+        }
+        /* Reset bucket time unconditionally, in case clock is stepped. */
+        babel_ifp->bucket_time = babel_now.tv_sec;
+    }
+
+    if(babel_ifp->bucket > 0) {
+        babel_ifp->bucket--;
+        return 1;
+    } else {
+        return 0;
+    }
+}
+
+static int
+fill_rtt_message(struct interface *ifp)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    if((babel_ifp->flags & BABEL_IF_TIMESTAMPS) &&
+       (babel_ifp->buffered_hello >= 0)) {
+        if(babel_ifp->sendbuf[babel_ifp->buffered_hello + 8] == SUBTLV_PADN &&
+           babel_ifp->sendbuf[babel_ifp->buffered_hello + 9] == 4) {
+            unsigned int time;
+            /* Change the type of sub-TLV. */
+            babel_ifp->sendbuf[babel_ifp->buffered_hello + 8] =
+                SUBTLV_TIMESTAMP;
+            gettime(&babel_now);
+            time = time_us(babel_now);
+            DO_HTONL(babel_ifp->sendbuf + babel_ifp->buffered_hello + 10, time);
+            return 1;
+        } else {
+            zlog_err("No space left for timestamp sub-TLV "
+                     "(this shouldn't happen)");
+            return -1;
+        }
+    }
+    return 0;
+}
+
+void
+flushbuf(struct interface *ifp)
+{
+    int rc;
+    struct sockaddr_in6 sin6;
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+
+    assert(babel_ifp->buffered <= babel_ifp->bufsize);
+
+    flushupdates(ifp);
+
+    if(babel_ifp->buffered > 0) {
+        debugf(BABEL_DEBUG_COMMON,"  (flushing %d buffered bytes on %s)",
+               babel_ifp->buffered, ifp->name);
+        if(check_bucket(ifp)) {
+            memset(&sin6, 0, sizeof(sin6));
+            sin6.sin6_family = AF_INET6;
+            memcpy(&sin6.sin6_addr, protocol_group, 16);
+            sin6.sin6_port = htons(protocol_port);
+            sin6.sin6_scope_id = ifp->ifindex;
+            DO_HTONS(packet_header + 2, babel_ifp->buffered);
+            fill_rtt_message(ifp);
+            rc = babel_send(protocol_socket,
+                            packet_header, sizeof(packet_header),
+                            babel_ifp->sendbuf, babel_ifp->buffered,
+                            (struct sockaddr*)&sin6, sizeof(sin6));
+            if(rc < 0)
+                zlog_err("send: %s", safe_strerror(errno));
+        } else {
+            zlog_err("Warning: bucket full, dropping packet to %s.",
+                     ifp->name);
+        }
+    }
+    VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp->sendbuf, babel_ifp->bufsize);
+    babel_ifp->buffered = 0;
+    babel_ifp->buffered_hello = -1;
+    babel_ifp->have_buffered_id = 0;
+    babel_ifp->have_buffered_nh = 0;
+    babel_ifp->have_buffered_prefix = 0;
+    babel_ifp->flush_timeout.tv_sec = 0;
+    babel_ifp->flush_timeout.tv_usec = 0;
+}
+
+static void
+schedule_flush(struct interface *ifp)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    unsigned msecs = jitter(babel_ifp, 0);
+    if(babel_ifp->flush_timeout.tv_sec != 0 &&
+       timeval_minus_msec(&babel_ifp->flush_timeout, &babel_now) < msecs)
+        return;
+    set_timeout(&babel_ifp->flush_timeout, msecs);
+}
+
+static void
+schedule_flush_now(struct interface *ifp)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    /* Almost now */
+    unsigned msecs = roughly(10);
+    if(babel_ifp->flush_timeout.tv_sec != 0 &&
+       timeval_minus_msec(&babel_ifp->flush_timeout, &babel_now) < msecs)
+        return;
+    set_timeout(&babel_ifp->flush_timeout, msecs);
+}
+
+static void
+schedule_unicast_flush(unsigned msecs)
+{
+    if(!unicast_neighbour)
+        return;
+    if(unicast_flush_timeout.tv_sec != 0 &&
+       timeval_minus_msec(&unicast_flush_timeout, &babel_now) < msecs)
+        return;
+    unicast_flush_timeout.tv_usec = (babel_now.tv_usec + msecs * 1000) %1000000;
+    unicast_flush_timeout.tv_sec =
+        babel_now.tv_sec + (babel_now.tv_usec / 1000 + msecs) / 1000;
+}
+
+static void
+ensure_space(struct interface *ifp, int space)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    if(babel_ifp->bufsize - babel_ifp->buffered < space)
+        flushbuf(ifp);
+}
+
+static void
+start_message(struct interface *ifp, int type, int len)
+{
+  babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    if(babel_ifp->bufsize - babel_ifp->buffered < len + 2)
+        flushbuf(ifp);
+    babel_ifp->sendbuf[babel_ifp->buffered++] = type;
+    babel_ifp->sendbuf[babel_ifp->buffered++] = len;
+}
+
+static void
+end_message(struct interface *ifp, int type, int bytes)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    assert(babel_ifp->buffered >= bytes + 2 &&
+           babel_ifp->sendbuf[babel_ifp->buffered - bytes - 2] == type &&
+           babel_ifp->sendbuf[babel_ifp->buffered - bytes - 1] == bytes);
+    schedule_flush(ifp);
+}
+
+static void
+accumulate_byte(struct interface *ifp, unsigned char value)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    babel_ifp->sendbuf[babel_ifp->buffered++] = value;
+}
+
+static void
+accumulate_short(struct interface *ifp, unsigned short value)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    DO_HTONS(babel_ifp->sendbuf + babel_ifp->buffered, value);
+    babel_ifp->buffered += 2;
+}
+
+static void
+accumulate_int(struct interface *ifp, unsigned int value)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    DO_HTONL(babel_ifp->sendbuf + babel_ifp->buffered, value);
+    babel_ifp->buffered += 4;
+}
+
+static void
+accumulate_bytes(struct interface *ifp,
+                 const unsigned char *value, unsigned len)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    memcpy(babel_ifp->sendbuf + babel_ifp->buffered, value, len);
+    babel_ifp->buffered += len;
+}
+
+static int
+start_unicast_message(struct neighbour *neigh, int type, int len)
+{
+    if(unicast_neighbour) {
+        if(neigh != unicast_neighbour ||
+           unicast_buffered + len + 2 >=
+           MIN(UNICAST_BUFSIZE, babel_get_if_nfo(neigh->ifp)->bufsize))
+            flush_unicast(0);
+    }
+    if(!unicast_buffer)
+        unicast_buffer = malloc(UNICAST_BUFSIZE);
+    if(!unicast_buffer) {
+        zlog_err("malloc(unicast_buffer): %s", safe_strerror(errno));
+        return -1;
+    }
+
+    unicast_neighbour = neigh;
+
+    unicast_buffer[unicast_buffered++] = type;
+    unicast_buffer[unicast_buffered++] = len;
+    return 1;
+}
+
+static void
+end_unicast_message(struct neighbour *neigh, int type, int bytes)
+{
+    assert(unicast_neighbour == neigh && unicast_buffered >= bytes + 2 &&
+           unicast_buffer[unicast_buffered - bytes - 2] == type &&
+           unicast_buffer[unicast_buffered - bytes - 1] == bytes);
+    schedule_unicast_flush(jitter(babel_get_if_nfo(neigh->ifp), 0));
+}
+
+static void
+accumulate_unicast_byte(struct neighbour *neigh, unsigned char value)
+{
+    unicast_buffer[unicast_buffered++] = value;
+}
+
+static void
+accumulate_unicast_short(struct neighbour *neigh, unsigned short value)
+{
+    DO_HTONS(unicast_buffer + unicast_buffered, value);
+    unicast_buffered += 2;
+}
+
+static void
+accumulate_unicast_int(struct neighbour *neigh, unsigned int value)
+{
+    DO_HTONL(unicast_buffer + unicast_buffered, value);
+    unicast_buffered += 4;
+}
+
+static void
+accumulate_unicast_bytes(struct neighbour *neigh,
+                         const unsigned char *value, unsigned len)
+{
+    memcpy(unicast_buffer + unicast_buffered, value, len);
+    unicast_buffered += len;
+}
+
+void
+send_ack(struct neighbour *neigh, unsigned short nonce, unsigned short interval)
+{
+    int rc;
+    debugf(BABEL_DEBUG_COMMON,"Sending ack (%04x) to %s on %s.",
+           nonce, format_address(neigh->address), neigh->ifp->name);
+    rc = start_unicast_message(neigh, MESSAGE_ACK, 2); if(rc < 0) return;
+    accumulate_unicast_short(neigh, nonce);
+    end_unicast_message(neigh, MESSAGE_ACK, 2);
+    /* Roughly yields a value no larger than 3/2, so this meets the deadline */
+    schedule_unicast_flush(roughly(interval * 6));
+}
+
+void
+send_hello_noupdate(struct interface *ifp, unsigned interval)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    /* This avoids sending multiple hellos in a single packet, which breaks
+       link quality estimation. */
+    if(babel_ifp->buffered_hello >= 0)
+        flushbuf(ifp);
+
+    babel_ifp->hello_seqno = seqno_plus(babel_ifp->hello_seqno, 1);
+    set_timeout(&babel_ifp->hello_timeout, babel_ifp->hello_interval);
+
+    if(!if_up(ifp))
+        return;
+
+    debugf(BABEL_DEBUG_COMMON,"Sending hello %d (%d) to %s.",
+           babel_ifp->hello_seqno, interval, ifp->name);
+
+    start_message(ifp, MESSAGE_HELLO,
+                  (babel_ifp->flags & BABEL_IF_TIMESTAMPS) ? 12 : 6);
+    babel_ifp->buffered_hello = babel_ifp->buffered - 2;
+    accumulate_short(ifp, 0);
+    accumulate_short(ifp, babel_ifp->hello_seqno);
+    accumulate_short(ifp, interval > 0xFFFF ? 0xFFFF : interval);
+    if(babel_ifp->flags & BABEL_IF_TIMESTAMPS) {
+        /* Sub-TLV containing the local time of emission. We use a
+           Pad4 sub-TLV, which we'll fill just before sending. */
+        accumulate_byte(ifp, SUBTLV_PADN);
+        accumulate_byte(ifp, 4);
+        accumulate_int(ifp, 0);
+    }
+    end_message(ifp, MESSAGE_HELLO,
+                (babel_ifp->flags & BABEL_IF_TIMESTAMPS) ? 12 : 6);
+}
+
+void
+send_hello(struct interface *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)
+        send_ihu(NULL, ifp);
+    else
+        send_marginal_ihu(ifp);
+}
+
+void
+flush_unicast(int dofree)
+{
+    struct sockaddr_in6 sin6;
+    int rc;
+
+    if(unicast_buffered == 0)
+        goto done;
+
+    if(!if_up(unicast_neighbour->ifp))
+        goto done;
+
+    /* Preserve ordering of messages */
+    flushbuf(unicast_neighbour->ifp);
+
+    if(check_bucket(unicast_neighbour->ifp)) {
+        memset(&sin6, 0, sizeof(sin6));
+        sin6.sin6_family = AF_INET6;
+        memcpy(&sin6.sin6_addr, unicast_neighbour->address, 16);
+        sin6.sin6_port = htons(protocol_port);
+        sin6.sin6_scope_id = unicast_neighbour->ifp->ifindex;
+        DO_HTONS(packet_header + 2, unicast_buffered);
+        fill_rtt_message(unicast_neighbour->ifp);
+        rc = babel_send(protocol_socket,
+                        packet_header, sizeof(packet_header),
+                        unicast_buffer, unicast_buffered,
+                        (struct sockaddr*)&sin6, sizeof(sin6));
+        if(rc < 0)
+            zlog_err("send(unicast): %s", safe_strerror(errno));
+    } else {
+        zlog_err("Warning: bucket full, dropping unicast packet to %s if %s.",
+                 format_address(unicast_neighbour->address),
+                 unicast_neighbour->ifp->name);
+    }
+
+ done:
+    VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer, UNICAST_BUFSIZE);
+    unicast_buffered = 0;
+    if(dofree && unicast_buffer) {
+        free(unicast_buffer);
+        unicast_buffer = NULL;
+    }
+    unicast_neighbour = NULL;
+    unicast_flush_timeout.tv_sec = 0;
+    unicast_flush_timeout.tv_usec = 0;
+}
+
+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 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;
+
+    add_metric = output_filter(id, prefix, plen, ifp->ifindex);
+    if(add_metric >= INFINITY)
+        return;
+
+    metric = MIN(metric + add_metric, INFINITY);
+    /* Worst case */
+    ensure_space(ifp, 20 + 12 + 28);
+
+    v4 = plen >= 96 && v4mapped(prefix);
+
+    if(v4) {
+        if(!babel_ifp->ipv4)
+            return;
+        if(!babel_ifp->have_buffered_nh ||
+           memcmp(babel_ifp->buffered_nh, babel_ifp->ipv4, 4) != 0) {
+            start_message(ifp, MESSAGE_NH, 6);
+            accumulate_byte(ifp, 1);
+            accumulate_byte(ifp, 0);
+            accumulate_bytes(ifp, babel_ifp->ipv4, 4);
+            end_message(ifp, MESSAGE_NH, 6);
+            memcpy(babel_ifp->buffered_nh, babel_ifp->ipv4, 4);
+            babel_ifp->have_buffered_nh = 1;
+        }
+
+        real_prefix = prefix + 12;
+        real_plen = plen - 96;
+    } else {
+        if(babel_ifp->have_buffered_prefix) {
+            while(omit < plen / 8 &&
+                  babel_ifp->buffered_prefix[omit] == prefix[omit])
+                omit++;
+        }
+        if(!babel_ifp->have_buffered_prefix || plen >= 48)
+            flags |= 0x80;
+        real_prefix = prefix;
+        real_plen = plen;
+    }
+
+    if(!babel_ifp->have_buffered_id
+       || memcmp(id, babel_ifp->buffered_id, 8) != 0) {
+        if(real_plen == 128 && memcmp(real_prefix + 8, id, 8) == 0) {
+            flags |= 0x40;
+        } else {
+            start_message(ifp, MESSAGE_ROUTER_ID, 10);
+            accumulate_short(ifp, 0);
+            accumulate_bytes(ifp, id, 8);
+            end_message(ifp, MESSAGE_ROUTER_ID, 10);
+        }
+        memcpy(babel_ifp->buffered_id, id, 16);
+        babel_ifp->have_buffered_id = 1;
+    }
+
+    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);
+    accumulate_byte(ifp, omit);
+    accumulate_short(ifp, (babel_ifp->update_interval + 5) / 10);
+    accumulate_short(ifp, seqno);
+    accumulate_short(ifp, metric);
+    accumulate_bytes(ifp, real_prefix + omit, (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);
+        babel_ifp->have_buffered_prefix = 1;
+    }
+}
+
+static int
+compare_buffered_updates(const void *av, const void *bv)
+{
+    const struct buffered_update *a = av, *b = bv;
+    int rc, v4a, v4b, ma, mb;
+
+    rc = memcmp(a->id, b->id, 8);
+    if(rc != 0)
+        return rc;
+
+    v4a = (a->plen >= 96 && v4mapped(a->prefix));
+    v4b = (b->plen >= 96 && v4mapped(b->prefix));
+
+    if(v4a > v4b)
+        return 1;
+    else if(v4a < v4b)
+        return -1;
+
+    ma = (!v4a && a->plen == 128 && memcmp(a->prefix + 8, a->id, 8) == 0);
+    mb = (!v4b && b->plen == 128 && memcmp(b->prefix + 8, b->id, 8) == 0);
+
+    if(ma > mb)
+        return -1;
+    else if(mb > ma)
+        return 1;
+
+    if(a->plen < b->plen)
+        return 1;
+    else if(a->plen > b->plen)
+        return -1;
+
+    return memcmp(a->prefix, b->prefix, 16);
+}
+
+void
+flushupdates(struct interface *ifp)
+{
+    babel_interface_nfo *babel_ifp = NULL;
+    struct xroute *xroute;
+    struct babel_route *route;
+    const unsigned char *last_prefix = NULL;
+    unsigned char last_plen = 0xFF;
+    int i;
+
+    if(ifp == NULL) {
+      struct interface *ifp_aux;
+      struct listnode *linklist_node = NULL;
+        FOR_ALL_INTERFACES(ifp_aux, linklist_node)
+            flushupdates(ifp_aux);
+        return;
+    }
+
+    babel_ifp = babel_get_if_nfo(ifp);
+    if(babel_ifp->num_buffered_updates > 0) {
+        struct buffered_update *b = babel_ifp->buffered_updates;
+        int n = babel_ifp->num_buffered_updates;
+
+        babel_ifp->buffered_updates = NULL;
+        babel_ifp->update_bufsize = 0;
+        babel_ifp->num_buffered_updates = 0;
+
+        if(!if_up(ifp))
+            goto done;
+
+        debugf(BABEL_DEBUG_COMMON,"  (flushing %d buffered updates on %s (%d))",
+               n, ifp->name, ifp->ifindex);
+
+        /* In order to send fewer update messages, we want to send updates
+           with the same router-id together, with IPv6 going out before IPv4. */
+
+        for(i = 0; i < n; i++) {
+            route = find_installed_route(b[i].prefix, b[i].plen);
+            if(route)
+                memcpy(b[i].id, route->src->id, 8);
+            else
+                memcpy(b[i].id, myid, 8);
+        }
+
+        qsort(b, n, sizeof(struct buffered_update), compare_buffered_updates);
+
+        for(i = 0; i < n; i++) {
+            /* 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. */
+
+            if(last_prefix) {
+                if(b[i].plen == last_plen &&
+                   memcmp(b[i].prefix, last_prefix, 16) == 0)
+                    continue;
+            }
+
+            xroute = find_xroute(b[i].prefix, b[i].plen);
+            route = find_installed_route(b[i].prefix, b[i].plen);
+
+            if(xroute && (!route || xroute->metric <= kernel_metric)) {
+                really_send_update(ifp, myid,
+                                   xroute->prefix, xroute->plen,
+                                   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_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,
+                                   channels, chlen);
+                update_source(route->src, seqno, metric);
+                last_prefix = route->src->prefix;
+                last_plen = route->src->plen;
+            } else {
+            /* 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, NULL, -1);
+            }
+        }
+        schedule_flush_now(ifp);
+    done:
+        free(b);
+    }
+    babel_ifp->update_flush_timeout.tv_sec = 0;
+    babel_ifp->update_flush_timeout.tv_usec = 0;
+}
+
+static void
+schedule_update_flush(struct interface *ifp, int urgent)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    unsigned msecs;
+    msecs = update_jitter(babel_ifp, urgent);
+    if(babel_ifp->update_flush_timeout.tv_sec != 0 &&
+       timeval_minus_msec(&babel_ifp->update_flush_timeout, &babel_now) < msecs)
+        return;
+    set_timeout(&babel_ifp->update_flush_timeout, msecs);
+}
+
+static void
+buffer_update(struct interface *ifp,
+              const unsigned char *prefix, unsigned char plen)
+{
+    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+    if(babel_ifp->num_buffered_updates > 0 &&
+       babel_ifp->num_buffered_updates >= babel_ifp->update_bufsize)
+        flushupdates(ifp);
+
+    if(babel_ifp->update_bufsize == 0) {
+        int n;
+        assert(babel_ifp->buffered_updates == NULL);
+        /* 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;
+            }
+            return;
+        }
+        babel_ifp->update_bufsize = n;
+        babel_ifp->num_buffered_updates = 0;
+    }
+
+    memcpy(babel_ifp->buffered_updates[babel_ifp->num_buffered_updates].prefix,
+           prefix, 16);
+    babel_ifp->buffered_updates[babel_ifp->num_buffered_updates].plen = plen;
+    babel_ifp->num_buffered_updates++;
+}
+
+void
+send_update(struct interface *ifp, int urgent,
+            const unsigned char *prefix, unsigned char plen)
+{
+    babel_interface_nfo *babel_ifp = NULL;
+
+    if(ifp == NULL) {
+      struct interface *ifp_aux;
+      struct listnode *linklist_node = NULL;
+        struct babel_route *route;
+        FOR_ALL_INTERFACES(ifp_aux, linklist_node)
+            send_update(ifp_aux, urgent, prefix, plen);
+        if(prefix) {
+            /* Since flushupdates only deals with non-wildcard interfaces, we
+               need to do this now. */
+            route = find_installed_route(prefix, plen);
+            if(route && route_metric(route) < INFINITY)
+                satisfy_request(prefix, plen, route->src->seqno, route->src->id,
+                                NULL);
+        }
+        return;
+    }
+
+    if(!if_up(ifp))
+        return;
+
+    babel_ifp = babel_get_if_nfo(ifp);
+    if(prefix) {
+        debugf(BABEL_DEBUG_COMMON,"Sending update to %s for %s.",
+               ifp->name, format_prefix(prefix, plen));
+        buffer_update(ifp, prefix, plen);
+    } else {
+        struct route_stream *routes = NULL;
+        send_self_update(ifp);
+        debugf(BABEL_DEBUG_COMMON,"Sending update to %s for any.", ifp->name);
+        routes = route_stream(1);
+        if(routes) {
+            while(1) {
+                struct babel_route *route = route_stream_next(routes);
+                if(route == NULL)
+                    break;
+                buffer_update(ifp, route->src->prefix, route->src->plen);
+            }
+            route_stream_done(routes);
+        } else {
+            zlog_err("Couldn't allocate route stream.");
+        }
+        set_timeout(&babel_ifp->update_timeout, babel_ifp->update_interval);
+        babel_ifp->last_update_time = babel_now.tv_sec;
+    }
+    schedule_update_flush(ifp, urgent);
+}
+
+void
+send_update_resend(struct interface *ifp,
+                   const unsigned char *prefix, unsigned char plen)
+{
+    assert(prefix != NULL);
+
+    send_update(ifp, 1, prefix, plen);
+    record_resend(RESEND_UPDATE, prefix, plen, 0, NULL, NULL, resend_delay);
+}
+
+void
+send_wildcard_retraction(struct interface *ifp)
+{
+    babel_interface_nfo *babel_ifp = NULL;
+    if(ifp == NULL) {
+      struct interface *ifp_aux;
+      struct listnode *linklist_node = NULL;
+        FOR_ALL_INTERFACES(ifp_aux, linklist_node)
+            send_wildcard_retraction(ifp_aux);
+        return;
+    }
+
+    if(!if_up(ifp))
+        return;
+
+    babel_ifp = babel_get_if_nfo(ifp);
+    start_message(ifp, MESSAGE_UPDATE, 10);
+    accumulate_byte(ifp, 0);
+    accumulate_byte(ifp, 0x40);
+    accumulate_byte(ifp, 0);
+    accumulate_byte(ifp, 0);
+    accumulate_short(ifp, 0xFFFF);
+    accumulate_short(ifp, myseqno);
+    accumulate_short(ifp, 0xFFFF);
+    end_message(ifp, MESSAGE_UPDATE, 10);
+
+    babel_ifp->have_buffered_id = 0;
+}
+
+void
+update_myseqno()
+{
+    myseqno = seqno_plus(myseqno, 1);
+}
+
+void
+send_self_update(struct interface *ifp)
+{
+    struct xroute_stream *xroutes;
+    if(ifp == NULL) {
+      struct interface *ifp_aux;
+      struct listnode *linklist_node = NULL;
+        FOR_ALL_INTERFACES(ifp_aux, linklist_node) {
+            if(!if_up(ifp_aux))
+                continue;
+            send_self_update(ifp_aux);
+        }
+        return;
+    }
+
+    debugf(BABEL_DEBUG_COMMON,"Sending self update to %s.", ifp->name);
+    xroutes = xroute_stream();
+    if(xroutes) {
+        while(1) {
+            struct xroute *xroute = xroute_stream_next(xroutes);
+            if(xroute == NULL) break;
+            send_update(ifp, 0, xroute->prefix, xroute->plen);
+        }
+        xroute_stream_done(xroutes);
+    } else {
+        zlog_err("Couldn't allocate xroute stream.");
+    }
+}
+
+void
+send_ihu(struct neighbour *neigh, struct interface *ifp)
+{
+    babel_interface_nfo *babel_ifp = NULL;
+    int rxcost, interval;
+    int ll;
+    int send_rtt_data;
+    int msglen;
+
+    if(neigh == NULL && ifp == NULL) {
+        struct interface *ifp_aux;
+      struct listnode *linklist_node = NULL;
+        FOR_ALL_INTERFACES(ifp_aux, linklist_node) {
+            if(if_up(ifp_aux))
+                continue;
+            send_ihu(NULL, ifp_aux);
+        }
+        return;
+    }
+
+    if(neigh == NULL) {
+        struct neighbour *ngh;
+        FOR_ALL_NEIGHBOURS(ngh) {
+            if(ngh->ifp == ifp)
+                send_ihu(ngh, ifp);
+        }
+        return;
+    }
+
+
+    if(ifp && neigh->ifp != ifp)
+        return;
+
+    ifp = neigh->ifp;
+    babel_ifp = babel_get_if_nfo(ifp);
+    if(!if_up(ifp))
+        return;
+
+    rxcost = neighbour_rxcost(neigh);
+    interval = (babel_ifp->hello_interval * 3 + 9) / 10;
+
+    /* Conceptually, an IHU is a unicast message.  We usually send them as
+       multicast, since this allows aggregation into a single packet and
+       avoids an ARP exchange.  If we already have a unicast message queued
+       for this neighbour, however, we might as well piggyback the IHU. */
+    debugf(BABEL_DEBUG_COMMON,"Sending %sihu %d on %s to %s.",
+           unicast_neighbour == neigh ? "unicast " : "",
+           rxcost,
+           neigh->ifp->name,
+           format_address(neigh->address));
+
+    ll = linklocal(neigh->address);
+
+    if((babel_ifp->flags & BABEL_IF_TIMESTAMPS) && neigh->hello_send_us
+       /* Checks whether the RTT data is not too old to be sent. */
+       && timeval_minus_msec(&babel_now,
+                             &neigh->hello_rtt_receive_time) < 1000000) {
+        send_rtt_data = 1;
+    } else {
+        neigh->hello_send_us = 0;
+        send_rtt_data = 0;
+    }
+
+    /* The length depends on the format of the address, and then an
+       optional 10-bytes sub-TLV for timestamps (used to compute a RTT). */
+    msglen = (ll ? 14 : 22) + (send_rtt_data ? 10 : 0);
+
+    if(unicast_neighbour != neigh) {
+        start_message(ifp, MESSAGE_IHU, msglen);
+        accumulate_byte(ifp, ll ? 3 : 2);
+        accumulate_byte(ifp, 0);
+        accumulate_short(ifp, rxcost);
+        accumulate_short(ifp, interval);
+        if(ll)
+            accumulate_bytes(ifp, neigh->address + 8, 8);
+        else
+            accumulate_bytes(ifp, neigh->address, 16);
+        if (send_rtt_data) {
+            accumulate_byte(ifp, SUBTLV_TIMESTAMP);
+            accumulate_byte(ifp, 8);
+            accumulate_int(ifp, neigh->hello_send_us);
+            accumulate_int(ifp, time_us(neigh->hello_rtt_receive_time));
+        }
+        end_message(ifp, MESSAGE_IHU, msglen);
+    } else {
+        int rc;
+        rc = start_unicast_message(neigh, MESSAGE_IHU, msglen);
+        if(rc < 0) return;
+        accumulate_unicast_byte(neigh, ll ? 3 : 2);
+        accumulate_unicast_byte(neigh, 0);
+        accumulate_unicast_short(neigh, rxcost);
+        accumulate_unicast_short(neigh, interval);
+        if(ll)
+            accumulate_unicast_bytes(neigh, neigh->address + 8, 8);
+        else
+            accumulate_unicast_bytes(neigh, neigh->address, 16);
+        if (send_rtt_data) {
+            accumulate_unicast_byte(neigh, SUBTLV_TIMESTAMP);
+            accumulate_unicast_byte(neigh, 8);
+            accumulate_unicast_int(neigh, neigh->hello_send_us);
+            accumulate_unicast_int(neigh,
+                                   time_us(neigh->hello_rtt_receive_time));
+        }
+        end_unicast_message(neigh, MESSAGE_IHU, msglen);
+    }
+}
+
+/* Send IHUs to all marginal neighbours */
+void
+send_marginal_ihu(struct interface *ifp)
+{
+    struct neighbour *neigh;
+    FOR_ALL_NEIGHBOURS(neigh) {
+        if(ifp && neigh->ifp != ifp)
+            continue;
+        if(neigh->txcost >= 384 || (neigh->reach & 0xF000) != 0xF000)
+            send_ihu(neigh, ifp);
+    }
+}
+
+void
+send_request(struct interface *ifp,
+             const unsigned char *prefix, unsigned char plen)
+{
+    int v4, pb, len;
+
+    if(ifp == NULL) {
+      struct interface *ifp_aux;
+      struct listnode *linklist_node = NULL;
+        FOR_ALL_INTERFACES(ifp_aux, linklist_node) {
+            if(if_up(ifp_aux))
+                continue;
+            send_request(ifp_aux, prefix, plen);
+        }
+        return;
+    }
+
+    /* make sure any buffered updates go out before this request. */
+    flushupdates(ifp);
+
+    if(!if_up(ifp))
+        return;
+
+    debugf(BABEL_DEBUG_COMMON,"sending request to %s for %s.",
+           ifp->name, prefix ? format_prefix(prefix, plen) : "any");
+    v4 = plen >= 96 && v4mapped(prefix);
+    pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
+    len = !prefix ? 2 : 2 + pb;
+
+    start_message(ifp, MESSAGE_REQUEST, len);
+    accumulate_byte(ifp, !prefix ? 0 : v4 ? 1 : 2);
+    accumulate_byte(ifp, !prefix ? 0 : v4 ? plen - 96 : plen);
+    if(prefix) {
+        if(v4)
+            accumulate_bytes(ifp, prefix + 12, pb);
+        else
+            accumulate_bytes(ifp, prefix, pb);
+    }
+    end_message(ifp, MESSAGE_REQUEST, len);
+}
+
+void
+send_unicast_request(struct neighbour *neigh,
+                     const unsigned char *prefix, unsigned char plen)
+{
+    int rc, v4, pb, len;
+
+    /* make sure any buffered updates go out before this request. */
+    flushupdates(neigh->ifp);
+
+    debugf(BABEL_DEBUG_COMMON,"sending unicast request to %s for %s.",
+           format_address(neigh->address),
+           prefix ? format_prefix(prefix, plen) : "any");
+    v4 = plen >= 96 && v4mapped(prefix);
+    pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
+    len = !prefix ? 2 : 2 + pb;
+
+    rc = start_unicast_message(neigh, MESSAGE_REQUEST, len);
+    if(rc < 0) return;
+    accumulate_unicast_byte(neigh, !prefix ? 0 : v4 ? 1 : 2);
+    accumulate_unicast_byte(neigh, !prefix ? 0 : v4 ? plen - 96 : plen);
+    if(prefix) {
+        if(v4)
+            accumulate_unicast_bytes(neigh, prefix + 12, pb);
+        else
+            accumulate_unicast_bytes(neigh, prefix, pb);
+    }
+    end_unicast_message(neigh, MESSAGE_REQUEST, len);
+}
+
+void
+send_multihop_request(struct interface *ifp,
+                      const unsigned char *prefix, unsigned char plen,
+                      unsigned short seqno, const unsigned char *id,
+                      unsigned short hop_count)
+{
+    int v4, pb, len;
+
+    /* Make sure any buffered updates go out before this request. */
+    flushupdates(ifp);
+
+    if(ifp == NULL) {
+      struct interface *ifp_aux;
+      struct listnode *linklist_node = NULL;
+        FOR_ALL_INTERFACES(ifp_aux, linklist_node) {
+            if(!if_up(ifp_aux))
+                continue;
+            send_multihop_request(ifp_aux, prefix, plen, seqno, id, hop_count);
+        }
+        return;
+    }
+
+    if(!if_up(ifp))
+        return;
+
+    debugf(BABEL_DEBUG_COMMON,"Sending request (%d) on %s for %s.",
+           hop_count, ifp->name, format_prefix(prefix, plen));
+    v4 = plen >= 96 && v4mapped(prefix);
+    pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
+    len = 6 + 8 + pb;
+
+    start_message(ifp, MESSAGE_MH_REQUEST, len);
+    accumulate_byte(ifp, v4 ? 1 : 2);
+    accumulate_byte(ifp, v4 ? plen - 96 : plen);
+    accumulate_short(ifp, seqno);
+    accumulate_byte(ifp, hop_count);
+    accumulate_byte(ifp, 0);
+    accumulate_bytes(ifp, id, 8);
+    if(prefix) {
+        if(v4)
+            accumulate_bytes(ifp, prefix + 12, pb);
+        else
+            accumulate_bytes(ifp, prefix, pb);
+    }
+    end_message(ifp, MESSAGE_MH_REQUEST, len);
+}
+
+void
+send_unicast_multihop_request(struct neighbour *neigh,
+                              const unsigned char *prefix, unsigned char plen,
+                              unsigned short seqno, const unsigned char *id,
+                              unsigned short hop_count)
+{
+    int rc, v4, pb, len;
+
+    /* Make sure any buffered updates go out before this request. */
+    flushupdates(neigh->ifp);
+
+    debugf(BABEL_DEBUG_COMMON,"Sending multi-hop request to %s for %s (%d hops).",
+           format_address(neigh->address),
+           format_prefix(prefix, plen), hop_count);
+    v4 = plen >= 96 && v4mapped(prefix);
+    pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
+    len = 6 + 8 + pb;
+
+    rc = start_unicast_message(neigh, MESSAGE_MH_REQUEST, len);
+    if(rc < 0) return;
+    accumulate_unicast_byte(neigh, v4 ? 1 : 2);
+    accumulate_unicast_byte(neigh, v4 ? plen - 96 : plen);
+    accumulate_unicast_short(neigh, seqno);
+    accumulate_unicast_byte(neigh, hop_count);
+    accumulate_unicast_byte(neigh, 0);
+    accumulate_unicast_bytes(neigh, id, 8);
+    if(prefix) {
+        if(v4)
+            accumulate_unicast_bytes(neigh, prefix + 12, pb);
+        else
+            accumulate_unicast_bytes(neigh, prefix, pb);
+    }
+    end_unicast_message(neigh, MESSAGE_MH_REQUEST, len);
+}
+
+void
+send_request_resend(struct neighbour *neigh,
+                    const unsigned char *prefix, unsigned char plen,
+                    unsigned short seqno, unsigned char *id)
+{
+    if(neigh)
+        send_unicast_multihop_request(neigh, prefix, plen, seqno, id, 127);
+    else
+        send_multihop_request(NULL, prefix, plen, seqno, id, 127);
+
+    record_resend(RESEND_REQUEST, prefix, plen, seqno, id,
+                  neigh ? neigh->ifp : NULL, resend_delay);
+}
+
+void
+handle_request(struct neighbour *neigh, const unsigned char *prefix,
+               unsigned char plen, unsigned char hop_count,
+               unsigned short seqno, const unsigned char *id)
+{
+    struct xroute *xroute;
+    struct babel_route *route;
+    struct neighbour *successor = NULL;
+
+    xroute = find_xroute(prefix, plen);
+    route = find_installed_route(prefix, plen);
+
+    if(xroute && (!route || xroute->metric <= kernel_metric)) {
+        if(hop_count > 0 && memcmp(id, myid, 8) == 0) {
+            if(seqno_compare(seqno, myseqno) > 0) {
+                if(seqno_minus(seqno, myseqno) > 100) {
+                    /* Hopelessly out-of-date request */
+                    return;
+                }
+                update_myseqno();
+            }
+        }
+        send_update(neigh->ifp, 1, prefix, plen);
+        return;
+    }
+
+    if(route &&
+       (memcmp(id, route->src->id, 8) != 0 ||
+        seqno_compare(seqno, route->seqno) <= 0)) {
+        send_update(neigh->ifp, 1, prefix, plen);
+        return;
+    }
+
+    if(hop_count <= 1)
+        return;
+
+    if(route && memcmp(id, route->src->id, 8) == 0 &&
+       seqno_minus(seqno, route->seqno) > 100) {
+        /* Hopelessly out-of-date */
+        return;
+    }
+
+    if(request_redundant(neigh->ifp, prefix, plen, seqno, id))
+        return;
+
+    /* Let's try to forward this request. */
+    if(route && route_metric(route) < INFINITY)
+        successor = route->neigh;
+
+    if(!successor || successor == neigh) {
+        /* We were about to forward a request to its requestor.  Try to
+           find a different neighbour to forward the request to. */
+        struct babel_route *other_route;
+
+        other_route = find_best_route(prefix, plen, 0, neigh);
+        if(other_route && route_metric(other_route) < INFINITY)
+            successor = other_route->neigh;
+    }
+
+    if(!successor || successor == neigh)
+        /* Give up */
+        return;
+
+    send_unicast_multihop_request(successor, prefix, plen, seqno, id,
+                                  hop_count - 1);
+    record_resend(RESEND_REQUEST, prefix, plen, seqno, id,
+                  neigh->ifp, 0);
+}