summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorSander Vrijders <sander.vrijders@ugent.be>2018-09-14 09:47:39 +0200
committerDimitri Staessens <dimitri.staessens@ugent.be>2018-09-14 10:15:55 +0200
commita0ea1751683d7fb242b9a8076b05058f21dfe052 (patch)
tree436c8fb4832b15b4b06af56ee0303a47ccb48aa7 /src
parent1c7dcc2d37dc5a41379ca08b523bda58a51f11de (diff)
downloadouroboros-a0ea1751683d7fb242b9a8076b05058f21dfe052.tar.gz
ouroboros-a0ea1751683d7fb242b9a8076b05058f21dfe052.zip
ipcpd: Simplify routing algorithm selection
Previously there was a separate function per routing algorithm selection, when in fact the algorithms all take as input a graph and output a routing table, making it possible to place them in a single function. Signed-off-by: Sander Vrijders <sander.vrijders@ugent.be> Signed-off-by: Dimitri Staessens <dimitri.staessens@ugent.be>
Diffstat (limited to 'src')
-rw-r--r--src/ipcpd/normal/pol/graph.c127
-rw-r--r--src/ipcpd/normal/pol/graph.h10
-rw-r--r--src/ipcpd/normal/pol/link_state.c37
3 files changed, 85 insertions, 89 deletions
diff --git a/src/ipcpd/normal/pol/graph.c b/src/ipcpd/normal/pol/graph.c
index f3c053ab..544f0403 100644
--- a/src/ipcpd/normal/pol/graph.c
+++ b/src/ipcpd/normal/pol/graph.c
@@ -547,27 +547,6 @@ static int graph_routing_table_simple(struct graph * graph,
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)
@@ -595,9 +574,10 @@ static int add_lfa_to_table(struct list_head * table,
return -1;
}
-int graph_routing_table_lfa(struct graph * graph,
- uint64_t s_addr,
- struct list_head * table)
+int graph_routing_table(struct graph * graph,
+ enum routing_algo algo,
+ uint64_t s_addr,
+ struct list_head * table)
{
int * s_dist;
int * n_dist[PROG_MAX_FLOWS];
@@ -617,66 +597,82 @@ int graph_routing_table_lfa(struct graph * graph,
pthread_mutex_lock(&graph->lock);
- for (j = 0; j < PROG_MAX_FLOWS; j++) {
- n_dist[j] = NULL;
- n_index[j] = -1;
- addrs[j] = -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);
+ /* Possibly augment the routing table. */
+ switch (algo) {
+ case ROUTING_SIMPLE:
+ break;
+ case ROUTING_LFA:
+ for (j = 0; j < PROG_MAX_FLOWS; j++) {
+ n_dist[j] = NULL;
+ n_index[j] = -1;
+ addrs[j] = -1;
+ }
- if (v->addr != s_addr)
- continue;
+ list_for_each(p, &graph->vertices) {
+ v = list_entry(p, struct vertex, next);
- /* Get the distances for every neighbor of the source. */
- list_for_each(q, &v->edges) {
- e = list_entry(q, struct edge, next);
+ if (v->addr != s_addr)
+ continue;
- addrs[i] = e->nb->addr;
- n_index[i] = e->nb->index;
- if (dijkstra(graph, e->nb->addr,
- &nhops, &(n_dist[i++])))
- goto fail_dijkstra;
+ /*
+ * Get the distances for every neighbor
+ * of the source.
+ */
+ list_for_each(q, &v->edges) {
+ e = list_entry(q, struct edge, next);
- free(nhops);
- }
+ addrs[i] = e->nb->addr;
+ n_index[i] = e->nb->index;
+ if (dijkstra(graph, e->nb->addr,
+ &nhops, &(n_dist[i++])))
+ goto fail_dijkstra;
- break;
- }
+ free(nhops);
+ }
- /* 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);
+ break;
+ }
- if (v->addr == s_addr)
- continue;
+ /* 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);
- /*
- * 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)
+ if (v->addr == s_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;
+ /*
+ * 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;
+ }
}
+
+ for (j = 0; j < i; j++)
+ free(n_dist[j]);
+
+ break;
+ default:
+ log_err("Unsupported algorithm.");
+ goto fail_algo;
}
pthread_mutex_unlock(&graph->lock);
- for (j = 0; j < i; j++)
- free(n_dist[j]);
-
free(s_dist);
return 0;
@@ -686,6 +682,7 @@ int graph_routing_table_lfa(struct graph * graph,
free(n_dist[k]);
fail_dijkstra:
free_routing_table(table);
+ fail_algo:
free(s_dist);
fail_table_simple:
pthread_mutex_unlock(&graph->lock);
diff --git a/src/ipcpd/normal/pol/graph.h b/src/ipcpd/normal/pol/graph.h
index 13657fd0..7cd14ad6 100644
--- a/src/ipcpd/normal/pol/graph.h
+++ b/src/ipcpd/normal/pol/graph.h
@@ -28,6 +28,11 @@
#include <inttypes.h>
+enum routing_algo {
+ ROUTING_SIMPLE = 0,
+ ROUTING_LFA
+};
+
struct nhop {
struct list_head next;
uint64_t nhop;
@@ -53,13 +58,10 @@ int graph_del_edge(struct graph * graph,
uint64_t d_addr);
int graph_routing_table(struct graph * graph,
+ enum routing_algo algo,
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 1c418ffc..59bae616 100644
--- a/src/ipcpd/normal/pol/link_state.c
+++ b/src/ipcpd/normal/pol/link_state.c
@@ -101,30 +101,26 @@ 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;
- size_t nbs_len;
- fset_t * mgmt_set;
+ struct list_head nbs;
+ size_t nbs_len;
+ fset_t * mgmt_set;
- struct list_head db;
- size_t db_len;
+ struct list_head db;
+ size_t db_len;
- pthread_rwlock_t db_lock;
+ pthread_rwlock_t db_lock;
- struct graph * graph;
+ struct graph * graph;
- pthread_t lsupdate;
- pthread_t lsreader;
- pthread_t listener;
+ pthread_t lsupdate;
+ pthread_t lsreader;
+ pthread_t listener;
- struct list_head routing_instances;
- pthread_mutex_t routing_i_lock;
+ struct list_head routing_instances;
+ pthread_mutex_t routing_i_lock;
- rtable_fn_t rtable;
+ enum routing_algo routing_algo;
} ls;
struct pol_routing_ops link_state_ops = {
@@ -500,7 +496,8 @@ static void calculate_pff(struct routing_i * instance)
struct list_head * q;
int fds[PROG_MAX_FLOWS];
- if (ls.rtable(ls.graph, ipcpi.dt_addr, &table))
+ if (graph_routing_table(ls.graph, ls.routing_algo,
+ ipcpi.dt_addr, &table))
return;
pff_lock(instance->pff);
@@ -902,11 +899,11 @@ int link_state_init(enum pol_routing pr)
switch (pr) {
case ROUTING_LINK_STATE:
log_dbg("Using link state routing policy.");
- ls.rtable = graph_routing_table;
+ ls.routing_algo = ROUTING_SIMPLE;
break;
case ROUTING_LINK_STATE_LFA:
log_dbg("Using Loop-Free Alternates policy.");
- ls.rtable = graph_routing_table_lfa;
+ ls.routing_algo = ROUTING_LFA;
break;
default:
goto fail_graph;