neighbour.c 9.73 KB
Newer Older
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
1 2 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
/*
Copyright (c) 2007 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 <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 36 37 38 39 40 41 42 43 44
#include "route.h"
#include "message.h"

struct neighbour neighs[MAXNEIGHBOURS];
int numneighs = 0;

void
flush_neighbour(struct neighbour *neigh)
{
    flush_neighbour_routes(neigh);
    memset(neigh, 0, sizeof(*neigh));
45 46 47
    VALGRIND_MAKE_MEM_UNDEFINED(neigh, sizeof(*neigh));
    neigh->id[0] = 0xFF;
    while(numneighs > 0 && neighs[numneighs - 1].id[0] == 0xFF) {
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
48
       numneighs--;
49 50
       VALGRIND_MAKE_MEM_UNDEFINED(&neighs[numneighs],
                                   sizeof(neighs[numneighs]));
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
51 52 53 54 55 56 57 58
    }
}

struct neighbour *
find_neighbour(const unsigned char *address, struct network *net)
{
    int i;
    for(i = 0; i < numneighs; i++) {
59
        if(neighs[i].id[0] == 0xFF)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
60 61 62 63 64 65 66 67 68 69 70 71 72
            continue;
        if(memcmp(address, neighs[i].address, 16) == 0 &&
           neighs[i].network == net)
            return &neighs[i];
    }
    return NULL;
}

struct neighbour *
add_neighbour(const unsigned char *id, const unsigned char *address,
              struct network *net)
{
    struct neighbour *neigh;
73
    const struct timeval zero = {0, 0};
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
74 75
    int i;

76 77 78 79 80
    if(id[0] == 0xFF) {
        fprintf(stderr, "Received neighbour announcement with id[0] = FF.\n");
        return NULL;
    }

Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
81 82 83 84 85 86 87 88 89 90 91 92 93 94
    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;
        }
    }
    debugf("Creating neighbour %s (%s).\n",
           format_address(id), format_address(address));
    for(i = 0; i < numneighs; i++) {
95
        if(neighs[i].id[0] == 0xFF)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
96 97 98 99 100 101 102 103 104 105 106 107 108
            neigh = &neighs[i];
    }
    if(!neigh) {
        if(numneighs >= MAXNEIGHBOURS) {
            fprintf(stderr, "Too many neighbours.\n");
            return NULL;
        }
        neigh = &neighs[numneighs++];
    }
    memcpy(neigh->id, id, 16);
    memcpy(neigh->address, address, 16);
    neigh->reach = 0;
    neigh->txcost = INFINITY;
109
    neigh->ihu_time = now;
110
    neigh->hello_time = zero;
111
    neigh->hello_interval = 0;
112
    neigh->ihu_interval = 0;
113
    neigh->hello_seqno = -1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
114 115 116 117 118
    neigh->network = net;
    send_hello(net);
    return neigh;
}

119 120
/* Recompute a neighbour's rxcost.  Return true if anything changed. */
int
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
121 122 123
update_neighbour(struct neighbour *neigh, int hello, int hello_interval)
{
    int missed_hellos;
124
    int rc = 0;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
125 126 127

    if(hello < 0) {
        if(neigh->hello_interval <= 0)
128
            return rc;
129 130 131
        missed_hellos =
            (timeval_minus_msec(&now, &neigh->hello_time) -
             neigh->hello_interval * 7) /
132
            (neigh->hello_interval * 10);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
133
        if(missed_hellos <= 0)
134 135 136
            return rc;
        timeval_plus_msec(&neigh->hello_time, &neigh->hello_time,
                          missed_hellos * neigh->hello_interval * 10);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
137
    } else {
138
        if(neigh->hello_seqno >= 0 && neigh->reach > 0) {
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
139
            missed_hellos = seqno_minus(hello, neigh->hello_seqno) - 1;
140 141 142 143 144
            if(missed_hellos < -8) {
                /* Probably a neighbour that rebooted and lost its seqno.
                   Reboot the universe. */
                neigh->reach = 0;
                missed_hellos = 0;
145
                rc = 1;
146
            } else if(missed_hellos < 0) {
147 148 149 150 151 152 153 154 155 156 157
                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. */
                    hello = 0;
                    missed_hellos = 0;
                }
158
                rc = 1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
159 160 161 162
            }
        } else {
            missed_hellos = 0;
        }
163
        neigh->hello_time = now;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
164 165 166
        neigh->hello_interval = hello_interval;
    }

