neighbour.c 10.8 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 "babel.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 "local.h"
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
37

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

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

52 53 54 55 56 57 58 59 60 61 62
struct neighbour *
find_neighbour_by_id(const unsigned char *id, struct network *net)
{
    struct neighbour *neigh;
    FOR_ALL_NEIGHBOURS(neigh) {
        if(memcmp(id, neigh->id, 16) == 0 && neigh->network == net)
            return neigh;
    }
    return NULL;
}

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
63 64 65 66
void
flush_neighbour(struct neighbour *neigh)
{
    flush_neighbour_routes(neigh);
67 68
    if(unicast_neighbour == neigh)
        flush_unicast(1);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
69

70 71 72 73 74 75 76
    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
77
    }
78
    local_notify_neighbour(neigh, LOCAL_FLUSH);
79
    free(neigh);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
80 81 82 83 84 85
}

struct neighbour *
add_neighbour(const unsigned char *id, const unsigned char *address,
              struct network *net)
{
86
    struct neighbour *neigh;
87
    const struct timeval zero = {0, 0};
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
88 89 90 91 92 93 94 95 96 97 98 99

    neigh = find_neighbour(address, net);
    if(neigh) {
        if(memcmp(neigh->id, id, 16) == 0) {
            return neigh;
        } else {
            fprintf(stderr, "Neighbour changed id (%s -> %s)!\n",
                    format_address(neigh->id), format_address(id));
            flush_neighbour(neigh);
            neigh = NULL;
        }
    }
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115

    neigh = find_neighbour_by_id(id, net);
    if(neigh) {
        if((neigh->reach & 0xE000) == 0) {
            /* The other neighbour is probably obsolete. */
            flush_neighbour(neigh);
            neigh = NULL;
        } else {
            fprintf(stderr, "Duplicate neighbour %s (%s and %s)!\n",
                    format_address(id),
                    format_address(neigh->address),
                    format_address(address));
            return NULL;
        }
    }

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
116 117
    debugf("Creating neighbour %s (%s).\n",
           format_address(id), format_address(address));
118 119 120 121 122

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

125
    neigh->hello_seqno = -1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
126 127 128 129
    memcpy(neigh->id, id, 16);
    memcpy(neigh->address, address, 16);
    neigh->reach = 0;
    neigh->txcost = INFINITY;
130
    neigh->ihu_time = now;
131
    neigh->hello_time = zero;
132
    neigh->hello_interval = 0;
133
    neigh->ihu_interval = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
134
    neigh->network = net;
135 136 137
    neigh->next = neighs;
    neighs = neigh;
    local_notify_neighbour(neigh, LOCAL_ADD);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
138 139 140 141
    send_hello(net);
    return neigh;
}

142 143
/* Recompute a neighbour's rxcost.  Return true if anything changed. */
int
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
144 145 146
update_neighbour(struct neighbour *neigh, int hello, int hello_interval)
{
    int missed_hellos;
147
    int rc = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
148 149 150

    if(hello < 0) {
        if(neigh->hello_interval <= 0)
151
            return rc;
152 153 154
        missed_hellos =
            (timeval_minus_msec(&now, &neigh->hello_time) -
             neigh->hello_interval * 7) /
155
            (neigh->hello_interval * 10);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
156
        if(missed_hellos <= 0)
157 158 159
            return rc;
        timeval_plus_msec(&neigh->hello_time, &neigh->hello_time,
                          missed_hellos * neigh->hello_interval * 10);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
160
    } else {
161
        if(neigh->hello_seqno >= 0 && neigh->reach > 0) {
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
162
            missed_hellos = seqno_minus(hello, neigh->hello_seqno) - 1;
163 164 165 166 167
            if(missed_hellos < -8) {
                /* Probably a neighbour that rebooted and lost its seqno.
                   Reboot the universe. */
                neigh->reach = 0;
                missed_hellos = 0;
168
                rc = 1;
169
            } else if(missed_hellos < 0) {
170 171 172 173 174 175 176
                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
177 178 179
                       packets during a link outage.  Ignore it, but reset
                       the expected seqno. */
                    neigh->hello_seqno = hello;
180
                    hello = -1;
181 182
                    missed_hellos = 0;
                }
183
                rc = 1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
184 185 186 187
            }
        } else {
            missed_hellos = 0;
        }
188
        neigh->hello_time = now;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
189 190 191
        neigh->hello_interval = hello_interval;
    }

