summaryrefslogtreecommitdiff
path: root/src/ipcpd/unicast/pol/graph.c
diff options
context:
space:
mode:
authorDimitri Staessens <dimitri@ouroboros.rocks>2020-02-16 13:42:18 +0100
committerSander Vrijders <sander@ouroboros.rocks>2020-02-16 18:32:21 +0100
commitaf8e7f78af9b13c2cf6615dc9eb6c52c51b2bc2c (patch)
treed9ff5e60b3bf8be2477b46ee98fc441c815cab63 /src/ipcpd/unicast/pol/graph.c
parent52e44a55d3b12819a79566067ff0361854da5002 (diff)
downloadouroboros-af8e7f78af9b13c2cf6615dc9eb6c52c51b2bc2c.tar.gz
ouroboros-af8e7f78af9b13c2cf6615dc9eb6c52c51b2bc2c.zip
Add equal-cost multipath routing policy
This adds an equal-cost multipath routing policy to Ouroboros, based on Nick Aerts' code. When selected, flows will send packets over all paths with equal cost (hop count). Path selection is round-robin. It does not yet take into account flows that are down. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
Diffstat (limited to 'src/ipcpd/unicast/pol/graph.c')
-rw-r--r--src/ipcpd/unicast/pol/graph.c112
1 files changed, 112 insertions, 0 deletions
diff --git a/src/ipcpd/unicast/pol/graph.c b/src/ipcpd/unicast/pol/graph.c
index e76a47fb..1e095ba4 100644
--- a/src/ipcpd/unicast/pol/graph.c
+++ b/src/ipcpd/unicast/pol/graph.c
@@ -5,6 +5,7 @@
*
* Dimitri Staessens <dimitri.staessens@ugent.be>
* Sander Vrijders <sander.vrijders@ugent.be>
+ * Nick Aerts <nick.aerts@ugent.be>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
@@ -697,6 +698,112 @@ static int graph_routing_table_lfa(struct graph * graph,
return -1;
}
+static int graph_routing_table_ecmp(struct graph * graph,
+ uint64_t s_addr,
+ struct list_head * table,
+ int ** dist)
+{
+ struct vertex ** nhops;
+ struct list_head * p;
+ struct list_head * h;
+ size_t i;
+ struct vertex * v;
+ struct vertex * src_v;
+ struct edge * e;
+ struct routing_table * t;
+ struct nhop * n;
+ struct list_head * forwarding;
+
+ assert(graph);
+ assert(dist);
+
+ if (graph-> nr_vertices < 2)
+ goto fail_vertices;
+
+ forwarding = malloc(sizeof(*forwarding) * graph->nr_vertices);
+ if (forwarding == NULL)
+ goto fail_vertices;
+
+ for (i = 0; i < graph->nr_vertices; ++i)
+ list_head_init(&forwarding[i]);
+
+ if (dijkstra(graph, s_addr, &nhops, dist))
+ goto fail_dijkstra;
+
+ free(nhops);
+
+ src_v = find_vertex_by_addr(graph, s_addr);
+ if (src_v == NULL)
+ goto fail_dijkstra;
+
+ list_for_each(p, &src_v->edges) {
+ int * tmp_dist;
+
+ e = list_entry(p, struct edge, next);
+ if (dijkstra(graph, e->nb->addr, &nhops, &tmp_dist))
+ goto fail_dijkstra;
+
+ free(nhops);
+
+ list_for_each(h, &graph->vertices) {
+ v = list_entry(h, struct vertex, next);
+ if (tmp_dist[v->index] + 1 == (*dist)[v->index]) {
+ n = malloc(sizeof(*n));
+ if (n == NULL) {
+ free(tmp_dist);
+ goto fail_dijkstra;
+ }
+ n->nhop = e->nb->addr;
+ list_add_tail(&n->next, &forwarding[v->index]);
+ }
+ }
+
+ free(tmp_dist);
+ }
+
+ list_head_init(table);
+ i = 0;
+ list_for_each(p, &graph->vertices) {
+ v = list_entry(p, struct vertex, next);
+ if (v->addr == s_addr) {
+ ++i;
+ continue;
+ }
+
+ t = malloc(sizeof(*t));
+ if (t == NULL)
+ goto fail_t;
+
+ t->dst = v->addr;
+
+ list_head_init(&t->nhops);
+ if (&forwarding[i] != forwarding[i].nxt) {
+ t->nhops.nxt = forwarding[i].nxt;
+ t->nhops.prv = forwarding[i].prv;
+ forwarding[i].prv->nxt = &t->nhops;
+ forwarding[i].nxt->prv = &t->nhops;
+ }
+
+ list_add(&t->next, table);
+ ++i;
+ }
+
+ free(*dist);
+ *dist = NULL;
+ free(forwarding);
+
+ return 0;
+
+ fail_t:
+ free_routing_table(table);
+ fail_dijkstra:
+ free(forwarding);
+ free(*dist);
+ fail_vertices:
+ *dist = NULL;
+ return -1;
+}
+
int graph_routing_table(struct graph * graph,
enum routing_algo algo,
uint64_t s_addr,
@@ -719,6 +826,11 @@ int graph_routing_table(struct graph * graph,
if (graph_routing_table_lfa(graph, s_addr, table, &s_dist))
goto fail_table;
break;
+
+ case ROUTING_ECMP:
+ if (graph_routing_table_ecmp(graph, s_addr, table, &s_dist))
+ goto fail_table;
+ break;
default:
log_err("Unsupported algorithm.");
goto fail_algo;