New routing metric plugin with sequence number handling.
[olsrd.git] / src / lq_plugin_default_ff.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2008 Henning Rogge <rogge@fgan.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  */
40
41 #include "tc_set.h"
42 #include "link_set.h"
43 #include "lq_plugin.h"
44 #include "olsr_spf.h"
45 #include "lq_packet.h"
46 #include "packet.h"
47 #include "olsr.h"
48 #include "lq_plugin_default_ff.h"
49 #include "parser.h"
50 #include "fpm.h"
51 #include "mid_set.h"
52 #include "scheduler.h"
53
54 /* etx lq plugin (freifunk fpm version) settings */
55 struct lq_handler lq_etx_ff_handler = {
56     &default_lq_initialize_ff,
57     &default_lq_calc_cost_ff,
58     &default_lq_calc_cost_ff,
59
60     &default_lq_is_relevant_costchange_ff,
61     &default_lq_packet_loss_worker_ff,
62     
63     &default_lq_memorize_foreign_hello_ff, 
64     &default_lq_copy_link2tc_ff,
65     &default_lq_clear_ff,
66     &default_lq_clear_ff,
67
68     &default_lq_serialize_hello_lq_pair_ff,
69     &default_lq_serialize_tc_lq_pair_ff,
70     &default_lq_deserialize_hello_lq_pair_ff,
71     &default_lq_deserialize_tc_lq_pair_ff,
72
73     &default_lq_print_ff,
74     &default_lq_print_ff,
75     &default_lq_print_cost_ff,
76
77     sizeof(struct default_lq_ff),
78     sizeof(struct default_lq_ff)
79 };
80
81 static void default_lq_parser_ff(struct olsr *olsr, struct interface *in_if, union olsr_ip_addr *from_addr) {
82   const union olsr_ip_addr *main_addr;
83   struct link_entry *lnk;
84   struct default_lq_ff *lq;
85   olsr_u32_t seq_diff;
86   
87   /* Find main address */
88   if (!(main_addr = mid_lookup_main_addr(from_addr)))
89     main_addr = from_addr;
90   
91   /* Loopup link entry */
92   lnk = lookup_link_entry(main_addr, NULL, in_if);
93   if (lnk == NULL) {
94     return;
95   }
96   
97   lq = (struct default_lq_ff *)lnk->linkquality;
98   
99   if (lq->last_seq_nr > olsr->olsr_seqno) {
100     seq_diff = (olsr_u32_t)olsr->olsr_seqno + 65536 - lq->last_seq_nr;
101   } else {
102     seq_diff = olsr->olsr_seqno - lq->last_seq_nr;
103   }
104   
105   /* Jump in sequence numbers ? */
106   if (seq_diff > 256) {
107     seq_diff = 1;
108   }
109   
110   lq->received[lq->activePtr]++;
111   lq->lost[lq->activePtr] += (seq_diff - 1);
112   
113   lq->last_seq_nr = olsr->olsr_seqno;
114 }
115
116 static void default_lq_ff_timer(void __attribute__((unused)) *context) {
117   struct link_entry *link;
118   OLSR_FOR_ALL_LINK_ENTRIES(link) {
119     struct default_lq_ff *tlq = (struct default_lq_ff *)link->linkquality;
120     fpm ratio;
121     olsr_u16_t i, received, lost;
122
123     received = 0;
124     lost = 0;
125
126     /* enlarge window if still in quickstart phase */
127     if (tlq->windowSize < LQ_FF_WINDOW) {
128       tlq->windowSize++;
129     }
130     for (i=0; i < tlq->windowSize; i++) {
131       received += tlq->received[i];
132       lost += tlq->lost[i];
133     }
134
135     /* calculate link quality */
136     if (received + lost == 0) {
137       tlq->valueLq = 0;
138     }
139     else {
140       // start with link-loss-factor
141       ratio = fpmidiv(itofpm(link->loss_link_multiplier), 65536);
142
143       // calculate received/(received + loss) factor
144       ratio = fpmmuli(ratio, (int)received);
145       ratio = fpmidiv(ratio, (int)(received + lost));
146       ratio = fpmmuli(ratio, 255);
147
148       tlq->valueLq = (olsr_u8_t)(fpmtoi(ratio));
149     }
150     link->linkcost = default_lq_calc_cost_ff(tlq);
151
152     // shift buffer
153     tlq->activePtr = (tlq->activePtr + 1) % LQ_FF_WINDOW;
154     tlq->lost[tlq->activePtr] = 0;
155     tlq->received[tlq->activePtr] = 0;
156   }OLSR_FOR_ALL_LINK_ENTRIES_END(link);
157 }
158
159 void default_lq_initialize_ff(void) {
160   olsr_packetparser_add_function(&default_lq_parser_ff);
161   olsr_start_timer(1000, 0, OLSR_TIMER_PERIODIC, &default_lq_ff_timer, NULL, 0);
162 }
163
164 olsr_linkcost default_lq_calc_cost_ff(const void *ptr) {
165   const struct default_lq_ff *lq = ptr;
166   olsr_linkcost cost;
167   
168   if (lq->valueLq < (unsigned int)(255 * MINIMAL_USEFUL_LQ) || lq->valueNlq < (unsigned int)(255 * MINIMAL_USEFUL_LQ)) {
169     return LINK_COST_BROKEN;
170   }
171   
172   cost = fpmidiv(itofpm(255 * 255), (int)lq->valueLq * (int)lq->valueNlq);
173   
174   if (cost > LINK_COST_BROKEN)
175     return LINK_COST_BROKEN;
176   if (cost == 0)
177     return 1;
178   return cost;
179 }
180
181 int default_lq_serialize_hello_lq_pair_ff(unsigned char *buff, void *ptr) {
182   struct default_lq_ff *lq = ptr;
183   
184   buff[0] = (unsigned char)lq->valueLq;
185   buff[1] = (unsigned char)lq->valueNlq;
186   buff[2] = (unsigned char)(0);
187   buff[3] = (unsigned char)(0);
188   
189   return 4;
190 }
191
192 void default_lq_deserialize_hello_lq_pair_ff(const olsr_u8_t **curr, void *ptr) {
193   struct default_lq_ff *lq = ptr;
194   
195   pkt_get_u8(curr, &lq->valueLq);
196   pkt_get_u8(curr, &lq->valueNlq);
197   pkt_ignore_u16(curr);
198 }
199
200 olsr_bool default_lq_is_relevant_costchange_ff(olsr_linkcost c1, olsr_linkcost c2) {
201   if (c1 > c2) {
202     return c2 - c1 > LQ_PLUGIN_RELEVANT_COSTCHANGE_FF;
203   }
204   return c1 - c2 > LQ_PLUGIN_RELEVANT_COSTCHANGE_FF;
205 }
206
207 int default_lq_serialize_tc_lq_pair_ff(unsigned char *buff, void *ptr) {
208   struct default_lq_ff *lq = ptr;
209   
210   buff[0] = (unsigned char)lq->valueLq;
211   buff[1] = (unsigned char)lq->valueNlq;
212   buff[2] = (unsigned char)(0);
213   buff[3] = (unsigned char)(0);
214   
215   return 4;
216 }
217
218 void default_lq_deserialize_tc_lq_pair_ff(const olsr_u8_t **curr, void *ptr) {
219   struct default_lq_ff *lq = ptr;
220   
221   pkt_get_u8(curr, &lq->valueLq);
222   pkt_get_u8(curr, &lq->valueNlq);
223   pkt_ignore_u16(curr);
224 }
225
226 olsr_linkcost default_lq_packet_loss_worker_ff(struct link_entry __attribute__((unused)) *link, void __attribute__((unused)) *ptr, olsr_bool __attribute__((unused)) lost) {
227   return link->linkcost;
228 }
229
230 void default_lq_memorize_foreign_hello_ff(void *ptrLocal, void *ptrForeign) {
231   struct default_lq_ff *local = ptrLocal;
232   struct default_lq_ff *foreign = ptrForeign;
233   
234   if (foreign) {
235     local->valueNlq = foreign->valueLq;
236   } else {
237     local->valueNlq = 0;
238   }
239 }
240
241 void default_lq_copy_link2tc_ff(void *target, void *source) {
242   memcpy(target, source, sizeof(struct default_lq_ff));
243 }
244
245 void default_lq_clear_ff(void *target) {
246   struct default_lq_ff *local = target;
247   int i;
248   
249   memset(target, 0, sizeof(struct default_lq_ff));
250   
251   local->windowSize = LQ_FF_QUICKSTART_INIT;
252   for (i=0; i<LQ_FF_WINDOW; i++) {
253     local->lost[i] = 3;
254   }
255 }
256
257 const char *default_lq_print_ff(void *ptr, struct lqtextbuffer *buffer) {
258   struct default_lq_ff *lq = ptr;
259   
260   sprintf(buffer->buf, "%s/%s", fpmtoa(fpmidiv(itofpm((int)lq->valueLq), 255)), fpmtoa(fpmidiv(itofpm((int)lq->valueNlq), 255)));
261   return buffer->buf;
262 }
263
264 const char *default_lq_print_cost_ff(olsr_linkcost cost, struct lqtextbuffer *buffer) {
265   sprintf(buffer->buf, "%s", fpmtoa(cost));
266   return buffer->buf;
267 }