* applied rt-refactoring-6.diff 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.49 2007/09/05 16:11:10 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 list_node path_list_node; /* SPF result list */
69   union olsr_ip_addr addr;
70   struct avl_tree edge_tree;
71   struct link_entry *next_hop; /* the link to the 1st hop neighbor */
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_list
141  *
142  * Insert an SPF result at the end of the path list.
143  */
144 static void
145 olsr_spf_add_path_list (struct list_node *head,
146                         int *path_count,
147                         struct olsr_spf_vertex *vert)
148 {
149   vert->path_list_node.data = vert;
150
151 #ifdef DEBUG
152   OLSR_PRINTF(1, "SPF: append 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 ? &vert->next_hop->neighbor_iface_addr : NULL));
156 #endif
157
158   list_add_before(head, &vert->path_list_node);
159   *path_count = *path_count + 1;
160 }
161
162 /*
163  * olsr_spf_add_vertex
164  *
165  * Add a node to the tree of all nodes in the network.
166  */
167 static struct olsr_spf_vertex *
168 olsr_spf_add_vertex (struct avl_tree *vertex_tree,
169                      union olsr_ip_addr *addr, float path_etx)
170 {
171   struct avl_node *node;
172   struct olsr_spf_vertex *vert;
173
174   // see whether this destination is already in our tree
175
176   node = avl_find(vertex_tree, addr);
177
178   if (node) {
179     return node->data;
180   }
181
182   // if it's not in our list, add it
183
184   vert = olsr_malloc(sizeof (struct olsr_spf_vertex), "Dijkstra vertex");
185
186   vert->tree_node.data = vert;
187   vert->tree_node.key = &vert->addr;
188
189   COPY_IP(&vert->addr, addr);
190     
191   vert->path_etx = path_etx;
192   vert->next_hop = NULL;
193   vert->hops = 0;
194
195   avl_init(&vert->edge_tree, avl_comp_default);
196
197   avl_insert(vertex_tree, &vert->tree_node, 0);
198   return vert;
199 }
200
201 static struct olsr_spf_vertex *
202 olsr_spf_add_edge (struct avl_tree *vertex_tree,
203                    union olsr_ip_addr *src, union olsr_ip_addr *dst,
204                    float etx)
205 {
206   struct avl_node *node;
207   struct olsr_spf_vertex *svert;
208   struct olsr_spf_vertex *dvert;
209   struct olsr_spf_edge *edge;
210
211   // source lookup
212
213   node = avl_find(vertex_tree, src);
214
215   // source vertex does not exist
216
217   if (node == NULL)
218     return NULL;
219
220   svert = node->data;
221
222   // destination lookup
223
224   node = avl_find(vertex_tree, dst);
225
226   // destination vertex does not exist
227
228   if (node == NULL)
229     return NULL;
230
231   dvert = node->data;
232
233   // check for existing forward edge
234
235   if (avl_find(&svert->edge_tree, dst) == NULL)
236   {
237     // add forward edge
238
239     edge = olsr_malloc(sizeof (struct olsr_spf_vertex), "Dijkstra forward edge");
240
241     edge->tree_node.data = edge;
242     edge->tree_node.key = &dvert->addr;
243
244     edge->dest = dvert;
245     edge->etx = etx;
246
247     avl_insert(&svert->edge_tree, &edge->tree_node, 0);
248   }
249
250   // check for existing inverse edge
251
252   if (avl_find(&dvert->edge_tree, src) == NULL)
253   {
254     // add inverse edge
255
256     edge = olsr_malloc(sizeof (struct olsr_spf_vertex), "Dijkstra inverse edge");
257
258     edge->tree_node.data = edge;
259     edge->tree_node.key = &svert->addr;
260
261     edge->dest = svert;
262     edge->etx = etx;
263
264     avl_insert(&dvert->edge_tree, &edge->tree_node, 0);
265   }
266
267   return svert;
268 }
269
270 static void olsr_free_everything(struct avl_tree *vertex_tree)
271 {
272   struct avl_node *vert_node;
273   struct avl_node *edge_node;
274   struct olsr_spf_vertex *vert;
275   struct olsr_spf_edge *edge;
276
277   vert_node = avl_walk_first(vertex_tree);
278
279   // loop through all vertices
280
281   while (vert_node)
282   {
283     vert = vert_node->data;
284     edge_node = avl_walk_first(&vert->edge_tree);
285
286     // loop through all edges of the current vertex
287
288     while (edge_node != NULL)
289     {
290       edge = edge_node->data;
291       edge_node = avl_walk_next(edge_node);
292       free(edge);
293     }
294
295     vert_node = avl_walk_next(vert_node);
296     free(vert);
297   }
298 }
299
300 /*
301  * olsr_spf_extract_best
302  *
303  * return the node with the minimum pathcost.
304  */
305 static struct olsr_spf_vertex *
306 olsr_spf_extract_best (struct avl_tree *tree)
307 {
308   struct avl_node *node;
309
310   node = avl_walk_first(tree);
311
312   return (node ? node->data :  NULL);
313 }
314
315
316 #ifdef DEBUG
317 static char *olsr_etx_to_string(float etx)
318 {
319   static char buff[20];
320
321   if (etx == INFINITE_ETX)
322     return "INF";
323
324   snprintf(buff, 20, "%.6f", etx);
325   return buff;
326 }
327 #endif
328
329
330 /*
331  * olsr_spf_relax
332  *
333  * Explore all edges of a node and add the node
334  * to the candidate tree if the if the aggregate
335  * path cost is better.
336  */
337 static void
338 olsr_spf_relax (struct avl_tree *cand_tree, struct olsr_spf_vertex *vert)
339 {
340   struct olsr_spf_edge *edge;
341   struct avl_node *edge_node;
342   float new_etx;
343
344 #ifdef DEBUG
345   OLSR_PRINTF(1, "SPF: exploring node %s, cost %f\n",
346               olsr_ip_to_string(&(vert->addr)),
347               vert->path_etx);
348 #endif
349
350   edge_node = avl_walk_first(&vert->edge_tree);
351
352   // loop through all edges of this vertex
353
354   while (edge_node != NULL)
355   {
356     edge = edge_node->data;
357
358     // total quality of the path through this vertex to the
359     // destination of this edge
360
361     new_etx = vert->path_etx + edge->etx;
362
363     // if it's better than the current path quality of this
364     // edge's destination, then we've found a better path to
365     // this destination
366
367     if (new_etx < edge->dest->path_etx)
368     {
369       /* if this node has been on the candidate tree delete it */
370       if (edge->dest->path_etx != INFINITE_ETX) {
371         olsr_spf_del_cand_tree(cand_tree, edge->dest);
372       }
373
374       /* re-insert on candidate tree with the better metric */
375       edge->dest->path_etx = new_etx;
376       olsr_spf_add_cand_tree(cand_tree, edge->dest);
377
378       /* pull-up the next-hop and bump the hop count */
379       if (vert->next_hop) {
380         edge->dest->next_hop = vert->next_hop;
381       }
382       edge->dest->hops = vert->hops + 1;
383
384 #ifdef DEBUG
385       OLSR_PRINTF(1, "SPF:   better path to %s, cost %s -> %s, via %s, hops %u\n",
386                   olsr_ip_to_string(&(edge->dest->addr)),
387                   olsr_etx_to_string(edge->dest->path_etx),
388                   olsr_etx_to_string(new_etx),
389                   olsr_ip_to_string(vert->next_hop ?
390                                     &vert->next_hop->neighbor_iface_addr : NULL),
391                   edge->dest->hops);
392 #endif
393
394     }
395
396     edge_node = avl_walk_next(edge_node);
397   }
398 }
399
400 /*
401  * olsr_spf_run_full
402  *
403  * Run the Dijkstra algorithm.
404  * 
405  * A node gets added to the candidate tree when one of its edges has
406  * an overall better root path cost than the node itself.
407  * The node with the shortest metric gets moved from the candidate to
408  * the path list every pass.
409  * The SPF computation is completed when there are no more nodes
410  * on the candidate tree. 
411  */ 
412 static void
413 olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
414                    int *path_count)
415 {
416   struct olsr_spf_vertex *vert;
417
418   *path_count = 0;
419
420   while ((vert = olsr_spf_extract_best(cand_tree))) {
421
422     olsr_spf_relax(cand_tree, vert);
423
424     /*
425      * move the best path from the candidate tree
426      * to the path list.
427      */
428     olsr_spf_del_cand_tree(cand_tree, vert);
429     olsr_spf_add_path_list(path_list, path_count, vert);
430   }
431 }
432
433 void
434 olsr_calculate_routing_table (void)
435 {
436   struct avl_tree vertex_tree, cand_tree;
437   struct list_node path_list;
438   int i, plen, max_host_plen, path_count = 0;
439   struct tc_entry *tcsrc;
440   struct topo_dst *tcdst;
441   struct olsr_spf_vertex *vert, *myself;
442   struct neighbor_entry *neigh;
443   struct mid_address *mid_walker;
444   float etx;
445   struct hna_entry *hna_gw;
446   struct hna_net *hna;
447   struct neighbor_2_entry *neigh2;
448   struct interface *inter;
449   struct link_entry *link;
450
451 #ifdef SPF_PROFILING
452   struct timeval t1, t2, t3, t4, t5, t6, spf_init, spf_run, route, kernel, cleanup, total;
453
454   gettimeofday(&t1, NULL);
455 #endif
456
457   max_host_plen = olsr_host_rt_maxplen();
458
459   // initialize the graph
460
461   avl_init(&vertex_tree, avl_comp_default);
462   avl_init(&cand_tree, avl_comp_etx);
463   list_head_init(&path_list);
464
465   olsr_bump_routingtree_version();
466
467   // add ourselves to the vertex and candidate tree
468
469   myself = olsr_spf_add_vertex(&vertex_tree, &olsr_cnf->main_addr, ZERO_ETX);
470   olsr_spf_add_cand_tree(&cand_tree, myself);
471
472   /*
473    * Add our neighbours.
474    */
475   for (i = 0; i < HASHSIZE; i++)
476     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
477          neigh = neigh->next) {
478
479       if (neigh->status != SYM)
480         continue;
481
482       olsr_spf_add_vertex(&vertex_tree, &neigh->neighbor_main_addr, INFINITE_ETX);
483     }
484
485   // add our two-hop neighbours
486
487   for (i = 0; i < HASHSIZE; i++)
488     for (neigh2 = two_hop_neighbortable[i].next;
489          neigh2 != &two_hop_neighbortable[i];
490          neigh2 = neigh2->next) {
491
492       olsr_spf_add_vertex(&vertex_tree, &neigh2->neighbor_2_addr, INFINITE_ETX);
493     }
494   // add remaining vertices
495
496   for (i = 0; i < HASHSIZE; i++)
497     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
498     {
499       // add source
500
501       olsr_spf_add_vertex(&vertex_tree, &tcsrc->T_last_addr, INFINITE_ETX);
502
503       // add destinations of this source
504
505       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
506            tcdst = tcdst->next)
507         olsr_spf_add_vertex(&vertex_tree, &tcdst->T_dest_addr, INFINITE_ETX);
508     }
509
510   // add edges to and from our neighbours
511
512   for (i = 0; i < HASHSIZE; i++)
513     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
514          neigh = neigh->next) {
515
516       if (neigh->status == SYM) {
517
518         link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
519         if (!link) {
520           continue;
521         }
522
523         if (olsr_cnf->lq_level < 2) {
524           /* for non-lq the etx is always 1.0 */
525           vert = olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr,
526                                    &olsr_cnf->main_addr, 1.0 );
527           vert->next_hop = link;
528
529         } else if (link->loss_link_quality2 >= MIN_LINK_QUALITY &&
530                    link->neigh_link_quality2 >= MIN_LINK_QUALITY) {
531             
532           etx = 1.0 / (link->loss_link_quality2 * link->neigh_link_quality2);
533
534           vert = olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr,
535                                      &olsr_cnf->main_addr, etx);
536           vert->next_hop = link;
537         }
538       }
539     }
540
541   /* add remaining edges from TC messages */
542
543   for (i = 0; i < HASHSIZE; i++)
544     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
545       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
546            tcdst = tcdst->next) {
547
548         if (olsr_cnf->lq_level < 2) {
549
550           /* for non-lq the etx is always 1.0 */
551           olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr,
552                             &tcsrc->T_last_addr, 1.0);
553
554         } else if (tcdst->link_quality >= MIN_LINK_QUALITY &&
555                    tcdst->inverse_link_quality >= MIN_LINK_QUALITY) {
556
557           etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
558
559           olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr,
560                             &tcsrc->T_last_addr, etx);
561         }
562       }
563
564 #ifdef SPF_PROFILING
565   gettimeofday(&t2, NULL);
566 #endif
567
568   /*
569    * Run the SPF calculation.
570    */
571   olsr_spf_run_full(&cand_tree, &path_list, &path_count);
572
573   OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
574               nowtm->tm_hour,
575               nowtm->tm_min,
576               nowtm->tm_sec,
577               (int)now.tv_usec/10000);
578
579 #ifdef SPF_PROFILING
580   gettimeofday(&t3, NULL);
581 #endif
582
583   olsr_fill_routing_table_with_neighbors();
584
585   /*
586    * In the path tree we have all the reachable nodes in our topology.
587    */
588   for (; !list_is_empty(&path_list); list_remove(path_list.next)) {
589
590     vert = path_list.next->data;
591     link = vert->next_hop;
592
593     if (!link) {
594       OLSR_PRINTF(2, "%s no next-hop\n", olsr_ip_to_string(&vert->addr));
595       continue;
596     }
597
598     /* find the interface for the found link */
599     inter = link->if_name ? if_ifwithname(link->if_name)
600       : if_ifwithaddr(&link->local_iface_addr);
601
602     /* interface is up ? */
603     if (inter) {
604
605       /* add a route to the main address of the destination node */
606       olsr_insert_routing_table(&vert->addr, max_host_plen, &vert->addr,
607                                 &link->neighbor_iface_addr, inter,
608                                 vert->hops, vert->path_etx);
609
610       /* add routes to the remaining interfaces of the destination node */
611       for (mid_walker = mid_lookup_aliases(&vert->addr);
612            mid_walker != NULL;
613            mid_walker = mid_walker->next_alias) {
614
615         olsr_insert_routing_table(&mid_walker->alias, max_host_plen, &vert->addr,
616                                   &link->neighbor_iface_addr, inter,
617                                   vert->hops, vert->path_etx);
618       }
619
620       /* find the node's HNAs */
621       hna_gw = olsr_lookup_hna_gw(&vert->addr);
622
623       /* node doesn't announce any HNAs */
624       if (!hna_gw) {
625         continue;
626       }
627
628       /* loop through the node's HNAs */
629       for (hna = hna_gw->networks.next;
630            hna != &hna_gw->networks;
631            hna = hna->next) {
632
633         plen = olsr_get_hna_prefix_len(hna);
634         if (vert->path_etx != INFINITE_ETX)
635         olsr_insert_routing_table(&hna->A_network_addr, plen, &vert->addr,
636                                   &link->neighbor_iface_addr, inter,
637                                   vert->hops, vert->path_etx);
638       }
639     }
640   }
641
642 #ifdef SPF_PROFILING
643   gettimeofday(&t4, NULL);
644 #endif
645
646   /* move the route changes into the kernel */
647
648   olsr_update_kernel_routes();
649
650 #ifdef SPF_PROFILING
651   gettimeofday(&t5, NULL);
652 #endif
653
654   /* free the SPF graph */
655
656   olsr_free_everything(&vertex_tree);
657
658 #ifdef SPF_PROFILING
659   gettimeofday(&t6, NULL);
660
661   timersub(&t2, &t1, &spf_init);
662   timersub(&t3, &t2, &spf_run);
663   timersub(&t4, &t3, &route);
664   timersub(&t5, &t4, &kernel);
665   timersub(&t6, &t5, &cleanup);
666   timersub(&t6, &t1, &total);
667   olsr_printf(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern/cleanup): %d, %d, %d, %d, %d, %d\n",
668               path_count, routingtree.count,
669               (int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec,
670               (int)route.tv_usec, (int)kernel.tv_usec,  (int)cleanup.tv_usec);
671 #endif
672 }
673
674 /*
675  * Local Variables:
676  * c-basic-offset: 2
677  * End:
678  */