diff options
Diffstat (limited to '')
| -rw-r--r-- | lib/cspf.c | 646 |
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; +} |