Fixed zero link quality problem. Initially, when the link is being
[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.3 2004/11/08 01:29:19 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 "lq_list.h"
32 #include "lq_route.h"
33
34 #define olsr_malloc(x, y) malloc(x)
35
36 struct dijk_edge
37 {
38   struct list_node node;
39   struct dijk_vertex *dest;
40   double link_quality;
41 };
42
43 struct dijk_vertex
44 {
45   struct list_node node;
46   union olsr_ip_addr addr;
47   struct list edge_list;
48   double path_quality;
49   struct dijk_vertex *prev;
50   olsr_bool done;
51 };
52
53 // XXX - bad complexity
54
55 static void add_vertex(struct list *vertex_list, union olsr_ip_addr *addr,
56                        double path_quality)
57 {
58   struct list_node *node;
59   struct dijk_vertex *vert;
60
61   // see whether this destination is already in our list
62
63   node = list_get_head(vertex_list);
64
65   while (node != NULL)
66   {
67     vert = node->data;
68
69     if (COMP_IP(&vert->addr, addr))
70       break;
71
72     node = list_get_next(node);
73   }
74
75   // if it's not in our list, add it
76
77   if (node == NULL)
78   {
79     vert = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra vertex");
80
81     vert->node.data = vert;
82
83     COPY_IP(&vert->addr, addr);
84     
85     vert->path_quality = path_quality;
86     vert->prev = NULL;
87     vert->done = OLSR_FALSE;
88
89     list_init(&vert->edge_list);
90
91     list_add_tail(vertex_list, &vert->node);
92   }
93 }
94
95 // XXX - bad complexity
96
97 static void add_edge(struct list *vertex_list, union olsr_ip_addr *src,
98                      union olsr_ip_addr *dst, double link_quality)
99 {
100   struct list_node *node;
101   struct dijk_vertex *vert;
102   struct dijk_vertex *svert;
103   struct dijk_vertex *dvert;
104   struct dijk_edge *edge;
105
106   // source and destination lookup
107
108   node = list_get_head(vertex_list);
109
110   svert = NULL;
111   dvert = NULL;
112
113   while (node != NULL)
114   {
115     vert = node->data;
116
117     if (COMP_IP(&vert->addr, src))
118     {
119       svert = vert;
120
121       if (dvert != NULL)
122         break;
123     }
124
125     else if (COMP_IP(&vert->addr, dst))
126     {
127       dvert = vert;
128
129       if (svert != NULL)
130         break;
131     }
132
133     node = list_get_next(node);
134   }
135
136   // source or destination vertex does not exist
137
138   if (svert == NULL || dvert == NULL)
139     return;
140
141   node = list_get_head(&svert->edge_list);
142
143   while (node != NULL)
144   {
145     edge = node->data;
146
147     if (edge->dest == dvert)
148       break;
149
150     node = list_get_next(node);
151   }
152
153   // edge already exists
154
155   if (node != NULL)
156     return;
157
158   edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge");
159
160   edge->node.data = edge;
161
162   edge->dest = dvert;
163   edge->link_quality = link_quality;
164
165   list_add_tail(&svert->edge_list, &edge->node);
166 }
167
168 static void free_everything(struct list *vertex_list)
169 {
170   struct list_node *vnode, *enode;
171   struct dijk_vertex *vert;
172   struct dijk_edge *edge;
173
174   vnode = list_get_head(vertex_list);
175
176   // loop through all vertices
177
178   while (vnode != NULL)
179   {
180     vert = vnode->data;
181
182     enode = list_get_head(&vert->edge_list);
183
184     // loop through all edges of the current vertex
185
186     while (enode != NULL)
187     {
188       edge = enode->data;
189
190       enode = list_get_next(enode);
191       free(edge);
192     }
193
194     vnode = list_get_next(vnode);
195     free(vert);
196   }
197 }
198
199 // XXX - bad complexity
200
201 static struct dijk_vertex *extract_best(struct list *vertex_list)
202 {
203   double best = 0.0;
204   struct list_node *node;
205   struct dijk_vertex *vert;
206   struct dijk_vertex *res = NULL;
207
208   node = list_get_head(vertex_list);
209
210   // loop through all vertices
211   
212   while (node != NULL)
213   {
214     vert = node->data;
215
216     // see whether the current vertex is better than what we have
217
218     if (!vert->done && vert->path_quality >= best)
219     {
220       best = vert->path_quality;
221       res = vert;
222     }
223
224     node = list_get_next(node);
225   }
226
227   // if we've found a vertex, remove it from the set
228
229   if (res != NULL)
230     res->done = OLSR_TRUE;
231
232   return res;
233 }
234
235 static void relax(struct dijk_vertex *vert)
236 {
237   struct dijk_edge *edge;
238   double new_quality;
239   struct list_node *node;
240
241   node = list_get_head(&vert->edge_list);
242
243   // loop through all edges of this vertex
244
245   while (node != NULL)
246   {
247     edge = node->data;
248
249     // total quality of the path through this vertex to the
250     // destination of this edge
251
252     new_quality = vert->path_quality * edge->link_quality;
253
254     // if it's better than the current path quality of this
255     // edge's destination, then we've found a better path to
256     // this destination
257
258     if (new_quality >= edge->dest->path_quality)
259     {
260       edge->dest->path_quality = new_quality;
261       edge->dest->prev = vert;
262     }
263
264     node = list_get_next(node);
265   }
266 }
267
268 void olsr_calculate_lq_routing_table(void)
269 {
270   struct list vertex_list;
271   int i;
272   struct tc_entry *tcsrc;
273   struct topo_dst *tcdst;
274   struct dijk_vertex *vert;
275   struct link_entry *link;
276   struct neighbor_entry *neigh;
277   struct list_node *node;
278   struct dijk_vertex *myself;
279   struct dijk_vertex *walker;
280   int hops;
281
282   // initialize the graph
283
284   list_init(&vertex_list);
285
286   // add ourselves to the vertex list
287
288   add_vertex(&vertex_list, &main_addr, 1.0);
289
290   // add our neighbours
291
292   for (i = 0; i < HASHSIZE; i++)
293     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
294          neigh = neigh->next)
295       if (neigh->status == SYM)
296         add_vertex(&vertex_list, &neigh->neighbor_main_addr, 0.0);
297
298   // add remaining vertices
299
300   for (i = 0; i < HASHSIZE; i++)
301     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
302     {
303       // add source
304
305       add_vertex(&vertex_list, &tcsrc->T_last_addr, 0.0);
306
307       // add destinations of this source
308
309       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
310            tcdst = tcdst->next)
311         add_vertex(&vertex_list, &tcdst->T_dest_addr, 0.0);
312     }
313
314   // add edges to and from our neighbours
315
316   for (i = 0; i < HASHSIZE; i++)
317     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
318          neigh = neigh->next)
319       if (neigh->status == SYM)
320       {
321         link = olsr_neighbor_best_link(&neigh->neighbor_main_addr);
322
323         add_edge(&vertex_list, &main_addr, &neigh->neighbor_main_addr,
324                  link->neigh_link_quality);
325
326         link = olsr_neighbor_best_inverse_link(&neigh->neighbor_main_addr);
327
328         add_edge(&vertex_list, &neigh->neighbor_main_addr, &main_addr,
329                  link->loss_link_quality);
330       }
331
332   // add remaining edges
333
334   for (i = 0; i < HASHSIZE; i++)
335     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
336       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
337            tcdst = tcdst->next)
338       {
339         add_edge(&vertex_list, &tcsrc->T_last_addr, &tcdst->T_dest_addr,
340                  tcdst->link_quality);
341
342         add_edge(&vertex_list, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
343                  tcdst->inverse_link_quality);
344       }
345
346   // run Dijkstra's algorithm
347
348   for (;;)
349   {
350     vert = extract_best(&vertex_list);
351
352     if (vert == NULL)
353       break;
354
355     relax(vert);
356   }
357
358   // save the old routing table
359
360   olsr_move_route_table(routingtable, old_routes);
361
362   for (i = 0; i < 2; i++)
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     node = list_get_next(node);
371
372     // loop through the remaining vertices
373
374     while (node != NULL)
375     {
376       vert = node->data;
377
378       // one-hop neighbours go first
379
380       if (i == 0 && vert->prev == myself)
381         olsr_insert_routing_table(&vert->addr, &vert->addr, 1);
382
383       // add everybody else in the second pass
384
385       if (i == 1)
386       {
387         hops = 1;
388         walker = vert;
389
390         // count hops to until a one-hop neighbour is reached
391
392         while (walker->prev != myself)
393         {
394           hops++;
395           walker = walker->prev;
396         }
397
398         // add, if this is not a one-hop neighbour
399
400         if (hops > 1)
401           olsr_insert_routing_table(&vert->addr, &walker->addr, hops);
402       }
403
404       node = list_get_next(node);
405     }
406   }
407
408   // free the graph
409
410   free_everything(&vertex_list);
411
412   // move the route changes into the kernel
413
414   olsr_update_kernel_routes();
415
416   // free the saved routing table
417
418   olsr_free_routing_table(old_routes);
419 }
420 #endif