[mirror_frr.git] / babeld / neighbour.c

/*
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.
*/

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <sys/time.h>
#include <time.h>

#include <zebra.h>
#include "if.h"

#include "babel_main.h"
#include "babeld.h"
#include "util.h"
#include "babel_interface.h"
#include "neighbour.h"
#include "source.h"
#include "route.h"
#include "message.h"
#include "resend.h"
#include "babel_errors.h"

struct neighbour *neighs = NULL;

static struct neighbour *
find_neighbour_nocreate(const unsigned char *address, struct interface *ifp)
{
    struct neighbour *neigh;
    FOR_ALL_NEIGHBOURS(neigh) {
        if(memcmp(address, neigh->address, 16) == 0 &&
           neigh->ifp == ifp)
            return neigh;
    }
    return NULL;
}

void
flush_neighbour(struct neighbour *neigh)
{
    debugf(BABEL_DEBUG_COMMON,"Flushing neighbour %s (reach 0x%04x)",
           format_address(neigh->address), neigh->reach);
    flush_neighbour_routes(neigh);
    if(unicast_neighbour == neigh)
        flush_unicast(1);
    flush_resends(neigh);

    if(neighs == neigh) {
        neighs = neigh->next;
    } else {
        struct neighbour *previous = neighs;
        while(previous->next != neigh)
            previous = previous->next;
        previous->next = neigh->next;
    }
    free(neigh);
}

struct neighbour *
find_neighbour(const unsigned char *address, struct interface *ifp)
{
    struct neighbour *neigh;
    const struct timeval zero = {0, 0};

    neigh = find_neighbour_nocreate(address, ifp);
    if(neigh)
        return neigh;

    debugf(BABEL_DEBUG_COMMON,"Creating neighbour %s on %s.",
           format_address(address), ifp->name);

    neigh = malloc(sizeof(struct neighbour));
    if(neigh == NULL) {
        flog_err(EC_BABEL_MEMORY, "malloc(neighbour): %s",
		  safe_strerror(errno));
        return NULL;
    }

    neigh->hello_seqno = -1;
    memcpy(neigh->address, address, 16);
    neigh->reach = 0;
    neigh->txcost = INFINITY;
    neigh->ihu_time = babel_now;
    neigh->hello_time = zero;
    neigh->hello_interval = 0;
    neigh->ihu_interval = 0;
    neigh->hello_send_us = 0;
    neigh->hello_rtt_receive_time = zero;
    neigh->rtt = 0;
    neigh->rtt_time = zero;
    neigh->ifp = ifp;
    neigh->next = neighs;
    neighs = neigh;
    send_hello(ifp);
    return neigh;
}

