summaryrefslogtreecommitdiff
path: root/src/ipcpd/normal/pol/graph.c
diff options
context:
space:
mode:
authorSander Vrijders <sander.vrijders@ugent.be>2017-09-29 13:20:20 +0000
committerdimitri staessens <dimitri.staessens@ugent.be>2017-09-29 13:20:20 +0000
commit5e974395fadc5e1922f200855c14ca0538ba50dc (patch)
treebc3808da222d245ab0aecf9d73e22eed5bfb6fd7 /src/ipcpd/normal/pol/graph.c
parentddba836eb79ace3bd80ea6af69801f402cbffd20 (diff)
parent39c7f82f4714f8515860d1c0e2726bff29e22944 (diff)
downloadouroboros-5e974395fadc5e1922f200855c14ca0538ba50dc.tar.gz
ouroboros-5e974395fadc5e1922f200855c14ca0538ba50dc.zip
Merged in sandervrijders/ouroboros/be-lfas (pull request #620)
ipcpd: normal: Add Loop-Free Alternates routing
Diffstat (limited to 'src/ipcpd/normal/pol/graph.c')
-rw-r--r--src/ipcpd/normal/pol/graph.c199
1 files changed, 172 insertions, 27 deletions
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;
}