Create a new ANSN if the detected link loss changes by more than 10
[olsrd.git] / src / lq_route.c
1 /* 
2  * OLSR ad-hoc routing table management protocol
3  * Copyright (C) 2004 Thomas Lopatic (thomas@lopatic.de)
4  *
5  * This file is part of the olsr.org OLSR daemon.
6  *
7  * olsr.org is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * olsr.org is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with olsr.org; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20  *
21  * $Id: lq_route.c,v 1.5 2004/11/10 14:07:48 tlopatic Exp $
22  *
23  */
24
25 #if defined USE_LINK_QUALITY
26 #include "defs.h"
27 #include "tc_set.h"
28 #include "neighbor_table.h"
29 #include "link_set.h"
30 #include "routing_table.h"
31 #include "mid_set.h"
32 #include "lq_list.h"
33 #include "lq_route.h"
34
35 #define olsr_malloc(x, y) malloc(x)
36
37 struct dijk_edge
38 {
39   struct list_node node;
40   struct dijk_vertex *dest;
41   double link_quality;
42 };
43
44 struct dijk_vertex
45 {
46   struct list_node node;
47   union olsr_ip_addr addr;
48   struct list edge_list;
49   double path_quality;
50   struct dijk_vertex *prev;
51   olsr_bool done;
52 };
53
54 // XXX - bad complexity
55
56 static void add_vertex(struct list *vertex_list, union olsr_ip_addr *addr,
57                        double path_quality)
58 {
59   struct list_node *node;
60   struct dijk_vertex *vert;
61
62   // see whether this destination is already in our list
63
64   node = list_get_head(vertex_list);
65
66   while (node != NULL)
67   {
68     vert = node->data;
69
70     if (COMP_IP(&vert->addr, addr))
71       break;
72
73     node = list_get_next(node);
74   }
75
76   // if it's not in our list, add it
77
78   if (node == NULL)
79   {
80     vert = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra vertex");
81
82     vert->node.data = vert;
83
84     COPY_IP(&vert->addr, addr);
85     
86     vert->path_quality = path_quality;
87     vert->prev = NULL;
88     vert->done = OLSR_FALSE;
89
90     list_init(&vert->edge_list);
91
92     list_add_tail(vertex_list, &vert->node);
93   }
94 }
95
96 // XXX - bad complexity
97
98 static void add_edge(struct list *vertex_list, union olsr_ip_addr *src,
99                      union olsr_ip_addr *dst, double link_quality)
100 {
101   struct list_node *node;
102   struct dijk_vertex *vert;
103   struct dijk_vertex *svert;
104   struct dijk_vertex *dvert;
105   struct dijk_edge *edge;
106
107   // source and destination lookup
108
109   node = list_get_head(vertex_list);
110
111   svert = NULL;
112   dvert = NULL;
113
114   while (node != NULL)
115   {
116     vert = node->data;
117
118     if (COMP_IP(&vert->addr, src))
119     {
120       svert = vert;
121
122       if (dvert != NULL)
123         break;
124     }
125
126     else if (COMP_IP(&vert->addr, dst))
127     {
128       dvert = vert;
129
130       if (svert != NULL)
131         break;
132     }
133
134     node = list_get_next(node);
135   }
136
137   // source or destination vertex does not exist
138
139   if (svert == NULL || dvert == NULL)
140     return;
141
142   node = list_get_head(&svert->edge_list);
143
144   while (node != NULL)
145   {
146     edge = node->data;
147
148     if (edge->dest == dvert)
149       break;
150
151     node = list_get_next(node);
152   }
153
154   // edge already exists
155
156   if (node != NULL)
157     return;
158
159   edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge");
160
161   edge->node.data = edge;
162
163   edge->dest = dvert;
164   edge->link_quality = link_quality;
165
166   list_add_tail(&svert->edge_list, &edge->node);
167 }
168
169 static void free_everything(struct list *vertex_list)
170 {
171   struct list_node *vnode, *enode;
172   struct dijk_vertex *vert;
173   struct dijk_edge *edge;
174
175   vnode = list_get_head(vertex_list);
176
177   // loop through all vertices
178
179   while (vnode != NULL)
180   {
181     vert = vnode->data;
182
183     enode = list_get_head(&vert->edge_list);
184
185     // loop through all edges of the current vertex
186
187     while (enode != NULL)
188     {
189       edge = enode->data;
190
191       enode = list_get_next(enode);
192       free(edge);
193     }
194
195     vnode = list_get_next(vnode);
196     free(vert);
197   }
198 }
199
200 // XXX - bad complexity
201
202 static struct dijk_vertex *extract_best(struct list *vertex_list)
203 {
204   double best = 0.0;
205   struct list_node *node;
206   struct dijk_vertex *vert;
207   struct dijk_vertex *res = NULL;
208
209   node = list_get_head(vertex_list);
210
211   // loop through all vertices
212   
213   while (node != NULL)
214   {
215     vert = node->data;
216
217     // see whether the current vertex is better than what we have
218
219     if (!vert->done && vert->path_quality >= best)
220     {
221       best = vert->path_quality;
222       res = vert;
223     }
224
225     node = list_get_next(node);
226   }
227
228   // if we've found a vertex, remove it from the set
229
230   if (res != NULL)
231     res->done = OLSR_TRUE;
232
233   return res;
234 }
235
236 static void relax(struct dijk_vertex *vert)
237 {
238   struct dijk_edge *edge;
239   double new_quality;
240   struct list_node *node;
241
242   node = list_get_head(&vert->edge_list);
243
244   // loop through all edges of this vertex
245
246   while (node != NULL)
247   {
248     edge = node->data;
249
250     // total quality of the path through this vertex to the
251     // destination of this edge
252
253     new_quality = vert->path_quality * edge->link_quality;
254
255     // if it's better than the current path quality of this
256     // edge's destination, then we've found a better path to
257     // this destination
258
259     if (new_quality > edge->dest->path_quality)
260     {
261       edge->dest->path_quality = new_quality;
262       edge->dest->prev = vert;
263     }
264
265     node = list_get_next(node);
266   }
267 }
268
269 void olsr_calculate_lq_routing_table(void)
270 {
271   struct list vertex_list;
272   int i;
273   struct tc_entry *tcsrc;
274   struct topo_dst *tcdst;
275   struct dijk_vertex *vert;
276   struct link_entry *link;
277   struct neighbor_entry *neigh;
278   struct list_node *node;
279   struct dijk_vertex *myself;
280   struct dijk_vertex *walker;
281   int hops;
282   struct addresses *mid_walker;
283
284   // initialize the graph
285
286   list_init(&vertex_list);
287
288   // add ourselves to the vertex list
289
290   add_vertex(&vertex_list, &main_addr, 1.0);
291
292   // add our neighbours
293
294   for (i = 0; i < HASHSIZE; i++)
295     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
296          neigh = neigh->next)
297       if (neigh->status == SYM)
298         add_vertex(&vertex_list, &neigh->neighbor_main_addr, -1.0);
299
300   // add remaining vertices
301
302   for (i = 0; i < HASHSIZE; i++)
303     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
304     {
305       // add source
306
307       add_vertex(&vertex_list, &tcsrc->T_last_addr, -1.0);
308
309       // add destinations of this source
310
311       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
312            tcdst = tcdst->next)
313         add_vertex(&vertex_list, &tcdst->T_dest_addr, -1.0);
314     }
315
316   // add edges to and from our neighbours
317
318   for (i = 0; i < HASHSIZE; i++)
319     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
320          neigh = neigh->next)
321       if (neigh->status == SYM)
322       {
323         link = olsr_neighbor_best_link(&neigh->neighbor_main_addr);
324
325         add_edge(&vertex_list, &main_addr, &neigh->neighbor_main_addr,
326                  link->neigh_link_quality);
327
328         link = olsr_neighbor_best_inverse_link(&neigh->neighbor_main_addr);
329
330         add_edge(&vertex_list, &neigh->neighbor_main_addr, &main_addr,
331                  link->loss_link_quality);
332       }
333
334   // add remaining edges
335
336   for (i = 0; i < HASHSIZE; i++)
337     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
338       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
339            tcdst = tcdst->next)
340       {
341         add_edge(&vertex_list, &tcsrc->T_last_addr, &tcdst->T_dest_addr,
342                  tcdst->link_quality);
343
344         add_edge(&vertex_list, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
345                  tcdst->inverse_link_quality);
346       }
347
348   // run Dijkstra's algorithm
349
350   for (;;)
351   {
352     vert = extract_best(&vertex_list);
353
354     if (vert == NULL)
355       break;
356
357     relax(vert);
358   }
359
360   // save the old routing table
361
362   olsr_move_route_table(routingtable, old_routes);
363
364   node = list_get_head(&vertex_list);
365
366   // we're the first vertex in the list
367   
368   myself = node->data;
369
370   for (node = list_get_next(node); node != NULL; node = list_get_next(node))
371   {
372     vert = node->data;
373
374     hops = 1;
375
376     // count hops to until we have reached a one-hop neighbour
377
378     for (walker = vert; walker->prev != myself; walker = walker->prev)
379       hops++;
380
381     // add a route to the main address of the destination node
382
383     olsr_insert_routing_table(&vert->addr, &walker->addr, hops);
384
385     // add routes to the remaining interfaces of the destination node
386
387     for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
388          mid_walker = mid_walker->next)
389       olsr_insert_routing_table(&mid_walker->address, &walker->addr, hops);
390   }
391
392   // free the graph
393
394   free_everything(&vertex_list);
395
396   // move the route changes into the kernel
397
398   olsr_update_kernel_routes();
399
400   // free the saved routing table
401
402   olsr_free_routing_table(old_routes);
403 }
404 #endif