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  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * * Redistributions of source code must retain the above copyright
  12  *   notice, this list of conditions and the following disclaimer.
  13  * * Redistributions in binary form must reproduce the above copyright
  14  *   notice, this list of conditions and the following disclaimer in
  15  *   the documentation and/or other materials provided with the
  16  *   distribution.
  17  * * Neither the name of olsr.org, olsrd nor the names of its
  18  *   contributors may be used to endorse or promote products derived
  19  *   from this software without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  32  * POSSIBILITY OF SUCH DAMAGE.
  33  *
  34  * Visit http://www.olsr.org for more information.
  35  *
  36  * If you find this software useful feel free to make a donation
  37  * to the project. For more information see the website or contact
  38  * the copyright holders.
  39  *
  40  * $Id: lq_route.c,v 1.45 2007/03/29 00:05:50 tlopatic Exp $
  41  */
  42
  43 #include "defs.h"
  44 #include "olsr.h"
  45 #include "tc_set.h"
  46 #include "neighbor_table.h"
  47 #include "two_hop_neighbor_table.h"
  48 #include "link_set.h"
  49 #include "routing_table.h"
  50 #include "mid_set.h"
  51 #include "hna_set.h"
  52 #include "lq_list.h"
  53 #include "lq_avl.h"
  54 #include "lq_route.h"
  55
  56 struct dijk_edge
  57 {
  58   struct avl_node tree_node;
  59   struct list_node node;
  60   struct dijk_vertex *dest;
  61   float etx;
  62 };
  63
  64 struct dijk_vertex
  65 {
  66   struct avl_node tree_node;
  67   struct list_node node;
  68   union olsr_ip_addr addr;
  69   struct avl_tree edge_tree;
  70   struct list edge_list;
  71   float path_etx;
  72   struct dijk_vertex *prev;
  73   olsr_bool done;
  74 };
  75
  76 static int avl_comp_ipv6(void *ip1, void *ip2)
  77 {
  78   return memcmp(ip1, ip2, olsr_cnf->ipsize);
  79 }
  80
  81 static int (*avl_comp)(void *, void *);
  82
  83 static void add_vertex(struct avl_tree *vertex_tree, union olsr_ip_addr *addr,
  84                        float path_etx)
  85 {
  86   struct avl_node *node;
  87   struct dijk_vertex *vert;
  88
  89   // see whether this destination is already in our list
  90
  91   node = avl_find(vertex_tree, addr);
  92
  93   // if it's not in our list, add it
  94
  95   if (node == NULL)
  96   {
  97     vert = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra vertex");
  98
  99     vert->tree_node.data = vert;
 100     vert->tree_node.key = &vert->addr;
 101
 102     COPY_IP(&vert->addr, addr);
 103
 104     vert->path_etx = path_etx;
 105     vert->prev = NULL;
 106     vert->done = OLSR_FALSE;
 107
 108     avl_init(&vert->edge_tree, avl_comp);
 109     list_init(&vert->edge_list);
 110
 111     avl_insert(vertex_tree, &vert->tree_node, 0);
 112   }
 113 }
 114
 115 static void add_edge(struct avl_tree *vertex_tree,
 116                      union olsr_ip_addr *src, union olsr_ip_addr *dst,
 117                      float etx)
 118 {
 119   struct avl_node *node;
 120   struct dijk_vertex *svert;
 121   struct dijk_vertex *dvert;
 122   struct dijk_edge *edge;
 123
 124   // source lookup
 125
 126   node = avl_find(vertex_tree, src);
 127
 128   // source vertex does not exist
 129
 130   if (node == NULL)
 131     return;
 132
 133   svert = node->data;
 134
 135   // destination lookup
 136
 137   node = avl_find(vertex_tree, dst);
 138
 139   // destination vertex does not exist
 140
 141   if (node == NULL)
 142     return;
 143
 144   dvert = node->data;
 145
 146   // check for existing forward edge
 147
 148   if (avl_find(&svert->edge_tree, dst) == NULL)
 149   {
 150     // add forward edge
 151
 152     edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge 1");
 153
 154     edge->tree_node.data = edge;
 155     edge->tree_node.key = &dvert->addr;
 156
 157     edge->node.data = edge;
 158
 159     edge->dest = dvert;
 160     edge->etx = etx;
 161
 162     avl_insert(&svert->edge_tree, &edge->tree_node, 0);
 163     list_add_tail(&svert->edge_list, &edge->node);
 164   }
 165
 166   // check for existing inverse edge
 167
 168   if (avl_find(&dvert->edge_tree, src) == NULL)
 169   {
 170     // add inverse edge
 171
 172     edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge 2");
 173
 174     edge->tree_node.data = edge;
 175     edge->tree_node.key = &svert->addr;
 176
 177     edge->node.data = edge;
 178
 179     edge->dest = svert;
 180     edge->etx = etx;
 181
 182     avl_insert(&dvert->edge_tree, &edge->tree_node, 0);
 183     list_add_tail(&dvert->edge_list, &edge->node);
 184   }
 185 }
 186
 187 static void create_vertex_list_rec(struct list *vertex_list,
 188                                    struct avl_node *node,
 189                                    int (*comp)(void *, void *))
 190 {
 191   struct dijk_vertex *vert = node->data;
 192
 193   if (node->left != NULL)
 194     create_vertex_list_rec(vertex_list, node->left, comp);
 195
 196   // add the vertex to the list, if it's not us
 197   if (NULL == comp) {
 198     if (inline_avl_comp_ipv4(&olsr_cnf->main_addr, node->key) != 0)
 199     {
 200       vert->node.data = vert;
 201       list_add_tail(vertex_list, &vert->node);
 202     }
 203   }
 204   else {
 205     if ((*comp)(&olsr_cnf->main_addr, node->key) != 0)
 206     {
 207       vert->node.data = vert;
 208       list_add_tail(vertex_list, &vert->node);
 209     }
 210   }
 211
 212   if (node->right != NULL)
 213     create_vertex_list_rec(vertex_list, node->right, comp);
 214 }
 215
 216 static void create_vertex_list(struct avl_tree *vertex_tree,
 217                                struct list *vertex_list)
 218 {
 219   struct avl_node *node;
 220   struct dijk_vertex *vert;
 221
 222   // make ourselves the first vertex in the list
 223
 224   node = avl_find(vertex_tree, &olsr_cnf->main_addr);
 225   vert = node->data;
 226
 227   vert->node.data = vert;
 228   list_add_tail(vertex_list, &vert->node);
 229
 230   // add the remaining vertices ordered by their main address
 231
 232   create_vertex_list_rec(vertex_list, vertex_tree->root, vertex_tree->comp);
 233 }
 234
 235 static void free_everything(struct list *vertex_list)
 236 {
 237   struct list_node *vnode, *enode;
 238   struct dijk_vertex *vert;
 239   struct dijk_edge *edge;
 240
 241   vnode = list_get_head(vertex_list);
 242
 243   // loop through all vertices
 244
 245   while (vnode != NULL)
 246   {
 247     vert = vnode->data;
 248
 249     enode = list_get_head(&vert->edge_list);
 250
 251     // loop through all edges of the current vertex
 252
 253     while (enode != NULL)
 254     {
 255       edge = enode->data;
 256
 257       enode = list_get_next(enode);
 258       free(edge);
 259     }
 260
 261     vnode = list_get_next(vnode);
 262     free(vert);
 263   }
 264 }
 265
 266 // XXX - bad complexity
 267 #define SVEN_OLA_OPTIMIZE
 268
 269 /*
 270  * The function extract_best() is most expensive (>50% CPU in profiling).
 271  * It is called in two modes: while doing Dijkstra route calculation and
 272  * while searching for a direct route/hna. The latter can be optimized
 273  * because the stored verices do not change from call to call and it is
 274  * more sufficient to have them sorted/popped from a list rather than
 275  * searching the complete list by every call. Sven-Ola@gmx.de, 11/2006
 276  *
 277  * The SVEN_OLA_OPTIMIZE changes work in our berlin environment. However,
 278  * they may introduce bugs, e.g. they are untested for IPv6. For this
 279  * reason, the source still contains the ifdef SVEN_OLA_OPIMIZE.
 280  */
 281
 282 #ifdef SVEN_OLA_OPTIMIZE
 283 static struct dijk_vertex **etx_cache = 0;
 284 static int etx_cache_count;
 285 static int etx_cache_get;
 286
 287 static int etx_cache_compare(const void *a, const void *b)
 288 {
 289   // Oh jeah. I love this macro assembler :)
 290
 291   if ((*(struct dijk_vertex **)a)->path_etx > (*(struct dijk_vertex **)b)->path_etx) return 1;
 292   if ((*(struct dijk_vertex **)a)->path_etx < (*(struct dijk_vertex **)b)->path_etx) return -1;
 293
 294   // This is for debugging only: etx==etx then compare pointers
 295   // to make it possible to compare to the original search algo.
 296   if (*(struct dijk_vertex **)a > *(struct dijk_vertex **)b) return 1;
 297   if (*(struct dijk_vertex **)a < *(struct dijk_vertex **)b) return -1;
 298
 299   return 0;
 300 }
 301
 302 static struct dijk_vertex *extract_best_route(struct list *vertex_list)
 303 {
 304   struct list_node *node;
 305   struct dijk_vertex *vert;
 306   struct dijk_vertex *res = NULL;
 307
 308   if (NULL == etx_cache)
 309   {
 310     int count = 0;
 311     node = list_get_head(vertex_list);
 312     while (node != NULL)
 313     {
 314       vert = node->data;
 315       if (!vert->done && vert->path_etx < INFINITE_ETX) count++;
 316       node = list_get_next(node);
 317     }
 318     if (0 < count)
 319     {
 320       etx_cache = olsr_malloc(sizeof(etx_cache[0]) * count, "ETX Cache");
 321       node = list_get_head(vertex_list);
 322       etx_cache_count = 0;
 323       etx_cache_get = 0;
 324       while (node != NULL)
 325       {
 326         vert = node->data;
 327         if (!vert->done && vert->path_etx < INFINITE_ETX)
 328         {
 329           etx_cache[etx_cache_count] = vert;
 330           etx_cache_count++;
 331         }
 332         node = list_get_next(node);
 333       }
 334       qsort(etx_cache, etx_cache_count, sizeof(etx_cache[0]), etx_cache_compare);
 335     }
 336   }
 337
 338   if (NULL != etx_cache && etx_cache_get < etx_cache_count)
 339   {
 340     res = etx_cache[etx_cache_get++];
 341   }
 342
 343   // if we've found a vertex, remove it from the set
 344
 345   if (res != NULL)
 346     res->done = OLSR_TRUE;
 347
 348   return res;
 349 }
 350 #endif // SVEN_OLA_OPTIMIZE
 351
 352 static struct dijk_vertex *extract_best(struct list *vertex_list)
 353 {
 354   float best_etx = INFINITE_ETX + 1.0;
 355   struct list_node *node;
 356   struct dijk_vertex *vert;
 357   struct dijk_vertex *res = NULL;
 358
 359   node = list_get_head(vertex_list);
 360
 361   // loop through all vertices
 362
 363   while (node != NULL)
 364   {
 365     vert = node->data;
 366
 367     // see whether the current vertex is better than what we have
 368
 369     if (!vert->done && vert->path_etx < best_etx)
 370     {
 371       best_etx = vert->path_etx;
 372       res = vert;
 373     }
 374
 375     node = list_get_next(node);
 376   }
 377
 378   // if we've found a vertex, remove it from the set
 379
 380   if (res != NULL)
 381     res->done = OLSR_TRUE;
 382
 383   return res;
 384 }
 385
 386 static void relax(struct dijk_vertex *vert)
 387 {
 388   struct dijk_edge *edge;
 389   float new_etx;
 390   struct list_node *node;
 391
 392   node = list_get_head(&vert->edge_list);
 393
 394   // loop through all edges of this vertex
 395
 396   while (node != NULL)
 397   {
 398     edge = node->data;
 399
 400     // total quality of the path through this vertex to the
 401     // destination of this edge
 402
 403     new_etx = vert->path_etx + edge->etx;
 404
 405     // if it's better than the current path quality of this
 406     // edge's destination, then we've found a better path to
 407     // this destination
 408
 409     if (new_etx < edge->dest->path_etx)
 410     {
 411       edge->dest->path_etx = new_etx;
 412       edge->dest->prev = vert;
 413     }
 414
 415     node = list_get_next(node);
 416   }
 417 }
 418
 419 static char *etx_to_string(float etx)
 420 {
 421   static char buff[20];
 422
 423   if (etx == INFINITE_ETX)
 424     return "INF";
 425
 426   snprintf(buff, 20, "%.2f", etx);
 427   return buff;
 428 }
 429
 430 void olsr_calculate_lq_routing_table(void)
 431 {
 432   struct avl_tree vertex_tree;
 433   struct list vertex_list;
 434   int i;
 435   struct tc_entry *tcsrc;
 436   struct topo_dst *tcdst;
 437   struct dijk_vertex *vert;
 438   struct link_entry *link;
 439   struct neighbor_entry *neigh;
 440   struct list_node *node;
 441   struct dijk_vertex *myself;
 442   struct dijk_vertex *walker;
 443   int hops;
 444   struct mid_address *mid_walker;
 445   float etx;
 446   struct hna_entry *hna_gw;
 447   struct hna_net *hna;
 448   struct rt_entry *gw_rt, *hna_rt, *head_rt;
 449   struct neighbor_2_entry *neigh2;
 450 #if 0
 451   struct neighbor_list_entry *neigh_walker;
 452 #endif
 453   struct interface *inter;
 454
 455   if (olsr_cnf->ipsize == 4)
 456     avl_comp = 0;
 457   else
 458     avl_comp = avl_comp_ipv6;
 459
 460   // initialize the graph
 461
 462   avl_init(&vertex_tree, avl_comp);
 463   list_init(&vertex_list);
 464
 465   // add ourselves to the vertex tree
 466
 467   add_vertex(&vertex_tree, &olsr_cnf->main_addr, 0.0);
 468
 469   // add our neighbours
 470
 471   for (i = 0; i < HASHSIZE; i++)
 472     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
 473          neigh = neigh->next)
 474       if (neigh->status == SYM)
 475         add_vertex(&vertex_tree, &neigh->neighbor_main_addr, INFINITE_ETX);
 476
 477   // add our two-hop neighbours
 478
 479   for (i = 0; i < HASHSIZE; i++)
 480     for (neigh2 = two_hop_neighbortable[i].next;
 481          neigh2 != &two_hop_neighbortable[i];
 482          neigh2 = neigh2->next)
 483       add_vertex(&vertex_tree, &neigh2->neighbor_2_addr, INFINITE_ETX);
 484
 485   // add remaining vertices
 486
 487   for (i = 0; i < HASHSIZE; i++)
 488     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
 489     {
 490       // add source
 491
 492       add_vertex(&vertex_tree, &tcsrc->T_last_addr, INFINITE_ETX);
 493
 494       // add destinations of this source
 495
 496       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
 497            tcdst = tcdst->next)
 498         add_vertex(&vertex_tree, &tcdst->T_dest_addr, INFINITE_ETX);
 499     }
 500
 501   // add edges to and from our neighbours
 502
 503   for (i = 0; i < HASHSIZE; i++)
 504     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
 505          neigh = neigh->next)
 506       if (neigh->status == SYM)
 507       {
 508         link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
 509
 510         if(!link)
 511           continue;
 512
 513         if (link->loss_link_quality2 >= MIN_LINK_QUALITY &&
 514             link->neigh_link_quality2 >= MIN_LINK_QUALITY)
 515           {
 516             etx = 1.0 / (link->loss_link_quality2 * link->neigh_link_quality2);
 517
 518             add_edge(&vertex_tree, &neigh->neighbor_main_addr, &olsr_cnf->main_addr, etx);
 519           }
 520       }
 521
 522 // we now rely solely on TC messages for routes to our two-hop neighbours
 523
 524 #if 0
 525
 526   // add edges between our neighbours and our two-hop neighbours
 527
 528   for (i = 0; i < HASHSIZE; i++)
 529     for (neigh2 = two_hop_neighbortable[i].next;
 530          neigh2 != &two_hop_neighbortable[i];
 531          neigh2 = neigh2->next)
 532       for (neigh_walker = neigh2->neighbor_2_nblist.next;
 533            neigh_walker != &neigh2->neighbor_2_nblist;
 534            neigh_walker = neigh_walker->next)
 535       {
 536         if (neigh_walker->second_hop_link_quality >=
 537             MIN_LINK_QUALITY * MIN_LINK_QUALITY)
 538         {
 539           neigh = neigh_walker->neighbor;
 540
 541           etx = 1.0 / neigh_walker->second_hop_link_quality;
 542
 543           add_edge(&vertex_tree, &neigh2->neighbor_2_addr,
 544                    &neigh->neighbor_main_addr, etx);
 545         }
 546       }
 547
 548 #endif
 549
 550   // add remaining edges
 551
 552   for (i = 0; i < HASHSIZE; i++)
 553     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
 554       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
 555            tcdst = tcdst->next)
 556       {
 557         if (tcdst->link_quality >= MIN_LINK_QUALITY &&
 558             tcdst->inverse_link_quality >= MIN_LINK_QUALITY)
 559           {
 560             etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
 561
 562             add_edge(&vertex_tree, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
 563                      etx);
 564           }
 565       }
 566
 567   // create a sorted vertex list from the vertex tree
 568
 569   create_vertex_list(&vertex_tree, &vertex_list);
 570
 571   // run Dijkstra's algorithm
 572
 573   for (;;)
 574   {
 575     vert = extract_best(&vertex_list);
 576
 577     if (vert == NULL)
 578       break;
 579
 580     relax(vert);
 581   }
 582
 583   // save the old routing table
 584
 585   olsr_move_route_table(routingtable, old_routes);
 586
 587   node = list_get_head(&vertex_list);
 588
 589   // we're the first vertex in the list
 590
 591   myself = node->data;
 592
 593   OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
 594               nowtm->tm_hour,
 595               nowtm->tm_min,
 596               nowtm->tm_sec,
 597               (int)now.tv_usec/10000)
 598
 599   for (node = list_get_next(node); node != NULL; node = list_get_next(node))
 600   {
 601     vert = node->data;
 602
 603     hops = 1;
 604
 605     // count hops to until the path ends or until we have reached a
 606     // one-hop neighbour
 607
 608     for (walker = vert; walker != NULL && walker->prev != myself;
 609          walker = walker->prev)
 610     {
 611       OLSR_PRINTF(2, "%s:%s <- ", olsr_ip_to_string(&walker->addr),
 612                   etx_to_string(walker->path_etx))
 613       hops++;
 614     }
 615
 616     // if no path to a one-hop neighbour was found, ignore this node
 617
 618     if (walker != NULL)
 619     {
 620       OLSR_PRINTF(2, "%s:%s (one-hop)\n", olsr_ip_to_string(&walker->addr),
 621                   etx_to_string(walker->path_etx))
 622
 623       // node reachable => add to the set of unprocessed nodes
 624       // for HNA processing
 625
 626       vert->done = OLSR_FALSE;
 627     }
 628
 629     else
 630     {
 631       OLSR_PRINTF(2, "%s FAILED\n", olsr_ip_to_string(&vert->addr))
 632       continue;
 633     }
 634
 635     // find the best link to the one-hop neighbour
 636
 637     link = get_best_link_to_neighbor(&walker->addr);
 638
 639     // we may see NULL here, if the one-hop neighbour is not in the
 640     // link and neighbour sets any longer, but we have derived an edge
 641     // between us and the one-hop neighbour from the TC set
 642
 643     if (link != NULL)
 644     {
 645       // find the interface for the found link
 646       inter = link->if_name ? if_ifwithname(link->if_name) :
 647               if_ifwithaddr(&link->local_iface_addr);
 648
 649       // we may see NULL here if the interface is down, but we have
 650       // links that haven't timed out, yet
 651
 652       if (inter != NULL)
 653       {
 654         // XXX - fix me: structurally prevent duplicates, don't test via
 655         //       olsr_lookup_routing_table()
 656
 657         // route addition, case A - add a route to the main address of the
 658         // destination node
 659
 660         if (olsr_lookup_routing_table(&vert->addr) == NULL)
 661           olsr_insert_routing_table(&vert->addr, &link->neighbor_iface_addr,
 662                                     inter, hops, vert->path_etx);
 663
 664         // route addition, case B - add routes to the remaining interfaces
 665         // of the destination node
 666
 667         for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
 668              mid_walker = mid_walker->next_alias)
 669           if (olsr_lookup_routing_table(&mid_walker->alias) == NULL)
 670             olsr_insert_routing_table(&mid_walker->alias,
 671                                       &link->neighbor_iface_addr, inter, hops,
 672                                       vert->path_etx);
 673
 674         // XXX - we used to use olsr_lookup_routing_table() only here, but
 675         //       this assumed that case A or case B had already happened for
 676         //       this destination; if case A or case B happened after case C
 677         //       for the same destination, we had duplicates, as cases A and
 678         //       B would not test whether case C had already happened
 679
 680         // route addition, case C - make sure that we have a route to the
 681         // router - e.g. in case the router's not the main address and it's
 682         // MID entry has timed out
 683
 684         if (olsr_lookup_routing_table(&link->neighbor_iface_addr) == NULL)
 685           olsr_insert_routing_table(&link->neighbor_iface_addr,
 686                                     &link->neighbor_iface_addr, inter, 1,
 687                                     vert->path_etx);
 688       }
 689     }
 690   }
 691
 692   // save the old HNA routing table
 693
 694   olsr_move_route_table(hna_routes, old_hna);
 695
 696   // add HNA routes - the set of unprocessed network nodes contains
 697   // all reachable network nodes
 698 #ifdef SVEN_OLA_OPTIMIZE
 699   if (NULL != etx_cache) {
 700     free(etx_cache);
 701     etx_cache = NULL;
 702   }
 703 #endif
 704
 705   for (;;)
 706   {
 707     // extract the network node with the best ETX and remove it
 708     // from the set of unprocessed network nodes
 709
 710 #ifdef SVEN_OLA_OPTIMIZE
 711     vert = extract_best_route(&vertex_list);
 712 #else
 713     vert = extract_best(&vertex_list);
 714 #endif
 715
 716     // no more nodes left
 717
 718     if (vert == NULL)
 719       break;
 720
 721     // find the node's HNAs
 722
 723     hna_gw = olsr_lookup_hna_gw(&vert->addr);
 724
 725     // node doesn't announce any HNAs
 726
 727     if (hna_gw == NULL)
 728       continue;
 729
 730     // find route to the node
 731
 732     gw_rt = olsr_lookup_routing_table(&hna_gw->A_gateway_addr);
 733
 734     // maybe we haven't found a link or an interface for the gateway above
 735     // and hence haven't added a route - skip the HNA in this case
 736
 737     if (gw_rt == NULL)
 738       continue;
 739
 740     // loop through the node's HNAs
 741
 742     for (hna = hna_gw->networks.next; hna != &hna_gw->networks;
 743          hna = hna->next)
 744     {
 745       // we already have a route via a previous (better) node
 746
 747       if (olsr_lookup_hna_routing_table(&hna->A_network_addr) != NULL)
 748         continue;
 749
 750       // create route for the HNA
 751
 752       hna_rt = olsr_malloc(sizeof(struct rt_entry), "LQ HNA route entry");
 753
 754       // set HNA IP address and netmask
 755
 756       COPY_IP(&hna_rt->rt_dst, &hna->A_network_addr);
 757       hna_rt->rt_mask = hna->A_netmask;
 758
 759       // copy remaining fields from the node's route
 760
 761       COPY_IP(&hna_rt->rt_router, &gw_rt->rt_router);
 762       hna_rt->rt_metric = gw_rt->rt_metric;
 763       hna_rt->rt_etx = gw_rt->rt_etx;
 764       hna_rt->rt_if = gw_rt->rt_if;
 765
 766       // we're not a host route
 767
 768       hna_rt->rt_flags = RTF_UP | RTF_GATEWAY;
 769
 770       // find the correct list
 771
 772       head_rt = &hna_routes[olsr_hashing(&hna->A_network_addr)];
 773
 774       // enqueue
 775
 776       head_rt->next->prev = hna_rt;
 777       hna_rt->next = head_rt->next;
 778
 779       head_rt->next = hna_rt;
 780       hna_rt->prev = head_rt;
 781     }
 782   }
 783
 784   // free the graph
 785
 786   free_everything(&vertex_list);
 787
 788   // move the route changes into the kernel
 789
 790   olsr_update_kernel_routes();
 791   olsr_update_kernel_hna_routes();
 792
 793   // free the saved routing table
 794
 795   olsr_free_routing_table(old_routes);
 796   olsr_free_routing_table(old_hna);
 797 }