79669336c0a8acf905d57dc4eab20ca3d90aaff5
[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.48 2007/08/02 22:07:19 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 neighbor_entry *neigh;
437   struct mid_address *mid_walker;
438   float etx;
439   struct hna_entry *hna_gw;
440   struct hna_net *hna;
441   struct rt_entry *gw_rt, *hna_rt, *head_rt;
442   struct neighbor_2_entry *neigh2;
443 #if 0
444   struct neighbor_list_entry *neigh_walker;
445 #endif
446   struct interface *inter;
447
448   if (olsr_cnf->ipsize != 4)
449     avl_comp_default = avl_comp_ipv6;
450
451   // initialize the graph
452
453   avl_init(&vertex_tree, avl_comp_default);
454   avl_init(&cand_tree, avl_comp_etx);
455   avl_init(&path_tree, avl_comp_etx);
456
457   // add ourselves to the vertex and candidate tree
458
459   myself = olsr_spf_add_vertex(&vertex_tree, &olsr_cnf->main_addr, ZERO_ETX);
460   olsr_spf_add_cand_tree(&cand_tree, myself);
461
462   /*
463    * Add our neighbours.
464    */
465   for (i = 0; i < HASHSIZE; i++)
466     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
467          neigh = neigh->next) {
468       if (neigh->status == SYM) {
469
470         vert = olsr_spf_add_vertex(&vertex_tree, &neigh->neighbor_main_addr,
471                                    INFINITE_ETX);
472
473         /*
474          * Set the next-hop pointer to ourselves.
475          * During olsr_spf_relax() the next_hop pointer will be
476          * pulled up to the new candidate node.
477          * At the End of the SPF computation every reachable node has
478          * a pointer to its corresponding first hop router.
479          */
480         vert->next_hop = &vert->addr;
481
482         /*
483          * one hop neighbors are just one hop away.
484          */
485         vert->hops = 1;
486       }
487     }
488
489   // add our two-hop neighbours
490
491   for (i = 0; i < HASHSIZE; i++)
492     for (neigh2 = two_hop_neighbortable[i].next;
493          neigh2 != &two_hop_neighbortable[i];
494          neigh2 = neigh2->next) {
495
496       vert = olsr_spf_add_vertex(&vertex_tree, &neigh2->neighbor_2_addr,
497                                  INFINITE_ETX);
498
499       /*
500        * two hop neighbors are two hops away.
501        */
502       vert->hops = 2;
503     }
504   // add remaining vertices
505
506   for (i = 0; i < HASHSIZE; i++)
507     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
508     {
509       // add source
510
511       olsr_spf_add_vertex(&vertex_tree, &tcsrc->T_last_addr, INFINITE_ETX);
512
513       // add destinations of this source
514
515       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
516            tcdst = tcdst->next)
517         olsr_spf_add_vertex(&vertex_tree, &tcdst->T_dest_addr, INFINITE_ETX);
518     }
519
520   // add edges to and from our neighbours
521
522   for (i = 0; i < HASHSIZE; i++)
523     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
524          neigh = neigh->next)
525       if (neigh->status == SYM)
526       {
527         struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
528
529         if(!lnk)
530           continue;
531
532         if (lnk->loss_link_quality2 >= MIN_LINK_QUALITY &&
533             lnk->neigh_link_quality2 >= MIN_LINK_QUALITY)
534           {
535             etx = 1.0 / (lnk->loss_link_quality2 * lnk->neigh_link_quality2);
536
537             olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr, &olsr_cnf->main_addr, etx);
538           }
539       }
540
541 // we now rely solely on TC messages for routes to our two-hop neighbours
542
543 #if 0
544
545   // add edges between our neighbours and our two-hop neighbours
546
547   for (i = 0; i < HASHSIZE; i++)
548     for (neigh2 = two_hop_neighbortable[i].next;
549          neigh2 != &two_hop_neighbortable[i];
550          neigh2 = neigh2->next)
551       for (neigh_walker = neigh2->neighbor_2_nblist.next;
552            neigh_walker != &neigh2->neighbor_2_nblist;
553            neigh_walker = neigh_walker->next)
554       {
555         if (neigh_walker->second_hop_link_quality >=
556             MIN_LINK_QUALITY * MIN_LINK_QUALITY)
557         {
558           neigh = neigh_walker->neighbor;
559
560           etx = 1.0 / neigh_walker->second_hop_link_quality;
561
562           olsr_spf_add_edge(&vertex_tree, &neigh2->neighbor_2_addr,
563                    &neigh->neighbor_main_addr, etx);
564         }
565       }
566
567 #endif
568
569   // add remaining edges
570
571   for (i = 0; i < HASHSIZE; i++)
572     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
573       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
574            tcdst = tcdst->next)
575       {
576         if (tcdst->link_quality >= MIN_LINK_QUALITY &&
577             tcdst->inverse_link_quality >= MIN_LINK_QUALITY)
578           {
579             etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
580
581             olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
582                      etx);
583           }
584       }
585
586   /*
587    * Run the SPF calculation.
588    */
589   olsr_spf_run_full(&cand_tree, &path_tree);
590
591   // save the old routing table
592
593   olsr_move_route_table(routingtable, old_routes);
594
595   OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
596               nowtm->tm_hour,
597               nowtm->tm_min,
598               nowtm->tm_sec,
599               (int)now.tv_usec/10000);
600
601   /*
602    * In the path tree we have all the reachable nodes
603    * in our topology sorted by etx metric.
604    */
605   for (tree_node = avl_walk_first(&path_tree);
606        tree_node != NULL;
607        tree_node = avl_walk_next(tree_node)) {
608     struct link_entry *lnk;
609     vert = tree_node->data;
610
611     if (!vert->next_hop) {
612       OLSR_PRINTF(2, "%s no next-hop\n", olsr_ip_to_string(&vert->addr));
613       continue;
614     }
615
616     // find the best link to the one-hop neighbour
617
618     lnk = get_best_link_to_neighbor(vert->next_hop);
619
620     // we may see NULL here, if the one-hop neighbour is not in the
621     // link and neighbour sets any longer, but we have derived an edge
622     // between us and the one-hop neighbour from the TC set
623
624     if (lnk != NULL)
625     {
626       // find the interface for the found link
627       inter = lnk->if_name ? if_ifwithname(lnk->if_name) : 
628               if_ifwithaddr(&lnk->local_iface_addr);
629
630       // we may see NULL here if the interface is down, but we have
631       // links that haven't timed out, yet
632
633       if (inter != NULL)
634       {
635         // XXX - fix me: structurally prevent duplicates, don't test via
636         //       olsr_lookup_routing_table()
637
638         // route addition, case A - add a route to the main address of the
639         // destination node
640
641         if (olsr_lookup_routing_table(&vert->addr) == NULL)
642           olsr_insert_routing_table(&vert->addr, &lnk->neighbor_iface_addr,
643                                     inter, vert->hops, vert->path_etx);
644
645         // route addition, case B - add routes to the remaining interfaces
646         // of the destination node
647
648         for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
649              mid_walker = mid_walker->next_alias)
650           if (olsr_lookup_routing_table(&mid_walker->alias) == NULL)
651             olsr_insert_routing_table(&mid_walker->alias,
652                                       &lnk->neighbor_iface_addr, inter, vert->hops, 
653                                       vert->path_etx);
654
655         // XXX - we used to use olsr_lookup_routing_table() only here, but
656         //       this assumed that case A or case B had already happened for
657         //       this destination; if case A or case B happened after case C
658         //       for the same destination, we had duplicates, as cases A and
659         //       B would not test whether case C had already happened
660
661         // route addition, case C - make sure that we have a route to the
662         // router - e.g. in case the router's not the main address and it's
663         // MID entry has timed out
664
665         if (olsr_lookup_routing_table(&lnk->neighbor_iface_addr) == NULL)
666           olsr_insert_routing_table(&lnk->neighbor_iface_addr,
667                                     &lnk->neighbor_iface_addr, inter, 1,
668                                     vert->path_etx);
669       }
670     }
671   }
672
673   // save the old HNA routing table
674
675   olsr_move_route_table(hna_routes, old_hna);
676
677   // add HNA routes
678
679   /*
680    * In the path tree we have all the reachable nodes
681    * in our topology sorted by etx metric.
682    */
683   for (tree_node = avl_walk_first(&path_tree);
684        tree_node;
685        tree_node = avl_walk_next(tree_node)) {
686
687     if (!(vert = tree_node->data)) {
688       break;
689     }
690
691     // find the node's HNAs
692
693     hna_gw = olsr_lookup_hna_gw(&vert->addr);
694
695     // node doesn't announce any HNAs
696
697     if (hna_gw == NULL)
698       continue;
699
700     // find route to the node
701
702     gw_rt = olsr_lookup_routing_table(&hna_gw->A_gateway_addr);
703
704     // maybe we haven't found a link or an interface for the gateway above
705     // and hence haven't added a route - skip the HNA in this case
706
707     if (gw_rt == NULL)
708       continue;
709
710     // loop through the node's HNAs
711
712     for (hna = hna_gw->networks.next; hna != &hna_gw->networks;
713          hna = hna->next)
714     {
715       // we already have a route via a previous (better) node
716
717       if (olsr_lookup_hna_routing_table(&hna->A_network_addr) != NULL)
718         continue;
719
720       // create route for the HNA
721
722       hna_rt = olsr_malloc(sizeof(struct rt_entry), "LQ HNA route entry");
723
724       // set HNA IP address and netmask
725
726       COPY_IP(&hna_rt->rt_dst, &hna->A_network_addr);
727       hna_rt->rt_mask = hna->A_netmask;
728
729       // copy remaining fields from the node's route
730
731       COPY_IP(&hna_rt->rt_router, &gw_rt->rt_router);
732       hna_rt->rt_metric = gw_rt->rt_metric;
733       hna_rt->rt_etx = gw_rt->rt_etx;
734       hna_rt->rt_if = gw_rt->rt_if;
735
736       // we're not a host route
737
738       hna_rt->rt_flags = RTF_UP | RTF_GATEWAY;
739
740       // find the correct list
741
742       head_rt = &hna_routes[olsr_hashing(&hna->A_network_addr)];
743
744       // enqueue
745
746       head_rt->next->prev = hna_rt;
747       hna_rt->next = head_rt->next;
748
749       head_rt->next = hna_rt;
750       hna_rt->prev = head_rt;
751     }
752   }
753
754   // free the graph
755
756   olsr_free_everything(&vertex_tree);
757
758   // move the route changes into the kernel
759
760   olsr_update_kernel_routes();
761   olsr_update_kernel_hna_routes();
762
763   // free the saved routing table
764
765   olsr_free_routing_table(old_routes);
766   olsr_free_routing_table(old_hna);
767 }
768
769 /*
770  * Local Variables:
771  * c-basic-offset: 2
772  * End:
773  */