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