babeld/neighbour.c

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