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