babeld/neighbour.c

   1 /*
   2  *  This file is free software: you may copy, redistribute and/or modify it
   3  *  under the terms of the GNU General Public License as published by the
   4  *  Free Software Foundation, either version 2 of the License, or (at your
   5  *  option) any later version.
   6  *
   7  *  This file is distributed in the hope that it will be useful, but
   8  *  WITHOUT ANY WARRANTY; without even the implied warranty of
   9  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  10  *  General Public License for more details.
  11  *
  12  *  You should have received a copy of the GNU General Public License
  13  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  14  *
  15  * This file incorporates work covered by the following copyright and
  16  * permission notice:
  17  *
  18 Copyright (c) 2007, 2008 by Juliusz Chroboczek
  19
  20 Permission is hereby granted, free of charge, to any person obtaining a copy
  21 of this software and associated documentation files (the "Software"), to deal
  22 in the Software without restriction, including without limitation the rights
  23 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  24 copies of the Software, and to permit persons to whom the Software is
  25 furnished to do so, subject to the following conditions:
  26
  27 The above copyright notice and this permission notice shall be included in
  28 all copies or substantial portions of the Software.
  29
  30 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  31 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  32 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  33 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  34 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  35 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  36 THE SOFTWARE.
  37 */
  38
  39 #include <stdlib.h>
  40 #include <string.h>
  41 #include <stdio.h>
  42 #include <sys/time.h>
  43 #include <time.h>
  44
  45 #include <zebra.h>
  46 #include "if.h"
  47
  48 #include "babel_main.h"
  49 #include "babeld.h"
  50 #include "util.h"
  51 #include "babel_interface.h"
  52 #include "neighbour.h"
  53 #include "source.h"
  54 #include "route.h"
  55 #include "message.h"
  56 #include "resend.h"
  57
  58 struct neighbour *neighs = NULL;
  59
  60 static struct neighbour *
  61 find_neighbour_nocreate(const unsigned char *address, struct interface *ifp)
  62 {
  63     struct neighbour *neigh;
  64     FOR_ALL_NEIGHBOURS(neigh) {
  65         if(memcmp(address, neigh->address, 16) == 0 &&
  66            neigh->ifp == ifp)
  67             return neigh;
  68     }
  69     return NULL;
  70 }
  71
  72 void
  73 flush_neighbour(struct neighbour *neigh)
  74 {
  75     flush_neighbour_routes(neigh);
  76     if(unicast_neighbour == neigh)
  77         flush_unicast(1);
  78     flush_resends(neigh);
  79
  80     if(neighs == neigh) {
  81         neighs = neigh->next;
  82     } else {
  83         struct neighbour *previous = neighs;
  84         while(previous->next != neigh)
  85             previous = previous->next;
  86         previous->next = neigh->next;
  87     }
  88     free(neigh);
  89 }
  90
  91 struct neighbour *
  92 find_neighbour(const unsigned char *address, struct interface *ifp)
  93 {
  94     struct neighbour *neigh;
  95     const struct timeval zero = {0, 0};
  96
  97     neigh = find_neighbour_nocreate(address, ifp);
  98     if(neigh)
  99         return neigh;
 100
 101     debugf(BABEL_DEBUG_COMMON,"Creating neighbour %s on %s.",
 102            format_address(address), ifp->name);
 103
 104     neigh = malloc(sizeof(struct neighbour));
 105     if(neigh == NULL) {
 106         zlog_err("malloc(neighbour): %s", safe_strerror(errno));
 107         return NULL;
 108     }
 109
 110     neigh->hello_seqno = -1;
 111     memcpy(neigh->address, address, 16);
 112     neigh->reach = 0;
 113     neigh->txcost = INFINITY;
 114     neigh->ihu_time = babel_now;
 115     neigh->hello_time = zero;
 116     neigh->hello_interval = 0;
 117     neigh->ihu_interval = 0;
 118     neigh->ifp = ifp;
 119     neigh->next = neighs;
 120     neighs = neigh;
 121     send_hello(ifp);
 122     return neigh;
 123 }
 124
 125 /* Recompute a neighbour's rxcost.  Return true if anything changed.
 126    This does not call local_notify_neighbour, see update_neighbour_metric. */
 127 int
 128 update_neighbour(struct neighbour *neigh, int hello, int hello_interval)
 129 {
 130     int missed_hellos;
 131     int rc = 0;
 132
 133     if(hello < 0) {
 134         if(neigh->hello_interval <= 0)
 135             return rc;
 136         missed_hellos =
 137             ((int)timeval_minus_msec(&babel_now, &neigh->hello_time) -
 138              neigh->hello_interval * 7) /
 139             (neigh->hello_interval * 10);
 140         if(missed_hellos <= 0)
 141             return rc;
 142         timeval_add_msec(&neigh->hello_time, &neigh->hello_time,
 143                           missed_hellos * neigh->hello_interval * 10);
 144     } else {
 145         if(neigh->hello_seqno >= 0 && neigh->reach > 0) {
 146             missed_hellos = seqno_minus(hello, neigh->hello_seqno) - 1;
 147             if(missed_hellos < -8) {
 148                 /* Probably a neighbour that rebooted and lost its seqno.
 149                    Reboot the universe. */
 150                 neigh->reach = 0;
 151                 missed_hellos = 0;
 152                 rc = 1;
 153             } else if(missed_hellos < 0) {
 154                 if(hello_interval > neigh->hello_interval) {
 155                     /* This neighbour has increased its hello interval,
 156                        and we didn't notice. */
 157                     neigh->reach <<= -missed_hellos;
 158                     missed_hellos = 0;
 159                 } else {
 160                     /* Late hello.  Probably due to the link layer buffering
 161                        packets during a link outage.  Ignore it, but reset
 162                        the expected seqno. */
 163                     neigh->hello_seqno = hello;
 164                     hello = -1;
 165                     missed_hellos = 0;
 166                 }
 167                 rc = 1;
 168             }
 169         } else {
 170             missed_hellos = 0;
 171         }
 172         neigh->hello_time = babel_now;
 173         neigh->hello_interval = hello_interval;
 174     }
 175
 176     if(missed_hellos > 0) {
 177         neigh->reach >>= missed_hellos;
 178         neigh->hello_seqno = seqno_plus(neigh->hello_seqno, missed_hellos);
 179         missed_hellos = 0;
 180         rc = 1;
 181     }
 182
 183     if(hello >= 0) {
 184         neigh->hello_seqno = hello;
 185         neigh->reach >>= 1;
 186         neigh->reach |= 0x8000;
 187         if((neigh->reach & 0xFC00) != 0xFC00)
 188             rc = 1;
 189     }
 190
 191     /* Make sure to give neighbours some feedback early after association */
 192     if((neigh->reach & 0xBF00) == 0x8000) {
 193         /* A new neighbour */
 194         send_hello(neigh->ifp);
 195     } else {
 196         /* Don't send hellos, in order to avoid a positive feedback loop. */
 197         int a = (neigh->reach & 0xC000);
 198         int b = (neigh->reach & 0x3000);
 199         if((a == 0xC000 && b == 0) || (a == 0 && b == 0x3000)) {
 200             /* Reachability is either 1100 or 0011 */
 201             send_self_update(neigh->ifp);
 202         }
 203     }
 204
 205     if((neigh->reach & 0xFC00) == 0xC000) {
 206         /* This is a newish neighbour, let's request a full route dump.
 207            We ought to avoid this when the network is dense */
 208         send_unicast_request(neigh, NULL, 0);
 209         send_ihu(neigh, NULL);
 210     }
 211     return rc;
 212 }
 213
 214 static int
 215 reset_txcost(struct neighbour *neigh)
 216 {
 217     unsigned delay;
 218
 219     delay = timeval_minus_msec(&babel_now, &neigh->ihu_time);
 220
 221     if(neigh->ihu_interval > 0 && delay < neigh->ihu_interval * 10U * 3U)
 222         return 0;
 223
 224     /* If we're losing a lot of packets, we probably lost an IHU too */
 225     if(delay >= 180000 || (neigh->reach & 0xFFF0) == 0 ||
 226        (neigh->ihu_interval > 0 &&
 227         delay >= neigh->ihu_interval * 10U * 10U)) {
 228         neigh->txcost = INFINITY;
 229         neigh->ihu_time = babel_now;
 230         return 1;
 231     }
 232
 233     return 0;
 234 }
 235
 236 unsigned
 237 neighbour_txcost(struct neighbour *neigh)
 238 {
 239     return neigh->txcost;
 240 }
 241
 242 unsigned
 243 check_neighbours()
 244 {
 245     struct neighbour *neigh;
 246     int changed, rc;
 247     unsigned msecs = 50000;
 248
 249     debugf(BABEL_DEBUG_COMMON,"Checking neighbours.");
 250
 251     neigh = neighs;
 252     while(neigh) {
 253         changed = update_neighbour(neigh, -1, 0);
 254
 255         if(neigh->reach == 0 ||
 256            neigh->hello_time.tv_sec > babel_now.tv_sec || /* clock stepped */
 257            timeval_minus_msec(&babel_now, &neigh->hello_time) > 300000) {
 258             struct neighbour *old = neigh;
 259             neigh = neigh->next;
 260             flush_neighbour(old);
 261             continue;
 262         }
 263
 264         rc = reset_txcost(neigh);
 265         changed = changed || rc;
 266
 267         update_neighbour_metric(neigh, changed);
 268
 269         if(neigh->hello_interval > 0)
 270             msecs = MIN(msecs, neigh->hello_interval * 10U);
 271         if(neigh->ihu_interval > 0)
 272             msecs = MIN(msecs, neigh->ihu_interval * 10U);
 273         neigh = neigh->next;
 274     }
 275
 276     return msecs;
 277 }
 278
 279 unsigned
 280 neighbour_rxcost(struct neighbour *neigh)
 281 {
 282     unsigned delay;
 283     unsigned short reach = neigh->reach;
 284
 285     delay = timeval_minus_msec(&babel_now, &neigh->hello_time);
 286
 287     if((reach & 0xFFF0) == 0 || delay >= 180000) {
 288         return INFINITY;
 289     } else if(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ) {
 290         int sreach =
 291             ((reach & 0x8000) >> 2) +
 292             ((reach & 0x4000) >> 1) +
 293             (reach & 0x3FFF);
 294         /* 0 <= sreach <= 0x7FFF */
 295         int cost = (0x8000 * babel_get_if_nfo(neigh->ifp)->cost) / (sreach + 1);
 296         /* cost >= interface->cost */
 297         if(delay >= 40000)
 298             cost = (cost * (delay - 20000) + 10000) / 20000;
 299         return MIN(cost, INFINITY);
 300     } else {
 301         /* To lose one hello is a misfortune, to lose two is carelessness. */
 302         if((reach & 0xC000) == 0xC000)
 303             return babel_get_if_nfo(neigh->ifp)->cost;
 304         else if((reach & 0xC000) == 0)
 305             return INFINITY;
 306         else if((reach & 0x2000))
 307             return babel_get_if_nfo(neigh->ifp)->cost;
 308         else
 309             return INFINITY;
 310     }
 311 }
 312
 313 unsigned
 314 neighbour_cost(struct neighbour *neigh)
 315 {
 316     unsigned a, b;
 317
 318     if(!if_up(neigh->ifp))
 319         return INFINITY;
 320
 321     a = neighbour_txcost(neigh);
 322
 323     if(a >= INFINITY)
 324         return INFINITY;
 325
 326     b = neighbour_rxcost(neigh);
 327     if(b >= INFINITY)
 328         return INFINITY;
 329
 330     if(!(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ)
 331        || (a < 256 && b < 256)) {
 332         return a;
 333     } else {
 334         /* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
 335            probabilities of a packet getting through in the direct and reverse
 336            directions. */
 337         a = MAX(a, 256);
 338         b = MAX(b, 256);
 339         /* 1/(alpha * beta), which is just plain ETX. */
 340         /* Since a and b are capped to 16 bits, overflow is impossible. */
 341         return (a * b + 128) >> 8;
 342     }
 343 }