From e3dba5812b1422a79e6e77ce9f923bade5a480e4 Mon Sep 17 00:00:00 2001 From: Sander Vrijders Date: Wed, 27 Sep 2017 15:33:39 +0200 Subject: ipcpd: normal: Add Loop-Free Alternates routing This adds the Loop-Free Alternates (LFA) policy. In case a link goes down a LFA may be selected to route the SDUs on without causing loops instead of the main hop that just went down. --- include/ouroboros/ipcp.h | 3 +- src/ipcpd/normal/pol-routing-ops.h | 2 +- src/ipcpd/normal/pol/graph.c | 199 ++++++++++++++++++++++++++++++++----- src/ipcpd/normal/pol/graph.h | 4 + src/ipcpd/normal/pol/link_state.c | 21 +++- src/ipcpd/normal/pol/link_state.h | 2 +- src/ipcpd/normal/routing.c | 3 +- src/tools/irm/irm_ipcp_bootstrap.c | 51 +++++----- 8 files changed, 229 insertions(+), 56 deletions(-) diff --git a/include/ouroboros/ipcp.h b/include/ouroboros/ipcp.h index 1b578fa2..3e682225 100644 --- a/include/ouroboros/ipcp.h +++ b/include/ouroboros/ipcp.h @@ -46,7 +46,8 @@ enum pol_addr_auth { }; enum pol_routing { - ROUTING_LINK_STATE = 0 + ROUTING_LINK_STATE = 0, + ROUTING_LINK_STATE_LFA }; enum pol_pff { diff --git a/src/ipcpd/normal/pol-routing-ops.h b/src/ipcpd/normal/pol-routing-ops.h index 9804d5ad..aa968e9f 100644 --- a/src/ipcpd/normal/pol-routing-ops.h +++ b/src/ipcpd/normal/pol-routing-ops.h @@ -26,7 +26,7 @@ #include "pff.h" struct pol_routing_ops { - int (* init)(void); + int (* init)(enum pol_routing pr); void (* fini)(void); diff --git a/src/ipcpd/normal/pol/graph.c b/src/ipcpd/normal/pol/graph.c index 9e723737..eade23e0 100644 --- a/src/ipcpd/normal/pol/graph.c +++ b/src/ipcpd/normal/pol/graph.c @@ -379,37 +379,43 @@ static int get_min_vertex(struct graph * graph, return index; } -static struct vertex ** dijkstra(struct graph * graph, - uint64_t src) +static int dijkstra(struct graph * graph, + uint64_t src, + struct vertex *** nhops, + int ** dist) { - int dist[graph->nr_vertices]; bool used[graph->nr_vertices]; struct list_head * p = NULL; int i = 0; struct vertex * v = NULL; struct edge * e = NULL; int alt; - struct vertex ** nhop; - nhop = malloc(sizeof(*nhop) * graph->nr_vertices); - if (nhop == NULL) - return NULL; + *nhops = malloc(sizeof(**nhops) * graph->nr_vertices); + if (*nhops == NULL) + return -1; + + *dist = malloc(sizeof(**dist) * graph->nr_vertices); + if (*dist == NULL) { + free(*nhops); + return -1; + } /* Init the data structures */ list_for_each(p, &graph->vertices) { v = list_entry(p, struct vertex, next); if (v->addr == src) - dist[i] = 0; + (*dist)[i] = 0; else - dist[i] = INT_MAX; + (*dist)[i] = INT_MAX; - nhop[i] = NULL; + (*nhops)[i] = NULL; used[i] = false; i++; } /* Perform actual Dijkstra */ - i = get_min_vertex(graph, dist, used, &v); + i = get_min_vertex(graph, *dist, used, &v); while (v != NULL) { list_for_each(p, &v->edges) { e = list_entry(p, struct edge, next); @@ -423,19 +429,19 @@ static struct vertex ** dijkstra(struct graph * graph, * Method could be extended to use a different * weight for a different QoS cube. */ - alt = dist[i] + 1; - if (alt < dist[e->nb->index]) { - dist[e->nb->index] = alt; + alt = (*dist)[i] + 1; + if (alt < (*dist)[e->nb->index]) { + (*dist)[e->nb->index] = alt; if (v->addr == src) - nhop[e->nb->index] = e->nb; + (*nhops)[e->nb->index] = e->nb; else - nhop[e->nb->index] = nhop[i]; + (*nhops)[e->nb->index] = (*nhops)[i]; } } - i = get_min_vertex(graph, dist, used, &v); + i = get_min_vertex(graph, *dist, used, &v); } - return nhop; + return 0; } static void free_routing_table(struct list_head * table) @@ -471,9 +477,10 @@ void graph_free_routing_table(struct graph * graph, pthread_mutex_unlock(&graph->lock); } -int graph_routing_table(struct graph * graph, - uint64_t s_addr, - struct list_head * table) +static int graph_routing_table_simple(struct graph * graph, + uint64_t s_addr, + struct list_head * table, + int ** dist) { struct vertex ** nhops; struct list_head * p; @@ -482,14 +489,11 @@ int graph_routing_table(struct graph * graph, struct routing_table * t; struct nhop * n; - pthread_mutex_lock(&graph->lock); - /* We need at least 2 vertices for a table */ if (graph->nr_vertices < 2) goto fail_vertices; - nhops = dijkstra(graph, s_addr); - if (nhops == NULL) + if (dijkstra(graph, s_addr, &nhops, dist)) goto fail_vertices; list_head_init(table); @@ -523,8 +527,6 @@ int graph_routing_table(struct graph * graph, i++; } - pthread_mutex_unlock(&graph->lock); - free(nhops); return 0; @@ -535,6 +537,149 @@ int graph_routing_table(struct graph * graph, free_routing_table(table); free(nhops); fail_vertices: + return -1; +} + +int graph_routing_table(struct graph * graph, + uint64_t s_addr, + struct list_head * table) +{ + int ret = 0; + int * dist; + + assert(graph); + assert(table); + + pthread_mutex_lock(&graph->lock); + + ret = graph_routing_table_simple(graph, s_addr, table, &dist); + + free(dist); + pthread_mutex_unlock(&graph->lock); + + return ret; +} + +static int add_lfa_to_table(struct list_head * table, + uint64_t addr, + uint64_t lfa) +{ + struct list_head * p = NULL; + struct nhop * n; + + n = malloc(sizeof(*n)); + if (n == NULL) + return -1; + + n->nhop = lfa; + + list_for_each(p, table) { + struct routing_table * t = + list_entry(p, struct routing_table, next); + if (t->dst == addr) { + list_add_tail(&n->next, &t->nhops); + return 0; + } + } + + return -1; +} + +int graph_routing_table_lfa(struct graph * graph, + uint64_t s_addr, + struct list_head * table) +{ + int * s_dist; + int * n_dist[AP_MAX_FLOWS]; + uint64_t addrs[AP_MAX_FLOWS]; + int n_index[AP_MAX_FLOWS]; + struct list_head * p; + struct list_head * q; + struct vertex * v; + struct edge * e; + struct vertex ** nhops; + int i = 0; + int j = 0; + int k; + + assert(graph); + assert(table); + + pthread_mutex_lock(&graph->lock); + + for (j = 0; j < AP_MAX_FLOWS; j++) { + n_dist[i] = NULL; + n_index[i] = -1; + addrs[i] = -1; + } + + /* Get the normal next hops routing table. */ + if (graph_routing_table_simple(graph, s_addr, table, &s_dist)) + goto fail_table_simple; + + list_for_each(p, &graph->vertices) { + v = list_entry(p, struct vertex, next); + + if (v->addr != s_addr) + continue; + + /* Get the distances for every neighbor of the source. */ + list_for_each(q, &v->edges) { + e = list_entry(q, struct edge, next); + + addrs[i] = e->nb->addr; + n_index[i] = e->nb->index; + if (dijkstra(graph, e->nb->addr, + &nhops, &(n_dist[i++]))) + goto fail_dijkstra; + + free(nhops); + } + + break; + } + + /* Loop though all nodes to see if we have a LFA for them. */ + list_for_each(p, &graph->vertices) { + v = list_entry(p, struct vertex, next); + + if (v->addr == s_addr) + continue; + + /* + * Check for every neighbor if dist(neighbor, destination) < + * dist(neighbor, source) + dist(source, destination). + */ + for (j = 0; j < i; j++) { + /* Exclude ourselves. */ + if (addrs[j] == v->addr) + continue; + + if (n_dist[j][v->index] < + s_dist[n_index[j]] + s_dist[v->index]) { + if (add_lfa_to_table(table, v->addr, addrs[j])) + goto fail_add_lfa; + } + + free(n_dist[j]); + } + } + + pthread_mutex_unlock(&graph->lock); + + free(s_dist); + + return 0; + + fail_add_lfa: + for (k = j; k < i; k++) + free(n_dist[k]); + fail_dijkstra: + free_routing_table(table); + free(s_dist); + fail_table_simple: + pthread_mutex_unlock(&graph->lock); + return -1; } diff --git a/src/ipcpd/normal/pol/graph.h b/src/ipcpd/normal/pol/graph.h index 7340ecb9..66c8f780 100644 --- a/src/ipcpd/normal/pol/graph.h +++ b/src/ipcpd/normal/pol/graph.h @@ -56,6 +56,10 @@ int graph_routing_table(struct graph * graph, uint64_t s_addr, struct list_head * table); +int graph_routing_table_lfa(struct graph * graph, + uint64_t s_addr, + struct list_head * table); + void graph_free_routing_table(struct graph * graph, struct list_head * table); diff --git a/src/ipcpd/normal/pol/link_state.c b/src/ipcpd/normal/pol/link_state.c index 51d317bc..6330cf81 100644 --- a/src/ipcpd/normal/pol/link_state.c +++ b/src/ipcpd/normal/pol/link_state.c @@ -89,6 +89,10 @@ struct nb { enum nb_type type; }; +typedef int (* rtable_fn_t)(struct graph * graph, + uint64_t s_addr, + struct list_head * table); + struct { struct list_head nbs; fset_t * mgmt_set; @@ -103,6 +107,8 @@ struct { pthread_t lsupdate; pthread_t lsreader; pthread_t listener; + + rtable_fn_t rtable; } ls; struct pol_routing_ops link_state_ops = { @@ -388,7 +394,7 @@ static void * calculate_pff(void * o) instance = (struct routing_i *) o; while (true) { - if (graph_routing_table(ls.graph, ipcpi.dt_addr, &table)) { + if (ls.rtable(ls.graph, ipcpi.dt_addr, &table)) { sleep(RECALC_TIME); continue; } @@ -664,7 +670,7 @@ void link_state_routing_i_destroy(struct routing_i * instance) free(instance); } -int link_state_init(void) +int link_state_init(enum pol_routing pr) { struct conn_info info; @@ -676,6 +682,17 @@ int link_state_init(void) info.pref_syntax = PROTO_GPB; info.addr = ipcpi.dt_addr; + switch (pr) { + case ROUTING_LINK_STATE: + ls.rtable = graph_routing_table; + break; + case ROUTING_LINK_STATE_LFA: + ls.rtable = graph_routing_table_lfa; + break; + default: + goto fail_graph; + } + ls.graph = graph_create(); if (ls.graph == NULL) goto fail_graph; diff --git a/src/ipcpd/normal/pol/link_state.h b/src/ipcpd/normal/pol/link_state.h index 58f90d91..cfdeb09d 100644 --- a/src/ipcpd/normal/pol/link_state.h +++ b/src/ipcpd/normal/pol/link_state.h @@ -28,7 +28,7 @@ #include "pol-routing-ops.h" -int link_state_init(void); +int link_state_init(enum pol_routing pr); void link_state_fini(void); diff --git a/src/ipcpd/normal/routing.c b/src/ipcpd/normal/routing.c index afef23a2..909f74cc 100644 --- a/src/ipcpd/normal/routing.c +++ b/src/ipcpd/normal/routing.c @@ -33,13 +33,14 @@ int routing_init(enum pol_routing pr) { switch (pr) { case ROUTING_LINK_STATE: + case ROUTING_LINK_STATE_LFA: r_ops = &link_state_ops; break; default: return -ENOTSUP; } - return r_ops->init(); + return r_ops->init(pr); } struct routing_i * routing_i_create(struct pff * pff) diff --git a/src/tools/irm/irm_ipcp_bootstrap.c b/src/tools/irm/irm_ipcp_bootstrap.c index 9812f860..26b86a16 100644 --- a/src/tools/irm/irm_ipcp_bootstrap.c +++ b/src/tools/irm/irm_ipcp_bootstrap.c @@ -33,28 +33,29 @@ #include "irm_ops.h" #include "irm_utils.h" -#define NORMAL "normal" -#define SHIM_UDP "shim-udp" -#define SHIM_ETH_LLC "shim-eth-llc" -#define LOCAL "local" - -#define MD5 "MD5" -#define SHA3_224 "SHA3_224" -#define SHA3_256 "SHA3_256" -#define SHA3_384 "SHA3_384" -#define SHA3_512 "SHA3_512" - -#define DEFAULT_ADDR_SIZE 4 -#define DEFAULT_FD_SIZE 2 -#define DEFAULT_DDNS 0 -#define DEFAULT_ADDR_AUTH ADDR_AUTH_FLAT_RANDOM -#define DEFAULT_ROUTING ROUTING_LINK_STATE -#define DEFAULT_PFF PFF_SIMPLE -#define DEFAULT_HASH_ALGO DIR_HASH_SHA3_256 -#define FLAT_RANDOM_ADDR_AUTH "flat" -#define LINK_STATE_ROUTING "link_state" -#define SIMPLE_PFF "simple" -#define ALTERNATE_PFF "alternate" +#define NORMAL "normal" +#define SHIM_UDP "shim-udp" +#define SHIM_ETH_LLC "shim-eth-llc" +#define LOCAL "local" + +#define MD5 "MD5" +#define SHA3_224 "SHA3_224" +#define SHA3_256 "SHA3_256" +#define SHA3_384 "SHA3_384" +#define SHA3_512 "SHA3_512" + +#define DEFAULT_ADDR_SIZE 4 +#define DEFAULT_FD_SIZE 2 +#define DEFAULT_DDNS 0 +#define DEFAULT_ADDR_AUTH ADDR_AUTH_FLAT_RANDOM +#define DEFAULT_ROUTING ROUTING_LINK_STATE +#define DEFAULT_PFF PFF_SIMPLE +#define DEFAULT_HASH_ALGO DIR_HASH_SHA3_256 +#define FLAT_RANDOM_ADDR_AUTH "flat" +#define LINK_STATE_ROUTING "link_state" +#define LINK_STATE_LFA_ROUTING "lfa" +#define SIMPLE_PFF "simple" +#define ALTERNATE_PFF "alternate" static void usage(void) { @@ -74,7 +75,8 @@ static void usage(void) " [pff [PFF_POLICY] (default: %s)]\n" " [hash [ALGORITHM] (default: %s)]\n" "where ADDRESS_POLICY = {"FLAT_RANDOM_ADDR_AUTH"}\n" - " ROUTING_POLICY = {"LINK_STATE_ROUTING"}\n" + " ROUTING_POLICY = {"LINK_STATE_ROUTING " " + LINK_STATE_LFA_ROUTING "}\n" " PFF_POLICY = {" SIMPLE_PFF " " ALTERNATE_PFF "}\n" " ALGORITHM = {" SHA3_224 " " SHA3_256 " " SHA3_384 " " SHA3_512 "}\n\n" @@ -151,6 +153,9 @@ int do_bootstrap_ipcp(int argc, char ** argv) } else if (matches(*argv, "routing") == 0) { if (strcmp(LINK_STATE_ROUTING, *(argv + 1)) == 0) routing_type = ROUTING_LINK_STATE; + else if (strcmp(LINK_STATE_LFA_ROUTING, + *(argv + 1)) == 0) + routing_type = ROUTING_LINK_STATE_LFA; else goto unknown_param; } else if (matches(*argv, "pff") == 0) { -- cgit v1.2.3