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. --- 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 +- 6 files changed, 199 insertions(+), 32 deletions(-) (limited to 'src/ipcpd/normal') 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) -- cgit v1.2.3