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