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