-/*
- * This file is free software: you may copy, redistribute and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation, either version 2 of the License, or (at your
- * option) any later version.
- *
- * This file is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program. If not, see <http://www.gnu.org/licenses/>.
- *
- * This file incorporates work covered by the following copyright and
- * permission notice:
- *
+/*
Copyright (c) 2007, 2008 by Juliusz Chroboczek
Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
#include "xroute.h"
#include "message.h"
#include "resend.h"
+#include "babel_errors.h"
static void consider_route(struct babel_route *route);
struct babel_route **routes = NULL;
static int route_slots = 0, max_route_slots = 0;
int kernel_metric = 0;
-int allow_duplicates = -1;
-int diversity_kind = DIVERSITY_NONE;
-int diversity_factor = 256; /* in units of 1/256 */
+enum babel_diversity diversity_kind = DIVERSITY_NONE;
+int diversity_factor = BABEL_DEFAULT_DIVERSITY_FACTOR;
int keep_unfeasible = 0;
+int smoothing_half_life = 0;
+static int two_to_the_one_over_hl = 0; /* 2^(1/hl) * 0x10000 */
+
/* We maintain a list of "slots", ordered by prefix. Every slot
contains a linked list of the routes to this prefix, with the
installed route, if any, at the head of the list. */
resize_route_table(max_route_slots < 1 ? 8 : 2 * max_route_slots);
if(route_slots >= max_route_slots)
return NULL;
+ assert(routes);
route->next = NULL;
if(n < route_slots)
memmove(routes + n + 1, routes + n,
}
void
-flush_all_routes()
+flush_all_routes(void)
{
int i;
while(i < route_slots) {
/* Uninstall first, to avoid calling route_lost. */
if(routes[i]->installed)
- uninstall_route(routes[0]);
+ uninstall_route(routes[i]);
flush_route(routes[i]);
}
i--;
}
}
-/* Iterate a function over all routes. */
-void
-for_all_routes(void (*f)(struct babel_route*, void*), void *closure)
+struct route_stream {
+ int installed;
+ int index;
+ struct babel_route *next;
+};
+
+
+struct route_stream *
+route_stream(int installed)
{
- int i;
+ struct route_stream *stream;
- for(i = 0; i < route_slots; i++) {
- struct babel_route *r = routes[i];
- while(r) {
- (*f)(r, closure);
- r = r->next;
+ stream = malloc(sizeof(struct route_stream));
+ if(stream == NULL)
+ return NULL;
+
+ stream->installed = installed;
+ stream->index = installed ? 0 : -1;
+ stream->next = NULL;
+
+ return stream;
+}
+
+struct babel_route *
+route_stream_next(struct route_stream *stream)
+{
+ if(stream->installed) {
+ while(stream->index < route_slots && !routes[stream->index]->installed)
+ stream->index++;
+
+ if(stream->index < route_slots)
+ return routes[stream->index++];
+ else
+ return NULL;
+ } else {
+ struct babel_route *next;
+ if(!stream->next) {
+ stream->index++;
+ if(stream->index >= route_slots)
+ return NULL;
+ stream->next = routes[stream->index];
}
+ next = stream->next;
+ stream->next = next->next;
+ return next;
}
}
void
-for_all_installed_routes(void (*f)(struct babel_route*, void*), void *closure)
+route_stream_done(struct route_stream *stream)
{
- int i;
-
- for(i = 0; i < route_slots; i++) {
- if(routes[i]->installed)
- (*f)(routes[i], closure);
- }
+ free(stream);
}
static int
return;
if(!route_feasible(route))
- zlog_err("WARNING: installing unfeasible route "
- "(this shouldn't happen).");
+ flog_err(EC_BABEL_ROUTE, "WARNING: installing unfeasible route "
+ "(this shouldn't happen).");
i = find_route_slot(route->src->prefix, route->src->plen, NULL);
assert(i >= 0 && i < route_slots);
if(routes[i] != route && routes[i]->installed) {
- fprintf(stderr, "WARNING: attempting to install duplicate route "
- "(this shouldn't happen).");
+ flog_err(EC_BABEL_ROUTE,
+ "WARNING: attempting to install duplicate route "
+ "(this shouldn't happen).");
return;
}
metric_to_kernel(route_metric(route)), NULL, 0, 0);
if(rc < 0) {
int save = errno;
- zlog_err("kernel_route(ADD): %s", safe_strerror(errno));
+ flog_err(EC_BABEL_ROUTE, "kernel_route(ADD): %s",
+ safe_strerror(errno));
if(save != EEXIST)
return;
}
route->neigh->ifp->ifindex,
metric_to_kernel(route_metric(route)), NULL, 0, 0);
if(rc < 0)
- zlog_err("kernel_route(FLUSH): %s", safe_strerror(errno));
+ flog_err(EC_BABEL_ROUTE, "kernel_route(FLUSH): %s",
+ safe_strerror(errno));
route->installed = 0;
}
return;
if(!route_feasible(new))
- zlog_err("WARNING: switching to unfeasible route "
- "(this shouldn't happen).");
+ flog_err(EC_BABEL_ROUTE, "WARNING: switching to unfeasible route "
+ "(this shouldn't happen).");
rc = kernel_route(ROUTE_MODIFY, old->src->prefix, old->src->plen,
old->nexthop, old->neigh->ifp->ifindex,
new->nexthop, new->neigh->ifp->ifindex,
metric_to_kernel(route_metric(new)));
if(rc < 0) {
- zlog_err("kernel_route(MODIFY): %s", safe_strerror(errno));
+ flog_err(EC_BABEL_ROUTE, "kernel_route(MODIFY): %s",
+ safe_strerror(errno));
return;
}
route->nexthop, route->neigh->ifp->ifindex,
new);
if(rc < 0) {
- zlog_err("kernel_route(MODIFY metric): %s", safe_strerror(errno));
+ flog_err(EC_BABEL_ROUTE, "kernel_route(MODIFY metric): %s",
+ safe_strerror(errno));
return;
}
}
+ /* Update route->smoothed_metric using the old metric. */
+ route_smoothed_metric(route);
+
route->refmetric = refmetric;
route->cost = cost;
route->add_metric = add;
+
+ if(smoothing_half_life == 0) {
+ route->smoothed_metric = route_metric(route);
+ route->smoothed_metric_time = babel_now.tv_sec;
+ }
}
static void
retract_route(struct babel_route *route)
{
+ /* We cannot simply remove the route from the kernel, as that might
+ cause a routing loop -- see RFC 6126 Sections 2.8 and 3.5.5. */
change_route_metric(route, INFINITY, INFINITY, 0);
}
}
}
return 0;
- default:
- fprintf(stderr, "Unknown kind of diversity.\n");
- return 1;
}
+
+ return 1;
}
int
(src->seqno == seqno && refmetric < src->metric));
}
-/* This returns the feasible route with the smallest metric. */
+void
+change_smoothing_half_life(int half_life)
+{
+ if(half_life <= 0) {
+ smoothing_half_life = 0;
+ two_to_the_one_over_hl = 0;
+ return;
+ }
+
+ smoothing_half_life = half_life;
+ switch(smoothing_half_life) {
+ case 1: two_to_the_one_over_hl = 131072; break;
+ case 2: two_to_the_one_over_hl = 92682; break;
+ case 3: two_to_the_one_over_hl = 82570; break;
+ case 4: two_to_the_one_over_hl = 77935; break;
+ default:
+ /* 2^(1/x) is 1 + log(2)/x + O(1/x^2) at infinity. */
+ two_to_the_one_over_hl = 0x10000 + 45426 / half_life;
+ }
+}
+
+/* Update the smoothed metric, return the new value. */
+int
+route_smoothed_metric(struct babel_route *route)
+{
+ int metric = route_metric(route);
+
+ if(smoothing_half_life <= 0 || /* no smoothing */
+ metric >= INFINITY || /* route retracted */
+ route->smoothed_metric_time > babel_now.tv_sec || /* clock stepped */
+ route->smoothed_metric == metric) { /* already converged */
+ route->smoothed_metric = metric;
+ route->smoothed_metric_time = babel_now.tv_sec;
+ } else {
+ int diff;
+ /* We randomise the computation, to minimise global synchronisation
+ and hence oscillations. */
+ while(route->smoothed_metric_time <=
+ babel_now.tv_sec - smoothing_half_life) {
+ diff = metric - route->smoothed_metric;
+ route->smoothed_metric += roughly(diff) / 2;
+ route->smoothed_metric_time += smoothing_half_life;
+ }
+ while(route->smoothed_metric_time < babel_now.tv_sec) {
+ diff = metric - route->smoothed_metric;
+ route->smoothed_metric +=
+ roughly(diff) * (two_to_the_one_over_hl - 0x10000) / 0x10000;
+ route->smoothed_metric_time++;
+ }
+
+ diff = metric - route->smoothed_metric;
+ if(diff > -4 && diff < 4)
+ route->smoothed_metric = metric;
+ }
+
+ /* change_route_metric relies on this */
+ assert(route->smoothed_metric_time == babel_now.tv_sec);
+ return route->smoothed_metric;
+}
+
+static int
+route_acceptable(struct babel_route *route, int feasible,
+ struct neighbour *exclude)
+{
+ if(route_expired(route))
+ return 0;
+ if(feasible && !route_feasible(route))
+ return 0;
+ if(exclude && route->neigh == exclude)
+ return 0;
+ return 1;
+}
+
+/* Find the best route according to the weak ordering. Any
+ linearisation of the strong ordering (see consider_route) will do,
+ we use sm <= sm'. We could probably use a lexical ordering, but
+ that's probably overkill. */
+
struct babel_route *
find_best_route(const unsigned char *prefix, unsigned char plen, int feasible,
struct neighbour *exclude)
return NULL;
route = routes[i];
+ while(route && !route_acceptable(route, feasible, exclude))
+ route = route->next;
+
+ if(!route)
+ return NULL;
r = route->next;
while(r) {
- if(!route_expired(r) &&
- (!feasible || route_feasible(r)) &&
- (!exclude || r->neigh != exclude) &&
- (route_metric(r) < route_metric(route)))
+ if(route_acceptable(r, feasible, exclude) &&
+ (route_smoothed_metric(r) < route_smoothed_metric(route)))
route = r;
r = r->next;
}
+
return route;
}
update_route_metric(struct babel_route *route)
{
int oldmetric = route_metric(route);
+ int old_smoothed_metric = route_smoothed_metric(route);
if(route_expired(route)) {
if(route->refmetric < INFINITY) {
neigh->ifp->ifindex);
change_route_metric(route, route->refmetric,
neighbour_cost(route->neigh), add_metric);
- if(route_metric(route) != oldmetric)
+ if(route_metric(route) != oldmetric ||
+ route_smoothed_metric(route) != old_smoothed_metric)
route_changed(route, route->src, oldmetric);
}
}
/* Called whenever a neighbour's cost changes, to update the metric of
- all routes through that neighbour. Calls local_notify_neighbour. */
+ all routes through that neighbour. */
void
update_neighbour_metric(struct neighbour *neigh, int changed)
{
return NULL;
if(martian_prefix(prefix, plen)) {
- zlog_err("Rejecting martian route to %s through %s.",
- format_prefix(prefix, plen), format_address(router_id));
+ flog_err(EC_BABEL_ROUTE, "Rejecting martian route to %s through %s.",
+ format_prefix(prefix, plen), format_address(nexthop));
return NULL;
}
debugf(BABEL_DEBUG_COMMON,"Unfeasible update for installed route to %s "
"(%s %d %d -> %s %d %d).",
format_prefix(src->prefix, src->plen),
- format_address(route->src->id),
+ format_eui64(route->src->id),
route->seqno, route->refmetric,
- format_address(src->id), seqno, refmetric);
+ format_eui64(src->id), seqno, refmetric);
if(src != route->src) {
uninstall_route(route);
lost = 1;
if((feasible || keep_unfeasible) && refmetric < INFINITY)
route->time = babel_now.tv_sec;
route->seqno = seqno;
+
+ memset(&route->channels, 0, sizeof(route->channels));
+ if(channels_len > 0)
+ memcpy(&route->channels, channels,
+ MIN(channels_len, DIVERSITY_HOPS));
+
change_route_metric(route,
refmetric, neighbour_cost(neigh), add_metric);
route->hold_time = hold_time;
memcpy(route->nexthop, nexthop, 16);
route->time = babel_now.tv_sec;
route->hold_time = hold_time;
+ route->smoothed_metric = MAX(route_metric(route), INFINITY / 2);
+ route->smoothed_metric_time = babel_now.tv_sec;
route->installed = 0;
memset(&route->channels, 0, sizeof(route->channels));
if(channels_len > 0)
route->next = NULL;
new_route = insert_route(route);
if(new_route == NULL) {
- fprintf(stderr, "Couldn't insert route.\n");
+ flog_err(EC_BABEL_ROUTE, "Couldn't insert route.");
free(route);
return NULL;
}
}
}
-/* This takes a feasible route and decides whether to install it. */
+/* This takes a feasible route and decides whether to install it.
+ This uses the strong ordering, which is defined by sm <= sm' AND
+ m <= m'. This ordering is not total, which is what causes
+ hysteresis. */
+
static void
consider_route(struct babel_route *route)
{
return;
xroute = find_xroute(route->src->prefix, route->src->plen);
- if(xroute && (allow_duplicates < 0 || xroute->metric >= allow_duplicates))
+ if(xroute)
return;
installed = find_installed_route(route->src->prefix, route->src->plen);
if(route_metric(installed) >= INFINITY)
goto install;
- if(route_metric(installed) >= route_metric(route) + 64)
+ if(route_metric(installed) >= route_metric(route) &&
+ route_smoothed_metric(installed) > route_smoothed_metric(route))
goto install;
return;
}
r = r->next;
}
- i++;
}
}
struct source *oldsrc, unsigned short oldmetric)
{
if(route->installed) {
- if(route_metric(route) > oldmetric) {
- struct babel_route *better_route;
- better_route =
- find_best_route(route->src->prefix, route->src->plen, 1, NULL);
- if(better_route &&
- route_metric(better_route) <= route_metric(route) - 96)
- consider_route(better_route);
- }
+ struct babel_route *better_route;
+ /* Do this unconditionally -- microoptimisation is not worth it. */
+ better_route =
+ find_best_route(route->src->prefix, route->src->plen, 1, NULL);
+ if(better_route && route_metric(better_route) < route_metric(route))
+ consider_route(better_route);
+ }
- if(route->installed)
- /* We didn't change routes after all. */
- send_triggered_update(route, oldsrc, oldmetric);
+ if(route->installed) {
+ /* We didn't change routes after all. */
+ send_triggered_update(route, oldsrc, oldmetric);
} else {
/* Reconsider routes even when their metric didn't decrease,
they may not have been feasible before. */
if(new_route) {
consider_route(new_route);
} else if(oldmetric < INFINITY) {
- /* Complain loudly. */
+ /* Avoid creating a blackhole. */
send_update_resend(NULL, src->prefix, src->plen);
- send_request_resend(NULL, src->prefix, src->plen,
- src->metric >= INFINITY ?
- src->seqno : seqno_plus(src->seqno, 1),
- src->id);
+ /* If the route was usable enough, try to get an alternate one.
+ If it was not, we could be dealing with oscillations around
+ the value of INFINITY. */
+ if(oldmetric <= INFINITY / 2)
+ send_request_resend(NULL, src->prefix, src->plen,
+ src->metric >= INFINITY ?
+ src->seqno : seqno_plus(src->seqno, 1),
+ src->id);
}
}
projects / mirror_frr.git / blobdiff