8d59fb21f00bcd89b56f503d261d37fe4654756e
[olsrd.git] / 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.46 2007/04/25 22:08:09 bernd67 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 }