]>
git.proxmox.com Git - mirror_frr.git/blob - lib/cspf.c
2 * Constraints Shortest Path First algorithms - cspf.c
4 * Author: Olivier Dugeon <olivier.dugeon@orange.com>
6 * Copyright (C) 2022 Orange http://www.orange.com
8 * This file is part of Free Range Routing (FRR).
10 * FRR is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by the
12 * Free Software Foundation; either version 2, or (at your option) any
15 * FRR is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * General Public License for more details.
20 * You should have received a copy of the GNU General Public License along
21 * with this program; see the file COPYING; if not, write to the Free Software
22 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
36 #include "link_state.h"
39 /* Link State Memory allocation */
40 DEFINE_MTYPE_STATIC(LIB
, PCA
, "Path Computation Algorithms");
43 * Create new Constrained Path. Memory is dynamically allocated.
45 * @param key Vertex key of the destination of this path
47 * @return Pointer to a new Constrained Path structure
49 static struct c_path
*cpath_new(uint64_t key
)
57 path
= XCALLOC(MTYPE_PCA
, sizeof(struct c_path
));
59 path
->status
= IN_PROGRESS
;
60 path
->edges
= list_new();
61 path
->weight
= MAX_COST
;
67 * Copy src Constrained Path into dst Constrained Path. A new Constrained Path
68 * structure is dynamically allocated if dst is NULL. If src is NULL, the
69 * function return the dst disregarding if it is NULL or not.
71 * @param dest Destination Constrained Path structure
72 * @param src Source Constrained Path structure
74 * @return Pointer to the destination Constrained Path structure
76 static struct c_path
*cpath_copy(struct c_path
*dest
, const struct c_path
*src
)
78 struct c_path
*new_path
;
84 new_path
= XCALLOC(MTYPE_PCA
, sizeof(struct c_path
));
88 list_delete(&new_path
->edges
);
91 new_path
->dst
= src
->dst
;
92 new_path
->weight
= src
->weight
;
93 new_path
->edges
= list_dup(src
->edges
);
94 new_path
->status
= src
->status
;
100 * Delete Constrained Path structure. Previous allocated memory is freed.
102 * @param path Constrained Path structure to be deleted
104 static void cpath_del(struct c_path
*path
)
110 list_delete(&path
->edges
);
112 XFREE(MTYPE_PCA
, path
);
117 * Replace the list of edges in the next Constrained Path by the list of edges
118 * in the current Constrained Path.
120 * @param next_path next Constrained Path structure
121 * @param cur_path current Constrained Path structure
123 static void cpath_replace(struct c_path
*next_path
, struct c_path
*cur_path
)
126 if (next_path
->edges
)
127 list_delete(&next_path
->edges
);
129 next_path
->edges
= list_dup(cur_path
->edges
);
133 * Create a new Visited Node structure from the provided Vertex. Structure is
134 * dynamically allocated.
136 * @param vertex Vertex structure
138 * @return Pointer to the new Visited Node structure
140 static struct v_node
*vnode_new(struct ls_vertex
*vertex
)
142 struct v_node
*vnode
;
147 vnode
= XCALLOC(MTYPE_PCA
, sizeof(struct v_node
));
148 vnode
->vertex
= vertex
;
149 vnode
->key
= vertex
->key
;
155 * Delete Visited Node structure. Previous allocated memory is freed.
157 * @param vnode Visited Node structure to be deleted
159 static void vnode_del(struct v_node
*vnode
)
164 XFREE(MTYPE_PCA
, vnode
);
169 * Search Vertex in TED by IPv4 address. The function search vertex by browsing
170 * the subnets table. It allows to find not only vertex by router ID, but also
171 * vertex by interface IPv4 address.
173 * @param ted Traffic Engineering Database
174 * @param ipv4 IPv4 address
176 * @return Vertex if found, NULL otherwise
178 static struct ls_vertex
*get_vertex_by_ipv4(struct ls_ted
*ted
,
181 struct ls_subnet
*subnet
;
187 frr_each (subnets
, &ted
->subnets
, subnet
) {
188 if (subnet
->key
.family
!= AF_INET
)
190 p
.prefixlen
= subnet
->key
.prefixlen
;
191 if (prefix_same(&subnet
->key
, &p
))
192 return subnet
->vertex
;
199 * Search Vertex in TED by IPv6 address. The function search vertex by browsing
200 * the subnets table. It allows to find not only vertex by router ID, but also
201 * vertex by interface IPv6 address.
203 * @param ted Traffic Engineering Database
204 * @param ipv6 IPv6 address
206 * @return Vertex if found, NULL otherwise
208 static struct ls_vertex
*get_vertex_by_ipv6(struct ls_ted
*ted
,
209 struct in6_addr ipv6
)
211 struct ls_subnet
*subnet
;
217 frr_each (subnets
, &ted
->subnets
, subnet
) {
218 if (subnet
->key
.family
!= AF_INET6
)
220 p
.prefixlen
= subnet
->key
.prefixlen
;
221 if (prefix_cmp(&subnet
->key
, &p
) == 0)
222 return subnet
->vertex
;
228 struct cspf
*cspf_new(void)
232 /* Allocate New CSPF structure */
233 algo
= XCALLOC(MTYPE_PCA
, sizeof(struct cspf
));
235 /* Initialize RB-Trees */
236 processed_init(&algo
->processed
);
237 visited_init(&algo
->visited
);
238 pqueue_init(&algo
->pqueue
);
246 struct cspf
*cspf_init(struct cspf
*algo
, const struct ls_vertex
*src
,
247 const struct ls_vertex
*dst
, struct constraints
*csts
)
249 struct cspf
*new_algo
;
256 new_algo
= cspf_new();
260 /* Initialize Processed Path and Priority Queue with Src & Dst */
262 psrc
= cpath_new(src
->key
);
264 processed_add(&new_algo
->processed
, psrc
);
265 pqueue_add(&new_algo
->pqueue
, psrc
);
266 new_algo
->path
= psrc
;
269 new_algo
->pdst
= cpath_new(dst
->key
);
270 processed_add(&new_algo
->processed
, new_algo
->pdst
);
273 memcpy(&new_algo
->csts
, csts
, sizeof(struct constraints
));
278 struct cspf
*cspf_init_v4(struct cspf
*algo
, struct ls_ted
*ted
,
279 const struct in_addr src
, const struct in_addr dst
,
280 struct constraints
*csts
)
282 struct ls_vertex
*vsrc
;
283 struct ls_vertex
*vdst
;
284 struct cspf
*new_algo
;
291 new_algo
= cspf_new();
295 /* Got Source and Destination Vertex from TED */
296 vsrc
= get_vertex_by_ipv4(ted
, src
);
297 vdst
= get_vertex_by_ipv4(ted
, dst
);
298 csts
->family
= AF_INET
;
300 return cspf_init(new_algo
, vsrc
, vdst
, csts
);
303 struct cspf
*cspf_init_v6(struct cspf
*algo
, struct ls_ted
*ted
,
304 const struct in6_addr src
, const struct in6_addr dst
,
305 struct constraints
*csts
)
307 struct ls_vertex
*vsrc
;
308 struct ls_vertex
*vdst
;
309 struct cspf
*new_algo
;
316 new_algo
= cspf_new();
320 /* Got Source and Destination Vertex from TED */
321 vsrc
= get_vertex_by_ipv6(ted
, src
);
322 vdst
= get_vertex_by_ipv6(ted
, dst
);
323 csts
->family
= AF_INET6
;
325 return cspf_init(new_algo
, vsrc
, vdst
, csts
);
328 void cspf_clean(struct cspf
*algo
)
331 struct v_node
*vnode
;
336 /* Normally, Priority Queue is empty. Clean it in case of. */
337 if (pqueue_count(&algo
->pqueue
)) {
338 frr_each_safe (pqueue
, &algo
->pqueue
, path
) {
339 pqueue_del(&algo
->pqueue
, path
);
343 /* Empty Processed Path tree and associated Path */
344 if (processed_count(&algo
->processed
)) {
345 frr_each_safe (processed
, &algo
->processed
, path
) {
346 processed_del(&algo
->processed
, path
);
351 /* Empty visited Vertex tree and associated Node */
352 if (visited_count(&algo
->visited
)) {
353 frr_each_safe (visited
, &algo
->visited
, vnode
) {
354 visited_del(&algo
->visited
, vnode
);
359 memset(&algo
->csts
, 0, sizeof(struct constraints
));
364 void cspf_del(struct cspf
*algo
)
369 /* Empty Priority Queue and Processes Path */
372 /* Then, reset Priority Queue, Processed Path and Visited RB-Tree */
373 pqueue_fini(&algo
->pqueue
);
374 processed_fini(&algo
->processed
);
375 visited_fini(&algo
->visited
);
377 XFREE(MTYPE_PCA
, algo
);
382 * Prune Edge if constraints are not met by testing Edge Attributes against
383 * given constraints and cumulative cost of the given constrained path.
385 * @param path On-going Computed Path with cumulative cost constraints
386 * @param edge Edge to be validate against Constraints
387 * @param csts Constraints for this path
389 * @return True if Edge should be prune, false if Edge is valid
391 static bool prune_edge(const struct c_path
*path
, const struct ls_edge
*edge
,
392 const struct constraints
*csts
)
394 struct ls_vertex
*dst
;
395 struct ls_attributes
*attr
;
397 /* Check that Path, Edge and Constraints are valid */
398 if (!path
|| !edge
|| !csts
)
401 /* Check that Edge has a valid destination */
402 if (!edge
->destination
)
404 dst
= edge
->destination
;
406 /* Check that Edge has valid attributes */
407 if (!edge
->attributes
)
409 attr
= edge
->attributes
;
411 /* Check that Edge belongs to the requested Address Family and type */
412 if (csts
->family
== AF_INET
) {
413 if (IPV4_NET0(attr
->standard
.local
.s_addr
))
415 if (csts
->type
== SR_TE
)
416 if (!CHECK_FLAG(attr
->flags
, LS_ATTR_ADJ_SID
) ||
417 !CHECK_FLAG(dst
->node
->flags
, LS_NODE_SR
))
420 if (csts
->family
== AF_INET6
) {
421 if (IN6_IS_ADDR_UNSPECIFIED(&attr
->standard
.local6
))
423 if (csts
->type
== SR_TE
)
424 if (!CHECK_FLAG(attr
->flags
, LS_ATTR_ADJ_SID6
) ||
425 !CHECK_FLAG(dst
->node
->flags
, LS_NODE_SR
))
430 * Check that total cost, up to this edge, respects the initial
433 switch (csts
->ctype
) {
435 if (!CHECK_FLAG(attr
->flags
, LS_ATTR_METRIC
))
437 if ((attr
->metric
+ path
->weight
) > csts
->cost
)
442 if (!CHECK_FLAG(attr
->flags
, LS_ATTR_TE_METRIC
))
444 if ((attr
->standard
.te_metric
+ path
->weight
) > csts
->cost
)
449 if (!CHECK_FLAG(attr
->flags
, LS_ATTR_DELAY
))
451 if ((attr
->extended
.delay
+ path
->weight
) > csts
->cost
)
456 /* If specified, check that Edge meet Bandwidth constraint */
457 if (csts
->bw
> 0.0) {
458 if (attr
->standard
.max_bw
< csts
->bw
||
459 attr
->standard
.max_rsv_bw
< csts
->bw
||
460 attr
->standard
.unrsv_bw
[csts
->cos
] < csts
->bw
)
464 /* All is fine. We can consider this Edge valid, so not to be prune */
469 * Relax constraints of the current path up to the destination vertex of the
470 * provided Edge. This function progress in the network topology by validating
471 * the next vertex on the computed path. If Vertex has not already been visited,
472 * list of edges of the current path is augmented with this edge if the new cost
473 * is lower than prior path up to this vertex. Current path is re-inserted in
474 * the Priority Queue with its new cost i.e. current cost + edge cost.
476 * @param algo CSPF structure
477 * @param edge Next Edge to be added to the current computed path
479 * @return True if current path reach destination, false otherwise
481 static bool relax_constraints(struct cspf
*algo
, struct ls_edge
*edge
)
484 struct c_path pkey
= {};
485 struct c_path
*next_path
;
486 struct v_node vnode
= {};
487 uint32_t total_cost
= MAX_COST
;
489 /* Verify that we have a current computed path */
493 /* Verify if we have not visited the next Vertex to avoid loop */
494 vnode
.key
= edge
->destination
->key
;
495 if (visited_member(&algo
->visited
, &vnode
)) {
500 * Get Next Computed Path from next vertex key
501 * or create a new one if it has not yet computed.
503 pkey
.dst
= edge
->destination
->key
;
504 next_path
= processed_find(&algo
->processed
, &pkey
);
506 next_path
= cpath_new(pkey
.dst
);
507 processed_add(&algo
->processed
, next_path
);
511 * Add or update the Computed Path in the Priority Queue if total cost
512 * is lower than cost associated to this next Vertex. This could occurs
513 * if we process a Vertex that as not yet been visited in the Graph
514 * or if we found a shortest path up to this Vertex.
516 switch (algo
->csts
.ctype
) {
518 total_cost
= edge
->attributes
->metric
+ algo
->path
->weight
;
521 total_cost
= edge
->attributes
->standard
.te_metric
+
526 edge
->attributes
->extended
.delay
+ algo
->path
->weight
;
531 if (total_cost
< next_path
->weight
) {
533 * It is not possible to directly update the q_path in the
534 * Priority Queue. Indeed, if we modify the path weight, the
535 * Priority Queue must be re-ordered. So, we need fist to remove
536 * the q_path if it is present in the Priority Queue, then,
537 * update the Path, in particular the Weight, and finally
538 * (re-)insert it in the Priority Queue.
541 frr_each_safe (pqueue
, &algo
->pqueue
, path
) {
542 if (path
->dst
== pkey
.dst
) {
543 pqueue_del(&algo
->pqueue
, path
);
547 next_path
->weight
= total_cost
;
548 cpath_replace(next_path
, algo
->path
);
549 listnode_add(next_path
->edges
, edge
);
550 pqueue_add(&algo
->pqueue
, next_path
);
553 /* Return True if we reach the destination */
554 return (next_path
->dst
== algo
->pdst
->dst
);
557 struct c_path
*compute_p2p_path(struct cspf
*algo
, struct ls_ted
*ted
)
559 struct listnode
*node
;
560 struct ls_vertex
*vertex
;
561 struct ls_edge
*edge
;
562 struct c_path
*optim_path
;
563 struct v_node
*vnode
;
566 optim_path
= cpath_new(0xFFFFFFFFFFFFFFFF);
567 optim_path
->status
= FAILED
;
569 /* Check that all is correctly initialized */
573 if (!algo
->csts
.ctype
)
577 optim_path
->status
= NO_DESTINATION
;
582 optim_path
->status
= NO_SOURCE
;
586 if (algo
->pdst
->dst
== algo
->path
->dst
) {
587 optim_path
->status
= SAME_SRC_DST
;
591 optim_path
->dst
= algo
->pdst
->dst
;
592 optim_path
->status
= IN_PROGRESS
;
595 * Process all Connected Vertex until priority queue becomes empty.
596 * Connected Vertices are added into the priority queue when
597 * processing the next Connected Vertex: see relax_constraints()
600 while (pqueue_count(&algo
->pqueue
) != 0) {
601 /* Got shortest current Path from the Priority Queue */
602 algo
->path
= pqueue_pop(&algo
->pqueue
);
604 /* Add destination Vertex of this path to the visited RB Tree */
605 vertex
= ls_find_vertex_by_key(ted
, algo
->path
->dst
);
608 vnode
= vnode_new(vertex
);
609 visited_add(&algo
->visited
, vnode
);
611 /* Process all outgoing links from this Vertex */
612 for (ALL_LIST_ELEMENTS_RO(vertex
->outgoing_edges
, node
, edge
)) {
614 * Skip Connected Edges that must be prune i.e.
615 * Edges that not satisfy the given constraints,
616 * in particular the Bandwidth, TE Metric and Delay.
618 if (prune_edge(algo
->path
, edge
, &algo
->csts
))
622 * Relax constraints and check if we got a shorter
625 if (relax_constraints(algo
, edge
) &&
626 algo
->pdst
->weight
< cur_cost
) {
627 cur_cost
= algo
->pdst
->weight
;
628 cpath_copy(optim_path
, algo
->pdst
);
629 optim_path
->status
= SUCCESS
;
635 * The priority queue is empty => all the possible (vertex, path)
636 * elements have been explored. The optim_path contains the optimal
637 * path if it exists. Otherwise an empty path with status failed is
640 if (optim_path
->status
== IN_PROGRESS
||
641 listcount(optim_path
->edges
) == 0)
642 optim_path
->status
= FAILED
;