/* Recompute a neighbour's rxcost.  Return true if anything changed. */
int
update_neighbour(struct neighbour *neigh, int hello, int hello_interval)
{
    int missed_hellos;
    int rc = 0;

    if(hello < 0) {
        if(neigh->hello_interval == 0)
            return rc;
        missed_hellos =
            ((int)timeval_minus_msec(&babel_now, &neigh->hello_time) -
             neigh->hello_interval * 7) /
            (neigh->hello_interval * 10);
        if(missed_hellos <= 0)
            return rc;
        timeval_add_msec(&neigh->hello_time, &neigh->hello_time,
                          missed_hellos * neigh->hello_interval * 10);
    } else {
        if(neigh->hello_seqno >= 0 && neigh->reach > 0) {
            missed_hellos = seqno_minus(hello, neigh->hello_seqno) - 1;
            if(missed_hellos < -8) {
                /* Probably a neighbour that rebooted and lost its seqno.
                   Reboot the universe. */
                neigh->reach = 0;
                missed_hellos = 0;
                rc = 1;
            } else if(missed_hellos < 0) {
                if(hello_interval > neigh->hello_interval) {
                    /* This neighbour has increased its hello interval,
                       and we didn't notice. */
                    neigh->reach <<= -missed_hellos;
                    missed_hellos = 0;
                } else {
                    /* Late hello.  Probably due to the link layer buffering
                       packets during a link outage.  Ignore it, but reset
                       the expected seqno. */
                    neigh->hello_seqno = hello;
                    hello = -1;
                    missed_hellos = 0;
                }
                rc = 1;
            }
        } else {
            missed_hellos = 0;
        }
        neigh->hello_time = babel_now;
        neigh->hello_interval = hello_interval;
    }

    if(missed_hellos > 0) {
        neigh->reach >>= missed_hellos;
        neigh->hello_seqno = seqno_plus(neigh->hello_seqno, missed_hellos);
        rc = 1;
    }

    if(hello >= 0) {
        neigh->hello_seqno = hello;
        neigh->reach >>= 1;
        neigh->reach |= 0x8000;
        if((neigh->reach & 0xFC00) != 0xFC00)
            rc = 1;
    }

    /* Make sure to give neighbours some feedback early after association */
    if((neigh->reach & 0xBF00) == 0x8000) {
        /* A new neighbour */
        send_hello(neigh->ifp);
    } else {
        /* Don't send hellos, in order to avoid a positive feedback loop. */
        int a = (neigh->reach & 0xC000);
        int b = (neigh->reach & 0x3000);
        if((a == 0xC000 && b == 0) || (a == 0 && b == 0x3000)) {
            /* Reachability is either 1100 or 0011 */
            send_self_update(neigh->ifp);
        }
    }

    if((neigh->reach & 0xFC00) == 0xC000) {
        /* This is a newish neighbour, let's request a full route dump.
           We ought to avoid this when the network is dense */
        send_unicast_request(neigh, NULL, 0);
        send_ihu(neigh, NULL);
    }
    return rc;
}

static int
reset_txcost(struct neighbour *neigh)
{
    unsigned delay;

    delay = timeval_minus_msec(&babel_now, &neigh->ihu_time);

    if(neigh->ihu_interval > 0 && delay < neigh->ihu_interval * 10U * 3U)
        return 0;

    /* If we're losing a lot of packets, we probably lost an IHU too */
    if(delay >= 180000 || (neigh->reach & 0xFFF0) == 0 ||
       (neigh->ihu_interval > 0 &&
        delay >= neigh->ihu_interval * 10U * 10U)) {
        neigh->txcost = INFINITY;
        neigh->ihu_time = babel_now;
        return 1;
    }

    return 0;
}

unsigned
neighbour_txcost(struct neighbour *neigh)
{
    return neigh->txcost;
}

unsigned
check_neighbours(void)
{
    struct neighbour *neigh;
    int changed, rc;
    unsigned msecs = 50000;

    debugf(BABEL_DEBUG_COMMON,"Checking neighbours.");

    neigh = neighs;
    while(neigh) {
        changed = update_neighbour(neigh, -1, 0);

        if(neigh->reach == 0 ||
           neigh->hello_time.tv_sec > babel_now.tv_sec || /* clock stepped */
           timeval_minus_msec(&babel_now, &neigh->hello_time) > 300000) {
            struct neighbour *old = neigh;
            neigh = neigh->next;
            flush_neighbour(old);
            continue;
        }

        rc = reset_txcost(neigh);
        changed = changed || rc;

        update_neighbour_metric(neigh, changed);

        if(neigh->hello_interval > 0)
            msecs = MIN(msecs, neigh->hello_interval * 10U);
        if(neigh->ihu_interval > 0)
            msecs = MIN(msecs, neigh->ihu_interval * 10U);
        neigh = neigh->next;
    }

    return msecs;
}

