gateway: fix stable count dampening in gw_default_timer
[olsrd.git] / src / gateway_default_handler.c
1 /*
2  * gateway_default_handler.c
3  *
4  *  Created on: Jan 29, 2010
5  *      Author: rogge
6  */
7 #ifdef __linux__
8
9 #include "gateway_default_handler.h"
10
11 #include "defs.h"
12 #include "gateway.h"
13 #include "lq_plugin.h"
14
15 static uint32_t gw_def_nodecount;
16 static uint32_t gw_def_stablecount;
17 static bool gw_def_finished_ipv4;
18 static bool gw_def_finished_ipv6;
19 static struct timer_entry *gw_def_timer;
20
21 /* forward declarations */
22 static void gw_default_init(void);
23 static void gw_default_cleanup(void);
24 static void gw_default_startup_handler(void);
25 static void gw_default_choosegw_handler(bool ipv4, bool ipv6);
26 static void gw_default_update_handler(struct gateway_entry *);
27 static void gw_default_delete_handler(struct gateway_entry *);
28
29 /**
30  * Callback list for the gateway (default) handler
31  */
32 struct olsr_gw_handler gw_def_handler = {
33     &gw_default_init,
34     &gw_default_cleanup,
35     &gw_default_startup_handler,
36     &gw_default_choosegw_handler,
37     &gw_default_update_handler,
38     &gw_default_delete_handler
39 };
40
41 /*
42  * Helper functions
43  */
44
45 /**
46  * Calculate the threshold path cost.
47  *
48  * @param path_cost the path cost
49  * @return the threshold path cost
50  */
51 static inline uint64_t gw_default_calc_threshold(uint64_t path_cost) {
52   uint64_t path_cost_times_threshold;
53
54   if (olsr_cnf->smart_gw_thresh == 0) {
55     path_cost_times_threshold = path_cost;
56   } else {
57     path_cost_times_threshold = (path_cost * (uint64_t) olsr_cnf->smart_gw_thresh + (uint64_t) 50) / (uint64_t) 100;
58   }
59
60   return path_cost_times_threshold;
61 }
62
63 /**
64  * Weigh the path costs and the gateway bandwidth.
65  *
66  * If the ETX divider is zero, then no weighing is performed and only the path
67  * costs are considered (classic behaviour).
68  *
69  * If either of the uplink or downlink bandwidths is zero, then UINT64_MAX is
70  * returned.
71  *
72  * @param path_cost the (ETX) path cost to the gateway
73  * @param exitUk the gateway exit link uplink bandwidth (in kbps)
74  * @param exitDk the gateway exit link downlink bandwidth (in kbps)
75  * @return the weighed path cost
76  */
77 static inline uint64_t gw_default_weigh_costs(uint64_t path_cost, uint32_t exitUk, uint32_t exitDk) {
78   uint8_t WexitU = olsr_cnf->smart_gw_weight_exitlink_up;
79   uint8_t WexitD = olsr_cnf->smart_gw_weight_exitlink_down;
80   uint8_t Wetx = olsr_cnf->smart_gw_weight_etx;
81   uint8_t Detx = olsr_cnf->smart_gw_divider_etx;
82   uint64_t costU;
83   uint64_t costD;
84   uint64_t costE;
85
86   if (!Detx) {
87     /* only consider path costs (classic behaviour) */
88     return path_cost;
89   }
90
91   if (!exitUk || !exitDk) {
92     /* zero bandwidth */
93     return UINT64_MAX;
94   }
95
96   /*
97    * Weighing of the path costs:
98    *
99    * exitUm = the gateway exit link uplink   bandwidth, in Mbps
100    * exitDm = the gateway exit link downlink bandwidth, in Mbps
101    * WexitU = the gateway exit link uplink   bandwidth weight   (configured)
102    * WexitD = the gateway exit link downlink bandwidth weight   (configured)
103    * Wetx   = the ETX path cost weight                          (configured)
104    * Detx   = the ETX path cost divider                         (configured)
105    *
106    *                      WexitU   WexitD   Wetx
107    * path_cost_weighed =  ------ + ------ + ---- * path_cost
108    *                      exitUm   exitDm   Detx
109    *
110    * Since the gateway exit link bandwidths are in Kbps, the following formula
111    * is used to convert them to the desired Mbps:
112    *
113    *       bwK
114    * bwM = ----       bwK = bandwidth in Kbps
115    *       1000       bwM = bandwidth in Mbps
116    *
117    * exitUm = the gateway exit link uplink   bandwidth, in Kbps
118    * exitDm = the gateway exit link downlink bandwidth, in Kbps
119    *
120    *                      1000 * WexitU   1000 * WexitD   Wetx
121    * path_cost_weighed =  ------------- + ------------- + ---- * path_cost
122    *                          exitUk          exitDk      Detx
123    *
124    *
125    * Analysis of the required bit width of the result:
126    *
127    * exitUk    = 29 bits = [1,   320,000,000]
128    * exitDk    = 29 bits = [1,   320,000,000]
129    * WexitU    =  8 bits = [1,           255]
130    * WexitD    =  8 bits = [1,           255]
131    * Wetx      =  8 bits = [1,           255]
132    * Detx      =  8 bits = [1,           255]
133    * path_cost = 32 bits = [1, 4,294,967,295]
134    *
135    *                          1000 * 255   1000 * 255   255
136    * path_cost_weighed(max) = ---------- + ---------- + --- * 4,294,967,295
137    *                               1             1       1
138    *
139    * path_cost_weighed(max) = 0x3E418    + 0x3E418    + 0xFEFFFFFF01
140    * path_cost_weighed(max) = 0xFF0007C731
141    *
142    * Because we can multiply 0xFF0007C731 by 2^24 without overflowing a
143    * 64 bits number, we do this to increase accuracy.
144    */
145
146   costU = (((uint64_t) (1000 * WexitU)) << 24) / exitUk;
147   costD = (((uint64_t) (1000 * WexitD)) << 24) / exitDk;
148   costE = (((uint64_t) (Wetx * path_cost)) << 24) / Detx;
149
150   return (costU + costD + costE);
151 }
152
153 /**
154  * Look through the gateway list and select the best gateway
155  * depending on the distance to this router
156  */
157 static void gw_default_choose_gateway(void) {
158   uint64_t cost_ipv4_threshold = UINT64_MAX;
159   uint64_t cost_ipv6_threshold = UINT64_MAX;
160   bool eval_cost_ipv4_threshold = false;
161   bool eval_cost_ipv6_threshold = false;
162   struct gateway_entry *inet_ipv4 = NULL;
163   struct gateway_entry *inet_ipv6 = NULL;
164   uint64_t cost_ipv4 = UINT64_MAX;
165   uint64_t cost_ipv6 = UINT64_MAX;
166   struct gateway_entry *gw;
167   struct tc_entry *tc;
168   bool dual;
169
170   if (olsr_cnf->smart_gw_thresh) {
171     /* determine the path cost thresholds */
172
173     gw = olsr_get_inet_gateway(false);
174     if (gw) {
175       tc = olsr_lookup_tc_entry(&gw->originator);
176       if (tc) {
177         uint64_t cost = gw_default_weigh_costs(tc->path_cost, gw->uplink, gw->downlink);
178         cost_ipv4_threshold = gw_default_calc_threshold(cost);
179         eval_cost_ipv4_threshold = true;
180       }
181     }
182     gw = olsr_get_inet_gateway(true);
183     if (gw) {
184       tc = olsr_lookup_tc_entry(&gw->originator);
185       if (tc) {
186         uint64_t cost = gw_default_weigh_costs(tc->path_cost, gw->uplink, gw->downlink);
187         cost_ipv6_threshold = gw_default_calc_threshold(cost);
188         eval_cost_ipv6_threshold = true;
189       }
190     }
191   }
192
193   OLSR_FOR_ALL_GATEWAY_ENTRIES(gw) {
194     uint64_t path_cost;
195     tc = olsr_lookup_tc_entry(&gw->originator);
196
197     if (!tc) {
198       /* gateways should not exist without tc entry */
199       continue;
200     }
201
202     if (tc->path_cost == ROUTE_COST_BROKEN) {
203       /* do not consider nodes with an infinite ETX */
204       continue;
205     }
206
207     if (!gw->uplink || !gw->downlink) {
208       /* do not consider nodes without bandwidth or with a uni-directional link */
209       continue;
210     }
211
212     /* determine the path cost */
213     path_cost = gw_default_weigh_costs(tc->path_cost, gw->uplink, gw->downlink);
214
215     if (!gw_def_finished_ipv4 && gw->ipv4 && gw->ipv4nat == olsr_cnf->smart_gw_allow_nat && path_cost < cost_ipv4
216         && (!eval_cost_ipv4_threshold || (path_cost < cost_ipv4_threshold))) {
217       inet_ipv4 = gw;
218       cost_ipv4 = path_cost;
219     }
220     if (!gw_def_finished_ipv6 && gw->ipv6 && path_cost < cost_ipv6
221         && (!eval_cost_ipv6_threshold || (path_cost < cost_ipv6_threshold))) {
222       inet_ipv6 = gw;
223       cost_ipv6 = path_cost;
224     }
225   } OLSR_FOR_ALL_GATEWAY_ENTRIES_END(gw)
226
227   /* determine if we found an IPv4 and IPv6 gateway */
228   gw_def_finished_ipv4 |= (inet_ipv4 != NULL);
229   gw_def_finished_ipv6 |= (inet_ipv6 != NULL);
230
231   /* determine if we are dealing with a dual stack gateway */
232   dual = (inet_ipv4 == inet_ipv6) && (inet_ipv4 != NULL);
233
234   if (inet_ipv4) {
235     /* we are dealing with an IPv4 or dual stack gateway */
236     olsr_set_inet_gateway(&inet_ipv4->originator, true, dual);
237   }
238   if (inet_ipv6 && !dual) {
239     /* we are dealing with an IPv6-only gateway */
240     olsr_set_inet_gateway(&inet_ipv6->originator, false, true);
241   }
242
243   if ((olsr_cnf->smart_gw_thresh == 0) && gw_def_finished_ipv4 && gw_def_finished_ipv6) {
244     /* stop looking for a better gateway */
245     olsr_stop_timer(gw_def_timer);
246     gw_def_timer = NULL;
247   }
248 }
249
250 /**
251  * Timer callback for lazy gateway selection
252  *
253  * @param unused unused
254  */
255 static void gw_default_timer(void *unused __attribute__ ((unused))) {
256   /* accept a 10% increase/decrease in the number of gateway nodes without triggering a stablecount reset */
257   unsigned int tree100percent = tc_tree.count * 10;
258   uint32_t nodecount090percent = gw_def_nodecount * 9;
259   uint32_t nodecount110percent = gw_def_nodecount * 11;
260   if ((tree100percent >= nodecount090percent) && (tree100percent <= nodecount110percent)) {
261     gw_def_nodecount = tc_tree.count;
262   }
263
264   if (tc_tree.count == gw_def_nodecount) {
265     /* the number of gateway nodes is 'stable' */
266     gw_def_stablecount++;
267   } else {
268     /* there was a significant change in the number of gateway nodes */
269     gw_def_nodecount = tc_tree.count;
270     gw_def_stablecount = 0;
271   }
272
273   if (gw_def_stablecount >= olsr_cnf->smart_gw_stablecount) {
274     /* the number of gateway nodes is stable enough, so we should select a new gateway now */
275     gw_default_choose_gateway();
276   }
277 }
278
279 /**
280  * Lookup a new gateway
281  *
282  * @param ipv4 lookup new v4 gateway
283  * @param ipv6 lookup new v6 gateway
284  */
285 static void gw_default_lookup_gateway(bool ipv4, bool ipv6) {
286   if (ipv4) {
287     /* get a new IPv4 gateway if we use OLSRv4 or NIIT */
288     gw_def_finished_ipv4 = !(olsr_cnf->ip_version == AF_INET || olsr_cnf->use_niit);
289   }
290   if (ipv6) {
291     /* get a new IPv6 gateway if we use OLSRv6 */
292     gw_def_finished_ipv6 = !(olsr_cnf->ip_version == AF_INET6);
293   }
294
295   if (!(gw_def_finished_ipv4 && gw_def_finished_ipv6)) {
296     gw_default_choose_gateway();
297   }
298 }
299
300 /*
301  * Exported functions
302  */
303
304 /*
305  * Handler functions
306  */
307
308 /**
309  * initialization of default gateway handler
310  */
311 static void gw_default_init(void) {
312   /* initialize values */
313   gw_def_nodecount = 0;
314   gw_def_stablecount = 0;
315   gw_def_finished_ipv4 = false;
316   gw_def_finished_ipv6 = false;
317   gw_def_timer = NULL;
318 }
319
320 /**
321  * Cleanup default gateway handler
322  */
323 static void gw_default_cleanup(void) {
324 }
325
326 /**
327  * Handle gateway startup
328  */
329 static void gw_default_startup_handler(void) {
330   /* reset node count */
331   gw_def_nodecount = tc_tree.count;
332   gw_def_stablecount = 0;
333
334   /* get a new IPv4 gateway if we use OLSRv4 or NIIT */
335   gw_def_finished_ipv4 = !(olsr_cnf->ip_version == AF_INET || olsr_cnf->use_niit);
336
337   /* get a new IPv6 gateway if we use OLSRv6 */
338   gw_def_finished_ipv6 = !(olsr_cnf->ip_version == AF_INET6);
339
340   /* keep in mind we might be a gateway ourself */
341   gw_def_finished_ipv4 |= olsr_cnf->has_ipv4_gateway;
342   gw_def_finished_ipv6 |= olsr_cnf->has_ipv6_gateway;
343
344   /* (re)start gateway lazy selection timer */
345   olsr_set_timer(&gw_def_timer, olsr_cnf->smart_gw_period, 0, true, &gw_default_timer, NULL, 0);
346 }
347
348 /**
349  * Choose a new gateway
350  *
351  * @param ipv4 lookup new v4 gateway
352  * @param ipv6 lookup new v6 gateway
353  */
354 static void gw_default_choosegw_handler(bool ipv4, bool ipv6) {
355   gw_default_lookup_gateway(ipv4, ipv6);
356
357   if (!(gw_def_finished_ipv4 && gw_def_finished_ipv6)) {
358     gw_default_startup_handler();
359   }
360 }
361
362 /**
363  * Update a gateway entry
364  *
365  * @param gw the gateway entry
366  */
367 static void gw_default_update_handler(struct gateway_entry *gw) {
368   bool v4changed = gw && (gw == olsr_get_inet_gateway(false))
369       && (!gw->ipv4 || (gw->ipv4nat && !olsr_cnf->smart_gw_allow_nat));
370   bool v6changed = gw && (gw == olsr_get_inet_gateway(true)) && !gw->ipv6;
371
372   if (v4changed || v6changed) {
373     gw_default_lookup_gateway(v4changed, v6changed);
374   }
375 }
376
377 /**
378  * Remove a gateway entry
379  *
380  * @param gw the gateway entry
381  */
382 static void gw_default_delete_handler(struct gateway_entry *gw) {
383   bool isv4 = gw && (gw == olsr_get_inet_gateway(false));
384   bool isv6 = gw && (gw == olsr_get_inet_gateway(true));
385
386   if (isv4 || isv6) {
387     gw_default_lookup_gateway(isv4, isv6);
388   }
389 }
390 #endif /* __linux__ */