babeld/route.c

   1 /*
   2 Copyright (c) 2007, 2008 by Juliusz Chroboczek
   3 Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
   4
   5 Permission is hereby granted, free of charge, to any person obtaining a copy
   6 of this software and associated documentation files (the "Software"), to deal
   7 in the Software without restriction, including without limitation the rights
   8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   9 copies of the Software, and to permit persons to whom the Software is
  10 furnished to do so, subject to the following conditions:
  11
  12 The above copyright notice and this permission notice shall be included in
  13 all copies or substantial portions of the Software.
  14
  15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  18 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  21 THE SOFTWARE.
  22 */
  23
  24 #include <zebra.h>
  25 #include "if.h"
  26
  27 #include "babeld.h"
  28 #include "util.h"
  29 #include "kernel.h"
  30 #include "babel_interface.h"
  31 #include "source.h"
  32 #include "neighbour.h"
  33 #include "route.h"
  34 #include "xroute.h"
  35 #include "message.h"
  36 #include "resend.h"
  37 #include "babel_errors.h"
  38
  39 static void consider_route(struct babel_route *route);
  40
  41 struct babel_route **routes = NULL;
  42 static int route_slots = 0, max_route_slots = 0;
  43 int kernel_metric = 0;
  44 enum babel_diversity diversity_kind = DIVERSITY_NONE;
  45 int diversity_factor = BABEL_DEFAULT_DIVERSITY_FACTOR;
  46 int keep_unfeasible = 0;
  47
  48 int smoothing_half_life = 0;
  49 static int two_to_the_one_over_hl = 0; /* 2^(1/hl) * 0x10000 */
  50
  51 /* We maintain a list of "slots", ordered by prefix.  Every slot
  52    contains a linked list of the routes to this prefix, with the
  53    installed route, if any, at the head of the list. */
  54
  55 static int
  56 route_compare(const unsigned char *prefix, unsigned char plen,
  57                struct babel_route *route)
  58 {
  59     int i = memcmp(prefix, route->src->prefix, 16);
  60     if(i != 0)
  61         return i;
  62
  63     if(plen < route->src->plen)
  64         return -1;
  65     else if(plen > route->src->plen)
  66         return 1;
  67     else
  68         return 0;
  69 }
  70
  71 /* Performs binary search, returns -1 in case of failure.  In the latter
  72    case, new_return is the place where to insert the new element. */
  73
  74 static int
  75 find_route_slot(const unsigned char *prefix, unsigned char plen,
  76                 int *new_return)
  77 {
  78     int p, m, g, c;
  79
  80     if(route_slots < 1) {
  81         if(new_return)
  82             *new_return = 0;
  83         return -1;
  84     }
  85
  86     p = 0; g = route_slots - 1;
  87
  88     do {
  89         m = (p + g) / 2;
  90         c = route_compare(prefix, plen, routes[m]);
  91         if(c == 0)
  92             return m;
  93         else if(c < 0)
  94             g = m - 1;
  95         else
  96             p = m + 1;
  97     } while(p <= g);
  98
  99     if(new_return)
 100         *new_return = p;
 101
 102     return -1;
 103 }
 104
 105 struct babel_route *
 106 find_route(const unsigned char *prefix, unsigned char plen,
 107            struct neighbour *neigh, const unsigned char *nexthop)
 108 {
 109     struct babel_route *route;
 110     int i = find_route_slot(prefix, plen, NULL);
 111
 112     if(i < 0)
 113         return NULL;
 114
 115     route = routes[i];
 116
 117     while(route) {
 118         if(route->neigh == neigh && memcmp(route->nexthop, nexthop, 16) == 0)
 119             return route;
 120         route = route->next;
 121     }
 122
 123     return NULL;
 124 }
 125
 126 struct babel_route *
 127 find_installed_route(const unsigned char *prefix, unsigned char plen)
 128 {
 129     int i = find_route_slot(prefix, plen, NULL);
 130
 131     if(i >= 0 && routes[i]->installed)
 132         return routes[i];
 133
 134     return NULL;
 135 }
 136
 137 /* Returns an overestimate of the number of installed routes. */
 138 int
 139 installed_routes_estimate(void)
 140 {
 141     return route_slots;
 142 }
 143
 144 static int
 145 resize_route_table(int new_slots)
 146 {
 147     struct babel_route **new_routes;
 148     assert(new_slots >= route_slots);
 149
 150     if(new_slots == 0) {
 151         new_routes = NULL;
 152         free(routes);
 153     } else {
 154         new_routes = realloc(routes, new_slots * sizeof(struct babel_route*));
 155         if(new_routes == NULL)
 156             return -1;
 157     }
 158
 159     max_route_slots = new_slots;
 160     routes = new_routes;
 161     return 1;
 162 }
 163
 164 /* Insert a route into the table.  If successful, retains the route.
 165    On failure, caller must free the route. */
 166 static struct babel_route *
 167 insert_route(struct babel_route *route)
 168 {
 169     int i, n;
 170
 171     assert(!route->installed);
 172
 173     i = find_route_slot(route->src->prefix, route->src->plen, &n);
 174
 175     if(i < 0) {
 176         if(route_slots >= max_route_slots)
 177             resize_route_table(max_route_slots < 1 ? 8 : 2 * max_route_slots);
 178         if(route_slots >= max_route_slots)
 179             return NULL;
 180         assert(routes);
 181         route->next = NULL;
 182         if(n < route_slots)
 183             memmove(routes + n + 1, routes + n,
 184                     (route_slots - n) * sizeof(struct babel_route*));
 185         route_slots++;
 186         routes[n] = route;
 187     } else {
 188         struct babel_route *r;
 189         r = routes[i];
 190         while(r->next)
 191             r = r->next;
 192         r->next = route;
 193         route->next = NULL;
 194     }
 195
 196     return route;
 197 }
 198
 199 void
 200 flush_route(struct babel_route *route)
 201 {
 202     int i;
 203     struct source *src;
 204     unsigned oldmetric;
 205     int lost = 0;
 206
 207     oldmetric = route_metric(route);
 208     src = route->src;
 209
 210     if(route->installed) {
 211         uninstall_route(route);
 212         lost = 1;
 213     }
 214
 215     i = find_route_slot(route->src->prefix, route->src->plen, NULL);
 216     assert(i >= 0 && i < route_slots);
 217
 218     if(route == routes[i]) {
 219         routes[i] = route->next;
 220         route->next = NULL;
 221         free(route);
 222
 223         if(routes[i] == NULL) {
 224             if(i < route_slots - 1)
 225                 memmove(routes + i, routes + i + 1,
 226                         (route_slots - i - 1) * sizeof(struct babel_route*));
 227             routes[route_slots - 1] = NULL;
 228             route_slots--;
 229         }
 230
 231         if(route_slots == 0)
 232             resize_route_table(0);
 233         else if(max_route_slots > 8 && route_slots < max_route_slots / 4)
 234             resize_route_table(max_route_slots / 2);
 235     } else {
 236         struct babel_route *r = routes[i];
 237         while(r->next != route)
 238             r = r->next;
 239         r->next = route->next;
 240         route->next = NULL;
 241         free(route);
 242     }
 243
 244     if(lost)
 245         route_lost(src, oldmetric);
 246
 247     release_source(src);
 248 }
 249
 250 void
 251 flush_all_routes(void)
 252 {
 253     int i;
 254
 255     /* Start from the end, to avoid shifting the table. */
 256     i = route_slots - 1;
 257     while(i >= 0) {
 258         while(i < route_slots) {
 259         /* Uninstall first, to avoid calling route_lost. */
 260             if(routes[i]->installed)
 261                 uninstall_route(routes[i]);
 262             flush_route(routes[i]);
 263         }
 264         i--;
 265     }
 266
 267     check_sources_released();
 268 }
 269
 270 void
 271 flush_neighbour_routes(struct neighbour *neigh)
 272 {
 273     int i;
 274
 275     i = 0;
 276     while(i < route_slots) {
 277         struct babel_route *r;
 278         r = routes[i];
 279         while(r) {
 280             if(r->neigh == neigh) {
 281                 flush_route(r);
 282                 goto again;
 283             }
 284             r = r->next;
 285         }
 286         i++;
 287     again:
 288         ;
 289     }
 290 }
 291
 292 void
 293 flush_interface_routes(struct interface *ifp, int v4only)
 294 {
 295     int i;
 296
 297     i = 0;
 298     while(i < route_slots) {
 299         struct babel_route *r;
 300         r = routes[i];
 301         while(r) {
 302             if(r->neigh->ifp == ifp &&
 303                (!v4only || v4mapped(r->nexthop))) {
 304                 flush_route(r);
 305                 goto again;
 306             }
 307             r = r->next;
 308         }
 309         i++;
 310     again:
 311         ;
 312     }
 313 }
 314
 315 struct route_stream {
 316     int installed;
 317     int index;
 318     struct babel_route *next;
 319 };
 320
 321
 322 struct route_stream *
 323 route_stream(int installed)
 324 {
 325     struct route_stream *stream;
 326
 327     stream = malloc(sizeof(struct route_stream));
 328     if(stream == NULL)
 329        return NULL;
 330
 331     stream->installed = installed;
 332     stream->index = installed ? 0 : -1;
 333     stream->next = NULL;
 334
 335     return stream;
 336 }
 337
 338 struct babel_route *
 339 route_stream_next(struct route_stream *stream)
 340 {
 341     if(stream->installed) {
 342         while(stream->index < route_slots && !routes[stream->index]->installed)
 343             stream->index++;
 344
 345         if(stream->index < route_slots)
 346             return routes[stream->index++];
 347         else
 348             return NULL;
 349     } else {
 350         struct babel_route *next;
 351         if(!stream->next) {
 352             stream->index++;
 353             if(stream->index >= route_slots)
 354                 return NULL;
 355             stream->next = routes[stream->index];
 356         }
 357         next = stream->next;
 358         stream->next = next->next;
 359         return next;
 360     }
 361 }
 362
 363 void
 364 route_stream_done(struct route_stream *stream)
 365 {
 366     free(stream);
 367 }
 368
 369 static int
 370 metric_to_kernel(int metric)
 371 {
 372     return metric < INFINITY ? kernel_metric : KERNEL_INFINITY;
 373 }
 374
 375 /* This is used to maintain the invariant that the installed route is at
 376    the head of the list. */
 377 static void
 378 move_installed_route(struct babel_route *route, int i)
 379 {
 380     assert(i >= 0 && i < route_slots);
 381     assert(route->installed);
 382
 383     if(route != routes[i]) {
 384         struct babel_route *r = routes[i];
 385         while(r->next != route)
 386             r = r->next;
 387         r->next = route->next;
 388         route->next = routes[i];
 389         routes[i] = route;
 390     }
 391 }
 392
 393 void
 394 install_route(struct babel_route *route)
 395 {
 396     int i, rc;
 397
 398     if(route->installed)
 399         return;
 400
 401     if(!route_feasible(route))
 402         flog_err(EC_BABEL_ROUTE, "WARNING: installing unfeasible route "
 403                   "(this shouldn't happen).");
 404
 405     i = find_route_slot(route->src->prefix, route->src->plen, NULL);
 406     assert(i >= 0 && i < route_slots);
 407
 408     if(routes[i] != route && routes[i]->installed) {
 409         flog_err(EC_BABEL_ROUTE,
 410                   "WARNING: attempting to install duplicate route "
 411                   "(this shouldn't happen).");
 412         return;
 413     }
 414
 415     rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen,
 416                       route->nexthop,
 417                       route->neigh->ifp->ifindex,
 418                       metric_to_kernel(route_metric(route)), NULL, 0, 0);
 419     if(rc < 0) {
 420         int save = errno;
 421         flog_err(EC_BABEL_ROUTE, "kernel_route(ADD): %s",
 422                   safe_strerror(errno));
 423         if(save != EEXIST)
 424             return;
 425     }
 426     route->installed = 1;
 427     move_installed_route(route, i);
 428
 429 }
 430
 431 void
 432 uninstall_route(struct babel_route *route)
 433 {
 434     int rc;
 435
 436     if(!route->installed)
 437         return;
 438
 439     rc = kernel_route(ROUTE_FLUSH, route->src->prefix, route->src->plen,
 440                       route->nexthop,
 441                       route->neigh->ifp->ifindex,
 442                       metric_to_kernel(route_metric(route)), NULL, 0, 0);
 443     if(rc < 0)
 444         flog_err(EC_BABEL_ROUTE, "kernel_route(FLUSH): %s",
 445                   safe_strerror(errno));
 446
 447     route->installed = 0;
 448 }
 449
 450 /* This is equivalent to uninstall_route followed with install_route,
 451    but without the race condition.  The destination of both routes
 452    must be the same. */
 453
 454 static void
 455 switch_routes(struct babel_route *old, struct babel_route *new)
 456 {
 457     int rc;
 458
 459     if(!old) {
 460         install_route(new);
 461         return;
 462     }
 463
 464     if(!old->installed)
 465         return;
 466
 467     if(!route_feasible(new))
 468         flog_err(EC_BABEL_ROUTE, "WARNING: switching to unfeasible route "
 469                   "(this shouldn't happen).");
 470
 471     rc = kernel_route(ROUTE_MODIFY, old->src->prefix, old->src->plen,
 472                       old->nexthop, old->neigh->ifp->ifindex,
 473                       metric_to_kernel(route_metric(old)),
 474                       new->nexthop, new->neigh->ifp->ifindex,
 475                       metric_to_kernel(route_metric(new)));
 476     if(rc < 0) {
 477         flog_err(EC_BABEL_ROUTE, "kernel_route(MODIFY): %s",
 478                   safe_strerror(errno));
 479         return;
 480     }
 481
 482     old->installed = 0;
 483     new->installed = 1;
 484     move_installed_route(new, find_route_slot(new->src->prefix, new->src->plen,
 485                                               NULL));
 486 }
 487
 488 static void
 489 change_route_metric(struct babel_route *route,
 490                     unsigned refmetric, unsigned cost, unsigned add)
 491 {
 492     int old, new;
 493     int newmetric = MIN(refmetric + cost + add, INFINITY);
 494
 495     old = metric_to_kernel(route_metric(route));
 496     new = metric_to_kernel(newmetric);
 497
 498     if(route->installed && old != new) {
 499         int rc;
 500         rc = kernel_route(ROUTE_MODIFY, route->src->prefix, route->src->plen,
 501                           route->nexthop, route->neigh->ifp->ifindex,
 502                           old,
 503                           route->nexthop, route->neigh->ifp->ifindex,
 504                           new);
 505         if(rc < 0) {
 506             flog_err(EC_BABEL_ROUTE, "kernel_route(MODIFY metric): %s",
 507                       safe_strerror(errno));
 508             return;
 509         }
 510     }
 511
 512     /* Update route->smoothed_metric using the old metric. */
 513     route_smoothed_metric(route);
 514
 515     route->refmetric = refmetric;
 516     route->cost = cost;
 517     route->add_metric = add;
 518
 519     if(smoothing_half_life == 0) {
 520         route->smoothed_metric = route_metric(route);
 521         route->smoothed_metric_time = babel_now.tv_sec;
 522     }
 523 }
 524
 525 static void
 526 retract_route(struct babel_route *route)
 527 {
 528     /* We cannot simply remove the route from the kernel, as that might
 529        cause a routing loop -- see RFC 6126 Sections 2.8 and 3.5.5. */
 530     change_route_metric(route, INFINITY, INFINITY, 0);
 531 }
 532
 533 int
 534 route_feasible(struct babel_route *route)
 535 {
 536     return update_feasible(route->src, route->seqno, route->refmetric);
 537 }
 538
 539 int
 540 route_old(struct babel_route *route)
 541 {
 542     return route->time < babel_now.tv_sec - route->hold_time * 7 / 8;
 543 }
 544
 545 int
 546 route_expired(struct babel_route *route)
 547 {
 548     return route->time < babel_now.tv_sec - route->hold_time;
 549 }
 550
 551 static int
 552 channels_interfere(int ch1, int ch2)
 553 {
 554     if(ch1 == BABEL_IF_CHANNEL_NONINTERFERING
 555        || ch2 == BABEL_IF_CHANNEL_NONINTERFERING)
 556         return 0;
 557     if(ch1 == BABEL_IF_CHANNEL_INTERFERING
 558        || ch2 == BABEL_IF_CHANNEL_INTERFERING)
 559         return 1;
 560     return ch1 == ch2;
 561 }
 562
 563 int
 564 route_interferes(struct babel_route *route, struct interface *ifp)
 565 {
 566     struct babel_interface *babel_ifp = NULL;
 567     switch(diversity_kind) {
 568     case DIVERSITY_NONE:
 569         return 1;
 570     case DIVERSITY_INTERFACE_1:
 571         return route->neigh->ifp == ifp;
 572     case DIVERSITY_CHANNEL_1:
 573     case DIVERSITY_CHANNEL:
 574         if(route->neigh->ifp == ifp)
 575             return 1;
 576         babel_ifp = babel_get_if_nfo(ifp);
 577         if(channels_interfere(babel_ifp->channel,
 578                               babel_get_if_nfo(route->neigh->ifp)->channel))
 579             return 1;
 580         if(diversity_kind == DIVERSITY_CHANNEL) {
 581             int i;
 582             for(i = 0; i < DIVERSITY_HOPS; i++) {
 583                 if(route->channels[i] == 0)
 584                     break;
 585                 if(channels_interfere(babel_ifp->channel, route->channels[i]))
 586                     return 1;
 587             }
 588         }
 589         return 0;
 590     }
 591
 592     return 1;
 593 }
 594
 595 int
 596 update_feasible(struct source *src,
 597                 unsigned short seqno, unsigned short refmetric)
 598 {
 599     if(src == NULL)
 600         return 1;
 601
 602     if(src->time < babel_now.tv_sec - SOURCE_GC_TIME)
 603         /* Never mind what is probably stale data */
 604         return 1;
 605
 606     if(refmetric >= INFINITY)
 607         /* Retractions are always feasible */
 608         return 1;
 609
 610     return (seqno_compare(seqno, src->seqno) > 0 ||
 611             (src->seqno == seqno && refmetric < src->metric));
 612 }
 613
 614 void
 615 change_smoothing_half_life(int half_life)
 616 {
 617     if(half_life <= 0) {
 618         smoothing_half_life = 0;
 619         two_to_the_one_over_hl = 0;
 620         return;
 621     }
 622
 623     smoothing_half_life = half_life;
 624     switch(smoothing_half_life) {
 625     case 1: two_to_the_one_over_hl = 131072; break;
 626     case 2: two_to_the_one_over_hl = 92682; break;
 627     case 3: two_to_the_one_over_hl = 82570; break;
 628     case 4: two_to_the_one_over_hl = 77935; break;
 629     default:
 630         /* 2^(1/x) is 1 + log(2)/x + O(1/x^2) at infinity. */
 631         two_to_the_one_over_hl = 0x10000 + 45426 / half_life;
 632     }
 633 }
 634
 635 /* Update the smoothed metric, return the new value. */
 636 int
 637 route_smoothed_metric(struct babel_route *route)
 638 {
 639     int metric = route_metric(route);
 640
 641     if(smoothing_half_life <= 0 ||                 /* no smoothing */
 642        metric >= INFINITY ||                       /* route retracted */
 643        route->smoothed_metric_time > babel_now.tv_sec || /* clock stepped */
 644        route->smoothed_metric == metric) {         /* already converged */
 645         route->smoothed_metric = metric;
 646         route->smoothed_metric_time = babel_now.tv_sec;
 647     } else {
 648         int diff;
 649         /* We randomise the computation, to minimise global synchronisation
 650            and hence oscillations. */
 651         while(route->smoothed_metric_time <=
 652               babel_now.tv_sec - smoothing_half_life) {
 653             diff = metric - route->smoothed_metric;
 654             route->smoothed_metric += roughly(diff) / 2;
 655             route->smoothed_metric_time += smoothing_half_life;
 656         }
 657         while(route->smoothed_metric_time < babel_now.tv_sec) {
 658             diff = metric - route->smoothed_metric;
 659             route->smoothed_metric +=
 660                 roughly(diff) * (two_to_the_one_over_hl - 0x10000) / 0x10000;
 661             route->smoothed_metric_time++;
 662         }
 663
 664         diff = metric - route->smoothed_metric;
 665         if(diff > -4 && diff < 4)
 666             route->smoothed_metric = metric;
 667     }
 668
 669     /* change_route_metric relies on this */
 670     assert(route->smoothed_metric_time == babel_now.tv_sec);
 671     return route->smoothed_metric;
 672 }
 673
 674 static int
 675 route_acceptable(struct babel_route *route, int feasible,
 676                  struct neighbour *exclude)
 677 {
 678     if(route_expired(route))
 679         return 0;
 680     if(feasible && !route_feasible(route))
 681         return 0;
 682     if(exclude && route->neigh == exclude)
 683         return 0;
 684     return 1;
 685 }
 686
 687 /* Find the best route according to the weak ordering.  Any
 688    linearisation of the strong ordering (see consider_route) will do,
 689    we use sm <= sm'.  We could probably use a lexical ordering, but
 690    that's probably overkill. */
 691
 692 struct babel_route *
 693 find_best_route(const unsigned char *prefix, unsigned char plen, int feasible,
 694                 struct neighbour *exclude)
 695 {
 696     struct babel_route *route = NULL, *r = NULL;
 697     int i = find_route_slot(prefix, plen, NULL);
 698
 699     if(i < 0)
 700         return NULL;
 701
 702     route = routes[i];
 703     while(route && !route_acceptable(route, feasible, exclude))
 704         route = route->next;
 705
 706     if(!route)
 707         return NULL;
 708
 709     r = route->next;
 710     while(r) {
 711         if(route_acceptable(r, feasible, exclude) &&
 712            (route_smoothed_metric(r) < route_smoothed_metric(route)))
 713             route = r;
 714         r = r->next;
 715     }
 716
 717     return route;
 718 }
 719
 720 void
 721 update_route_metric(struct babel_route *route)
 722 {
 723     int oldmetric = route_metric(route);
 724     int old_smoothed_metric = route_smoothed_metric(route);
 725
 726     if(route_expired(route)) {
 727         if(route->refmetric < INFINITY) {
 728             route->seqno = seqno_plus(route->src->seqno, 1);
 729             retract_route(route);
 730             if(oldmetric < INFINITY)
 731                 route_changed(route, route->src, oldmetric);
 732         }
 733     } else {
 734         struct neighbour *neigh = route->neigh;
 735         int add_metric = input_filter(route->src->id,
 736                                       route->src->prefix, route->src->plen,
 737                                       neigh->address,
 738                                       neigh->ifp->ifindex);
 739         change_route_metric(route, route->refmetric,
 740                             neighbour_cost(route->neigh), add_metric);
 741         if(route_metric(route) != oldmetric ||
 742            route_smoothed_metric(route) != old_smoothed_metric)
 743             route_changed(route, route->src, oldmetric);
 744     }
 745 }
 746
 747 /* Called whenever a neighbour's cost changes, to update the metric of
 748    all routes through that neighbour. */
 749 void
 750 update_neighbour_metric(struct neighbour *neigh, int changed)
 751 {
 752
 753     if(changed) {
 754         int i;
 755
 756         for(i = 0; i < route_slots; i++) {
 757             struct babel_route *r = routes[i];
 758             while(r) {
 759                 if(r->neigh == neigh)
 760                     update_route_metric(r);
 761                 r = r->next;
 762             }
 763         }
 764     }
 765 }
 766
 767 void
 768 update_interface_metric(struct interface *ifp)
 769 {
 770     int i;
 771
 772     for(i = 0; i < route_slots; i++) {
 773         struct babel_route *r = routes[i];
 774         while(r) {
 775             if(r->neigh->ifp == ifp)
 776                 update_route_metric(r);
 777             r = r->next;
 778         }
 779     }
 780 }
 781
 782 /* This is called whenever we receive an update. */
 783 struct babel_route *
 784 update_route(const unsigned char *router_id,
 785              const unsigned char *prefix, unsigned char plen,
 786              unsigned short seqno, unsigned short refmetric,
 787              unsigned short interval,
 788              struct neighbour *neigh, const unsigned char *nexthop,
 789              const unsigned char *channels, int channels_len)
 790 {
 791     struct babel_route *route;
 792     struct source *src;
 793     int metric, feasible;
 794     int add_metric;
 795     int hold_time = MAX((4 * interval) / 100 + interval / 50, 15);
 796
 797     if(memcmp(router_id, myid, 8) == 0)
 798         return NULL;
 799
 800     if(martian_prefix(prefix, plen)) {
 801         flog_err(EC_BABEL_ROUTE, "Rejecting martian route to %s through %s.",
 802                  format_prefix(prefix, plen), format_address(nexthop));
 803         return NULL;
 804     }
 805
 806     add_metric = input_filter(router_id, prefix, plen,
 807                               neigh->address, neigh->ifp->ifindex);
 808     if(add_metric >= INFINITY)
 809         return NULL;
 810
 811     route = find_route(prefix, plen, neigh, nexthop);
 812
 813     if(route && memcmp(route->src->id, router_id, 8) == 0)
 814         /* Avoid scanning the source table. */
 815         src = route->src;
 816     else
 817         src = find_source(router_id, prefix, plen, 1, seqno);
 818
 819     if(src == NULL)
 820         return NULL;
 821
 822     feasible = update_feasible(src, seqno, refmetric);
 823     metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY);
 824
 825     if(route) {
 826         struct source *oldsrc;
 827         unsigned short oldmetric;
 828         int lost = 0;
 829
 830         oldsrc = route->src;
 831         oldmetric = route_metric(route);
 832
 833         /* If a successor switches sources, we must accept his update even
 834            if it makes a route unfeasible in order to break any routing loops
 835            in a timely manner.  If the source remains the same, we ignore
 836            the update. */
 837         if(!feasible && route->installed) {
 838             debugf(BABEL_DEBUG_COMMON,"Unfeasible update for installed route to %s "
 839                    "(%s %d %d -> %s %d %d).",
 840                    format_prefix(src->prefix, src->plen),
 841                    format_eui64(route->src->id),
 842                    route->seqno, route->refmetric,
 843                    format_eui64(src->id), seqno, refmetric);
 844             if(src != route->src) {
 845                 uninstall_route(route);
 846                 lost = 1;
 847             }
 848         }
 849
 850         route->src = retain_source(src);
 851         if((feasible || keep_unfeasible) && refmetric < INFINITY)
 852             route->time = babel_now.tv_sec;
 853         route->seqno = seqno;
 854
 855         memset(&route->channels, 0, sizeof(route->channels));
 856         if(channels_len > 0)
 857             memcpy(&route->channels, channels,
 858                    MIN(channels_len, DIVERSITY_HOPS));
 859
 860         change_route_metric(route,
 861                             refmetric, neighbour_cost(neigh), add_metric);
 862         route->hold_time = hold_time;
 863
 864         route_changed(route, oldsrc, oldmetric);
 865         if(lost)
 866             route_lost(oldsrc, oldmetric);
 867
 868         if(!feasible)
 869             send_unfeasible_request(neigh, route->installed && route_old(route),
 870                                     seqno, metric, src);
 871         release_source(oldsrc);
 872     } else {
 873         struct babel_route *new_route;
 874
 875         if(refmetric >= INFINITY)
 876             /* Somebody's retracting a route we never saw. */
 877             return NULL;
 878         if(!feasible) {
 879             send_unfeasible_request(neigh, 0, seqno, metric, src);
 880             if(!keep_unfeasible)
 881                 return NULL;
 882         }
 883
 884         route = malloc(sizeof(struct babel_route));
 885         if(route == NULL) {
 886             perror("malloc(route)");
 887             return NULL;
 888         }
 889
 890         route->src = retain_source(src);
 891         route->refmetric = refmetric;
 892         route->cost = neighbour_cost(neigh);
 893         route->add_metric = add_metric;
 894         route->seqno = seqno;
 895         route->neigh = neigh;
 896         memcpy(route->nexthop, nexthop, 16);
 897         route->time = babel_now.tv_sec;
 898         route->hold_time = hold_time;
 899         route->smoothed_metric = MAX(route_metric(route), INFINITY / 2);
 900         route->smoothed_metric_time = babel_now.tv_sec;
 901         route->installed = 0;
 902         memset(&route->channels, 0, sizeof(route->channels));
 903         if(channels_len > 0)
 904             memcpy(&route->channels, channels,
 905                    MIN(channels_len, DIVERSITY_HOPS));
 906         route->next = NULL;
 907         new_route = insert_route(route);
 908         if(new_route == NULL) {
 909             flog_err(EC_BABEL_ROUTE, "Couldn't insert route.");
 910             free(route);
 911             return NULL;
 912         }
 913         consider_route(route);
 914     }
 915     return route;
 916 }
 917
 918 /* We just received an unfeasible update.  If it's any good, send
 919    a request for a new seqno. */
 920 void
 921 send_unfeasible_request(struct neighbour *neigh, int force,
 922                         unsigned short seqno, unsigned short metric,
 923                         struct source *src)
 924 {
 925     struct babel_route *route = find_installed_route(src->prefix, src->plen);
 926
 927     if(seqno_minus(src->seqno, seqno) > 100) {
 928         /* Probably a source that lost its seqno.  Let it time-out. */
 929         return;
 930     }
 931
 932     if(force || !route || route_metric(route) >= metric + 512) {
 933         send_unicast_multihop_request(neigh, src->prefix, src->plen,
 934                                       src->metric >= INFINITY ?
 935                                       src->seqno :
 936                                       seqno_plus(src->seqno, 1),
 937                                       src->id, 127);
 938     }
 939 }
 940
 941 /* This takes a feasible route and decides whether to install it.
 942    This uses the strong ordering, which is defined by sm <= sm' AND
 943    m <= m'.  This ordering is not total, which is what causes
 944    hysteresis. */
 945
 946 static void
 947 consider_route(struct babel_route *route)
 948 {
 949     struct babel_route *installed;
 950     struct xroute *xroute;
 951
 952     if(route->installed)
 953         return;
 954
 955     if(!route_feasible(route))
 956         return;
 957
 958     xroute = find_xroute(route->src->prefix, route->src->plen);
 959     if(xroute)
 960         return;
 961
 962     installed = find_installed_route(route->src->prefix, route->src->plen);
 963
 964     if(installed == NULL)
 965         goto install;
 966
 967     if(route_metric(route) >= INFINITY)
 968         return;
 969
 970     if(route_metric(installed) >= INFINITY)
 971         goto install;
 972
 973     if(route_metric(installed) >= route_metric(route) &&
 974        route_smoothed_metric(installed) > route_smoothed_metric(route))
 975         goto install;
 976
 977     return;
 978
 979  install:
 980     switch_routes(installed, route);
 981     if(installed && route->installed)
 982         send_triggered_update(route, installed->src, route_metric(installed));
 983     else
 984         send_update(NULL, 1, route->src->prefix, route->src->plen);
 985     return;
 986 }
 987
 988 void
 989 retract_neighbour_routes(struct neighbour *neigh)
 990 {
 991     int i;
 992
 993     for(i = 0; i < route_slots; i++) {
 994         struct babel_route *r = routes[i];
 995         while(r) {
 996             if(r->neigh == neigh) {
 997                 if(r->refmetric != INFINITY) {
 998                     unsigned short oldmetric = route_metric(r);
 999                     retract_route(r);
1000                     if(oldmetric != INFINITY)
1001                         route_changed(r, r->src, oldmetric);
1002                 }
1003             }
1004             r = r->next;
1005         }
1006     }
1007 }
1008
1009 void
1010 send_triggered_update(struct babel_route *route, struct source *oldsrc,
1011                       unsigned oldmetric)
1012 {
1013     unsigned newmetric, diff;
1014     /* 1 means send speedily, 2 means resend */
1015     int urgent;
1016
1017     if(!route->installed)
1018         return;
1019
1020     newmetric = route_metric(route);
1021     diff =
1022         newmetric >= oldmetric ? newmetric - oldmetric : oldmetric - newmetric;
1023
1024     if(route->src != oldsrc || (oldmetric < INFINITY && newmetric >= INFINITY))
1025         /* Switching sources can cause transient routing loops.
1026            Retractions can cause blackholes. */
1027         urgent = 2;
1028     else if(newmetric > oldmetric && oldmetric < 6 * 256 && diff >= 512)
1029         /* Route getting significantly worse */
1030         urgent = 1;
1031     else if(unsatisfied_request(route->src->prefix, route->src->plen,
1032                                 route->seqno, route->src->id))
1033         /* Make sure that requests are satisfied speedily */
1034         urgent = 1;
1035     else if(oldmetric >= INFINITY && newmetric < INFINITY)
1036         /* New route */
1037         urgent = 0;
1038     else if(newmetric < oldmetric && diff < 1024)
1039         /* Route getting better.  This may be a transient fluctuation, so
1040            don't advertise it to avoid making routes unfeasible later on. */
1041         return;
1042     else if(diff < 384)
1043         /* Don't fret about trivialities */
1044         return;
1045     else
1046         urgent = 0;
1047
1048     if(urgent >= 2)
1049         send_update_resend(NULL, route->src->prefix, route->src->plen);
1050     else
1051         send_update(NULL, urgent, route->src->prefix, route->src->plen);
1052
1053     if(oldmetric < INFINITY) {
1054         if(newmetric >= oldmetric + 512) {
1055             send_request_resend(NULL, route->src->prefix, route->src->plen,
1056                                 route->src->metric >= INFINITY ?
1057                                 route->src->seqno :
1058                                 seqno_plus(route->src->seqno, 1),
1059                                 route->src->id);
1060         } else if(newmetric >= oldmetric + 288) {
1061             send_request(NULL, route->src->prefix, route->src->plen);
1062         }
1063     }
1064 }
1065
1066 /* A route has just changed.  Decide whether to switch to a different route or
1067    send an update. */
1068 void
1069 route_changed(struct babel_route *route,
1070               struct source *oldsrc, unsigned short oldmetric)
1071 {
1072     if(route->installed) {
1073         struct babel_route *better_route;
1074         /* Do this unconditionally -- microoptimisation is not worth it. */
1075         better_route =
1076             find_best_route(route->src->prefix, route->src->plen, 1, NULL);
1077         if(better_route && route_metric(better_route) < route_metric(route))
1078             consider_route(better_route);
1079     }
1080
1081     if(route->installed) {
1082         /* We didn't change routes after all. */
1083         send_triggered_update(route, oldsrc, oldmetric);
1084     } else {
1085         /* Reconsider routes even when their metric didn't decrease,
1086            they may not have been feasible before. */
1087         consider_route(route);
1088     }
1089 }
1090
1091 /* We just lost the installed route to a given destination. */
1092 void
1093 route_lost(struct source *src, unsigned oldmetric)
1094 {
1095     struct babel_route *new_route;
1096     new_route = find_best_route(src->prefix, src->plen, 1, NULL);
1097     if(new_route) {
1098         consider_route(new_route);
1099     } else if(oldmetric < INFINITY) {
1100         /* Avoid creating a blackhole. */
1101         send_update_resend(NULL, src->prefix, src->plen);
1102         /* If the route was usable enough, try to get an alternate one.
1103            If it was not, we could be dealing with oscillations around
1104            the value of INFINITY. */
1105         if(oldmetric <= INFINITY / 2)
1106             send_request_resend(NULL, src->prefix, src->plen,
1107                                 src->metric >= INFINITY ?
1108                                 src->seqno : seqno_plus(src->seqno, 1),
1109                                 src->id);
1110     }
1111 }
1112
1113 /* This is called periodically to flush old routes.  It will also send
1114    requests for routes that are about to expire. */
1115 void
1116 expire_routes(void)
1117 {
1118     struct babel_route *r;
1119     int i;
1120
1121     debugf(BABEL_DEBUG_COMMON,"Expiring old routes.");
1122
1123     i = 0;
1124     while(i < route_slots) {
1125         r = routes[i];
1126         while(r) {
1127             /* Protect against clock being stepped. */
1128             if(r->time > babel_now.tv_sec || route_old(r)) {
1129                 flush_route(r);
1130                 goto again;
1131             }
1132
1133             update_route_metric(r);
1134
1135             if(r->installed && r->refmetric < INFINITY) {
1136                 if(route_old(r))
1137                     /* Route about to expire, send a request. */
1138                     send_unicast_request(r->neigh,
1139                                          r->src->prefix, r->src->plen);
1140             }
1141             r = r->next;
1142         }
1143         i++;
1144     again:
1145         ;
1146     }
1147 }