src/lq_route.c

   1 /*
   2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   3  * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
   4  * IPv4 performance optimization (c) 2006, sven-ola(gmx.de)
   5  * SPF implementation (c) 2007, Hannes Gredler (hannes@gredler.at)
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * * Redistributions of source code must retain the above copyright
  13  *   notice, this list of conditions and the following disclaimer.
  14  * * Redistributions in binary form must reproduce the above copyright
  15  *   notice, this list of conditions and the following disclaimer in
  16  *   the documentation and/or other materials provided with the
  17  *   distribution.
  18  * * Neither the name of olsr.org, olsrd nor the names of its
  19  *   contributors may be used to endorse or promote products derived
  20  *   from this software without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  26  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  30  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  32  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  33  * POSSIBILITY OF SUCH DAMAGE.
  34  *
  35  * Visit http://www.olsr.org for more information.
  36  *
  37  * If you find this software useful feel free to make a donation
  38  * to the project. For more information see the website or contact
  39  * the copyright holders.
  40  *
  41  * Implementation of Dijkstras algorithm. Initially all nodes
  42  * are initialized to infinite cost. First we put ourselves
  43  * on the heap of reachable nodes. Our heap implementation
  44  * is based on an AVL tree which gives interesting performance
  45  * characteristics for the frequent operations of minimum key
  46  * extraction and re-keying. Next all neighbors of a node are
  47  * explored and put on the heap if the cost of reaching them is
  48  * better than reaching the current candidate node.
  49  * The SPF calculation is terminated if there are no more nodes
  50  * on the heap.
  51  */
  52
  53 #define SPF_PROFILING 0
  54
  55 #include "ipcalc.h"
  56 #include "defs.h"
  57 #include "olsr.h"
  58 #include "tc_set.h"
  59 #include "neighbor_table.h"
  60 #include "two_hop_neighbor_table.h"
  61 #include "link_set.h"
  62 #include "routing_table.h"
  63 #include "mid_set.h"
  64 #include "hna_set.h"
  65 #include "lq_list.h"
  66 #include "lq_avl.h"
  67 #include "lq_route.h"
  68 #include "net_olsr.h"
  69
  70 /*
  71  * avl_comp_etx
  72  *
  73  * compare two etx metrics.
  74  * return 0 if there is an exact match and
  75  * -1 / +1 depending on being smaller or bigger.
  76  * note that this results in the most optimal code
  77  * after compiler optimization.
  78  */
  79 static int
  80 avl_comp_etx (const void *etx1, const void *etx2)
  81 {
  82   if (*(const float *)etx1 < *(const float *)etx2) {
  83     return -1;
  84   }
  85
  86   if (*(const float *)etx1 > *(const float *)etx2) {
  87     return +1;
  88   }
  89
  90   return 0;
  91 }
  92
  93 /*
  94  * olsr_spf_add_cand_tree
  95  *
  96  * Key an existing vertex to a candidate tree.
  97  */
  98 static void
  99 olsr_spf_add_cand_tree (struct avl_tree *tree,
 100                         struct tc_entry *tc)
 101 {
 102 #if !defined(NODEBUG) && defined(DEBUG)
 103   struct ipaddr_str buf;
 104 #endif
 105   tc->cand_tree_node.key = &tc->path_etx;
 106   tc->cand_tree_node.data = tc;
 107
 108 #ifdef DEBUG
 109   OLSR_PRINTF(1, "SPF: insert candidate %s, cost %f\n",
 110               olsr_ip_to_string(&buf, &tc->addr),
 111               tc->path_etx);
 112 #endif
 113
 114   avl_insert(tree, &tc->cand_tree_node, AVL_DUP);
 115 }
 116
 117 /*
 118  * olsr_spf_del_cand_tree
 119  *
 120  * Unkey an existing vertex from a candidate tree.
 121  */
 122 static void
 123 olsr_spf_del_cand_tree (struct avl_tree *tree,
 124                         struct tc_entry *tc)
 125 {
 126
 127 #ifdef DEBUG
 128 #ifndef NODEBUG
 129   struct ipaddr_str buf;
 130 #endif
 131   OLSR_PRINTF(1, "SPF: delete candidate %s, cost %f\n",
 132               olsr_ip_to_string(&buf, &tc->addr),
 133               tc->path_etx);
 134 #endif
 135
 136   avl_delete(tree, &tc->cand_tree_node);
 137 }
 138
 139 /*
 140  * olsr_spf_add_path_list
 141  *
 142  * Insert an SPF result at the end of the path list.
 143  */
 144 static void
 145 olsr_spf_add_path_list (struct list_node *head, int *path_count,
 146                         struct tc_entry *tc)
 147 {
 148 #if !defined(NODEBUG) && defined(DEBUG)
 149   struct ipaddr_str pathbuf, nbuf;
 150 #endif
 151   tc->path_list_node.data = tc;
 152
 153 #ifdef DEBUG
 154   OLSR_PRINTF(1, "SPF: append path %s, cost %f, via %s\n",
 155               olsr_ip_to_string(&pathbuf, &tc->addr),
 156               tc->path_etx,
 157               tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "-");
 158 #endif
 159
 160   list_add_before(head, &tc->path_list_node);
 161   *path_count = *path_count + 1;
 162 }
 163
 164 /*
 165  * olsr_spf_extract_best
 166  *
 167  * return the node with the minimum pathcost.
 168  */
 169 static struct tc_entry *
 170 olsr_spf_extract_best (struct avl_tree *tree)
 171 {
 172   struct avl_node *node = avl_walk_first(tree);
 173
 174   return (node ? node->data :  NULL);
 175 }
 176
 177
 178 const char *olsr_etx_to_string(float etx)
 179 {
 180   static char buff[20];
 181
 182   if (etx == INFINITE_ETX) {
 183     return "INF";
 184   }
 185   snprintf(buff, sizeof(buff), "%.6f", etx);
 186   return buff;
 187 }
 188
 189
 190 /*
 191  * olsr_spf_relax
 192  *
 193  * Explore all edges of a node and add the node
 194  * to the candidate tree if the if the aggregate
 195  * path cost is better.
 196  */
 197 static void
 198 olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *tc)
 199 {
 200   struct avl_node *edge_node;
 201   float new_etx;
 202
 203 #ifdef DEBUG
 204 #ifndef NODEBUG
 205   struct ipaddr_str buf, nbuf;
 206 #endif
 207   OLSR_PRINTF(1, "SPF: exploring node %s, cost %f\n",
 208               olsr_ip_to_string(&buf, &tc->addr),
 209               tc->path_etx);
 210 #endif
 211
 212   /*
 213    * loop through all edges of this vertex.
 214    */
 215   for (edge_node = avl_walk_first(&tc->edge_tree);
 216        edge_node;
 217        edge_node = avl_walk_next(edge_node)) {
 218
 219     struct tc_entry *new_tc;
 220     struct tc_edge_entry *tc_edge = edge_node->data;
 221
 222     /*
 223      * We are not interested in dead-end or dying edges.
 224      */
 225     if (!tc_edge->edge_inv || (tc_edge->flags & OLSR_TC_EDGE_DOWN)) {
 226 #ifdef DEBUG
 227       OLSR_PRINTF(1, "SPF:   ignoring edge %s\n",
 228                   olsr_ip_to_string(&buf, &tc_edge->T_dest_addr));
 229       if (tc_edge->flags & OLSR_TC_EDGE_DOWN) {
 230         OLSR_PRINTF(1, "SPF:     edge down\n");
 231       }
 232       if (!tc_edge->edge_inv) {
 233         OLSR_PRINTF(1, "SPF:     no inverse edge\n");
 234       }
 235 #endif
 236       continue;
 237     }
 238
 239     /*
 240      * total quality of the path through this vertex
 241      * to the destination of this edge
 242      */
 243     new_etx = tc->path_etx + tc_edge->etx;
 244
 245 #ifdef DEBUG
 246       OLSR_PRINTF(1, "SPF:   exploring edge %s, cost %s\n",
 247                   olsr_ip_to_string(&buf, &tc_edge->T_dest_addr),
 248                   olsr_etx_to_string(new_etx));
 249 #endif
 250
 251       /*
 252        * if it's better than the current path quality of this edge's
 253        * destination node, then we've found a better path to this node.
 254        */
 255     new_tc = tc_edge->edge_inv->tc;
 256
 257     if (new_etx < new_tc->path_etx) {
 258
 259       /* if this node has been on the candidate tree delete it */
 260       if (new_tc->path_etx != INFINITE_ETX) {
 261         olsr_spf_del_cand_tree(cand_tree, new_tc);
 262       }
 263
 264       /* re-insert on candidate tree with the better metric */
 265       new_tc->path_etx = new_etx;
 266       olsr_spf_add_cand_tree(cand_tree, new_tc);
 267
 268       /* pull-up the next-hop and bump the hop count */
 269       if (tc->next_hop) {
 270         new_tc->next_hop = tc->next_hop;
 271       }
 272       new_tc->hops = tc->hops + 1;
 273
 274 #ifdef DEBUG
 275       OLSR_PRINTF(1, "SPF:   better path to %s, cost %s -> %s, via %s, hops %u\n",
 276                   olsr_ip_to_string(&buf, &new_tc->addr),
 277                   olsr_etx_to_string(new_tc->path_etx),
 278                   olsr_etx_to_string(new_etx),
 279                   tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "<none>",
 280                   new_tc->hops);
 281 #endif
 282
 283     }
 284   }
 285 }
 286
 287 /*
 288  * olsr_spf_run_full
 289  *
 290  * Run the Dijkstra algorithm.
 291  *
 292  * A node gets added to the candidate tree when one of its edges has
 293  * an overall better root path cost than the node itself.
 294  * The node with the shortest metric gets moved from the candidate to
 295  * the path list every pass.
 296  * The SPF computation is completed when there are no more nodes
 297  * on the candidate tree.
 298  */
 299 static void
 300 olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
 301                    int *path_count)
 302 {
 303   struct tc_entry *tc;
 304
 305   *path_count = 0;
 306
 307   while ((tc = olsr_spf_extract_best(cand_tree))) {
 308
 309     olsr_spf_relax(cand_tree, tc);
 310
 311     /*
 312      * move the best path from the candidate tree
 313      * to the path list.
 314      */
 315     olsr_spf_del_cand_tree(cand_tree, tc);
 316     olsr_spf_add_path_list(path_list, path_count, tc);
 317   }
 318 }
 319
 320 void
 321 olsr_calculate_routing_table (void)
 322 {
 323   struct avl_tree cand_tree;
 324   struct avl_node *rtp_tree_node;
 325   struct list_node path_list; /* head of the path_list */
 326   int i, path_count = 0;
 327   struct tc_entry *tc;
 328   struct rt_path *rtp;
 329   struct tc_edge_entry *tc_edge;
 330   struct neighbor_entry *neigh;
 331   struct link_entry *link;
 332
 333 #ifdef SPF_PROFILING
 334   struct timeval t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
 335
 336   gettimeofday(&t1, NULL);
 337 #endif
 338
 339   /*
 340    * Prepare the candidate tree and result list.
 341    */
 342   avl_init(&cand_tree, avl_comp_etx);
 343   list_head_init(&path_list);
 344   olsr_bump_routingtree_version();
 345
 346   /*
 347    * Initialize vertices in the lsdb.
 348    */
 349   OLSR_FOR_ALL_TC_ENTRIES(tc) {
 350     tc->next_hop = NULL;
 351     tc->path_etx = INFINITE_ETX;
 352     tc->hops = 0;
 353   } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 354
 355   /*
 356    * zero ourselves and add us to the candidate tree.
 357    */
 358   olsr_change_myself_tc();
 359   tc_myself->path_etx = ZERO_ETX;
 360   olsr_spf_add_cand_tree(&cand_tree, tc_myself);
 361
 362   /*
 363    * add edges to and from our neighbours.
 364    */
 365   for (i = 0; i < HASHSIZE; i++)
 366     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
 367          neigh = neigh->next) {
 368
 369       if (neigh->status == SYM) {
 370
 371         tc_edge = olsr_lookup_tc_edge(tc_myself, &neigh->neighbor_main_addr);
 372         link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
 373         if (!link) {
 374
 375           /*
 376            * If there is no best link to this neighbor
 377            * and we had an edge before then flush the edge.
 378            */
 379           if (tc_edge) {
 380             olsr_delete_tc_edge_entry(tc_edge);
 381           }
 382           continue;
 383         }
 384
 385         /* find the interface for the link */
 386         if (link->if_name) {
 387           link->inter = if_ifwithname(link->if_name);
 388         } else {
 389           link->inter = if_ifwithaddr(&link->local_iface_addr);
 390         }
 391
 392         /*
 393          * Set the next-hops of our neighbors.
 394          */
 395         if (!tc_edge) {
 396           tc_edge = olsr_add_tc_edge_entry(tc_myself, &neigh->neighbor_main_addr,
 397                                            0, link->vtime,
 398                                            link->loss_link_quality2,
 399                                            link->neigh_link_quality2);
 400         } else {
 401
 402           /*
 403            * Update LQ and timers, such that the edge does not get deleted.
 404            */
 405           tc_edge->link_quality = link->loss_link_quality2;
 406           tc_edge->inverse_link_quality = link->neigh_link_quality2;
 407           olsr_set_tc_edge_timer(tc_edge, link->vtime*1000);
 408           olsr_calc_tc_edge_entry_etx(tc_edge);
 409         }
 410         if (tc_edge->edge_inv) {
 411           tc_edge->edge_inv->tc->next_hop = link;
 412         }
 413       }
 414     }
 415
 416 #ifdef SPF_PROFILING
 417   gettimeofday(&t2, NULL);
 418 #endif
 419
 420   /*
 421    * Run the SPF calculation.
 422    */
 423   olsr_spf_run_full(&cand_tree, &path_list, &path_count);
 424
 425   OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
 426               nowtm->tm_hour,
 427               nowtm->tm_min,
 428               nowtm->tm_sec,
 429               (int)now.tv_usec/10000);
 430
 431 #ifdef SPF_PROFILING
 432   gettimeofday(&t3, NULL);
 433 #endif
 434
 435   /*
 436    * In the path list we have all the reachable nodes in our topology.
 437    */
 438   for (; !list_is_empty(&path_list); list_remove(path_list.next)) {
 439
 440     tc = path_list.next->data;
 441     link = tc->next_hop;
 442
 443     if (!link) {
 444 #ifdef DEBUG
 445       /*
 446        * Supress the error msg when our own tc_entry
 447        * does not contain a next-hop.
 448        */
 449       if (tc != tc_myself) {
 450 #ifndef NODEBUG
 451         struct ipaddr_str buf;
 452 #endif
 453         OLSR_PRINTF(1, "SPF: %s no next-hop\n", olsr_ip_to_string(&buf, &tc->addr));
 454       }
 455 #endif
 456       continue;
 457     }
 458
 459     /*
 460      * Now walk all prefixes advertised by that node.
 461      * Since the node is reachable, insert the prefix into the global RIB.
 462      * If the prefix is already in the RIB, refresh the entry such
 463      * that olsr_delete_outdated_routes() does not purge it off.
 464      */
 465     for (rtp_tree_node = avl_walk_first(&tc->prefix_tree);
 466          rtp_tree_node;
 467          rtp_tree_node = avl_walk_next(rtp_tree_node)) {
 468
 469       rtp = rtp_tree_node->data;
 470
 471       if (rtp->rtp_rt) {
 472
 473         /*
 474          * If there is a route entry, the prefix is already in the global RIB.
 475          */
 476         olsr_update_rt_path(rtp, tc, link);
 477
 478       } else {
 479
 480         /*
 481          * The prefix is reachable and not yet in the global RIB.
 482          * Build a rt_entry for it.
 483          */
 484         olsr_insert_rt_path(rtp, tc, link);
 485       }
 486     }
 487   }
 488
 489   /* Update the RIB based on the new SPF results */
 490
 491   olsr_update_rib_routes();
 492
 493 #ifdef SPF_PROFILING
 494   gettimeofday(&t4, NULL);
 495 #endif
 496
 497   /* move the route changes into the kernel */
 498
 499   olsr_update_kernel_routes();
 500
 501 #ifdef SPF_PROFILING
 502   gettimeofday(&t5, NULL);
 503 #endif
 504
 505 #ifdef SPF_PROFILING
 506   timersub(&t2, &t1, &spf_init);
 507   timersub(&t3, &t2, &spf_run);
 508   timersub(&t4, &t3, &route);
 509   timersub(&t5, &t4, &kernel);
 510   timersub(&t5, &t1, &total);
 511   OLSR_PRINTF(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern): "
 512               "%d, %d, %d, %d, %d\n",
 513               path_count, routingtree.count,
 514               (int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec,
 515               (int)route.tv_usec, (int)kernel.tv_usec);
 516 #endif
 517 }
 518
 519 /*
 520  * Local Variables:
 521  * c-basic-offset: 2
 522  * End:
 523  */