unsigned
neighbour_rxcost(struct neighbour *neigh)
{
    unsigned delay;
    unsigned short reach = neigh->reach;

    delay = timeval_minus_msec(&babel_now, &neigh->hello_time);

    if((reach & 0xFFF0) == 0 || delay >= 180000) {
        return INFINITY;
    } else if(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ) {
        int sreach =
            ((reach & 0x8000) >> 2) +
            ((reach & 0x4000) >> 1) +
            (reach & 0x3FFF);
        /* 0 <= sreach <= 0x7FFF */
        int cost = (0x8000 * babel_get_if_nfo(neigh->ifp)->cost) / (sreach + 1);
        /* cost >= interface->cost */
        if(delay >= 40000)
            cost = (cost * (delay - 20000) + 10000) / 20000;
        return MIN(cost, INFINITY);
    } else {
        /* To lose one hello is a misfortune, to lose two is carelessness. */
        if((reach & 0xC000) == 0xC000)
            return babel_get_if_nfo(neigh->ifp)->cost;
        else if((reach & 0xC000) == 0)
            return INFINITY;
        else if((reach & 0x2000))
            return babel_get_if_nfo(neigh->ifp)->cost;
        else
            return INFINITY;
    }
}

unsigned
neighbour_rttcost(struct neighbour *neigh)
{
    struct interface *ifp = neigh->ifp;
    babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);

    if(!babel_ifp->max_rtt_penalty || !valid_rtt(neigh))
        return 0;

    /* Function: linear behaviour between rtt_min and rtt_max. */
    if(neigh->rtt <= babel_ifp->rtt_min) {
        return 0;
    } else if(neigh->rtt <= babel_ifp->rtt_max) {
        unsigned long long tmp =
            (unsigned long long)babel_ifp->max_rtt_penalty *
            (neigh->rtt - babel_ifp->rtt_min) /
            (babel_ifp->rtt_max - babel_ifp->rtt_min);
        assert((tmp & 0x7FFFFFFF) == tmp);
        return tmp;
    } else {
        return babel_ifp->max_rtt_penalty;
    }
}

unsigned
neighbour_cost(struct neighbour *neigh)
{
    unsigned a, b, cost;

    if(!if_up(neigh->ifp))
        return INFINITY;

    a = neighbour_txcost(neigh);

    if(a >= INFINITY)
        return INFINITY;

    b = neighbour_rxcost(neigh);
    if(b >= INFINITY)
        return INFINITY;

    if(!(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ)
       || (a < 256 && b < 256)) {
        cost = a;
    } else {
        /* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
           probabilities of a packet getting through in the direct and reverse
           directions. */
        a = MAX(a, 256);
        b = MAX(b, 256);
        /* 1/(alpha * beta), which is just plain ETX. */
        /* Since a and b are capped to 16 bits, overflow is impossible. */
        cost = (a * b + 128) >> 8;
    }

    cost += neighbour_rttcost(neigh);

    return MIN(cost, INFINITY);
}

int
valid_rtt(struct neighbour *neigh)
{
    return (timeval_minus_msec(&babel_now, &neigh->rtt_time) < 180000) ? 1 : 0;
}
Commit	Line	Data
ca10883e DS	1	/*
	2	Copyright (c) 2007, 2008 by Juliusz Chroboczek
	3
	4	Permission is hereby granted, free of charge, to any person obtaining a copy
	5	of this software and associated documentation files (the "Software"), to deal
	6	in the Software without restriction, including without limitation the rights
	7	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
	8	copies of the Software, and to permit persons to whom the Software is
	9	furnished to do so, subject to the following conditions:
	10
	11	The above copyright notice and this permission notice shall be included in
	12	all copies or substantial portions of the Software.
	13
	14	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	15	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	16	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
	17	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
	18	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
	19	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
	20	THE SOFTWARE.
	21	*/
	22
b45ac5f5 DL	23	#ifdef HAVE_CONFIG_H
	24	#include "config.h"
	25	#endif
	26
ca10883e DS	27	#include <stdlib.h>
	28	#include <string.h>
	29	#include <stdio.h>
	30	#include <sys/time.h>
	31	#include <time.h>
	32
	33	#include <zebra.h>
	34	#include "if.h"
	35
	36	#include "babel_main.h"
	37	#include "babeld.h"
	38	#include "util.h"
	39	#include "babel_interface.h"
	40	#include "neighbour.h"
	41	#include "source.h"
	42	#include "route.h"
	43	#include "message.h"
	44	#include "resend.h"
