summaryrefslogtreecommitdiff
path: root/src/ipcpd/normal/pol/graph.c
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/ipcpd/normal/pol/graph.c
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/ipcpd/normal/pol/graph.c')
-rw-r--r--src/ipcpd/normal/pol/graph.c127
1 files changed, 62 insertions, 65 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);