neighbour.c 9.35 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 "interface.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
static struct neighbour *
42
find_neighbour_nocreate(const unsigned char *address, struct interface *ifp)
43
{
44 45 46
    struct neighbour *neigh;
    FOR_ALL_NEIGHBOURS(neigh) {
        if(memcmp(address, neigh->address, 16) == 0 &&
47
           neigh->ifp == ifp)
48 49 50
            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 interface *ifp)
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
    neigh = find_neighbour_nocreate(address, ifp);
80 81
    if(neigh)
        return neigh;
82

83
    debugf("Creating neighbour %s on %s.\n",
84
           format_address(address), ifp->name);
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;
100
    neigh->ifp = ifp;
101 102 103
    neigh->next = neighs;
    neighs = neigh;
    local_notify_neighbour(neigh, LOCAL_ADD);
104
    send_hello(ifp);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
105 106 107
    return neigh;
}

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

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

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

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

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

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

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

    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;
}

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

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

    debugf("Checking neighbours.\n");

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

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

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

250
        update_neighbour_metric(neigh, changed);
251

252 253 254 255
        if(neigh->hello_interval > 0)
            msecs = MIN(msecs, neigh->hello_interval * 10);
        if(neigh->ihu_interval > 0)
            msecs = MIN(msecs, neigh->ihu_interval * 10);
256
        neigh = neigh->next;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
257
    }
258 259

    return msecs;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
260 261
}

262
unsigned
263
neighbour_rxcost(struct neighbour *neigh)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
264
{
265
    unsigned delay;
266 267 268 269
    unsigned short reach = neigh->reach;

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

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

296
unsigned
297
neighbour_cost(struct neighbour *neigh)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
298
{
299
    unsigned a, b;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
300

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

304
    a = neighbour_txcost(neigh);
305 306

    if(a >= INFINITY)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
307 308
        return INFINITY;

309 310
    b = neighbour_rxcost(neigh);
    if(b >= INFINITY)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
311 312
        return INFINITY;

313
    if(!(neigh->ifp->flags & IF_LQ) || (a < 256 && b < 256)) {
314
        return a;
315
    } else {
316 317 318
        /* 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. */
319 320
        a = MAX(a, 256);
        b = MAX(b, 256);
321 322 323
        /* 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;
324
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
325
}