e33b116c	45	#include "babel_errors.h"
ca10883e DS	46
	47	struct neighbour *neighs = NULL;
	48
	49	static struct neighbour *
	50	find_neighbour_nocreate(const unsigned char address, struct interface ifp)
	51	{
	52	struct neighbour *neigh;
	53	FOR_ALL_NEIGHBOURS(neigh) {
	54	if(memcmp(address, neigh->address, 16) == 0 &&
	55	neigh->ifp == ifp)
	56	return neigh;
	57	}
	58	return NULL;
	59	}
	60
	61	void
	62	flush_neighbour(struct neighbour *neigh)
	63	{
	64	debugf(BABEL_DEBUG_COMMON,"Flushing neighbour %s (reach 0x%04x)",
	65	format_address(neigh->address), neigh->reach);
	66	flush_neighbour_routes(neigh);
	67	if(unicast_neighbour == neigh)
	68	flush_unicast(1);
	69	flush_resends(neigh);
	70
	71	if(neighs == neigh) {
	72	neighs = neigh->next;
	73	} else {
	74	struct neighbour *previous = neighs;
	75	while(previous->next != neigh)
	76	previous = previous->next;
	77	previous->next = neigh->next;
	78	}
	79	free(neigh);
	80	}
	81
	82	struct neighbour *
	83	find_neighbour(const unsigned char address, struct interface ifp)
	84	{
	85	struct neighbour *neigh;
	86	const struct timeval zero = {0, 0};
	87
	88	neigh = find_neighbour_nocreate(address, ifp);
	89	if(neigh)
	90	return neigh;
	91
	92	debugf(BABEL_DEBUG_COMMON,"Creating neighbour %s on %s.",
	93	format_address(address), ifp->name);
	94
	95	neigh = malloc(sizeof(struct neighbour));
	96	if(neigh == NULL) {
5b003f31	97	flog_err(EC_BABEL_MEMORY, "malloc(neighbour): %s",
e33b116c	98	safe_strerror(errno));
ca10883e DS	99	return NULL;
	100	}
	101
	102	neigh->hello_seqno = -1;
	103	memcpy(neigh->address, address, 16);
	104	neigh->reach = 0;
	105	neigh->txcost = INFINITY;
	106	neigh->ihu_time = babel_now;
	107	neigh->hello_time = zero;
	108	neigh->hello_interval = 0;
	109	neigh->ihu_interval = 0;
	110	neigh->hello_send_us = 0;
	111	neigh->hello_rtt_receive_time = zero;
	112	neigh->rtt = 0;
	113	neigh->rtt_time = zero;
	114	neigh->ifp = ifp;
	115	neigh->next = neighs;
	116	neighs = neigh;
	117	send_hello(ifp);
	118	return neigh;
	119	}
	120
	121	/* Recompute a neighbour's rxcost. Return true if anything changed. */
	122	int
	123	update_neighbour(struct neighbour *neigh, int hello, int hello_interval)
	124	{
	125	int missed_hellos;
	126	int rc = 0;
	127
	128	if(hello < 0) {
d11c6941	129	if(neigh->hello_interval == 0)
ca10883e DS	130	return rc;
	131	missed_hellos =
	132	((int)timeval_minus_msec(&babel_now, &neigh->hello_time) -
	133	neigh->hello_interval * 7) /
	134	(neigh->hello_interval * 10);
	135	if(missed_hellos <= 0)
	136	return rc;
	137	timeval_add_msec(&neigh->hello_time, &neigh->hello_time,
	138	missed_hellos * neigh->hello_interval * 10);
	139	} else {
	140	if(neigh->hello_seqno >= 0 && neigh->reach > 0) {
	141	missed_hellos = seqno_minus(hello, neigh->hello_seqno) - 1;
	142	if(missed_hellos < -8) {
	143	/* Probably a neighbour that rebooted and lost its seqno.
	144	Reboot the universe. */
	145	neigh->reach = 0;
	146	missed_hellos = 0;
	147	rc = 1;
	148	} else if(missed_hellos < 0) {
	149	if(hello_interval > neigh->hello_interval) {
	150	/* This neighbour has increased its hello interval,
	151	and we didn't notice. */
	152	neigh->reach <<= -missed_hellos;
	153	missed_hellos = 0;
	154	} else {
	155	/* Late hello. Probably due to the link layer buffering
	156	packets during a link outage. Ignore it, but reset
	157	the expected seqno. */
	158	neigh->hello_seqno = hello;
	159	hello = -1;
	160	missed_hellos = 0;
	161	}
	162	rc = 1;
	163	}
	164	} else {
	165	missed_hellos = 0;
	166	}
	167	neigh->hello_time = babel_now;
	168	neigh->hello_interval = hello_interval;
	169	}
	170
	171	if(missed_hellos > 0) {
	172	neigh->reach >>= missed_hellos;
	173	neigh->hello_seqno = seqno_plus(neigh->hello_seqno, missed_hellos);
ca10883e DS	174	rc = 1;
	175	}
	176
	177	if(hello >= 0) {
	178	neigh->hello_seqno = hello;
	179	neigh->reach >>= 1;
	180	neigh->reach \|= 0x8000;
	181	if((neigh->reach & 0xFC00) != 0xFC00)
	182	rc = 1;
	183	}
	184
	185	/* Make sure to give neighbours some feedback early after association */
	186	if((neigh->reach & 0xBF00) == 0x8000) {
	187	/* A new neighbour */
	188	send_hello(neigh->ifp);
	189	} else {
	190	/* Don't send hellos, in order to avoid a positive feedback loop. */
	191	int a = (neigh->reach & 0xC000);
	192	int b = (neigh->reach & 0x3000);
	193	if((a == 0xC000 && b == 0) \|\| (a == 0 && b == 0x3000)) {
	194	/* Reachability is either 1100 or 0011 */
	195	send_self_update(neigh->ifp);
	196	}
	197	}
	198
	199	if((neigh->reach & 0xFC00) == 0xC000) {
	200	/* This is a newish neighbour, let's request a full route dump.
	201	We ought to avoid this when the network is dense */
	202	send_unicast_request(neigh, NULL, 0);
	203	send_ihu(neigh, NULL);
	204	}
	205	return rc;
	206	}
	207
	208	static int
	209	reset_txcost(struct neighbour *neigh)
	210	{
	211	unsigned delay;
	212
	213	delay = timeval_minus_msec(&babel_now, &neigh->ihu_time);
	214
	215	if(neigh->ihu_interval > 0 && delay < neigh->ihu_interval * 10U * 3U)
	216	return 0;
	217
	218	/* If we're losing a lot of packets, we probably lost an IHU too */
	219	if(delay >= 180000 \|\| (neigh->reach & 0xFFF0) == 0 \|\|
	220	(neigh->ihu_interval > 0 &&
	221	delay >= neigh->ihu_interval * 10U * 10U)) {
	222	neigh->txcost = INFINITY;
	223	neigh->ihu_time = babel_now;
	224	return 1;
	225	}
	226
	227	return 0;
	228	}
	229
	230	unsigned
	231	neighbour_txcost(struct neighbour *neigh)
	232	{
	233	return neigh->txcost;
	234	}
	235
	236	unsigned
