[Olsr-dev] [PATCH v2 3/4] gateway: add exit link weighing
Ferry Huberts
(spam-protected)
Fri Aug 3 11:33:03 CEST 2012
From: Ferry Huberts <(spam-protected)>
Only performed when the weighing factors are set
Signed-off-by: Ferry Huberts <(spam-protected)>
---
README-Olsr-Extensions | 49 ++++++++++++++++++++++
src/gateway_default_handler.c | 96 +++++++++++++++++++++++++++++++++++++++++--
2 files changed, 142 insertions(+), 3 deletions(-)
diff --git a/README-Olsr-Extensions b/README-Olsr-Extensions
index a6e9d13..ac244cf 100644
--- a/README-Olsr-Extensions
+++ b/README-Olsr-Extensions
@@ -264,6 +264,55 @@ All other parameters will be ignored if SmartGateway is set to "no"
of a new outgoing gateway if its routing cost is lower or equal to the
configured percentage of the routing cost of the current gateway.
The default setting is 0, which disables it.
+5- SmartGatewayWeightExitLinkUp, SmartGatewayWeightExitLinkDown,
+ SmartGatewayWeightEtx and SmartGatewayDividerEtx control the weighing
+ of gateway bandwidth and ETX costs.
+
+ If SmartGatewayDividerEtx is zero then no weighing is performed (classical
+ behaviour). Classical behaviour only takes ETX costs into account when
+ choosing a gateway (select the 'nearest' gateway).
+
+ The weighing also takes the gateway bandwidths into account (select the
+ 'nearest fat pipe' gateway).
+
+ Gateways that have zero bandwidth for either their uplink or downlink are
+ ignored.
+
+ * The Weighing Process
+ ======================
+
+ ** Configuration Parameters
+ ===========================
+ SmartGatewayWeightExitLinkUp = gateway exit link uplink weight
+ SmartGatewayWeightExitLinkDown = gateway exit link downlink weight
+ SmartGatewayWeightEtx = ETX path cost weight
+ SmartGatewayDividerEtx = ETX path cost divider
+
+ ** Gateway Parameters
+ ===========================
+ gw->uplink (Mbps) = gateway exit link uplink , in Mbps
+ gw->downlink (Mbps) = gateway exit link downlink, in Mbps
+
+ ** Weighing Formula
+ ===================
+ SmartGatewayWeightExitLinkUp
+ path_cost_weighed = ---------------------------- +
+ gw->uplink (Mbps)
+
+ SmartGatewayWeightExitLinkDown
+ ------------------------------ +
+ gw->downlink (Mbps)
+
+ SmartGatewayWeightEtx
+ ---------------------- * path_cost
+ SmartGatewayDividerEtx
+
+ ** Recommended Configuration Parameter Settings
+ ===============================================
+ SmartGatewayWeightExitLinkUp = 1 (default is 1)
+ SmartGatewayWeightExitLinkDown = 1 (default is 1)
+ SmartGatewayWeightEtx = 1 (default is 1)
+ SmartGatewayDividerEtx = 4 (default is 0)
5.3) Uplink Side
diff --git a/src/gateway_default_handler.c b/src/gateway_default_handler.c
index a20924c..d96c20e 100644
--- a/src/gateway_default_handler.c
+++ b/src/gateway_default_handler.c
@@ -57,6 +57,96 @@ static inline uint64_t gw_default_calc_threshold(uint64_t path_cost) {
}
/**
+ * Weigh the path costs and the gateway bandwidth.
+ *
+ * If the ETX divider is zero, then no weighing is performed and only the path
+ * costs are considered (classic behaviour).
+ *
+ * If either of the uplink or downlink bandwidths is zero, then UINT64_MAX is
+ * returned.
+ *
+ * @param path_cost the (ETX) path cost to the gateway
+ * @param exitUk the gateway exit link uplink bandwidth (in kbps)
+ * @param exitDk the gateway exit link downlink bandwidth (in kbps)
+ * @return the weighed path cost
+ */
+static inline uint64_t gw_default_weigh_costs(uint64_t path_cost, uint32_t exitUk, uint32_t exitDk) {
+ uint8_t WexitU = olsr_cnf->smart_gw_weight_exitlink_up;
+ uint8_t WexitD = olsr_cnf->smart_gw_weight_exitlink_down;
+ uint8_t Wetx = olsr_cnf->smart_gw_weight_etx;
+ uint8_t Detx = olsr_cnf->smart_gw_divider_etx;
+ uint64_t costU;
+ uint64_t costD;
+ uint64_t costE;
+
+ if (!Detx) {
+ /* only consider path costs (classic behaviour) */
+ return path_cost;
+ }
+
+ if (!exitUk || !exitDk) {
+ /* zero bandwidth */
+ return UINT64_MAX;
+ }
+
+ /*
+ * Weighing of the path costs:
+ *
+ * exitUm = the gateway exit link uplink bandwidth, in Mbps
+ * exitDm = the gateway exit link downlink bandwidth, in Mbps
+ * WexitU = the gateway exit link uplink bandwidth weight (configured)
+ * WexitD = the gateway exit link downlink bandwidth weight (configured)
+ * Wetx = the ETX path cost weight (configured)
+ * Detx = the ETX path cost divider (configured)
+ *
+ * WexitU WexitD Wetx
+ * path_cost_weighed = ------ + ------ + ---- * path_cost
+ * exitUm exitDm Detx
+ *
+ * Since the gateway exit link bandwidths are in Kbps, the following formula
+ * is used to convert them to the desired Mbps:
+ *
+ * bwK
+ * bwM = ---- bwK = bandwidth in Kbps
+ * 1000 bwM = bandwidth in Mbps
+ *
+ * exitUm = the gateway exit link uplink bandwidth, in Kbps
+ * exitDm = the gateway exit link downlink bandwidth, in Kbps
+ *
+ * 1000 * WexitU 1000 * WexitD Wetx
+ * path_cost_weighed = ------------- + ------------- + ---- * path_cost
+ * exitUk exitDk Detx
+ *
+ *
+ * Analysis of the required bit width of the result:
+ *
+ * exitUk = 29 bits = [1, 320,000,000]
+ * exitDk = 29 bits = [1, 320,000,000]
+ * WexitU = 8 bits = [1, 255]
+ * WexitD = 8 bits = [1, 255]
+ * Wetx = 8 bits = [1, 255]
+ * Detx = 8 bits = [1, 255]
+ * path_cost = 32 bits = [1, 4,294,967,295]
+ *
+ * 1000 * 255 1000 * 255 255
+ * path_cost_weighed(max) = ---------- + ---------- + --- * 4,294,967,295
+ * 1 1 1
+ *
+ * path_cost_weighed(max) = 0x3E418 + 0x3E418 + 0xFEFFFFFF01
+ * path_cost_weighed(max) = 0xFF0007C731
+ *
+ * Because we can multiply 0xFF0007C731 by 2^24 without overflowing a
+ * 64 bits number, we do this to increase accuracy.
+ */
+
+ costU = (((uint64_t)(1000 * WexitU )) << 24) / exitUk;
+ costD = (((uint64_t)(1000 * WexitD )) << 24) / exitDk;
+ costE = (((uint64_t)(Wetx * path_cost)) << 24) / Detx;
+
+ return (costU + costD + costE);
+}
+
+/**
* Look through the gateway list and select the best gateway
* depending on the distance to this router
*/
@@ -80,7 +170,7 @@ static void gw_default_choose_gateway(void) {
if (gw) {
tc = olsr_lookup_tc_entry(&gw->originator);
if (tc) {
- uint64_t cost = tc->path_cost;
+ uint64_t cost = gw_default_weigh_costs(tc->path_cost, gw->uplink, gw->downlink);
cost_ipv4_threshold = gw_default_calc_threshold(cost);
eval_cost_ipv4_threshold = true;
}
@@ -89,7 +179,7 @@ static void gw_default_choose_gateway(void) {
if (gw) {
tc = olsr_lookup_tc_entry(&gw->originator);
if (tc) {
- uint64_t cost = tc->path_cost;
+ uint64_t cost = gw_default_weigh_costs(tc->path_cost, gw->uplink, gw->downlink);
cost_ipv6_threshold = gw_default_calc_threshold(cost);
eval_cost_ipv6_threshold = true;
}
@@ -116,7 +206,7 @@ static void gw_default_choose_gateway(void) {
}
/* determine the path cost */
- path_cost = tc->path_cost;
+ path_cost = gw_default_weigh_costs(tc->path_cost, gw->uplink, gw->downlink);
if (!gw_def_finished_ipv4 && gw->ipv4 && gw->ipv4nat == olsr_cnf->smart_gw_allow_nat && path_cost < cost_ipv4 &&
(!eval_cost_ipv4_threshold || (path_cost < cost_ipv4_threshold))) {
--
1.7.11.2
More information about the Olsr-dev
mailing list