neighbour.c 9.46 KB
Newer Older
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1
/*
2
Copyright (c) 2007, 2008 by Juliusz Chroboczek
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

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 <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <sys/time.h>
#include <time.h>

29
#include "babeld.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
30
#include "util.h"
31
#include "network.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
32
#include "neighbour.h"
33
#include "source.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
34 35
#include "route.h"
#include "message.h"
36
#include "resend.h"
37
#include "local.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
38

39
struct neighbour *neighs = NULL;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
40

41 42
static struct neighbour *
find_neighbour_nocreate(const unsigned char *address, struct network *net)
43
{
44 45 46 47 48 49 50
    struct neighbour *neigh;
    FOR_ALL_NEIGHBOURS(neigh) {
        if(memcmp(address, neigh->address, 16) == 0 &&
           neigh->network == net)
            return neigh;
    }
    return NULL;
51 52
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
53 54 55 56
void
flush_neighbour(struct neighbour *neigh)
{
    flush_neighbour_routes(neigh);
57 58
    if(unicast_neighbour == neigh)
        flush_unicast(1);
59
    flush_resends(neigh);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
60

61 62 63 64 65 66 67
    if(neighs == neigh) {
        neighs = neigh->next;
    } else {
        struct neighbour *previous = neighs;
        while(previous->next != neigh)
            previous = previous->next;
        previous->next = neigh->next;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
68
    }
69
    local_notify_neighbour(neigh, LOCAL_FLUSH);
70
    free(neigh);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
71 72 73
}

struct neighbour *
74
find_neighbour(const unsigned char *address, struct network *net)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
75
{
76
    struct neighbour *neigh;
77
    const struct timeval zero = {0, 0};
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
78

79 80 81
    neigh = find_neighbour_nocreate(address, net);
    if(neigh)
        return neigh;
82

83 84
    debugf("Creating neighbour %s on %s.\n",
           format_address(address), net->ifname);
85 86 87 88 89

    neigh = malloc(sizeof(struct neighbour));
    if(neigh == NULL) {
        perror("malloc(neighbour)");
        return NULL;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
90
    }
91

92
    neigh->hello_seqno = -1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
93 94 95
    memcpy(neigh->address, address, 16);
    neigh->reach = 0;
    neigh->txcost = INFINITY;
96
    neigh->ihu_time = now;
97
    neigh->hello_time = zero;
98
    neigh->hello_interval = 0;
99
    neigh->ihu_interval = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
100
    neigh->network = net;
101 102 103
    neigh->next = neighs;
    neighs = neigh;
    local_notify_neighbour(neigh, LOCAL_ADD);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
104 105 106 107
    send_hello(net);
    return neigh;
}

108 109
/* Recompute a neighbour's rxcost.  Return true if anything changed. */
int
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
110 111 112
update_neighbour(struct neighbour *neigh, int hello, int hello_interval)
{
    int missed_hellos;
113
    int rc = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
114 115 116

    if(hello < 0) {
        if(neigh->hello_interval <= 0)
117
            return rc;
118
        missed_hellos =
119
            ((int)timeval_minus_msec(&now, &neigh->hello_time) -
120
             neigh->hello_interval * 7) /
121
            (neigh->hello_interval * 10);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
122
        if(missed_hellos <= 0)
123 124 125
            return rc;
        timeval_plus_msec(&neigh->hello_time, &neigh->hello_time,
                          missed_hellos * neigh->hello_interval * 10);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
126
    } else {
127
        if(neigh->hello_seqno >= 0 && neigh->reach > 0) {
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
128
            missed_hellos = seqno_minus(hello, neigh->hello_seqno) - 1;
129 130 131 132 133
            if(missed_hellos < -8) {
                /* Probably a neighbour that rebooted and lost its seqno.
                   Reboot the universe. */
                neigh->reach = 0;
                missed_hellos = 0;
134
                rc = 1;
135
            } else if(missed_hellos < 0) {
136 137 138 139 140 141 142
                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
143 144 145
                       packets during a link outage.  Ignore it, but reset
                       the expected seqno. */
                    neigh->hello_seqno = hello;
146
                    hello = -1;
147 148
                    missed_hellos = 0;
                }
149
                rc = 1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
150 151 152 153
            }
        } else {
            missed_hellos = 0;
        }
154
        neigh->hello_time = now;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
155 156 157
        neigh->hello_interval = hello_interval;
    }

158 159
    if(missed_hellos > 0) {
        neigh->reach >>= missed_hellos;
160
        neigh->hello_seqno = seqno_plus(neigh->hello_seqno, missed_hellos);
161 162 163
        missed_hellos = 0;
        rc = 1;
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
164 165 166 167 168

    if(hello >= 0) {
        neigh->hello_seqno = hello;
        neigh->reach >>= 1;
        neigh->reach |= 0x8000;
169
        if((neigh->reach & 0xFC00) != 0xFC00)
170
            rc = 1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
171 172 173
    }

    /* Make sure to give neighbours some feedback early after association */
174
    if((neigh->reach & 0xBF00) == 0x8000) {
175
        /* A new neighbour */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
176 177
        send_hello(neigh->network);
    } else {
178
        /* Don't send hellos, in order to avoid a positive feedback loop. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
179 180 181
        int a = (neigh->reach & 0xC000);
        int b = (neigh->reach & 0x3000);
        if((a == 0xC000 && b == 0) || (a == 0 && b == 0x3000)) {
182
            /* Reachability is either 1100 or 0011 */
183
            send_self_update(neigh->network);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
184 185
        }
    }