4d762f26	237	check_neighbours(void)
ca10883e DS	238	{
	239	struct neighbour *neigh;
	240	int changed, rc;
	241	unsigned msecs = 50000;
	242
	243	debugf(BABEL_DEBUG_COMMON,"Checking neighbours.");
	244
	245	neigh = neighs;
	246	while(neigh) {
	247	changed = update_neighbour(neigh, -1, 0);
	248
	249	if(neigh->reach == 0 \|\|
	250	neigh->hello_time.tv_sec > babel_now.tv_sec \|\| /* clock stepped */
	251	timeval_minus_msec(&babel_now, &neigh->hello_time) > 300000) {
	252	struct neighbour *old = neigh;
	253	neigh = neigh->next;
	254	flush_neighbour(old);
	255	continue;
	256	}
	257
	258	rc = reset_txcost(neigh);
	259	changed = changed \|\| rc;
	260
	261	update_neighbour_metric(neigh, changed);
	262
	263	if(neigh->hello_interval > 0)
	264	msecs = MIN(msecs, neigh->hello_interval * 10U);
	265	if(neigh->ihu_interval > 0)
	266	msecs = MIN(msecs, neigh->ihu_interval * 10U);
	267	neigh = neigh->next;
	268	}
	269
	270	return msecs;
	271	}
	272
	273	unsigned
	274	neighbour_rxcost(struct neighbour *neigh)
	275	{
	276	unsigned delay;
	277	unsigned short reach = neigh->reach;
	278
	279	delay = timeval_minus_msec(&babel_now, &neigh->hello_time);
	280
	281	if((reach & 0xFFF0) == 0 \|\| delay >= 180000) {
	282	return INFINITY;
	283	} else if(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ) {
	284	int sreach =
	285	((reach & 0x8000) >> 2) +
	286	((reach & 0x4000) >> 1) +
	287	(reach & 0x3FFF);
	288	/* 0 <= sreach <= 0x7FFF */
	289	int cost = (0x8000 * babel_get_if_nfo(neigh->ifp)->cost) / (sreach + 1);
	290	/* cost >= interface->cost */
	291	if(delay >= 40000)
	292	cost = (cost * (delay - 20000) + 10000) / 20000;
	293	return MIN(cost, INFINITY);
	294	} else {
	295	/* To lose one hello is a misfortune, to lose two is carelessness. */
	296	if((reach & 0xC000) == 0xC000)
	297	return babel_get_if_nfo(neigh->ifp)->cost;
	298	else if((reach & 0xC000) == 0)
	299	return INFINITY;
	300	else if((reach & 0x2000))
	301	return babel_get_if_nfo(neigh->ifp)->cost;
302	else
303	return INFINITY;
304	}
305	}
306
307	unsigned
308	neighbour_rttcost(struct neighbour *neigh)
309	{
310	struct interface *ifp = neigh->ifp;
311	babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
312
313	if(!babel_ifp->max_rtt_penalty \|\| !valid_rtt(neigh))
314	return 0;
315
316	/* Function: linear behaviour between rtt_min and rtt_max. */
317	if(neigh->rtt <= babel_ifp->rtt_min) {
318	return 0;
319	} else if(neigh->rtt <= babel_ifp->rtt_max) {
320	unsigned long long tmp =
321	(unsigned long long)babel_ifp->max_rtt_penalty *
322	(neigh->rtt - babel_ifp->rtt_min) /
323	(babel_ifp->rtt_max - babel_ifp->rtt_min);
324	assert((tmp & 0x7FFFFFFF) == tmp);
325	return tmp;
326	} else {
327	return babel_ifp->max_rtt_penalty;
328	}
329	}
330
331	unsigned
332	neighbour_cost(struct neighbour *neigh)
333	{
334	unsigned a, b, cost;
335
336	if(!if_up(neigh->ifp))
337	return INFINITY;
338
339	a = neighbour_txcost(neigh);
340
341	if(a >= INFINITY)
342	return INFINITY;
343
344	b = neighbour_rxcost(neigh);
345	if(b >= INFINITY)
346	return INFINITY;
347
348	if(!(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ)
349	\|\| (a < 256 && b < 256)) {
350	cost = a;
351	} else {
352	/* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
353	probabilities of a packet getting through in the direct and reverse
354	directions. */
355	a = MAX(a, 256);
356	b = MAX(b, 256);
357	/* 1/(alpha * beta), which is just plain ETX. */
358	/* Since a and b are capped to 16 bits, overflow is impossible. */
359	cost = (a * b + 128) >> 8;
360	}
361
362	cost += neighbour_rttcost(neigh);
363
364	return MIN(cost, INFINITY);
365	}
366
367	int
368	valid_rtt(struct neighbour *neigh)
369	{
370	return (timeval_minus_msec(&babel_now, &neigh->rtt_time) < 180000) ? 1 : 0;
371	}