167 168
    if(missed_hellos > 0) {
        neigh->reach >>= missed_hellos;
169
        neigh->hello_seqno = seqno_plus(neigh->hello_seqno, missed_hellos);
170 171 172
        missed_hellos = 0;
        rc = 1;
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
173 174 175 176 177

    if(hello >= 0) {
        neigh->hello_seqno = hello;
        neigh->reach >>= 1;
        neigh->reach |= 0x8000;
178 179 180 181
        if((neigh->reach & 0xFC00) == 0xFC00)
            return rc;
        else
            rc = 1;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
182 183 184
    }

    /* Make sure to give neighbours some feedback early after association */
185
    if((neigh->reach & 0xBF00) == 0x8000) {
186
        /* A new neighbour */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
187 188
        send_hello(neigh->network);
    } else {
189
        /* Don't send hellos, in order to avoid a positive feedback loop. */
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
190 191 192
        int a = (neigh->reach & 0xC000);
        int b = (neigh->reach & 0x3000);
        if((a == 0xC000 && b == 0) || (a == 0 && b == 0x3000)) {
193
            /* Reachability is either 1100 or 0011 */
194
            send_self_update(neigh->network, 0);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
195 196 197
            send_neighbour_update(neigh, NULL);
        }
    }
198

199 200 201
    if((neigh->reach & 0xF000) != 0xF000 && (neigh->reach & 0xF000) != 0x0000)
        send_ihu(neigh, NULL);

202
    if((neigh->reach & 0xFC00) == 0xC000) {
203
        /* This is a newish neighbour.  If we don't have another route to it,
204 205
           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. */
206
        struct route *route = NULL;
207 208
        if(!martian_prefix(neigh->id, 128))
           route = find_installed_route(neigh->id, 128);
209
        if(!route || route->metric >= INFINITY || route->neigh == neigh)
210
            send_unicast_request(neigh, NULL, 0, 0, 0, 0);
211
    }
212
    return rc;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
213 214
}

215 216
int
check_neighbours()
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
217
{
218
    int i, changed, delay;
219 220 221 222 223 224 225
    int msecs = 50000;

    debugf("Checking neighbours.\n");

    for(i = 0; i < numneighs; i++) {
        if(neighs[i].id[0] == 0xFF)
            continue;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
226

227 228 229 230 231 232
        changed = update_neighbour(&neighs[i], -1, 0);

        if(neighs[i].reach == 0 ||
           timeval_minus_msec(&now, &neighs[i].hello_time) > 300000) {
            flush_neighbour(&neighs[i]);
            continue;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
233
        }
234

235 236 237 238 239 240 241 242 243 244
        delay = timeval_minus_msec(&now, &neighs[i].ihu_time);

        if(delay >= 180000 ||
           (neighs[i].ihu_interval > 0 &&
            delay >= neighs[i].ihu_interval * 10 * 4)) {
            neighs[i].txcost = INFINITY;
            neighs[i].ihu_time = now;
            changed = 1;
        }

245 246 247 248 249
        if(changed)
            update_neighbour_metric(&neighs[i]);

        if(neighs[i].hello_interval > 0)
            msecs = MIN(msecs, neighs[i].hello_interval * 10);
250 251
        if(neighs[i].ihu_interval > 0)
            msecs = MIN(msecs, neighs[i].ihu_interval * 10);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
252
    }
253 254

    return msecs;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
255 256 257
}

int
258
neighbour_rxcost(struct neighbour *neigh)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
259
{
260 261 262 263 264
    int delay;
    unsigned short reach = neigh->reach;

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

265
    if((reach & 0xFFF0) == 0 || delay >= 180000) {
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
266
        return INFINITY;
267 268 269 270 271 272 273 274 275
    } 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
276 277
            return INFINITY;
    } else {
278 279 280 281 282 283 284 285
        int sreach = (reach & 0x7FFF) + ((reach & 0x8000) >> 1);
        /* 0 <= sreach <= 0xBFFF */
        int cost = (0xC000 * neigh->network->cost) / (sreach + 1);
        /* cost >= network->cost */
        if(delay >= 40000)
            cost = (cost * (delay - 20000) + 10000) / 20000;

        return MIN(cost, INFINITY);
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
286 287 288 289
    }
}

int
290
neighbour_cost(struct neighbour *neigh)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
291
{
292
    int a, b;
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
293

294 295 296
    if(!neigh->network->up)
        return INFINITY;

297 298 299
    a = neigh->txcost;

    if(a >= INFINITY)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
300 301
        return INFINITY;

302 303
    b = neighbour_rxcost(neigh);
    if(b >= INFINITY)
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
304 305
        return INFINITY;

306 307
    if(a <= 256 && b <= 256) {
        return MAX(a, b);
308
    } else {
309 310 311
        /* 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. */
312 313
        a = MAX(a, 256);
        b = MAX(b, 256);
314 315 316 317
        /* (1/(alpha * beta) + 1/beta) / 2, which is half the expected
           number of transmissions, in both directions.
           ETX uses 1/(alpha * beta), which is the expected number of
           transmissions in the forward direction. */
318
        return (((a * b + 128) >> 8) + b + 1) >> 1;
319
    }
Juliusz Chroboczek's avatar
Juliusz Chroboczek committed
320
}