[Olsr-dev] [PATCH v1 1/3] gateway: also take gateway bandwidth into account...
Ferry Huberts
(spam-protected)
Thu Jul 26 16:23:17 CEST 2012
From: Ferry Huberts <(spam-protected)>
..when the weighing factors are set
Signed-off-by: Ferry Huberts <(spam-protected)>
---
src/cfgparser/olsrd_conf.c | 4 ++
src/gateway_default_handler.c | 88 +++++++++++++++++++++++++++++++++++++++----
src/olsr_cfg.h | 4 ++
3 files changed, 89 insertions(+), 7 deletions(-)
diff --git a/src/cfgparser/olsrd_conf.c b/src/cfgparser/olsrd_conf.c
index 32db6bf..4ab9e47 100644
--- a/src/cfgparser/olsrd_conf.c
+++ b/src/cfgparser/olsrd_conf.c
@@ -569,6 +569,8 @@ olsrd_sanity_check_cnf(struct olsrd_config *cnf)
return -1;
}
+ /* no checks are needed on cnf->smart_gw_weight_exitlink and cnf->smart_gw_weight_etx */
+
if (cnf->smart_gw_type >= GW_UPLINK_CNT) {
fprintf(stderr, "Error, illegal gateway uplink type: %d\n", cnf->smart_gw_type);
return -1;
@@ -781,6 +783,8 @@ set_default_cnf(struct olsrd_config *cnf)
cnf->smart_gw_period = DEF_GW_PERIOD;
cnf->smart_gw_stablecount = DEF_GW_STABLE_COUNT;
cnf->smart_gw_thresh = DEF_GW_THRESH;
+ cnf->smart_gw_weight_exitlink = DEF_GW_WEIGHT_EXITLINK;
+ cnf->smart_gw_weight_etx = DEF_GW_WEIGHT_ETX;
cnf->smart_gw_type = DEF_GW_TYPE;
cnf->smart_gw_uplink = DEF_UPLINK_SPEED;
cnf->smart_gw_uplink_nat = DEF_GW_UPLINK_NAT;
diff --git a/src/gateway_default_handler.c b/src/gateway_default_handler.c
index ec6225c..3d248e5 100644
--- a/src/gateway_default_handler.c
+++ b/src/gateway_default_handler.c
@@ -39,19 +39,93 @@ static struct olsr_gw_handler gw_def_handler = {
*/
/**
+ * Weigh the path costs and the gateway bandwidth.
+ * If either of weighing factors is zero, then no weighing is performed and
+ * only the path costs are considered (classic behaviour).
+ *
+ * @param path_cost the path cost (ETX) to the gateway
+ * @param uplink the uplink speed of the gateway (in kbps)
+ * @param downlink the downlink speed of the gateway (in kbps)
+ * @return the weighed costs
+ */
+static uint64_t gw_default_weigh_costs(uint32_t path_cost, uint32_t uplink, uint32_t downlink) {
+ uint8_t wExit = olsr_cnf->smart_gw_weight_exitlink;
+ uint8_t wEtx = olsr_cnf->smart_gw_weight_etx;
+ uint32_t bwK;
+ uint64_t denominator;
+ uint64_t divider;
+
+ if (!wExit || !wEtx) {
+ /* only consider path costs (classic behaviour) */
+ return path_cost;
+ }
+
+ bwK = uplink + downlink;
+ if (!bwK) {
+ /* zero bandwidth */
+ return UINT64_MAX;
+ }
+
+ /*
+ * Weighing of the path costs is performed here.
+ * The two formulas that we use are:
+ *
+ * bwK wExit path_cost
+ * bwM = ---- new_path_cost = ----- + ---------
+ * 1000 bwM wEtx
+ *
+ * which together gives
+ *
+ * 1000 * wExit path_cost
+ * new_path_cost = ------------ + ---------
+ * bwK wEtx
+ *
+ * which simplifies to
+ *
+ * 1000 * wExit * wEtx + bwK * path_cost
+ * new_path_cost = -------------------------------------
+ * bwK * wEtx
+ *
+ *
+ * Analysis of the required bit width of the result:
+ *
+ * The range of both uplink and downlink is [0, 320000000]. Therefore the
+ * range of bwK is [0, 640000000].
+ *
+ * new_path_cost = (1000 * 255 * 255 + 640000000 * 4294967295) / (640000000 * 255 )
+ * = (0x3e8 * 0xff * 0xff + 0x2625a000 * 0xffffffff) / (0x2625a000 * 0xff)
+ * = (0x3e033e8 + 0x26259fffd9da6000 ) / (0x25ff7a6000 )
+ * = (0x26259fffddba93e8 ) / (0x25ff7a6000 )
+ *
+ * Because we can multiply 0x26259fffddba93e8 by 6 without overflowing a
+ * 64 bits number, we do this to increase accuracy.
+ */
+
+ denominator = 1000 * wExit * wEtx + bwK * path_cost;
+ divider = bwK * wEtx;
+
+ /* we multiply by 6 to increase accuracy */
+ denominator *= 6;
+ /* we add (divider >> 1) for correct rounding */
+ denominator += (divider >> 1);
+
+ return (denominator / divider);
+}
+
+/**
* Look through the gateway list and select the best gateway
* depending on the distance to this router
*/
static void gw_default_choose_gateway(void) {
struct gateway_entry *inet_ipv4 = NULL;
struct gateway_entry *inet_ipv6 = NULL;
- olsr_linkcost cost_ipv4 = ROUTE_COST_BROKEN;
- olsr_linkcost cost_ipv6 = ROUTE_COST_BROKEN;
struct gateway_entry *gw;
bool dual;
OLSR_FOR_ALL_GATEWAY_ENTRIES(gw) {
- olsr_linkcost path_cost_times_threshold;
+ uint64_t path_cost_times_threshold;
+ uint64_t cost_ipv4 = UINT64_MAX;
+ uint64_t cost_ipv6 = UINT64_MAX;
struct tc_entry *tc = olsr_lookup_tc_entry(&gw->originator);
if (!tc) {
@@ -69,11 +143,11 @@ static void gw_default_choose_gateway(void) {
continue;
}
+ path_cost_times_threshold = gw_default_weigh_costs(tc->path_cost, gw->uplink, gw->downlink);
+
/* determine the path costs threshold */
- if (olsr_cnf->smart_gw_thresh == 0) {
- path_cost_times_threshold = tc->path_cost;
- } else {
- path_cost_times_threshold = ((long long)tc->path_cost * (long long)olsr_cnf->smart_gw_thresh + 50LL) / 100LL;
+ if (!olsr_cnf->smart_gw_thresh) {
+ path_cost_times_threshold = (path_cost_times_threshold * olsr_cnf->smart_gw_thresh + 50) / 100;
}
if (!gw_def_finished_ipv4 && gw->ipv4 && gw->ipv4nat == olsr_cnf->smart_gw_allow_nat && path_cost_times_threshold < cost_ipv4) {
diff --git a/src/olsr_cfg.h b/src/olsr_cfg.h
index 8dc83ec..816eb23 100644
--- a/src/olsr_cfg.h
+++ b/src/olsr_cfg.h
@@ -85,6 +85,8 @@
#define DEF_GW_STABLE_COUNT 6
#define DEF_GW_ALLOW_NAT true
#define DEF_GW_THRESH 0
+#define DEF_GW_WEIGHT_EXITLINK 0
+#define DEF_GW_WEIGHT_ETX 0
#define DEF_GW_TYPE GW_UPLINK_IPV46
#define DEF_GW_UPLINK_NAT true
#define DEF_UPLINK_SPEED 128
@@ -275,6 +277,8 @@ struct olsrd_config {
uint32_t smart_gw_period;
uint8_t smart_gw_stablecount;
uint8_t smart_gw_thresh;
+ uint8_t smart_gw_weight_exitlink;
+ uint8_t smart_gw_weight_etx;
enum smart_gw_uplinktype smart_gw_type;
uint32_t smart_gw_uplink, smart_gw_downlink;
struct olsr_ip_prefix smart_gw_prefix;
--
1.7.11.2
More information about the Olsr-dev
mailing list