summaryrefslogtreecommitdiffstats
path: root/lib/cspf.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--lib/cspf.c646
1 files changed, 646 insertions, 0 deletions
diff --git a/lib/cspf.c b/lib/cspf.c
new file mode 100644
index 0000000..ef3e7c2
--- /dev/null
+++ b/lib/cspf.c
@@ -0,0 +1,646 @@
+/*
+ * Constraints Shortest Path First algorithms - cspf.c
+ *
+ * Author: Olivier Dugeon <olivier.dugeon@orange.com>
+ *
+ * Copyright (C) 2022 Orange http://www.orange.com
+ *
+ * This file is part of Free Range Routing (FRR).
+ *
+ * FRR is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2, or (at your option) any
+ * later version.
+ *
+ * FRR is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; see the file COPYING; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <zebra.h>
+
+#include "if.h"
+#include "linklist.h"
+#include "log.h"
+#include "hash.h"
+#include "memory.h"
+#include "prefix.h"
+#include "table.h"
+#include "stream.h"
+#include "printfrr.h"
+#include "link_state.h"
+#include "cspf.h"
+
+/* Link State Memory allocation */
+DEFINE_MTYPE_STATIC(LIB, PCA, "Path Computation Algorithms");
+
+/**
+ * Create new Constrained Path. Memory is dynamically allocated.
+ *
+ * @param key Vertex key of the destination of this path
+ *
+ * @return Pointer to a new Constrained Path structure
+ */
+static struct c_path *cpath_new(uint64_t key)
+{
+ struct c_path *path;
+
+ /* Sanity Check */
+ if (key == 0)
+ return NULL;
+
+ path = XCALLOC(MTYPE_PCA, sizeof(struct c_path));
+ path->dst = key;
+ path->status = IN_PROGRESS;
+ path->edges = list_new();
+ path->weight = MAX_COST;
+
+ return path;
+}
+
+/**
+ * Copy src Constrained Path into dst Constrained Path. A new Constrained Path
+ * structure is dynamically allocated if dst is NULL. If src is NULL, the
+ * function return the dst disregarding if it is NULL or not.
+ *
+ * @param dest Destination Constrained Path structure
+ * @param src Source Constrained Path structure
+ *
+ * @return Pointer to the destination Constrained Path structure
+ */
+static struct c_path *cpath_copy(struct c_path *dest, const struct c_path *src)
+{
+ struct c_path *new_path;
+
+ if (!src)
+ return dest;
+
+ if (!dest) {
+ new_path = XCALLOC(MTYPE_PCA, sizeof(struct c_path));
+ } else {
+ new_path = dest;
+ if (dest->edges)
+ list_delete(&new_path->edges);
+ }
+
+ new_path->dst = src->dst;
+ new_path->weight = src->weight;
+ new_path->edges = list_dup(src->edges);
+ new_path->status = src->status;
+
+ return new_path;
+}
+
+/**
+ * Delete Constrained Path structure. Previous allocated memory is freed.
+ *
+ * @param path Constrained Path structure to be deleted
+ */
+static void cpath_del(struct c_path *path)
+{
+ if (!path)
+ return;
+
+ if (path->edges)
+ list_delete(&path->edges);
+
+ XFREE(MTYPE_PCA, path);
+ path = NULL;
+}
+
+/**
+ * Replace the list of edges in the next Constrained Path by the list of edges
+ * in the current Constrained Path.
+ *
+ * @param next_path next Constrained Path structure
+ * @param cur_path current Constrained Path structure
+ */
+static void cpath_replace(struct c_path *next_path, struct c_path *cur_path)
+{
+
+ if (next_path->edges)
+ list_delete(&next_path->edges);
+
+ next_path->edges = list_dup(cur_path->edges);
+}
+
+/**
+ * Create a new Visited Node structure from the provided Vertex. Structure is
+ * dynamically allocated.
+ *
+ * @param vertex Vertex structure
+ *
+ * @return Pointer to the new Visited Node structure
+ */
+static struct v_node *vnode_new(struct ls_vertex *vertex)
+{
+ struct v_node *vnode;
+
+ if (!vertex)
+ return NULL;
+
+ vnode = XCALLOC(MTYPE_PCA, sizeof(struct v_node));
+ vnode->vertex = vertex;
+ vnode->key = vertex->key;
+
+ return vnode;
+}
+
+/**
+ * Delete Visited Node structure. Previous allocated memory is freed.
+ *
+ * @param vnode Visited Node structure to be deleted
+ */
+static void vnode_del(struct v_node *vnode)
+{
+ if (!vnode)
+ return;
+
+ XFREE(MTYPE_PCA, vnode);
+ vnode = NULL;
+}
+
+/**
+ * Search Vertex in TED by IPv4 address. The function search vertex by browsing
+ * the subnets table. It allows to find not only vertex by router ID, but also
+ * vertex by interface IPv4 address.
+ *
+ * @param ted Traffic Engineering Database
+ * @param ipv4 IPv4 address
+ *
+ * @return Vertex if found, NULL otherwise
+ */
+static struct ls_vertex *get_vertex_by_ipv4(struct ls_ted *ted,
+ struct in_addr ipv4)
+{
+ struct ls_subnet *subnet;
+ struct prefix p;
+
+ p.family = AF_INET;
+ p.u.prefix4 = ipv4;
+
+ frr_each (subnets, &ted->subnets, subnet) {
+ if (subnet->key.family != AF_INET)
+ continue;
+ p.prefixlen = subnet->key.prefixlen;
+ if (prefix_same(&subnet->key, &p))
+ return subnet->vertex;
+ }
+
+ return NULL;
+}
+
+/**
+ * Search Vertex in TED by IPv6 address. The function search vertex by browsing
+ * the subnets table. It allows to find not only vertex by router ID, but also
+ * vertex by interface IPv6 address.
+ *
+ * @param ted Traffic Engineering Database
+ * @param ipv6 IPv6 address
+ *
+ * @return Vertex if found, NULL otherwise
+ */
+static struct ls_vertex *get_vertex_by_ipv6(struct ls_ted *ted,
+ struct in6_addr ipv6)
+{
+ struct ls_subnet *subnet;
+ struct prefix p;
+
+ p.family = AF_INET6;
+ p.u.prefix6 = ipv6;
+
+ frr_each (subnets, &ted->subnets, subnet) {
+ if (subnet->key.family != AF_INET6)
+ continue;
+ p.prefixlen = subnet->key.prefixlen;
+ if (prefix_cmp(&subnet->key, &p) == 0)
+ return subnet->vertex;
+ }
+
+ return NULL;
+}
+
+struct cspf *cspf_new(void)
+{
+ struct cspf *algo;
+
+ /* Allocate New CSPF structure */
+ algo = XCALLOC(MTYPE_PCA, sizeof(struct cspf));
+
+ /* Initialize RB-Trees */
+ processed_init(&algo->processed);
+ visited_init(&algo->visited);
+ pqueue_init(&algo->pqueue);
+
+ algo->path = NULL;
+ algo->pdst = NULL;
+
+ return algo;
+}
+
+struct cspf *cspf_init(struct cspf *algo, const struct ls_vertex *src,
+ const struct ls_vertex *dst, struct constraints *csts)
+{
+ struct cspf *new_algo;
+ struct c_path *psrc;
+
+ if (!csts)
+ return NULL;
+
+ if (!algo)
+ new_algo = cspf_new();
+ else
+ new_algo = algo;
+
+ /* Initialize Processed Path and Priority Queue with Src & Dst */
+ if (src) {
+ psrc = cpath_new(src->key);
+ psrc->weight = 0;
+ processed_add(&new_algo->processed, psrc);
+ pqueue_add(&new_algo->pqueue, psrc);
+ new_algo->path = psrc;
+ }
+ if (dst) {
+ new_algo->pdst = cpath_new(dst->key);
+ processed_add(&new_algo->processed, new_algo->pdst);
+ }
+
+ memcpy(&new_algo->csts, csts, sizeof(struct constraints));
+
+ return new_algo;
+}
+
+struct cspf *cspf_init_v4(struct cspf *algo, struct ls_ted *ted,
+ const struct in_addr src, const struct in_addr dst,
+ struct constraints *csts)
+{
+ struct ls_vertex *vsrc;
+ struct ls_vertex *vdst;
+ struct cspf *new_algo;
+
+ /* Sanity Check */
+ if (!ted)
+ return algo;
+
+ if (!algo)
+ new_algo = cspf_new();
+ else
+ new_algo = algo;
+
+ /* Got Source and Destination Vertex from TED */
+ vsrc = get_vertex_by_ipv4(ted, src);
+ vdst = get_vertex_by_ipv4(ted, dst);
+ csts->family = AF_INET;
+
+ return cspf_init(new_algo, vsrc, vdst, csts);
+}
+
+struct cspf *cspf_init_v6(struct cspf *algo, struct ls_ted *ted,
+ const struct in6_addr src, const struct in6_addr dst,
+ struct constraints *csts)
+{
+ struct ls_vertex *vsrc;
+ struct ls_vertex *vdst;
+ struct cspf *new_algo;
+
+ /* Sanity Check */
+ if (!ted)
+ return algo;
+
+ if (!algo)
+ new_algo = cspf_new();
+ else
+ new_algo = algo;
+
+ /* Got Source and Destination Vertex from TED */
+ vsrc = get_vertex_by_ipv6(ted, src);
+ vdst = get_vertex_by_ipv6(ted, dst);
+ csts->family = AF_INET6;
+
+ return cspf_init(new_algo, vsrc, vdst, csts);
+}
+
+void cspf_clean(struct cspf *algo)
+{
+ struct c_path *path;
+ struct v_node *vnode;
+
+ if (!algo)
+ return;
+
+ /* Normally, Priority Queue is empty. Clean it in case of. */
+ if (pqueue_count(&algo->pqueue)) {
+ frr_each_safe (pqueue, &algo->pqueue, path) {
+ pqueue_del(&algo->pqueue, path);
+ }
+ }
+
+ /* Empty Processed Path tree and associated Path */
+ if (processed_count(&algo->processed)) {
+ frr_each_safe (processed, &algo->processed, path) {
+ processed_del(&algo->processed, path);
+ cpath_del(path);
+ }
+ }
+
+ /* Empty visited Vertex tree and associated Node */
+ if (visited_count(&algo->visited)) {
+ frr_each_safe (visited, &algo->visited, vnode) {
+ visited_del(&algo->visited, vnode);
+ vnode_del(vnode);
+ }
+ }
+
+ memset(&algo->csts, 0, sizeof(struct constraints));
+ algo->path = NULL;
+ algo->pdst = NULL;
+}
+
+void cspf_del(struct cspf *algo)
+{
+ if (!algo)
+ return;
+
+ /* Empty Priority Queue and Processes Path */
+ cspf_clean(algo);
+
+ /* Then, reset Priority Queue, Processed Path and Visited RB-Tree */
+ pqueue_fini(&algo->pqueue);
+ processed_fini(&algo->processed);
+ visited_fini(&algo->visited);
+
+ XFREE(MTYPE_PCA, algo);
+ algo = NULL;
+}
+
+/**
+ * Prune Edge if constraints are not met by testing Edge Attributes against
+ * given constraints and cumulative cost of the given constrained path.
+ *
+ * @param path On-going Computed Path with cumulative cost constraints
+ * @param edge Edge to be validate against Constraints
+ * @param csts Constraints for this path
+ *
+ * @return True if Edge should be prune, false if Edge is valid
+ */
+static bool prune_edge(const struct c_path *path, const struct ls_edge *edge,
+ const struct constraints *csts)
+{
+ struct ls_vertex *dst;
+ struct ls_attributes *attr;
+
+ /* Check that Path, Edge and Constraints are valid */
+ if (!path || !edge || !csts)
+ return true;
+
+ /* Check that Edge has a valid destination */
+ if (!edge->destination)
+ return true;
+ dst = edge->destination;
+
+ /* Check that Edge has valid attributes */
+ if (!edge->attributes)
+ return true;
+ attr = edge->attributes;
+
+ /* Check that Edge belongs to the requested Address Family and type */
+ if (csts->family == AF_INET) {
+ if (IPV4_NET0(attr->standard.local.s_addr))
+ return true;
+ if (csts->type == SR_TE)
+ if (!CHECK_FLAG(attr->flags, LS_ATTR_ADJ_SID) ||
+ !CHECK_FLAG(dst->node->flags, LS_NODE_SR))
+ return true;
+ }
+ if (csts->family == AF_INET6) {
+ if (IN6_IS_ADDR_UNSPECIFIED(&attr->standard.local6))
+ return true;
+ if (csts->type == SR_TE)
+ if (!CHECK_FLAG(attr->flags, LS_ATTR_ADJ_SID6) ||
+ !CHECK_FLAG(dst->node->flags, LS_NODE_SR))
+ return true;
+ }
+
+ /*
+ * Check that total cost, up to this edge, respects the initial
+ * constraints
+ */
+ switch (csts->ctype) {
+ case CSPF_METRIC:
+ if (!CHECK_FLAG(attr->flags, LS_ATTR_METRIC))
+ return true;
+ if ((attr->metric + path->weight) > csts->cost)
+ return true;
+ break;
+
+ case CSPF_TE_METRIC:
+ if (!CHECK_FLAG(attr->flags, LS_ATTR_TE_METRIC))
+ return true;
+ if ((attr->standard.te_metric + path->weight) > csts->cost)
+ return true;
+ break;
+
+ case CSPF_DELAY:
+ if (!CHECK_FLAG(attr->flags, LS_ATTR_DELAY))
+ return true;
+ if ((attr->extended.delay + path->weight) > csts->cost)
+ return true;
+ break;
+ }
+
+ /* If specified, check that Edge meet Bandwidth constraint */
+ if (csts->bw > 0.0) {
+ if (attr->standard.max_bw < csts->bw ||
+ attr->standard.max_rsv_bw < csts->bw ||
+ attr->standard.unrsv_bw[csts->cos] < csts->bw)
+ return true;
+ }
+
+ /* All is fine. We can consider this Edge valid, so not to be prune */
+ return false;
+}
+
+/**
+ * Relax constraints of the current path up to the destination vertex of the
+ * provided Edge. This function progress in the network topology by validating
+ * the next vertex on the computed path. If Vertex has not already been visited,
+ * list of edges of the current path is augmented with this edge if the new cost
+ * is lower than prior path up to this vertex. Current path is re-inserted in
+ * the Priority Queue with its new cost i.e. current cost + edge cost.
+ *
+ * @param algo CSPF structure
+ * @param edge Next Edge to be added to the current computed path
+ *
+ * @return True if current path reach destination, false otherwise
+ */
+static bool relax_constraints(struct cspf *algo, struct ls_edge *edge)
+{
+
+ struct c_path pkey = {};
+ struct c_path *next_path;
+ struct v_node vnode = {};
+ uint32_t total_cost = MAX_COST;
+
+ /* Verify that we have a current computed path */
+ if (!algo->path)
+ return false;
+
+ /* Verify if we have not visited the next Vertex to avoid loop */
+ vnode.key = edge->destination->key;
+ if (visited_member(&algo->visited, &vnode)) {
+ return false;
+ }
+
+ /*
+ * Get Next Computed Path from next vertex key
+ * or create a new one if it has not yet computed.
+ */
+ pkey.dst = edge->destination->key;
+ next_path = processed_find(&algo->processed, &pkey);
+ if (!next_path) {
+ next_path = cpath_new(pkey.dst);
+ processed_add(&algo->processed, next_path);
+ }
+
+ /*
+ * Add or update the Computed Path in the Priority Queue if total cost
+ * is lower than cost associated to this next Vertex. This could occurs
+ * if we process a Vertex that as not yet been visited in the Graph
+ * or if we found a shortest path up to this Vertex.
+ */
+ switch (algo->csts.ctype) {
+ case CSPF_METRIC:
+ total_cost = edge->attributes->metric + algo->path->weight;
+ break;
+ case CSPF_TE_METRIC:
+ total_cost = edge->attributes->standard.te_metric +
+ algo->path->weight;
+ break;
+ case CSPF_DELAY:
+ total_cost =
+ edge->attributes->extended.delay + algo->path->weight;
+ break;
+ default:
+ break;
+ }
+ if (total_cost < next_path->weight) {
+ /*
+ * It is not possible to directly update the q_path in the
+ * Priority Queue. Indeed, if we modify the path weight, the
+ * Priority Queue must be re-ordered. So, we need fist to remove
+ * the q_path if it is present in the Priority Queue, then,
+ * update the Path, in particular the Weight, and finally
+ * (re-)insert it in the Priority Queue.
+ */
+ struct c_path *path;
+ frr_each_safe (pqueue, &algo->pqueue, path) {
+ if (path->dst == pkey.dst) {
+ pqueue_del(&algo->pqueue, path);
+ break;
+ }
+ }
+ next_path->weight = total_cost;
+ cpath_replace(next_path, algo->path);
+ listnode_add(next_path->edges, edge);
+ pqueue_add(&algo->pqueue, next_path);
+ }
+
+ /* Return True if we reach the destination */
+ return (next_path->dst == algo->pdst->dst);
+}
+
+struct c_path *compute_p2p_path(struct cspf *algo, struct ls_ted *ted)
+{
+ struct listnode *node;
+ struct ls_vertex *vertex;
+ struct ls_edge *edge;
+ struct c_path *optim_path;
+ struct v_node *vnode;
+ uint32_t cur_cost;
+
+ optim_path = cpath_new(0xFFFFFFFFFFFFFFFF);
+ optim_path->status = FAILED;
+
+ /* Check that all is correctly initialized */
+ if (!algo)
+ return optim_path;
+
+ if (!algo->csts.ctype)
+ return optim_path;
+
+ if (!algo->pdst) {
+ optim_path->status = NO_DESTINATION;
+ return optim_path;
+ }
+
+ if (!algo->path) {
+ optim_path->status = NO_SOURCE;
+ return optim_path;
+ }
+
+ if (algo->pdst->dst == algo->path->dst) {
+ optim_path->status = SAME_SRC_DST;
+ return optim_path;
+ }
+
+ optim_path->dst = algo->pdst->dst;
+ optim_path->status = IN_PROGRESS;
+
+ /*
+ * Process all Connected Vertex until priority queue becomes empty.
+ * Connected Vertices are added into the priority queue when
+ * processing the next Connected Vertex: see relax_constraints()
+ */
+ cur_cost = MAX_COST;
+ while (pqueue_count(&algo->pqueue) != 0) {
+ /* Got shortest current Path from the Priority Queue */
+ algo->path = pqueue_pop(&algo->pqueue);
+
+ /* Add destination Vertex of this path to the visited RB Tree */
+ vertex = ls_find_vertex_by_key(ted, algo->path->dst);
+ if (!vertex)
+ continue;
+ vnode = vnode_new(vertex);
+ visited_add(&algo->visited, vnode);
+
+ /* Process all outgoing links from this Vertex */
+ for (ALL_LIST_ELEMENTS_RO(vertex->outgoing_edges, node, edge)) {
+ /*
+ * Skip Connected Edges that must be prune i.e.
+ * Edges that not satisfy the given constraints,
+ * in particular the Bandwidth, TE Metric and Delay.
+ */
+ if (prune_edge(algo->path, edge, &algo->csts))
+ continue;
+
+ /*
+ * Relax constraints and check if we got a shorter
+ * candidate path
+ */
+ if (relax_constraints(algo, edge) &&
+ algo->pdst->weight < cur_cost) {
+ cur_cost = algo->pdst->weight;
+ cpath_copy(optim_path, algo->pdst);
+ optim_path->status = SUCCESS;
+ }
+ }
+ }
+
+ /*
+ * The priority queue is empty => all the possible (vertex, path)
+ * elements have been explored. The optim_path contains the optimal
+ * path if it exists. Otherwise an empty path with status failed is
+ * returned.
+ */
+ if (optim_path->status == IN_PROGRESS ||
+ listcount(optim_path->edges) == 0)
+ optim_path->status = FAILED;
+ cspf_clean(algo);
+
+ return optim_path;
+}