Use real (bi-directional) ETX.
[olsrd.git] / src / tc_set.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
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: tc_set.c,v 1.15 2004/11/28 13:43:59 tlopatic Exp $
40  */
41
42
43 #include "tc_set.h"
44 #include "olsr.h"
45 #include "scheduler.h"
46 #include "lq_route.h"
47
48 /**
49  * Initialize the topology set
50  *
51  */
52
53 int
54 olsr_init_tc()
55 {
56   int index;
57   
58   /* Set timer to zero */
59   send_empty_tc.tv_sec = 0;
60   send_empty_tc.tv_usec = 0;
61
62   changes = OLSR_FALSE;
63
64   olsr_printf(5, "TC: init topo\n");
65
66   olsr_register_timeout_function(&olsr_time_out_tc_set);
67
68   for(index=0;index<HASHSIZE;index++)
69     {
70       tc_table[index].next = &tc_table[index];
71       tc_table[index].prev = &tc_table[index];
72     }
73
74   return 1;
75 }
76
77
78 /**
79  *Delete a TC entry if it has no associated
80  *destinations
81  *
82  *@param entry the TC entry to check and possibly delete
83  *
84  *@return 1 if entry deleted 0 if not
85  */
86
87 int
88 olsr_tc_delete_entry_if_empty(struct tc_entry *entry)
89 {
90
91   //olsr_printf(1, "TC: del entry if empty\n");
92
93   if(entry->destinations.next == &entry->destinations)
94     {
95       /* dequeue */
96       DEQUEUE_ELEM(entry);
97       //entry->prev->next = entry->next;
98       //entry->next->prev = entry->prev;
99       olsr_printf(1, "TC-SET: Deleting empty entry %s ->\n", olsr_ip_to_string(&entry->T_last_addr));
100       free(entry);
101       return 1;
102     }
103   return 0;
104 }
105
106
107
108 /**
109  * Look up a entry from the TC tabe based
110  * on address
111  *
112  *@param adr the address to look for
113  *
114  *@return the entry found or NULL
115  */
116
117 struct tc_entry *
118 olsr_lookup_tc_entry(union olsr_ip_addr *adr)
119 {
120   struct tc_entry *entries;
121   olsr_u32_t hash;
122
123   //olsr_printf(1, "TC: lookup entry\n");
124
125   hash = olsr_hashing(adr);
126
127   for(entries = tc_table[hash].next; 
128       entries != &tc_table[hash]; 
129       entries = entries->next)
130     {
131       //printf("TC lookup checking: %s\n", olsr_ip_to_string(&entries->T_last_addr));
132       if(COMP_IP(adr, &entries->T_last_addr))
133         return entries;
134     }
135
136   return NULL;
137 }
138
139
140 /**
141  *Add a new tc_entry to the tc set
142  *
143  *@param (last)adr address of the entry
144  *
145  *@return a pointer to the created entry
146  */
147
148 struct tc_entry *
149 olsr_add_tc_entry(union olsr_ip_addr *adr)
150 {
151   struct tc_entry *new_entry;
152   olsr_u32_t hash;
153
154   olsr_printf(1, "TC: adding entry %s\n", olsr_ip_to_string(adr));
155
156   hash = olsr_hashing(adr);
157
158   new_entry = olsr_malloc(sizeof(struct tc_entry), "New TC entry");
159
160   /* Fill entry */
161   COPY_IP(&new_entry->T_last_addr, adr);
162   new_entry->destinations.next = &new_entry->destinations;
163   new_entry->destinations.prev = &new_entry->destinations;
164
165   /* Queue entry */
166   QUEUE_ELEM(tc_table[hash], new_entry);
167   /*
168   new_entry->next = tc_table[hash].next;
169   new_entry->prev = tc_table[hash].next->prev;
170   tc_table[hash].next->prev = new_entry;
171   tc_table[hash].next = new_entry;
172   */
173
174   return new_entry;
175 }
176
177
178 /**
179  *Delete all destinations that have a
180  *lower ANSN than the one in the message
181  *
182  *@param entry the entry to delete destenations from
183  *@param msg the message to fetch the ANSN from
184  *
185  *@return 1 if any destinations were deleted 0 if not
186  */
187
188 int
189 olsr_tc_delete_mprs(struct tc_entry *entry, struct tc_message *msg)
190 {
191   struct topo_dst *tmp_dsts, *dst_to_del;
192   int retval;
193
194   //olsr_printf(5, "TC: deleting MPRS\n");
195
196   tmp_dsts = entry->destinations.next;
197   retval = 0;
198
199   while(tmp_dsts != &entry->destinations)
200     {
201       if(SEQNO_GREATER_THAN(msg->ansn, tmp_dsts->T_seq))
202         {
203           /* Delete entry */
204           dst_to_del = tmp_dsts;
205           tmp_dsts = tmp_dsts->next;
206
207           /* dequeue */
208           DEQUEUE_ELEM(dst_to_del);
209
210           free(dst_to_del);
211           retval = 1;
212         }
213       else
214         tmp_dsts = tmp_dsts->next;
215
216     }
217
218   return retval;
219 }
220
221
222 /**
223  *Update the destinations registered on an entry.
224  *Creates new dest-entries if not registered.
225  *Bases update on a receivied TC message
226  *
227  *@param entry the TC entry to check
228  *@msg the TC message to update by
229  *
230  *@return 1 if entries are added 0 if not
231  */
232
233 int
234 olsr_tc_update_mprs(struct tc_entry *entry, struct tc_message *msg)
235 {
236   struct tc_mpr_addr *mprs;
237   struct topo_dst *new_topo_dst, *existing_dst;
238   int retval;
239
240   //olsr_printf(1, "TC: update MPRS\n");
241
242   retval = 0;
243
244
245   mprs = msg->multipoint_relay_selector_address;
246   
247   /* Add all the MPRs */
248
249   while(mprs != NULL)
250     {
251       existing_dst = olsr_tc_lookup_dst(entry, &mprs->address);
252
253       if(existing_dst == NULL)
254         {
255           /* New entry */
256           new_topo_dst = olsr_malloc(sizeof(struct topo_dst), "add TC destination");
257
258           COPY_IP(&new_topo_dst->T_dest_addr, &mprs->address);
259           olsr_get_timestamp((olsr_u32_t) msg->vtime*1000, &new_topo_dst->T_time);
260           new_topo_dst->T_seq = msg->ansn;
261
262 #if defined USE_LINK_QUALITY
263     if (olsr_cnf->lq_level > 0)
264       {
265         new_topo_dst->link_quality = mprs->neigh_link_quality;
266         new_topo_dst->inverse_link_quality = mprs->link_quality;
267
268         new_topo_dst->saved_link_quality = new_topo_dst->link_quality;
269         new_topo_dst->saved_inverse_link_quality =
270           new_topo_dst->inverse_link_quality;
271       }
272 #endif
273
274           /* Add to queue */
275           new_topo_dst->prev = &entry->destinations;
276           new_topo_dst->next = entry->destinations.next;
277           entry->destinations.next->prev = new_topo_dst;
278           entry->destinations.next = new_topo_dst;
279
280           retval = 1;
281         }
282       else
283         {
284           /* Update entry */
285           olsr_get_timestamp((olsr_u32_t) msg->vtime*1000, &existing_dst->T_time);
286           existing_dst->T_seq = msg->ansn;
287
288 #if defined USE_LINK_QUALITY
289           if (olsr_cnf->lq_level > 0)
290             {
291               double saved_lq, rel_lq;
292
293               saved_lq = existing_dst->saved_link_quality;
294
295               if (saved_lq == 0.0)
296                 saved_lq = -1.0;
297
298               existing_dst->link_quality = mprs->neigh_link_quality;
299
300               rel_lq = existing_dst->link_quality / saved_lq;
301
302               if (rel_lq > 1.1 || rel_lq < 0.9)
303                 {
304                   existing_dst->saved_link_quality =
305                     existing_dst->link_quality;
306
307                   retval = 1;
308                 }
309
310               saved_lq = existing_dst->saved_inverse_link_quality;
311
312               if (saved_lq == 0.0)
313                 saved_lq = -1.0;
314
315               existing_dst->inverse_link_quality = mprs->link_quality;
316
317               rel_lq = existing_dst->inverse_link_quality / saved_lq;
318
319               if (rel_lq > 1.1 || rel_lq < 0.9)
320                 {
321                   existing_dst->saved_inverse_link_quality =
322                     existing_dst->inverse_link_quality;
323
324                   retval = 1;
325                 }
326             }
327 #endif
328         }
329
330       mprs = mprs->next;
331     }
332
333   return retval;
334 }
335
336
337
338 /**
339  *Lookup a destination in a TC entry
340  *
341  *@param entry the entry to check
342  *@param dst_addr the destination address to check for
343  *
344  *@return a pointer to the topo_dst found - or NULL
345  */
346 struct topo_dst *
347 olsr_tc_lookup_dst(struct tc_entry *entry, union olsr_ip_addr *dst_addr)
348 {
349   struct topo_dst *dsts;
350   
351   //olsr_printf(1, "TC: lookup dst\n");
352
353   for(dsts = entry->destinations.next; 
354       dsts != &entry->destinations; 
355       dsts = dsts->next)
356     {
357       if(COMP_IP(dst_addr, &dsts->T_dest_addr))
358         return dsts;
359     }
360   return NULL;
361 }
362
363
364
365
366
367
368 /**
369  * Time out entries
370  *
371  *@return nada
372  */
373
374 void
375 olsr_time_out_tc_set()
376 {
377   int index, deleted;
378   struct tc_entry *entry, *entry2;
379   struct topo_dst *dst_entry, *dst_to_delete;
380
381
382   for(index=0;index<HASHSIZE;index++)
383     {
384       /* For all TC entries */
385       entry = tc_table[index].next;
386       while(entry != &tc_table[index])
387         {
388           //printf("INDEX: %d\n", index);
389           /* For all destination entries of that TC entry */
390           deleted = 0;
391           dst_entry = entry->destinations.next;
392           while(dst_entry != &entry->destinations)
393             {
394               /* If timed out - delete */
395               if(TIMED_OUT(&dst_entry->T_time))
396                 {
397                   deleted = 1;
398                   /* Dequeue */
399                   DEQUEUE_ELEM(dst_entry);
400                   //dst_entry->prev->next = dst_entry->next;
401                   //dst_entry->next->prev = dst_entry->prev;
402
403                   dst_to_delete = dst_entry;
404
405                   dst_entry = dst_entry->next;
406
407                   /* Delete */
408                   free(dst_to_delete);
409
410                 }
411               else
412                 dst_entry = dst_entry->next;
413             }
414           /* Delete entry if no destinations */
415           entry2 = entry;
416           entry = entry->next;
417           if(deleted)
418             olsr_tc_delete_entry_if_empty(entry2);
419         }
420     }
421
422   return;
423 }
424
425
426 /**
427  *Print the topology table to stdout
428  */
429 int
430 olsr_print_tc_table()
431 {
432   int i;
433   struct tc_entry *entry;
434   struct topo_dst *dst_entry;
435   char *fstr;
436 #if defined USE_LINK_QUALITY
437   float etx;
438 #endif
439   
440   olsr_printf(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- TOPOLOGY\n\n",
441               nowtm->tm_hour,
442               nowtm->tm_min,
443               nowtm->tm_sec,
444               now.tv_usec / 10000);
445
446   if (olsr_cnf->ip_version == AF_INET)
447   {
448     olsr_printf(1, "Source IP addr   Dest IP addr     LQ     ILQ    ETX\n");
449     fstr = "%-15s  %-15s  %5.3f  %5.3f  %.2f\n";
450   }
451
452   else
453   {
454     olsr_printf(1, "Source IP addr                Dest IP addr                    LQ     ILQ    ETX\n");
455     fstr = "%-30s%-30s  %5.3f  %5.3f  %.2f\n";
456   }
457
458   for (i = 0; i < HASHSIZE; i++)
459   {
460     entry = tc_table[i].next;
461
462     while (entry != &tc_table[i])
463     {
464       dst_entry = entry->destinations.next;
465
466       while(dst_entry != &entry->destinations)
467       {
468 #if defined USE_LINK_QUALITY
469         if (dst_entry->link_quality < MIN_LINK_QUALITY ||
470             dst_entry->inverse_link_quality < MIN_LINK_QUALITY)
471           etx = 0.0;
472
473         else
474           etx = 1.0 / (dst_entry->link_quality *
475                        dst_entry->inverse_link_quality);
476
477         olsr_printf(1, fstr, olsr_ip_to_string(&entry->T_last_addr),
478                     olsr_ip_to_string(&dst_entry->T_dest_addr),
479                     dst_entry->link_quality, dst_entry->inverse_link_quality,
480                     etx);
481 #else
482         olsr_printf(1, fstr, olsr_ip_to_string(&entry->T_last_addr),
483                     olsr_ip_to_string(&dst_entry->T_dest_addr),
484                     0.0, 0.0, 0.0);
485 #endif
486
487         dst_entry = dst_entry->next;
488       }
489
490       entry = entry->next;
491     }
492   }
493
494   return 1;
495 }