186

187
    if((neigh->reach & 0xFC00) == 0xC000) {
188 189
        /* This is a newish neighbour, let's request a full route dump.
           We ought to avoid this when the network is dense */
190
        send_unicast_request(neigh, NULL, 0);
191
        send_ihu(neigh, NULL);
192
    }
193
    if(rc)
194
        local_notify_neighbour(neigh, LOCAL_CHANGE);
195
    return rc;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
196 197
}

198 199 200
static int
reset_txcost(struct neighbour *neigh)
{
201
    unsigned delay;
202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219

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

    if(neigh->ihu_interval > 0 && delay < neigh->ihu_interval * 10 * 3)
        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 * 10 * 10)) {
        neigh->txcost = INFINITY;
        neigh->ihu_time = now;
        return 1;
    }

    return 0;
}

220
unsigned
221 222 223 224 225
neighbour_txcost(struct neighbour *neigh)
{
    return neigh->txcost;
}

226
unsigned
227
check_neighbours()
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
228
{
229
    struct neighbour *neigh;
230 231
    int changed, rc;
    unsigned msecs = 50000;
232 233 234

    debugf("Checking neighbours.\n");

235 236
    neigh = neighs;
    while(neigh) {
237
        changed = update_neighbour(neigh, -1, 0);
238

239 240 241
        if(neigh->reach == 0 ||
           neigh->hello_time.tv_sec > now.tv_sec || /* clock stepped */
           timeval_minus_msec(&now, &neigh->hello_time) > 300000) {
242 243 244
            struct neighbour *old = neigh;
            neigh = neigh->next;
            flush_neighbour(old);
245
            continue;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
246
        }
247

248 249
        rc = reset_txcost(neigh);
        changed = changed || rc;
250

251
        if(changed) {
252 253 254
            update_neighbour_metric(neigh);
            local_notify_neighbour(neigh, LOCAL_CHANGE);
        }
255

256 257 258 259
        if(neigh->hello_interval > 0)
            msecs = MIN(msecs, neigh->hello_interval * 10);
        if(neigh->ihu_interval > 0)
            msecs = MIN(msecs, neigh->ihu_interval * 10);
260
        neigh = neigh->next;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
261
    }
262 263

    return msecs;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
264 265
}

266
unsigned
267
neighbour_rxcost(struct neighbour *neigh)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
268
{
269
    unsigned delay;
270 271 272 273
    unsigned short reach = neigh->reach;

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

274
    if((reach & 0xFFF0) == 0 || delay >= 180000) {
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
275
        return INFINITY;
276
    } else if((neigh->network->flags & NET_LQ)) {
277 278 279 280 281 282
        int sreach =
            ((reach & 0x8000) >> 2) +
            ((reach & 0x4000) >> 1) +
            (reach & 0x3FFF);
        /* 0 <= sreach <= 0x7FFF */
        int cost = (0x8000 * neigh->network->cost) / (sreach + 1);
283 284 285 286
        /* cost >= network->cost */
        if(delay >= 40000)
            cost = (cost * (delay - 20000) + 10000) / 20000;
        return MIN(cost, INFINITY);
287 288 289 290 291 292 293 294 295 296
    } else {
        /* To lose one hello is a misfortune, to lose two is carelessness. */
        if((reach & 0xC000) == 0xC000)
            return neigh->network->cost;
        else if((reach & 0xC000) == 0)
            return INFINITY;
        else if((reach & 0x2000))
            return neigh->network->cost;
        else
            return INFINITY;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
297 298 299
    }
}

300
unsigned
301
neighbour_cost(struct neighbour *neigh)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
302
{
303
    unsigned a, b;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
304

305
    if(!net_up(neigh->network))
306 307
        return INFINITY;

308
    a = neighbour_txcost(neigh);
309 310

    if(a >= INFINITY)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
311 312
        return INFINITY;

313 314
    b = neighbour_rxcost(neigh);
    if(b >= INFINITY)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
315 316
        return INFINITY;

317
    if(!(neigh->network->flags & NET_LQ) || (a <= 256 && b <= 256)) {
318
        return a;
319
    } else {
320 321 322
        /* 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. */
323 324
        a = MAX(a, 256);
        b = MAX(b, 256);
325 326 327
        /* 1/(alpha * beta), which is just plain ETX. */
        /* Since a and b are capped to 16 bits, overflow is impossible. */
        return (a * b + 128) >> 8;
328
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
329
}