From af8e7f78af9b13c2cf6615dc9eb6c52c51b2bc2c Mon Sep 17 00:00:00 2001 From: Dimitri Staessens Date: Sun, 16 Feb 2020 13:42:18 +0100 Subject: Add equal-cost multipath routing policy This adds an equal-cost multipath routing policy to Ouroboros, based on Nick Aerts' code. When selected, flows will send packets over all paths with equal cost (hop count). Path selection is round-robin. It does not yet take into account flows that are down. Signed-off-by: Dimitri Staessens Signed-off-by: Sander Vrijders --- src/ipcpd/unicast/CMakeLists.txt | 3 +- src/ipcpd/unicast/pff.c | 5 + src/ipcpd/unicast/pff.h | 3 +- src/ipcpd/unicast/pol/alternate_pff.c | 12 +-- src/ipcpd/unicast/pol/graph.c | 112 +++++++++++++++++++ src/ipcpd/unicast/pol/graph.h | 3 +- src/ipcpd/unicast/pol/link_state.c | 8 +- src/ipcpd/unicast/pol/multipath_pff.c | 198 ++++++++++++++++++++++++++++++++++ src/ipcpd/unicast/pol/multipath_pff.h | 58 ++++++++++ src/ipcpd/unicast/pol/pft.c | 1 + src/ipcpd/unicast/pol/simple_pff.c | 10 +- src/ipcpd/unicast/routing.c | 4 + 12 files changed, 402 insertions(+), 15 deletions(-) create mode 100644 src/ipcpd/unicast/pol/multipath_pff.c create mode 100644 src/ipcpd/unicast/pol/multipath_pff.h (limited to 'src/ipcpd') diff --git a/src/ipcpd/unicast/CMakeLists.txt b/src/ipcpd/unicast/CMakeLists.txt index d6ec4a93..c0c55519 100644 --- a/src/ipcpd/unicast/CMakeLists.txt +++ b/src/ipcpd/unicast/CMakeLists.txt @@ -45,11 +45,12 @@ set(SOURCE_FILES psched.c # Add policies last pol/pft.c - pol/alternate_pff.c pol/flat.c pol/link_state.c pol/graph.c pol/simple_pff.c + pol/alternate_pff.c + pol/multipath_pff.c ) add_executable(ipcpd-unicast ${SOURCE_FILES} ${IPCP_SOURCES} diff --git a/src/ipcpd/unicast/pff.c b/src/ipcpd/unicast/pff.c index 4e380e05..19432972 100644 --- a/src/ipcpd/unicast/pff.c +++ b/src/ipcpd/unicast/pff.c @@ -28,6 +28,7 @@ #include "pff.h" #include "pol-pff-ops.h" #include "pol/alternate_pff.h" +#include "pol/multipath_pff.h" #include "pol/simple_pff.h" struct pff { @@ -52,6 +53,10 @@ struct pff * pff_create(enum pol_pff pol) log_dbg("Using simple PFF policy."); pff->ops = &simple_pff_ops; break; + case PFF_MULTIPATH: + log_dbg("Using multipath PFF policy."); + pff->ops = &multipath_pff_ops; + break; default: goto err; } diff --git a/src/ipcpd/unicast/pff.h b/src/ipcpd/unicast/pff.h index a7b618dc..962ae594 100644 --- a/src/ipcpd/unicast/pff.h +++ b/src/ipcpd/unicast/pff.h @@ -31,7 +31,8 @@ enum pol_pff { PFF_SIMPLE = 0, - PFF_ALTERNATE + PFF_ALTERNATE, + PFF_MULTIPATH }; struct pff * pff_create(enum pol_pff pol); diff --git a/src/ipcpd/unicast/pol/alternate_pff.c b/src/ipcpd/unicast/pol/alternate_pff.c index 80c93f0e..f26bb047 100644 --- a/src/ipcpd/unicast/pol/alternate_pff.c +++ b/src/ipcpd/unicast/pol/alternate_pff.c @@ -27,13 +27,13 @@ #include #include +#include "pft.h" +#include "alternate_pff.h" + #include #include #include -#include "pft.h" -#include "alternate_pff.h" - struct nhop { struct list_head next; int fd; @@ -336,7 +336,7 @@ int alternate_flow_state_change(struct pff_i * pff_i, int fd, bool up) { - struct list_head * pos = NULL; + struct list_head * p; size_t len; int * fds; size_t i; @@ -358,8 +358,8 @@ int alternate_flow_state_change(struct pff_i * pff_i, } } - list_for_each(pos, &pff_i->addrs) { - struct addr * e = list_entry(pos, struct addr, next); + list_for_each(p, &pff_i->addrs) { + struct addr * e = list_entry(p, struct addr, next); if (pft_lookup(pff_i->pft, e->addr, &fds, &len)) { pthread_rwlock_unlock(&pff_i->lock); return -1; diff --git a/src/ipcpd/unicast/pol/graph.c b/src/ipcpd/unicast/pol/graph.c index e76a47fb..1e095ba4 100644 --- a/src/ipcpd/unicast/pol/graph.c +++ b/src/ipcpd/unicast/pol/graph.c @@ -5,6 +5,7 @@ * * Dimitri Staessens * Sander Vrijders + * Nick Aerts * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License version 2 as @@ -697,6 +698,112 @@ static int graph_routing_table_lfa(struct graph * graph, return -1; } +static int graph_routing_table_ecmp(struct graph * graph, + uint64_t s_addr, + struct list_head * table, + int ** dist) +{ + struct vertex ** nhops; + struct list_head * p; + struct list_head * h; + size_t i; + struct vertex * v; + struct vertex * src_v; + struct edge * e; + struct routing_table * t; + struct nhop * n; + struct list_head * forwarding; + + assert(graph); + assert(dist); + + if (graph-> nr_vertices < 2) + goto fail_vertices; + + forwarding = malloc(sizeof(*forwarding) * graph->nr_vertices); + if (forwarding == NULL) + goto fail_vertices; + + for (i = 0; i < graph->nr_vertices; ++i) + list_head_init(&forwarding[i]); + + if (dijkstra(graph, s_addr, &nhops, dist)) + goto fail_dijkstra; + + free(nhops); + + src_v = find_vertex_by_addr(graph, s_addr); + if (src_v == NULL) + goto fail_dijkstra; + + list_for_each(p, &src_v->edges) { + int * tmp_dist; + + e = list_entry(p, struct edge, next); + if (dijkstra(graph, e->nb->addr, &nhops, &tmp_dist)) + goto fail_dijkstra; + + free(nhops); + + list_for_each(h, &graph->vertices) { + v = list_entry(h, struct vertex, next); + if (tmp_dist[v->index] + 1 == (*dist)[v->index]) { + n = malloc(sizeof(*n)); + if (n == NULL) { + free(tmp_dist); + goto fail_dijkstra; + } + n->nhop = e->nb->addr; + list_add_tail(&n->next, &forwarding[v->index]); + } + } + + free(tmp_dist); + } + + list_head_init(table); + i = 0; + list_for_each(p, &graph->vertices) { + v = list_entry(p, struct vertex, next); + if (v->addr == s_addr) { + ++i; + continue; + } + + t = malloc(sizeof(*t)); + if (t == NULL) + goto fail_t; + + t->dst = v->addr; + + list_head_init(&t->nhops); + if (&forwarding[i] != forwarding[i].nxt) { + t->nhops.nxt = forwarding[i].nxt; + t->nhops.prv = forwarding[i].prv; + forwarding[i].prv->nxt = &t->nhops; + forwarding[i].nxt->prv = &t->nhops; + } + + list_add(&t->next, table); + ++i; + } + + free(*dist); + *dist = NULL; + free(forwarding); + + return 0; + + fail_t: + free_routing_table(table); + fail_dijkstra: + free(forwarding); + free(*dist); + fail_vertices: + *dist = NULL; + return -1; +} + int graph_routing_table(struct graph * graph, enum routing_algo algo, uint64_t s_addr, @@ -719,6 +826,11 @@ int graph_routing_table(struct graph * graph, if (graph_routing_table_lfa(graph, s_addr, table, &s_dist)) goto fail_table; break; + + case ROUTING_ECMP: + if (graph_routing_table_ecmp(graph, s_addr, table, &s_dist)) + goto fail_table; + break; default: log_err("Unsupported algorithm."); goto fail_algo; diff --git a/src/ipcpd/unicast/pol/graph.h b/src/ipcpd/unicast/pol/graph.h index b6a9e891..473a5163 100644 --- a/src/ipcpd/unicast/pol/graph.h +++ b/src/ipcpd/unicast/pol/graph.h @@ -30,7 +30,8 @@ enum routing_algo { ROUTING_SIMPLE = 0, - ROUTING_LFA + ROUTING_LFA, + ROUTING_ECMP }; struct nhop { diff --git a/src/ipcpd/unicast/pol/link_state.c b/src/ipcpd/unicast/pol/link_state.c index e2656a98..5360f556 100644 --- a/src/ipcpd/unicast/pol/link_state.c +++ b/src/ipcpd/unicast/pol/link_state.c @@ -934,6 +934,10 @@ int link_state_init(enum pol_routing pr) log_dbg("Using Loop-Free Alternates policy."); ls.routing_algo = ROUTING_LFA; break; + case ROUTING_LINK_STATE_ECMP: + log_dbg("Using Equal-Cost Multipath policy."); + ls.routing_algo = ROUTING_ECMP; + break; default: goto fail_graph; } @@ -974,8 +978,8 @@ int link_state_init(enum pol_routing pr) if (rib_reg(LSDB, &r_ops)) goto fail_rib_reg; - ls.db_len = 0; - ls.nbs_len = 0; + ls.db_len = 0; + ls.nbs_len = 0; return 0; diff --git a/src/ipcpd/unicast/pol/multipath_pff.c b/src/ipcpd/unicast/pol/multipath_pff.c new file mode 100644 index 00000000..8f619006 --- /dev/null +++ b/src/ipcpd/unicast/pol/multipath_pff.c @@ -0,0 +1,198 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2020 + * + * Policy for PFF supporting multipath routing + * + * Dimitri Staessens + * Sander Vrijders + * Nick Aerts + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * This program 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, write to the Free Software + * Foundation, Inc., http://www.fsf.org/about/contact/. + */ + +#define _POSIX_C_SOURCE 200112L + +#include "config.h" + +#include + +#include "pft.h" +#include "multipath_pff.h" + +#include +#include +#include + +struct pff_i { + struct pft * pft; + pthread_rwlock_t lock; +}; + +struct pol_pff_ops multipath_pff_ops = { + .create = multipath_pff_create, + .destroy = multipath_pff_destroy, + .lock = multipath_pff_lock, + .unlock = multipath_pff_unlock, + .add = multipath_pff_add, + .update = multipath_pff_update, + .del = multipath_pff_del, + .flush = multipath_pff_flush, + .nhop = multipath_pff_nhop, + .flow_state_change = NULL +}; + +struct pff_i * multipath_pff_create(void) +{ + struct pff_i * tmp; + + tmp = malloc(sizeof(*tmp)); + if (tmp == NULL) + return NULL; + + if (pthread_rwlock_init(&tmp->lock, NULL)) { + free(tmp); + return NULL; + } + + tmp->pft = pft_create(PFT_SIZE, false); + if (tmp->pft == NULL) { + pthread_rwlock_destroy(&tmp->lock); + free(tmp); + return NULL; + } + + return tmp; +} + +void multipath_pff_destroy(struct pff_i * pff_i) +{ + assert(pff_i); + + pft_destroy(pff_i->pft); + + pthread_rwlock_destroy(&pff_i->lock); + free(pff_i); +} + +void multipath_pff_lock(struct pff_i * pff_i) +{ + pthread_rwlock_wrlock(&pff_i->lock); +} + +void multipath_pff_unlock(struct pff_i * pff_i) +{ + pthread_rwlock_unlock(&pff_i->lock); +} + +int multipath_pff_add(struct pff_i * pff_i, + uint64_t addr, + int * fds, + size_t len) +{ + int * tmp; + + assert(pff_i); + assert(fds); + assert(len > 0); + + tmp = malloc(len * sizeof(*tmp)); + if (tmp == NULL) + return -ENOMEM; + + memcpy(tmp,fds, len * sizeof(*tmp)); + + if (pft_insert(pff_i->pft, addr, tmp, len)) { + free(tmp); + return -1; + } + + return 0; +} + +int multipath_pff_update(struct pff_i * pff_i, + uint64_t addr, + int * fds, + size_t len) +{ + int * tmp; + + assert(pff_i); + assert(fds); + assert(len > 0); + + tmp = malloc(sizeof(*tmp)); + if (fds == NULL) + return -ENOMEM; + + memcpy(tmp,fds, len * sizeof(*tmp)); + + if (pft_delete(pff_i->pft, addr)) { + free(tmp); + return -1; + } + + if (pft_insert(pff_i->pft, addr, fds, 1)) { + free(tmp); + return -1; + } + + return 0; +} + +int multipath_pff_del(struct pff_i * pff_i, + uint64_t addr) +{ + assert(pff_i); + + if (pft_delete(pff_i->pft, addr)) + return -1; + + return 0; +} + +void multipath_pff_flush(struct pff_i * pff_i) +{ + assert(pff_i); + + pft_flush(pff_i->pft); +} + +int multipath_pff_nhop(struct pff_i * pff_i, + uint64_t addr) +{ + int fd; + int * fds; + size_t len; + + assert(pff_i); + + pthread_rwlock_rdlock(&pff_i->lock); + + if (pft_lookup(pff_i->pft, addr, &fds, &len)) { + pthread_rwlock_unlock(&pff_i->lock); + return -1; + } + + fd = *fds; + + assert(len > 0); + + /* Rotate fds left. */ + memcpy(fds, fds + 1, (len - 1) * sizeof(*fds)); + fds[len - 1] = fd; + + pthread_rwlock_unlock(&pff_i->lock); + + return fd; +} diff --git a/src/ipcpd/unicast/pol/multipath_pff.h b/src/ipcpd/unicast/pol/multipath_pff.h new file mode 100644 index 00000000..a8ee088f --- /dev/null +++ b/src/ipcpd/unicast/pol/multipath_pff.h @@ -0,0 +1,58 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2020 + * + * Policy for PFF supporting multipath routing + * + * Dimitri Staessens + * Sander Vrijders + * Nick Aerts + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * This program 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, write to the Free Software + * Foundation, Inc., http://www.fsf.org/about/contact/. + */ + +#ifndef OUROBOROS_IPCPD_UNICAST_MULTIPATH_PFF_H +#define OUROBOROS_IPCPD_UNICAST_MULTIPATH_PFF_H + +#include "pol-pff-ops.h" + +struct pff_i * multipath_pff_create(void); + +void multipath_pff_destroy(struct pff_i * pff_i); + +void multipath_pff_lock(struct pff_i * pff_i); + +void multipath_pff_unlock(struct pff_i * pff_i); + +int multipath_pff_add(struct pff_i * pff_i, + uint64_t addr, + int * fds, + size_t len); + +int multipath_pff_update(struct pff_i * pff_i, + uint64_t addr, + int * fds, + size_t len); + +int multipath_pff_del(struct pff_i * pff_i, + uint64_t addr); + +void multipath_pff_flush(struct pff_i * pff_i); + +/* Returns fd towards next hop */ +int multipath_pff_nhop(struct pff_i * pff_i, + uint64_t addr); + +struct pol_pff_ops multipath_pff_ops; + +#endif /* OUROBOROS_IPCPD_UNICAST_MULTIPATH_PFF_H */ diff --git a/src/ipcpd/unicast/pol/pft.c b/src/ipcpd/unicast/pol/pft.c index 924efbe1..53acc08e 100644 --- a/src/ipcpd/unicast/pol/pft.c +++ b/src/ipcpd/unicast/pol/pft.c @@ -149,6 +149,7 @@ int pft_insert(struct pft * pft, struct list_head * p; assert(pft); + assert(len > 0); lookup_key = calc_key(pft, dst); diff --git a/src/ipcpd/unicast/pol/simple_pff.c b/src/ipcpd/unicast/pol/simple_pff.c index c5780703..5bd73d8a 100644 --- a/src/ipcpd/unicast/pol/simple_pff.c +++ b/src/ipcpd/unicast/pol/simple_pff.c @@ -26,14 +26,14 @@ #include -#include -#include - #include "pft.h" #include "simple_pff.h" +#include +#include + struct pff_i { - struct pft * pft; + struct pft * pft; pthread_rwlock_t lock; }; @@ -101,6 +101,7 @@ int simple_pff_add(struct pff_i * pff_i, int * fds; assert(pff_i); + assert(fd); assert(len > 0); (void) len; @@ -127,6 +128,7 @@ int simple_pff_update(struct pff_i * pff_i, int * fds; assert(pff_i); + assert(fd); assert(len > 0); (void) len; diff --git a/src/ipcpd/unicast/routing.c b/src/ipcpd/unicast/routing.c index 0794555e..0ac43f9f 100644 --- a/src/ipcpd/unicast/routing.c +++ b/src/ipcpd/unicast/routing.c @@ -43,6 +43,10 @@ int routing_init(enum pol_routing pr) pff_type = PFF_ALTERNATE; r_ops = &link_state_ops; break; + case ROUTING_LINK_STATE_ECMP: + pff_type=PFF_MULTIPATH; + r_ops = &link_state_ops; + break; default: return -ENOTSUP; } -- cgit v1.2.3