From 5734509c0545ebd95a5b8e3f22a911c1a39ffa1b Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Sun, 25 Dec 2011 17:52:09 +0100 Subject: babeld: Initial import, for Babel routing protocol. * Initial import of the Babel routing protocol, ported to Quagga. * LICENCE: Update the original LICENCE file to include all known potentially applicable copyright claims. Ask that any future contributors to babeld/ grant MIT/X11 licence to their work. * *.{c,h}: Add GPL headers, in according with the SFLC guidance on dealing with potentially mixed GPL/other licensed work, at: https://www.softwarefreedom.org/resources/2007/gpl-non-gpl-collaboration.html --- babeld/route.h | 104 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 104 insertions(+) create mode 100644 babeld/route.h (limited to 'babeld/route.h') diff --git a/babeld/route.h b/babeld/route.h new file mode 100644 index 00000000..e36f6c34 --- /dev/null +++ b/babeld/route.h @@ -0,0 +1,104 @@ +/* + * 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 . + * + * 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 + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#include "babel_interface.h" +#include "source.h" + +struct route { + struct source *src; + unsigned short metric; + unsigned short refmetric; + unsigned short seqno; + struct neighbour *neigh; + unsigned char nexthop[16]; + time_t time; + unsigned short hold_time; /* in seconds */ + short installed; +}; + +static inline int +route_metric(const struct route *route) +{ + return route->metric; +} + +extern struct route *routes; +extern int numroutes, maxroutes; +extern int kernel_metric, allow_duplicates; + +struct route *find_route(const unsigned char *prefix, unsigned char plen, + struct neighbour *neigh, const unsigned char *nexthop); +struct route *find_installed_route(const unsigned char *prefix, + unsigned char plen); +void flush_route(struct route *route); +void flush_neighbour_routes(struct neighbour *neigh); +void flush_interface_routes(struct interface *ifp, int v4only); +void install_route(struct route *route); +void uninstall_route(struct route *route); +void switch_route(struct route *old, struct route *new); +int route_feasible(struct route *route); +int route_old(struct route *route); +int route_expired(struct route *route); +int update_feasible(struct source *src, + unsigned short seqno, unsigned short refmetric); +struct route *find_best_route(const unsigned char *prefix, unsigned char plen, + int feasible, struct neighbour *exclude); +struct route *install_best_route(const unsigned char prefix[16], + unsigned char plen); +void update_neighbour_metric(struct neighbour *neigh, int change); +void update_interface_metric(struct interface *ifp); +void update_route_metric(struct route *route); +struct route *update_route(const unsigned char *a, + const unsigned char *p, unsigned char plen, + unsigned short seqno, unsigned short refmetric, + unsigned short interval, struct neighbour *neigh, + const unsigned char *nexthop); +void retract_neighbour_routes(struct neighbour *neigh); +void send_unfeasible_request(struct neighbour *neigh, int force, + unsigned short seqno, unsigned short metric, + struct source *src); +void send_triggered_update(struct route *route, + struct source *oldsrc, unsigned oldmetric); +void route_changed(struct route *route, + struct source *oldsrc, unsigned short oldmetric); +void route_lost(struct source *src, unsigned oldmetric); +void expire_routes(void); + +void babel_uninstall_all_routes(void); +struct route *babel_route_get_by_source(struct source *src); -- cgit v1.2.1 From ef4de4d36c2dc10a68d41e518057d04b262ec867 Mon Sep 17 00:00:00 2001 From: Denis Ovsienko Date: Sun, 8 Jan 2012 15:29:19 +0400 Subject: babeld: address FreeBSD "struct route" issue FreeBSD system headers have their own "struct route", which made it impossible to compile babeld. Switching babeld to "struct babel_route". --- babeld/route.h | 38 +++++++++++++++++++------------------- 1 file changed, 19 insertions(+), 19 deletions(-) (limited to 'babeld/route.h') diff --git a/babeld/route.h b/babeld/route.h index e36f6c34..dbb205d1 100644 --- a/babeld/route.h +++ b/babeld/route.h @@ -40,7 +40,7 @@ THE SOFTWARE. #include "babel_interface.h" #include "source.h" -struct route { +struct babel_route { struct source *src; unsigned short metric; unsigned short refmetric; @@ -53,38 +53,38 @@ struct route { }; static inline int -route_metric(const struct route *route) +route_metric(const struct babel_route *route) { return route->metric; } -extern struct route *routes; +extern struct babel_route *routes; extern int numroutes, maxroutes; extern int kernel_metric, allow_duplicates; -struct route *find_route(const unsigned char *prefix, unsigned char plen, +struct babel_route *find_route(const unsigned char *prefix, unsigned char plen, struct neighbour *neigh, const unsigned char *nexthop); -struct route *find_installed_route(const unsigned char *prefix, +struct babel_route *find_installed_route(const unsigned char *prefix, unsigned char plen); -void flush_route(struct route *route); +void flush_route(struct babel_route *route); void flush_neighbour_routes(struct neighbour *neigh); void flush_interface_routes(struct interface *ifp, int v4only); -void install_route(struct route *route); -void uninstall_route(struct route *route); -void switch_route(struct route *old, struct route *new); -int route_feasible(struct route *route); -int route_old(struct route *route); -int route_expired(struct route *route); +void install_route(struct babel_route *route); +void uninstall_route(struct babel_route *route); +void switch_route(struct babel_route *old, struct babel_route *new); +int route_feasible(struct babel_route *route); +int route_old(struct babel_route *route); +int route_expired(struct babel_route *route); int update_feasible(struct source *src, unsigned short seqno, unsigned short refmetric); -struct route *find_best_route(const unsigned char *prefix, unsigned char plen, +struct babel_route *find_best_route(const unsigned char *prefix, unsigned char plen, int feasible, struct neighbour *exclude); -struct route *install_best_route(const unsigned char prefix[16], +struct babel_route *install_best_route(const unsigned char prefix[16], unsigned char plen); void update_neighbour_metric(struct neighbour *neigh, int change); void update_interface_metric(struct interface *ifp); -void update_route_metric(struct route *route); -struct route *update_route(const unsigned char *a, +void update_route_metric(struct babel_route *route); +struct babel_route *update_route(const unsigned char *a, const unsigned char *p, unsigned char plen, unsigned short seqno, unsigned short refmetric, unsigned short interval, struct neighbour *neigh, @@ -93,12 +93,12 @@ void retract_neighbour_routes(struct neighbour *neigh); void send_unfeasible_request(struct neighbour *neigh, int force, unsigned short seqno, unsigned short metric, struct source *src); -void send_triggered_update(struct route *route, +void send_triggered_update(struct babel_route *route, struct source *oldsrc, unsigned oldmetric); -void route_changed(struct route *route, +void route_changed(struct babel_route *route, struct source *oldsrc, unsigned short oldmetric); void route_lost(struct source *src, unsigned oldmetric); void expire_routes(void); void babel_uninstall_all_routes(void); -struct route *babel_route_get_by_source(struct source *src); +struct babel_route *babel_route_get_by_source(struct source *src); -- cgit v1.2.1 From c7c53fa88ccdbc2d48cf7327c9e4f33cdc517a8a Mon Sep 17 00:00:00 2001 From: Matthieu Boutier Date: Sun, 8 Jan 2012 16:43:08 +0100 Subject: babeld: address some other compilation warnings. --- babeld/route.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'babeld/route.h') diff --git a/babeld/route.h b/babeld/route.h index dbb205d1..e38f1577 100644 --- a/babeld/route.h +++ b/babeld/route.h @@ -52,7 +52,7 @@ struct babel_route { short installed; }; -static inline int +static inline unsigned short route_metric(const struct babel_route *route) { return route->metric; -- cgit v1.2.1 From 1f39f466e439f217dcbae741ddc23a5340a05ec9 Mon Sep 17 00:00:00 2001 From: Matthieu Boutier Date: Wed, 18 Jan 2012 20:01:31 +0100 Subject: babeld: add command: "show_babel_database". --- babeld/route.h | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'babeld/route.h') diff --git a/babeld/route.h b/babeld/route.h index e38f1577..c08332a6 100644 --- a/babeld/route.h +++ b/babeld/route.h @@ -37,6 +37,9 @@ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +#ifndef BABEL_ROUTE_H +#define BABEL_ROUTE_H + #include "babel_interface.h" #include "source.h" @@ -102,3 +105,5 @@ void expire_routes(void); void babel_uninstall_all_routes(void); struct babel_route *babel_route_get_by_source(struct source *src); + +#endif -- cgit v1.2.1 From c35fafdf887aa32c5be6ad738d3a3b0140cea6e8 Mon Sep 17 00:00:00 2001 From: Matthieu Boutier Date: Mon, 23 Jan 2012 23:46:32 +0100 Subject: babeld: babelz merge. Babelz is the last version of the stand-alone babel daemon. In particular, it use multiple channels to diminuate interferences. Please refer to this one for more details. --- babeld/route.h | 50 ++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 38 insertions(+), 12 deletions(-) (limited to 'babeld/route.h') diff --git a/babeld/route.h b/babeld/route.h index c08332a6..b6d2d294 100644 --- a/babeld/route.h +++ b/babeld/route.h @@ -43,41 +43,69 @@ THE SOFTWARE. #include "babel_interface.h" #include "source.h" +#define DIVERSITY_NONE 0 +#define DIVERSITY_INTERFACE_1 1 +#define DIVERSITY_CHANNEL_1 2 +#define DIVERSITY_CHANNEL 3 + +#define DIVERSITY_HOPS 8 + struct babel_route { struct source *src; - unsigned short metric; unsigned short refmetric; + unsigned short cost; + unsigned short add_metric; unsigned short seqno; struct neighbour *neigh; unsigned char nexthop[16]; time_t time; unsigned short hold_time; /* in seconds */ short installed; + unsigned char channels[DIVERSITY_HOPS]; + struct babel_route *next; }; -static inline unsigned short +extern struct babel_route **routes; +extern int kernel_metric, allow_duplicates; +extern int diversity_kind, diversity_factor; +extern int keep_unfeasible; + +static inline int route_metric(const struct babel_route *route) { - return route->metric; + int m = (int)route->refmetric + route->cost + route->add_metric; + return MIN(m, INFINITY); } -extern struct babel_route *routes; -extern int numroutes, maxroutes; -extern int kernel_metric, allow_duplicates; +static inline int +route_metric_noninterfering(const struct babel_route *route) +{ + int m = + (int)route->refmetric + + (diversity_factor * route->cost + 128) / 256 + + route->add_metric; + m = MAX(m, route->refmetric + 1); + return MIN(m, INFINITY); +} struct babel_route *find_route(const unsigned char *prefix, unsigned char plen, struct neighbour *neigh, const unsigned char *nexthop); struct babel_route *find_installed_route(const unsigned char *prefix, unsigned char plen); +int installed_routes_estimate(void); void flush_route(struct babel_route *route); +void flush_all_routes(void); void flush_neighbour_routes(struct neighbour *neigh); void flush_interface_routes(struct interface *ifp, int v4only); +void for_all_routes(void (*f)(struct babel_route*, void*), void *closure); +void for_all_installed_routes(void (*f)(struct babel_route*, void*), void *closure); void install_route(struct babel_route *route); void uninstall_route(struct babel_route *route); void switch_route(struct babel_route *old, struct babel_route *new); int route_feasible(struct babel_route *route); int route_old(struct babel_route *route); int route_expired(struct babel_route *route); +int route_interferes(struct babel_route *route, struct interface *ifp); int update_feasible(struct source *src, unsigned short seqno, unsigned short refmetric); struct babel_route *find_best_route(const unsigned char *prefix, unsigned char plen, @@ -87,11 +115,12 @@ struct babel_route *install_best_route(const unsigned char prefix[16], void update_neighbour_metric(struct neighbour *neigh, int change); void update_interface_metric(struct interface *ifp); void update_route_metric(struct babel_route *route); -struct babel_route *update_route(const unsigned char *a, - const unsigned char *p, unsigned char plen, +struct babel_route *update_route(const unsigned char *id, + const unsigned char *prefix, unsigned char plen, unsigned short seqno, unsigned short refmetric, unsigned short interval, struct neighbour *neigh, - const unsigned char *nexthop); + const unsigned char *nexthop, + const unsigned char *channels, int channels_len); void retract_neighbour_routes(struct neighbour *neigh); void send_unfeasible_request(struct neighbour *neigh, int force, unsigned short seqno, unsigned short metric, @@ -103,7 +132,4 @@ void route_changed(struct babel_route *route, void route_lost(struct source *src, unsigned oldmetric); void expire_routes(void); -void babel_uninstall_all_routes(void); -struct babel_route *babel_route_get_by_source(struct source *src); - #endif -- cgit v1.2.1