cad80d6d4a5e2f88a32b80911ee5f8e03675f45f
[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  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without 
7  * modification, are permitted provided that the following conditions 
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright 
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright 
13  *   notice, this list of conditions and the following disclaimer in 
14  *   the documentation and/or other materials provided with the 
15  *   distribution.
16  * * Neither the name of olsr.org, olsrd nor the names of its 
17  *   contributors may be used to endorse or promote products derived 
18  *   from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
31  * POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Visit http://www.olsr.org for more information.
34  *
35  * If you find this software useful feel free to make a donation
36  * to the project. For more information see the website or contact
37  * the copyright holders.
38  *
39  * $Id: lq_route.c,v 1.12 2004/11/21 11:28:56 kattemat Exp $
40  */
41
42 #if defined USE_LINK_QUALITY
43 #include "defs.h"
44 #include "tc_set.h"
45 #include "neighbor_table.h"
46 #include "link_set.h"
47 #include "routing_table.h"
48 #include "mid_set.h"
49 #include "lq_list.h"
50 #include "lq_route.h"
51
52 #define INFINITE_ETX (1 << 30)
53 #define MIN_LINK_QUALITY 0.0001
54
55 struct dijk_edge
56 {
57   struct list_node node;
58   struct dijk_vertex *dest;
59   int etx;
60 };
61
62 struct dijk_vertex
63 {
64   struct list_node node;
65   union olsr_ip_addr addr;
66   struct list edge_list;
67   int path_etx;
68   struct dijk_vertex *prev;
69   olsr_bool done;
70 };
71
72 // XXX - bad complexity
73
74 static void add_vertex(struct list *vertex_list, union olsr_ip_addr *addr,
75                        int path_etx)
76 {
77   struct list_node *node;
78   struct dijk_vertex *vert;
79
80   // see whether this destination is already in our list
81
82   node = list_get_head(vertex_list);
83
84   while (node != NULL)
85   {
86     vert = node->data;
87
88     if (COMP_IP(&vert->addr, addr))
89       break;
90
91     node = list_get_next(node);
92   }
93
94   // if it's not in our list, add it
95
96   if (node == NULL)
97   {
98     vert = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra vertex");
99
100     vert->node.data = vert;
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     list_init(&vert->edge_list);
109
110     list_add_tail(vertex_list, &vert->node);
111   }
112 }
113
114 // XXX - bad complexity
115
116 static void add_edge(struct list *vertex_list, union olsr_ip_addr *src,
117                      union olsr_ip_addr *dst, int etx)
118 {
119   struct list_node *node;
120   struct dijk_vertex *vert;
121   struct dijk_vertex *svert;
122   struct dijk_vertex *dvert;
123   struct dijk_edge *edge;
124
125   // source and destination lookup
126
127   node = list_get_head(vertex_list);
128
129   svert = NULL;
130   dvert = NULL;
131
132   while (node != NULL)
133   {
134     vert = node->data;
135
136     if (COMP_IP(&vert->addr, src))
137     {
138       svert = vert;
139
140       if (dvert != NULL)
141         break;
142     }
143
144     else if (COMP_IP(&vert->addr, dst))
145     {
146       dvert = vert;
147
148       if (svert != NULL)
149         break;
150     }
151
152     node = list_get_next(node);
153   }
154
155   // source or destination vertex does not exist
156
157   if (svert == NULL || dvert == NULL)
158     return;
159
160   node = list_get_head(&svert->edge_list);
161
162   while (node != NULL)
163   {
164     edge = node->data;
165
166     if (edge->dest == dvert)
167       break;
168
169     node = list_get_next(node);
170   }
171
172   // edge already exists
173
174   if (node != NULL)
175     return;
176
177   edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge");
178
179   edge->node.data = edge;
180
181   edge->dest = dvert;
182   edge->etx = etx;
183
184   list_add_tail(&svert->edge_list, &edge->node);
185 }
186
187 static void free_everything(struct list *vertex_list)
188 {
189   struct list_node *vnode, *enode;
190   struct dijk_vertex *vert;
191   struct dijk_edge *edge;
192
193   vnode = list_get_head(vertex_list);
194
195   // loop through all vertices
196
197   while (vnode != NULL)
198   {
199     vert = vnode->data;
200
201     enode = list_get_head(&vert->edge_list);
202
203     // loop through all edges of the current vertex
204
205     while (enode != NULL)
206     {
207       edge = enode->data;
208
209       enode = list_get_next(enode);
210       free(edge);
211     }
212
213     vnode = list_get_next(vnode);
214     free(vert);
215   }
216 }
217
218 // XXX - bad complexity
219
220 static struct dijk_vertex *extract_best(struct list *vertex_list)
221 {
222   int best_etx = INFINITE_ETX + 1;
223   struct list_node *node;
224   struct dijk_vertex *vert;
225   struct dijk_vertex *res = NULL;
226
227   node = list_get_head(vertex_list);
228
229   // loop through all vertices
230   
231   while (node != NULL)
232   {
233     vert = node->data;
234
235     // see whether the current vertex is better than what we have
236
237     if (!vert->done && vert->path_etx < best_etx)
238     {
239       best_etx = vert->path_etx;
240       res = vert;
241     }
242
243     node = list_get_next(node);
244   }
245
246   // if we've found a vertex, remove it from the set
247
248   if (res != NULL)
249     res->done = OLSR_TRUE;
250
251   return res;
252 }
253
254 static void relax(struct dijk_vertex *vert)
255 {
256   struct dijk_edge *edge;
257   int new_etx;
258   struct list_node *node;
259
260   node = list_get_head(&vert->edge_list);
261
262   // loop through all edges of this vertex
263
264   while (node != NULL)
265   {
266     edge = node->data;
267
268     // total quality of the path through this vertex to the
269     // destination of this edge
270
271     new_etx = vert->path_etx + edge->etx;
272
273     // if it's better than the current path quality of this
274     // edge's destination, then we've found a better path to
275     // this destination
276
277     if (new_etx < edge->dest->path_etx)
278     {
279       edge->dest->path_etx = new_etx;
280       edge->dest->prev = vert;
281     }
282
283     node = list_get_next(node);
284   }
285 }
286
287 static char *etx_to_string(int etx)
288 {
289   static char buff[10];
290
291   if (etx == INFINITE_ETX)
292     return "INF";
293
294   sprintf(buff, "%d", etx);
295   return buff;
296 }
297
298 void olsr_calculate_lq_routing_table(void)
299 {
300   struct list vertex_list;
301   int i;
302   struct tc_entry *tcsrc;
303   struct topo_dst *tcdst;
304   struct dijk_vertex *vert;
305   struct link_entry *link;
306   struct neighbor_entry *neigh;
307   struct list_node *node;
308   struct dijk_vertex *myself;
309   struct dijk_vertex *walker;
310   int hops;
311   struct addresses *mid_walker;
312
313   // initialize the graph
314
315   list_init(&vertex_list);
316
317   // add ourselves to the vertex list
318
319   add_vertex(&vertex_list, &main_addr, 0);
320
321   // add our neighbours
322
323   for (i = 0; i < HASHSIZE; i++)
324     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
325          neigh = neigh->next)
326       if (neigh->status == SYM)
327         add_vertex(&vertex_list, &neigh->neighbor_main_addr, INFINITE_ETX);
328
329   // add remaining vertices
330
331   for (i = 0; i < HASHSIZE; i++)
332     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
333     {
334       // add source
335
336       add_vertex(&vertex_list, &tcsrc->T_last_addr, INFINITE_ETX);
337
338       // add destinations of this source
339
340       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
341            tcdst = tcdst->next)
342         add_vertex(&vertex_list, &tcdst->T_dest_addr, INFINITE_ETX);
343     }
344
345   // add edges to and from our neighbours
346
347   for (i = 0; i < HASHSIZE; i++)
348     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
349          neigh = neigh->next)
350       if (neigh->status == SYM)
351       {
352         link = olsr_neighbor_best_link(&neigh->neighbor_main_addr);
353
354         if (link->neigh_link_quality >= MIN_LINK_QUALITY)
355           add_edge(&vertex_list, &main_addr, &neigh->neighbor_main_addr,
356                    (int)(1.0 / link->neigh_link_quality));
357
358         link = olsr_neighbor_best_inverse_link(&neigh->neighbor_main_addr);
359
360         if (link->loss_link_quality >= MIN_LINK_QUALITY)
361           add_edge(&vertex_list, &neigh->neighbor_main_addr, &main_addr,
362                    (int)(1.0 / link->loss_link_quality));
363       }
364
365   // add remaining edges
366
367   for (i = 0; i < HASHSIZE; i++)
368     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
369       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
370            tcdst = tcdst->next)
371       {
372         if (tcdst->link_quality >= MIN_LINK_QUALITY)
373           add_edge(&vertex_list, &tcsrc->T_last_addr, &tcdst->T_dest_addr,
374                    (int)(1.0 / tcdst->link_quality));
375
376         if (tcdst->inverse_link_quality >= MIN_LINK_QUALITY)
377           add_edge(&vertex_list, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
378                    (int)(1.0 / tcdst->inverse_link_quality));
379       }
380
381   // run Dijkstra's algorithm
382
383   for (;;)
384   {
385     vert = extract_best(&vertex_list);
386
387     if (vert == NULL)
388       break;
389
390     relax(vert);
391   }
392
393   // save the old routing table
394
395   olsr_move_route_table(routingtable, old_routes);
396
397   node = list_get_head(&vertex_list);
398
399   // we're the first vertex in the list
400   
401   myself = node->data;
402
403   olsr_printf(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
404               nowtm->tm_hour,
405               nowtm->tm_min,
406               nowtm->tm_sec,
407               now.tv_usec/10000);
408
409   for (node = list_get_next(node); node != NULL; node = list_get_next(node))
410   {
411     vert = node->data;
412
413     hops = 1;
414
415     // count hops to until the path ends or until we have reached a
416     // one-hop neighbour
417
418     for (walker = vert; walker != NULL && walker->prev != myself;
419          walker = walker->prev)
420     {
421       olsr_printf(2, "%s:%s <- ", olsr_ip_to_string(&walker->addr),
422                   etx_to_string(walker->path_etx));
423       hops++;
424     }
425
426     // if no path to a one-hop neighbour was found, ignore this node
427
428     if (walker != NULL)
429       olsr_printf(2, "%s:%s (one-hop)\n", olsr_ip_to_string(&walker->addr),
430                   etx_to_string(walker->path_etx));
431
432     else
433     {
434       olsr_printf(2, "FAILED\n", olsr_ip_to_string(&vert->addr));
435       continue;
436     }
437
438     // add a route to the main address of the destination node
439
440     olsr_insert_routing_table(&vert->addr, &walker->addr, hops);
441
442     // add routes to the remaining interfaces of the destination node
443
444     for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
445          mid_walker = mid_walker->next)
446       olsr_insert_routing_table(&mid_walker->address, &walker->addr, hops);
447   }
448
449   // free the graph
450
451   free_everything(&vertex_list);
452
453   // move the route changes into the kernel
454
455   olsr_update_kernel_routes();
456
457   // free the saved routing table
458
459   olsr_free_routing_table(old_routes);
460 }
461 #endif