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         rc = 1;
 169     }
 170
 171     if(hello >= 0) {
 172         neigh->hello_seqno = hello;
 173         neigh->reach >>= 1;
 174         neigh->reach |= 0x8000;
 175         if((neigh->reach & 0xFC00) != 0xFC00)
 176             rc = 1;
 177     }
 178
 179     /* Make sure to give neighbours some feedback early after association */
 180     if((neigh->reach & 0xBF00) == 0x8000) {
 181         /* A new neighbour */
 182         send_hello(neigh->ifp);
 183     } else {
 184         /* Don't send hellos, in order to avoid a positive feedback loop. */
 185         int a = (neigh->reach & 0xC000);
 186         int b = (neigh->reach & 0x3000);
 187         if((a == 0xC000 && b == 0) || (a == 0 && b == 0x3000)) {
 188             /* Reachability is either 1100 or 0011 */
 189             send_self_update(neigh->ifp);
 190         }
 191     }
 192
 193     if((neigh->reach & 0xFC00) == 0xC000) {
 194         /* This is a newish neighbour, let's request a full route dump.
 195            We ought to avoid this when the network is dense */
 196         send_unicast_request(neigh, NULL, 0);
 197         send_ihu(neigh, NULL);
 198     }
 199     return rc;
 200 }
 201
 202 static int
 203 reset_txcost(struct neighbour *neigh)
 204 {
 205     unsigned delay;
 206
 207     delay = timeval_minus_msec(&babel_now, &neigh->ihu_time);
 208
 209     if(neigh->ihu_interval > 0 && delay < neigh->ihu_interval * 10U * 3U)
 210         return 0;
 211
 212     /* If we're losing a lot of packets, we probably lost an IHU too */
 213     if(delay >= 180000 || (neigh->reach & 0xFFF0) == 0 ||
 214        (neigh->ihu_interval > 0 &&
 215         delay >= neigh->ihu_interval * 10U * 10U)) {
 216         neigh->txcost = INFINITY;
 217         neigh->ihu_time = babel_now;
 218         return 1;
 219     }
 220
 221     return 0;
 222 }
 223
 224 unsigned
 225 neighbour_txcost(struct neighbour *neigh)
 226 {
 227     return neigh->txcost;
 228 }
 229
 230 unsigned
 231 check_neighbours()
 232 {
 233     struct neighbour *neigh;
 234     int changed, rc;
 235     unsigned msecs = 50000;
 236
 237     debugf(BABEL_DEBUG_COMMON,"Checking neighbours.");
 238
 239     neigh = neighs;
 240     while(neigh) {
 241         changed = update_neighbour(neigh, -1, 0);
 242
 243         if(neigh->reach == 0 ||
 244            neigh->hello_time.tv_sec > babel_now.tv_sec || /* clock stepped */
 245            timeval_minus_msec(&babel_now, &neigh->hello_time) > 300000) {
 246             struct neighbour *old = neigh;
 247             neigh = neigh->next;
 248             flush_neighbour(old);
 249             continue;
 250         }
 251
 252         rc = reset_txcost(neigh);
 253         changed = changed || rc;
 254
 255         update_neighbour_metric(neigh, changed);
 256
 257         if(neigh->hello_interval > 0)
 258             msecs = MIN(msecs, neigh->hello_interval * 10U);
 259         if(neigh->ihu_interval > 0)
 260             msecs = MIN(msecs, neigh->ihu_interval * 10U);
 261         neigh = neigh->next;
 262     }
 263
 264     return msecs;
 265 }
 266
 267 unsigned
 268 neighbour_rxcost(struct neighbour *neigh)
 269 {
 270     unsigned delay;
 271     unsigned short reach = neigh->reach;
 272
 273     delay = timeval_minus_msec(&babel_now, &neigh->hello_time);
 274
 275     if((reach & 0xFFF0) == 0 || delay >= 180000) {
 276         return INFINITY;
 277     } else if(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ) {
 278         int sreach =
 279             ((reach & 0x8000) >> 2) +
 280             ((reach & 0x4000) >> 1) +
 281             (reach & 0x3FFF);
 282         /* 0 <= sreach <= 0x7FFF */
 283         int cost = (0x8000 * babel_get_if_nfo(neigh->ifp)->cost) / (sreach + 1);
 284         /* cost >= interface->cost */
 285         if(delay >= 40000)
 286             cost = (cost * (delay - 20000) + 10000) / 20000;
 287         return MIN(cost, INFINITY);
 288     } else {
 289         /* To lose one hello is a misfortune, to lose two is carelessness. */
 290         if((reach & 0xC000) == 0xC000)
 291             return babel_get_if_nfo(neigh->ifp)->cost;
 292         else if((reach & 0xC000) == 0)
 293             return INFINITY;
 294         else if((reach & 0x2000))
 295             return babel_get_if_nfo(neigh->ifp)->cost;
 296         else
 297             return INFINITY;
 298     }
 299 }
 300
 301 unsigned
 302 neighbour_rttcost(struct neighbour *neigh)
 303 {
 304     struct interface *ifp = neigh->ifp;
 305     babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
 306
 307     if(!babel_ifp->max_rtt_penalty || !valid_rtt(neigh))
 308         return 0;
 309
 310     /* Function: linear behaviour between rtt_min and rtt_max. */
 311     if(neigh->rtt <= babel_ifp->rtt_min) {
 312         return 0;
 313     } else if(neigh->rtt <= babel_ifp->rtt_max) {
 314         unsigned long long tmp =
 315             (unsigned long long)babel_ifp->max_rtt_penalty *
 316             (neigh->rtt - babel_ifp->rtt_min) /
 317             (babel_ifp->rtt_max - babel_ifp->rtt_min);
 318         assert((tmp & 0x7FFFFFFF) == tmp);
 319         return tmp;
 320     } else {
 321         return babel_ifp->max_rtt_penalty;
 322     }
 323 }
 324
 325 unsigned
 326 neighbour_cost(struct neighbour *neigh)
 327 {
 328     unsigned a, b, cost;
 329
 330     if(!if_up(neigh->ifp))
 331         return INFINITY;
 332
 333     a = neighbour_txcost(neigh);
 334
 335     if(a >= INFINITY)
 336         return INFINITY;
 337
 338     b = neighbour_rxcost(neigh);
 339     if(b >= INFINITY)
 340         return INFINITY;
 341
 342     if(!(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ)
 343        || (a < 256 && b < 256)) {
 344         cost = a;
 345     } else {
 346         /* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
 347            probabilities of a packet getting through in the direct and reverse
 348            directions. */
 349         a = MAX(a, 256);
 350         b = MAX(b, 256);
 351         /* 1/(alpha * beta), which is just plain ETX. */
 352         /* Since a and b are capped to 16 bits, overflow is impossible. */
 353         cost = (a * b + 128) >> 8;
 354     }
 355
 356     cost += neighbour_rttcost(neigh);
 357
 358     return MIN(cost, INFINITY);
 359 }
 360
 361 int
 362 valid_rtt(struct neighbour *neigh)
 363 {
 364     return (timeval_minus_msec(&babel_now, &neigh->rtt_time) < 180000) ? 1 : 0;
 365 }