added the SPF refactoring from Hannes Gredler <hannes@gredler.at>:
[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  * 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  * $Id: lq_route.c,v 1.47 2007/07/05 22:43:46 bernd67 Exp $
42  */
43
44 #include "defs.h"
45 #include "olsr.h"
46 #include "tc_set.h"
47 #include "neighbor_table.h"
48 #include "two_hop_neighbor_table.h"
49 #include "link_set.h"
50 #include "routing_table.h"
51 #include "mid_set.h"
52 #include "hna_set.h"
53 #include "lq_list.h"
54 #include "lq_avl.h"
55 #include "lq_route.h"
56
57 struct olsr_spf_edge
58 {
59   struct avl_node tree_node;
60   struct olsr_spf_vertex *dest;
61   float etx;
62 };
63
64 struct olsr_spf_vertex
65 {
66   struct avl_node tree_node; /* node keyed by ip address */
67   struct avl_node cand_tree_node; /* node keyed by etx */
68   struct avl_node path_tree_node; /* node keyed by etx */
69   union olsr_ip_addr addr;
70   struct avl_tree edge_tree;
71   union olsr_ip_addr *next_hop; /* the gateway router */
72   float path_etx;
73   olsr_u8_t hops;
74 };
75
76 /*
77  * avl_comp_etx
78  *
79  * compare two etx metrics.
80  * return 0 if there is an exact match and
81  * -1 / +1 depending on being smaller or bigger.
82  * note that this results in the most optimal code
83  * after compiler optimization.
84  */
85 static int
86 avl_comp_etx (void *etx1, void *etx2)
87 {       
88   if (*(float *)etx1 < *(float *)etx2) {
89     return -1;
90   }
91
92   if (*(float *)etx1 > *(float *)etx2) {
93     return +1;
94   }
95
96   return 0;
97 }
98
99 /*
100  * olsr_spf_add_cand_tree
101  *
102  * Key an existing vertex to a candidate tree.
103  */
104 static void
105 olsr_spf_add_cand_tree (struct avl_tree *tree,
106                         struct olsr_spf_vertex *vert)
107 {
108   vert->cand_tree_node.key = &vert->path_etx;
109   vert->cand_tree_node.data = vert;
110
111 #ifdef DEBUG
112   OLSR_PRINTF(1, "SPF: insert candidate %s, cost %f\n",
113               olsr_ip_to_string(&(vert->addr)),
114               vert->path_etx);
115 #endif
116
117   avl_insert(tree, &vert->cand_tree_node, 1);
118 }
119
120 /*
121  * olsr_spf_del_cand_tree
122  *
123  * Unkey an existing vertex from a candidate tree.
124  */
125 static void
126 olsr_spf_del_cand_tree (struct avl_tree *tree,
127                         struct olsr_spf_vertex *vert)
128 {
129
130 #ifdef DEBUG
131   OLSR_PRINTF(1, "SPF: delete candidate %s, cost %f\n",
132               olsr_ip_to_string(&(vert->addr)),
133               vert->path_etx);
134 #endif
135
136   avl_delete(tree, &vert->cand_tree_node);
137 }
138
139 /*
140  * olsr_spf_add_path_tree
141  *
142  * Key an existing vertex to a path tree.
143  */
144 static void
145 olsr_spf_add_path_tree (struct avl_tree *tree,
146                         struct olsr_spf_vertex *vert)
147 {
148   vert->path_tree_node.key = &vert->path_etx;
149   vert->path_tree_node.data = vert;
150
151 #ifdef DEBUG
152   OLSR_PRINTF(1, "SPF: insert path %s, cost %f, via %s\n",
153               olsr_ip_to_string(&(vert->addr)),
154               vert->path_etx,
155               olsr_ip_to_string(vert->next_hop));
156 #endif
157
158   avl_insert(tree, &vert->path_tree_node, 1);
159 }
160
161 /*
162  * olsr_spf_add_vertex
163  *
164  * Add a node to the tree of all nodes in the network.
165  */
166 static struct olsr_spf_vertex *
167 olsr_spf_add_vertex (struct avl_tree *vertex_tree,
168                      union olsr_ip_addr *addr, float path_etx)
169 {
170   struct avl_node *node;
171   struct olsr_spf_vertex *vert;
172
173   // see whether this destination is already in our tree
174
175   node = avl_find(vertex_tree, addr);
176
177   if (node) {
178     return node->data;
179   }
180
181   // if it's not in our list, add it
182
183   vert = olsr_malloc(sizeof (struct olsr_spf_vertex), "Dijkstra vertex");
184
185   vert->tree_node.data = vert;
186   vert->tree_node.key = &vert->addr;
187
188   COPY_IP(&vert->addr, addr);
189     
190   vert->path_etx = path_etx;
191   vert->next_hop = NULL;
192   vert->hops = 0;
193
194   avl_init(&vert->edge_tree, avl_comp_default);
195
196   avl_insert(vertex_tree, &vert->tree_node, 0);
197   return vert;
198 }
199
200 static void
201 olsr_spf_add_edge (struct avl_tree *vertex_tree,
202                    union olsr_ip_addr *src, union olsr_ip_addr *dst,
203                    float etx)
204 {
205   struct avl_node *node;
206   struct olsr_spf_vertex *svert;
207   struct olsr_spf_vertex *dvert;
208   struct olsr_spf_edge *edge;
209
210   // source lookup
211
212   node = avl_find(vertex_tree, src);
213
214   // source vertex does not exist
215
216   if (node == NULL)
217     return;
218
219   svert = node->data;
220
221   // destination lookup
222
223   node = avl_find(vertex_tree, dst);
224
225   // destination vertex does not exist
226
227   if (node == NULL)
228     return;
229
230   dvert = node->data;
231
232   // check for existing forward edge
233
234   if (avl_find(&svert->edge_tree, dst) == NULL)
235   {
236     // add forward edge
237
238     edge = olsr_malloc(sizeof (struct olsr_spf_vertex), "Dijkstra forward edge");
239
240     edge->tree_node.data = edge;
241     edge->tree_node.key = &dvert->addr;
242
243     edge->dest = dvert;
244     edge->etx = etx;
245
246     avl_insert(&svert->edge_tree, &edge->tree_node, 0);
247   }
248
249   // check for existing inverse edge
250
251   if (avl_find(&dvert->edge_tree, src) == NULL)
252   {
253     // add inverse edge
254
255     edge = olsr_malloc(sizeof (struct olsr_spf_vertex), "Dijkstra inverse edge");
256
257     edge->tree_node.data = edge;
258     edge->tree_node.key = &svert->addr;
259
260     edge->dest = svert;
261     edge->etx = etx;
262
263     avl_insert(&dvert->edge_tree, &edge->tree_node, 0);
264   }
265 }
266
267 static void olsr_free_everything(struct avl_tree *vertex_tree)
268 {
269   struct avl_node *vert_node;
270   struct avl_node *edge_node;
271   struct olsr_spf_vertex *vert;
272   struct olsr_spf_edge *edge;
273
274   vert_node = avl_walk_first(vertex_tree);
275
276   // loop through all vertices
277
278   while (vert_node)
279   {
280     vert = vert_node->data;
281     edge_node = avl_walk_first(&vert->edge_tree);
282
283     // loop through all edges of the current vertex
284
285     while (edge_node != NULL)
286     {
287       edge = edge_node->data;
288       edge_node = avl_walk_next(edge_node);
289       free(edge);
290     }
291
292     vert_node = avl_walk_next(vert_node);
293     free(vert);
294   }
295 }
296
297 /*
298  * olsr_spf_extract_best
299  *
300  * return the node with the minimum pathcost.
301  */
302 static struct olsr_spf_vertex *
303 olsr_spf_extract_best (struct avl_tree *tree)
304 {
305   struct avl_node *node;
306
307   node = avl_walk_first(tree);
308
309   return (node ? node->data :  NULL);
310 }
311
312
313 #ifdef DEBUG
314 static char *olsr_etx_to_string(float etx)
315 {
316   static char buff[20];
317
318   if (etx == INFINITE_ETX)
319     return "INF";
320
321   snprintf(buff, 20, "%.6f", etx);
322   return buff;
323 }
324 #endif
325
326
327 /*
328  * olsr_spf_relax
329  *
330  * Explore all edges of a node and add the node
331  * to the candidate tree if the if the aggregate
332  * path cost is better.
333  */
334 static void
335 olsr_spf_relax (struct avl_tree *cand_tree, struct olsr_spf_vertex *vert)
336 {
337   struct olsr_spf_edge *edge;
338   struct avl_node *edge_node;
339   float new_etx;
340
341 #ifdef DEBUG
342   OLSR_PRINTF(1, "SPF: exploring node %s, cost %f\n",
343               olsr_ip_to_string(&(vert->addr)),
344               vert->path_etx);
345 #endif
346
347   edge_node = avl_walk_first(&vert->edge_tree);
348
349   // loop through all edges of this vertex
350
351   while (edge_node != NULL)
352   {
353     edge = edge_node->data;
354
355     // total quality of the path through this vertex to the
356     // destination of this edge
357
358     new_etx = vert->path_etx + edge->etx;
359
360     // if it's better than the current path quality of this
361     // edge's destination, then we've found a better path to
362     // this destination
363
364     if (new_etx < edge->dest->path_etx)
365     {
366       /* if this node has been on the candidate tree delete it */
367       if (edge->dest->path_etx != INFINITE_ETX) {
368         olsr_spf_del_cand_tree(cand_tree, edge->dest);
369       }
370
371       /* re-insert on candidate tree with the better metric */
372       edge->dest->path_etx = new_etx;
373       olsr_spf_add_cand_tree(cand_tree, edge->dest);
374
375       /* pull-up the next-hop and bump the hop count */
376       if (vert->next_hop) {
377         edge->dest->next_hop = vert->next_hop;
378       }
379       edge->dest->hops = vert->hops + 1;
380
381 #ifdef DEBUG
382       OLSR_PRINTF(1, "SPF:   better path to %s, cost %s -> %s, via %s, hops %u\n",
383                   olsr_ip_to_string(&(edge->dest->addr)),
384                   olsr_etx_to_string(edge->dest->path_etx),
385                   olsr_etx_to_string(new_etx),
386                   olsr_ip_to_string(vert->next_hop),
387                   edge->dest->hops);
388 #endif
389
390     }
391
392     edge_node = avl_walk_next(edge_node);
393   }
394 }
395
396 /*
397  * olsr_spf_run_full
398  *
399  * Run the Dijkstra algorithm.
400  * 
401  * We are using two trees: the candidate and the path tree.
402  * A node gets added to the candidate tree when one of its edges has
403  * an overall better root path cost than the node itself.
404  * The node with the shortest metric gets moved from the candidate to
405  * the path tree every pass.
406  * The SPF computation is completed when there are no more nodes
407  * on the candidate tree. 
408  */ 
409 static void
410 olsr_spf_run_full (struct avl_tree *cand_tree, struct avl_tree *path_tree)
411 {
412   struct olsr_spf_vertex *vert;
413
414   while ((vert = olsr_spf_extract_best(cand_tree))) {
415
416     olsr_spf_relax(cand_tree, vert);
417
418     /*
419      * move the best path from the candidate tree
420      * to the path tree.
421      */
422     olsr_spf_del_cand_tree(cand_tree, vert);
423     olsr_spf_add_path_tree(path_tree, vert);
424   }
425 }
426
427 void
428 olsr_calculate_lq_routing_table (void)
429 {
430   struct avl_tree vertex_tree, cand_tree, path_tree;
431   struct avl_node *tree_node;
432   int i;
433   struct tc_entry *tcsrc;
434   struct topo_dst *tcdst;
435   struct olsr_spf_vertex *vert, *myself;
436   struct link_entry *link;
437   struct neighbor_entry *neigh;
438   struct mid_address *mid_walker;
439   float etx;
440   struct hna_entry *hna_gw;
441   struct hna_net *hna;
442   struct rt_entry *gw_rt, *hna_rt, *head_rt;
443   struct neighbor_2_entry *neigh2;
444 #if 0
445   struct neighbor_list_entry *neigh_walker;
446 #endif
447   struct interface *inter;
448
449   if (olsr_cnf->ipsize != 4)
450     avl_comp_default = avl_comp_ipv6;
451
452   // initialize the graph
453
454   avl_init(&vertex_tree, avl_comp_default);
455   avl_init(&cand_tree, avl_comp_etx);
456   avl_init(&path_tree, avl_comp_etx);
457
458   // add ourselves to the vertex and candidate tree
459
460   myself = olsr_spf_add_vertex(&vertex_tree, &olsr_cnf->main_addr, ZERO_ETX);
461   olsr_spf_add_cand_tree(&cand_tree, myself);
462
463   /*
464    * Add our neighbours.
465    */
466   for (i = 0; i < HASHSIZE; i++)
467     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
468          neigh = neigh->next) {
469       if (neigh->status == SYM) {
470
471         vert = olsr_spf_add_vertex(&vertex_tree, &neigh->neighbor_main_addr,
472                                    INFINITE_ETX);
473
474         /*
475          * Set the next-hop pointer to ourselves.
476          * During olsr_spf_relax() the next_hop pointer will be
477          * pulled up to the new candidate node.
478          * At the End of the SPF computation every reachable node has
479          * a pointer to its corresponding first hop router.
480          */
481         vert->next_hop = &vert->addr;
482
483         /*
484          * one hop neighbors are just one hop away.
485          */
486         vert->hops = 1;
487       }
488     }
489
490   // add our two-hop neighbours
491
492   for (i = 0; i < HASHSIZE; i++)
493     for (neigh2 = two_hop_neighbortable[i].next;
494          neigh2 != &two_hop_neighbortable[i];
495          neigh2 = neigh2->next) {
496
497       vert = olsr_spf_add_vertex(&vertex_tree, &neigh2->neighbor_2_addr,
498                                  INFINITE_ETX);
499
500       /*
501        * two hop neighbors are two hops away.
502        */
503       vert->hops = 2;
504     }
505   // add remaining vertices
506
507   for (i = 0; i < HASHSIZE; i++)
508     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
509     {
510       // add source
511
512       olsr_spf_add_vertex(&vertex_tree, &tcsrc->T_last_addr, INFINITE_ETX);
513
514       // add destinations of this source
515
516       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
517            tcdst = tcdst->next)
518         olsr_spf_add_vertex(&vertex_tree, &tcdst->T_dest_addr, INFINITE_ETX);
519     }
520
521   // add edges to and from our neighbours
522
523   for (i = 0; i < HASHSIZE; i++)
524     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
525          neigh = neigh->next)
526       if (neigh->status == SYM)
527       {
528         link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
529
530         if(!link)
531           continue;
532
533         if (link->loss_link_quality2 >= MIN_LINK_QUALITY &&
534             link->neigh_link_quality2 >= MIN_LINK_QUALITY)
535           {
536             etx = 1.0 / (link->loss_link_quality2 * link->neigh_link_quality2);
537
538             olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr, &olsr_cnf->main_addr, etx);
539           }
540       }
541
542 // we now rely solely on TC messages for routes to our two-hop neighbours
543
544 #if 0
545
546   // add edges between our neighbours and our two-hop neighbours
547
548   for (i = 0; i < HASHSIZE; i++)
549     for (neigh2 = two_hop_neighbortable[i].next;
550          neigh2 != &two_hop_neighbortable[i];
551          neigh2 = neigh2->next)
552       for (neigh_walker = neigh2->neighbor_2_nblist.next;
553            neigh_walker != &neigh2->neighbor_2_nblist;
554            neigh_walker = neigh_walker->next)
555       {
556         if (neigh_walker->second_hop_link_quality >=
557             MIN_LINK_QUALITY * MIN_LINK_QUALITY)
558         {
559           neigh = neigh_walker->neighbor;
560
561           etx = 1.0 / neigh_walker->second_hop_link_quality;
562
563           olsr_spf_add_edge(&vertex_tree, &neigh2->neighbor_2_addr,
564                    &neigh->neighbor_main_addr, etx);
565         }
566       }
567
568 #endif
569
570   // add remaining edges
571
572   for (i = 0; i < HASHSIZE; i++)
573     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
574       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
575            tcdst = tcdst->next)
576       {
577         if (tcdst->link_quality >= MIN_LINK_QUALITY &&
578             tcdst->inverse_link_quality >= MIN_LINK_QUALITY)
579           {
580             etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
581
582             olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
583                      etx);
584           }
585       }
586
587   /*
588    * Run the SPF calculation.
589    */
590   olsr_spf_run_full(&cand_tree, &path_tree);
591
592   // save the old routing table
593
594   olsr_move_route_table(routingtable, old_routes);
595
596   OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
597               nowtm->tm_hour,
598               nowtm->tm_min,
599               nowtm->tm_sec,
600               (int)now.tv_usec/10000);
601
602   /*
603    * In the path tree we have all the reachable nodes
604    * in our topology sorted by etx metric.
605    */
606   for (tree_node = avl_walk_first(&path_tree);
607        tree_node != NULL;
608        tree_node = avl_walk_next(tree_node)) {
609
610     vert = tree_node->data;
611
612     if (!vert->next_hop) {
613       OLSR_PRINTF(2, "%s no next-hop\n", olsr_ip_to_string(&vert->addr));
614       continue;
615     }
616
617     // find the best link to the one-hop neighbour
618
619     link = get_best_link_to_neighbor(vert->next_hop);
620
621     // we may see NULL here, if the one-hop neighbour is not in the
622     // link and neighbour sets any longer, but we have derived an edge
623     // between us and the one-hop neighbour from the TC set
624
625     if (link != NULL)
626     {
627       // find the interface for the found link
628       inter = link->if_name ? if_ifwithname(link->if_name) : 
629               if_ifwithaddr(&link->local_iface_addr);
630
631       // we may see NULL here if the interface is down, but we have
632       // links that haven't timed out, yet
633
634       if (inter != NULL)
635       {
636         // XXX - fix me: structurally prevent duplicates, don't test via
637         //       olsr_lookup_routing_table()
638
639         // route addition, case A - add a route to the main address of the
640         // destination node
641
642         if (olsr_lookup_routing_table(&vert->addr) == NULL)
643           olsr_insert_routing_table(&vert->addr, &link->neighbor_iface_addr,
644                                     inter, vert->hops, vert->path_etx);
645
646         // route addition, case B - add routes to the remaining interfaces
647         // of the destination node
648
649         for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
650              mid_walker = mid_walker->next_alias)
651           if (olsr_lookup_routing_table(&mid_walker->alias) == NULL)
652             olsr_insert_routing_table(&mid_walker->alias,
653                                       &link->neighbor_iface_addr, inter, vert->hops, 
654                                       vert->path_etx);
655
656         // XXX - we used to use olsr_lookup_routing_table() only here, but
657         //       this assumed that case A or case B had already happened for
658         //       this destination; if case A or case B happened after case C
659         //       for the same destination, we had duplicates, as cases A and
660         //       B would not test whether case C had already happened
661
662         // route addition, case C - make sure that we have a route to the
663         // router - e.g. in case the router's not the main address and it's
664         // MID entry has timed out
665
666         if (olsr_lookup_routing_table(&link->neighbor_iface_addr) == NULL)
667           olsr_insert_routing_table(&link->neighbor_iface_addr,
668                                     &link->neighbor_iface_addr, inter, 1,
669                                     vert->path_etx);
670       }
671     }
672   }
673
674   // save the old HNA routing table
675
676   olsr_move_route_table(hna_routes, old_hna);
677
678   // add HNA routes
679
680   /*
681    * In the path tree we have all the reachable nodes
682    * in our topology sorted by etx metric.
683    */
684   for (tree_node = avl_walk_first(&path_tree);
685        tree_node;
686        tree_node = avl_walk_next(tree_node)) {
687
688     if (!(vert = tree_node->data)) {
689       break;
690     }
691
692     // find the node's HNAs
693
694     hna_gw = olsr_lookup_hna_gw(&vert->addr);
695
696     // node doesn't announce any HNAs
697
698     if (hna_gw == NULL)
699       continue;
700
701     // find route to the node
702
703     gw_rt = olsr_lookup_routing_table(&hna_gw->A_gateway_addr);
704
705     // maybe we haven't found a link or an interface for the gateway above
706     // and hence haven't added a route - skip the HNA in this case
707
708     if (gw_rt == NULL)
709       continue;
710
711     // loop through the node's HNAs
712
713     for (hna = hna_gw->networks.next; hna != &hna_gw->networks;
714          hna = hna->next)
715     {
716       // we already have a route via a previous (better) node
717
718       if (olsr_lookup_hna_routing_table(&hna->A_network_addr) != NULL)
719         continue;
720
721       // create route for the HNA
722
723       hna_rt = olsr_malloc(sizeof(struct rt_entry), "LQ HNA route entry");
724
725       // set HNA IP address and netmask
726
727       COPY_IP(&hna_rt->rt_dst, &hna->A_network_addr);
728       hna_rt->rt_mask = hna->A_netmask;
729
730       // copy remaining fields from the node's route
731
732       COPY_IP(&hna_rt->rt_router, &gw_rt->rt_router);
733       hna_rt->rt_metric = gw_rt->rt_metric;
734       hna_rt->rt_etx = gw_rt->rt_etx;
735       hna_rt->rt_if = gw_rt->rt_if;
736
737       // we're not a host route
738
739       hna_rt->rt_flags = RTF_UP | RTF_GATEWAY;
740
741       // find the correct list
742
743       head_rt = &hna_routes[olsr_hashing(&hna->A_network_addr)];
744
745       // enqueue
746
747       head_rt->next->prev = hna_rt;
748       hna_rt->next = head_rt->next;
749
750       head_rt->next = hna_rt;
751       hna_rt->prev = head_rt;
752     }
753   }
754
755   // free the graph
756
757   olsr_free_everything(&vertex_tree);
758
759   // move the route changes into the kernel
760
761   olsr_update_kernel_routes();
762   olsr_update_kernel_hna_routes();
763
764   // free the saved routing table
765
766   olsr_free_routing_table(old_routes);
767   olsr_free_routing_table(old_hna);
768 }
769
770 /*
771  * Local Variables:
772  * c-basic-offset: 2
773  * End:
774  */