192 193
    if(missed_hellos > 0) {
        neigh->reach >>= missed_hellos;
194
        neigh->hello_seqno = seqno_plus(neigh->hello_seqno, missed_hellos);
195 196 197
        missed_hellos = 0;
        rc = 1;
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
198 199 200 201 202

    if(hello >= 0) {
        neigh->hello_seqno = hello;
        neigh->reach >>= 1;
        neigh->reach |= 0x8000;
203
        if((neigh->reach & 0xFC00) != 0xFC00)
204
            rc = 1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
205 206 207
    }

    /* Make sure to give neighbours some feedback early after association */
208
    if((neigh->reach & 0xBF00) == 0x8000) {
209
        /* A new neighbour */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
210 211
        send_hello(neigh->network);
    } else {
212
        /* Don't send hellos, in order to avoid a positive feedback loop. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
213 214 215
        int a = (neigh->reach & 0xC000);
        int b = (neigh->reach & 0x3000);
        if((a == 0xC000 && b == 0) || (a == 0 && b == 0x3000)) {
216
            /* Reachability is either 1100 or 0011 */
217
            send_self_update(neigh->network, 0);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
218 219
        }
    }
220

221
    if((neigh->reach & 0xFC00) == 0xC000) {
222
        /* This is a newish neighbour.  If we don't have another route to it,
223 224
           request a full route dump.  This assumes that the neighbour's id
           is also its IP address and that it is exporting a route to itself. */
225
        struct route *route = NULL;
226
        send_ihu(neigh, NULL);
227 228
        if(!martian_prefix(neigh->id, 128))
           route = find_installed_route(neigh->id, 128);
229
        if(!route || route->metric >= INFINITY || route->neigh == neigh)
230
            send_unicast_request(neigh, NULL, 0, 0, 0, 0);
231
    }
232
    if(rc)
233
        local_notify_neighbour(neigh, LOCAL_CHANGE);
234
    return rc;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
235 236
}

237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258
static int
reset_txcost(struct neighbour *neigh)
{
    int delay;

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

259
unsigned
260 261 262 263 264 265
neighbour_txcost(struct neighbour *neigh)
{
    reset_txcost(neigh);
    return neigh->txcost;
}

266
unsigned
267
check_neighbours()
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
268
{
269 270
    struct neighbour *neigh;
    int changed, delay;
271 272 273 274
    int msecs = 50000;

    debugf("Checking neighbours.\n");

275 276
    neigh = neighs;
    while(neigh) {
277
        changed = update_neighbour(neigh, -1, 0);
278

279 280 281
        if(neigh->reach == 0 ||
           neigh->hello_time.tv_sec > now.tv_sec || /* clock stepped */
           timeval_minus_msec(&now, &neigh->hello_time) > 300000) {
282 283 284
            struct neighbour *old = neigh;
            neigh = neigh->next;
            flush_neighbour(old);
285
            continue;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
286
        }
287

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

290
        changed = changed || reset_txcost(neigh);
291

292
        if(changed) {
293 294 295
            update_neighbour_metric(neigh);
            local_notify_neighbour(neigh, LOCAL_CHANGE);
        }
296

297 298 299 300
        if(neigh->hello_interval > 0)
            msecs = MIN(msecs, neigh->hello_interval * 10);
        if(neigh->ihu_interval > 0)
            msecs = MIN(msecs, neigh->ihu_interval * 10);
301
        neigh = neigh->next;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
302
    }
303 304

    return msecs;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
305 306
}

307
unsigned
308
neighbour_rxcost(struct neighbour *neigh)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
309
{
310 311 312 313 314
    int delay;
    unsigned short reach = neigh->reach;

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

315
    if((reach & 0xFFF0) == 0 || delay >= 180000) {
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
316
        return INFINITY;
317 318 319 320 321 322 323 324 325
    } else if(neigh->network->wired) {
        /* 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
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
326 327
            return INFINITY;
    } else {
328 329 330 331 332 333
        int sreach =
            ((reach & 0x8000) >> 2) +
            ((reach & 0x4000) >> 1) +
            (reach & 0x3FFF);
        /* 0 <= sreach <= 0x7FFF */
        int cost = (0x8000 * neigh->network->cost) / (sreach + 1);
334 335 336 337 338
        /* cost >= network->cost */
        if(delay >= 40000)
            cost = (cost * (delay - 20000) + 10000) / 20000;

        return MIN(cost, INFINITY);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
339 340 341
    }
}

342
unsigned
343
neighbour_cost(struct neighbour *neigh)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
344
{
345
    unsigned a, b;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
346

347 348 349
    if(!neigh->network->up)
        return INFINITY;

350
    a = neighbour_txcost(neigh);
351 352

    if(a >= INFINITY)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
353 354
        return INFINITY;

355 356
    b = neighbour_rxcost(neigh);
    if(b >= INFINITY)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
357 358
        return INFINITY;

359
    if(neigh->network->wired || (a <= 256 && b <= 256)) {
360
        return a;
361
    } else {
362 363 364
        /* 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. */
365 366
        a = MAX(a, 256);
        b = MAX(b, 256);
367 368 369
        /* 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;
370
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
371
}