Line data Source code
1 : /*
2 : * Constraints Shortest Path First algorithms - cspf.c
3 : *
4 : * Author: Olivier Dugeon <olivier.dugeon@orange.com>
5 : *
6 : * Copyright (C) 2022 Orange http://www.orange.com
7 : *
8 : * This file is part of Free Range Routing (FRR).
9 : *
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
13 : * later version.
14 : *
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.
19 : *
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
23 : */
24 :
25 : #include <zebra.h>
26 :
27 : #include "if.h"
28 : #include "linklist.h"
29 : #include "log.h"
30 : #include "hash.h"
31 : #include "memory.h"
32 : #include "prefix.h"
33 : #include "table.h"
34 : #include "stream.h"
35 : #include "printfrr.h"
36 : #include "link_state.h"
37 : #include "cspf.h"
38 :
39 : /* Link State Memory allocation */
40 12 : DEFINE_MTYPE_STATIC(LIB, PCA, "Path Computation Algorithms");
41 :
42 : /**
43 : * Create new Constrained Path. Memory is dynamically allocated.
44 : *
45 : * @param key Vertex key of the destination of this path
46 : *
47 : * @return Pointer to a new Constrained Path structure
48 : */
49 0 : static struct c_path *cpath_new(uint64_t key)
50 : {
51 0 : struct c_path *path;
52 :
53 : /* Sanity Check */
54 0 : if (key == 0)
55 : return NULL;
56 :
57 0 : path = XCALLOC(MTYPE_PCA, sizeof(struct c_path));
58 0 : path->dst = key;
59 0 : path->status = IN_PROGRESS;
60 0 : path->edges = list_new();
61 0 : path->weight = MAX_COST;
62 :
63 0 : return path;
64 : }
65 :
66 : /**
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.
70 : *
71 : * @param dest Destination Constrained Path structure
72 : * @param src Source Constrained Path structure
73 : *
74 : * @return Pointer to the destination Constrained Path structure
75 : */
76 0 : static struct c_path *cpath_copy(struct c_path *dest, const struct c_path *src)
77 : {
78 0 : struct c_path *new_path;
79 :
80 0 : if (!src)
81 : return dest;
82 :
83 0 : if (!dest) {
84 0 : new_path = XCALLOC(MTYPE_PCA, sizeof(struct c_path));
85 : } else {
86 0 : new_path = dest;
87 0 : if (dest->edges)
88 0 : list_delete(&new_path->edges);
89 : }
90 :
91 0 : new_path->dst = src->dst;
92 0 : new_path->weight = src->weight;
93 0 : new_path->edges = list_dup(src->edges);
94 0 : new_path->status = src->status;
95 :
96 0 : return new_path;
97 : }
98 :
99 : /**
100 : * Delete Constrained Path structure. Previous allocated memory is freed.
101 : *
102 : * @param path Constrained Path structure to be deleted
103 : */
104 0 : static void cpath_del(struct c_path *path)
105 : {
106 0 : if (!path)
107 : return;
108 :
109 0 : if (path->edges)
110 0 : list_delete(&path->edges);
111 :
112 0 : XFREE(MTYPE_PCA, path);
113 0 : path = NULL;
114 : }
115 :
116 : /**
117 : * Replace the list of edges in the next Constrained Path by the list of edges
118 : * in the current Constrained Path.
119 : *
120 : * @param next_path next Constrained Path structure
121 : * @param cur_path current Constrained Path structure
122 : */
123 0 : static void cpath_replace(struct c_path *next_path, struct c_path *cur_path)
124 : {
125 :
126 0 : if (next_path->edges)
127 0 : list_delete(&next_path->edges);
128 :
129 0 : next_path->edges = list_dup(cur_path->edges);
130 0 : }
131 :
132 : /**
133 : * Create a new Visited Node structure from the provided Vertex. Structure is
134 : * dynamically allocated.
135 : *
136 : * @param vertex Vertex structure
137 : *
138 : * @return Pointer to the new Visited Node structure
139 : */
140 0 : static struct v_node *vnode_new(struct ls_vertex *vertex)
141 : {
142 0 : struct v_node *vnode;
143 :
144 0 : if (!vertex)
145 : return NULL;
146 :
147 0 : vnode = XCALLOC(MTYPE_PCA, sizeof(struct v_node));
148 0 : vnode->vertex = vertex;
149 0 : vnode->key = vertex->key;
150 :
151 0 : return vnode;
152 : }
153 :
154 : /**
155 : * Delete Visited Node structure. Previous allocated memory is freed.
156 : *
157 : * @param vnode Visited Node structure to be deleted
158 : */
159 0 : static void vnode_del(struct v_node *vnode)
160 : {
161 0 : if (!vnode)
162 : return;
163 :
164 0 : XFREE(MTYPE_PCA, vnode);
165 0 : vnode = NULL;
166 : }
167 :
168 : /**
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.
172 : *
173 : * @param ted Traffic Engineering Database
174 : * @param ipv4 IPv4 address
175 : *
176 : * @return Vertex if found, NULL otherwise
177 : */
178 0 : static struct ls_vertex *get_vertex_by_ipv4(struct ls_ted *ted,
179 : struct in_addr ipv4)
180 : {
181 0 : struct ls_subnet *subnet;
182 0 : struct prefix p;
183 :
184 0 : p.family = AF_INET;
185 0 : p.u.prefix4 = ipv4;
186 :
187 0 : frr_each (subnets, &ted->subnets, subnet) {
188 0 : if (subnet->key.family != AF_INET)
189 0 : continue;
190 0 : p.prefixlen = subnet->key.prefixlen;
191 0 : if (prefix_same(&subnet->key, &p))
192 0 : return subnet->vertex;
193 : }
194 :
195 : return NULL;
196 : }
197 :
198 : /**
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.
202 : *
203 : * @param ted Traffic Engineering Database
204 : * @param ipv6 IPv6 address
205 : *
206 : * @return Vertex if found, NULL otherwise
207 : */
208 0 : static struct ls_vertex *get_vertex_by_ipv6(struct ls_ted *ted,
209 : struct in6_addr ipv6)
210 : {
211 0 : struct ls_subnet *subnet;
212 0 : struct prefix p;
213 :
214 0 : p.family = AF_INET6;
215 0 : p.u.prefix6 = ipv6;
216 :
217 0 : frr_each (subnets, &ted->subnets, subnet) {
218 0 : if (subnet->key.family != AF_INET6)
219 0 : continue;
220 0 : p.prefixlen = subnet->key.prefixlen;
221 0 : if (prefix_cmp(&subnet->key, &p) == 0)
222 0 : return subnet->vertex;
223 : }
224 :
225 : return NULL;
226 : }
227 :
228 0 : struct cspf *cspf_new(void)
229 : {
230 0 : struct cspf *algo;
231 :
232 : /* Allocate New CSPF structure */
233 0 : algo = XCALLOC(MTYPE_PCA, sizeof(struct cspf));
234 :
235 : /* Initialize RB-Trees */
236 0 : processed_init(&algo->processed);
237 0 : visited_init(&algo->visited);
238 0 : pqueue_init(&algo->pqueue);
239 :
240 0 : algo->path = NULL;
241 0 : algo->pdst = NULL;
242 :
243 0 : return algo;
244 : }
245 :
246 0 : struct cspf *cspf_init(struct cspf *algo, const struct ls_vertex *src,
247 : const struct ls_vertex *dst, struct constraints *csts)
248 : {
249 0 : struct cspf *new_algo;
250 0 : struct c_path *psrc;
251 :
252 0 : if (!csts)
253 : return NULL;
254 :
255 0 : if (!algo)
256 0 : new_algo = cspf_new();
257 : else
258 : new_algo = algo;
259 :
260 : /* Initialize Processed Path and Priority Queue with Src & Dst */
261 0 : if (src) {
262 0 : psrc = cpath_new(src->key);
263 0 : psrc->weight = 0;
264 0 : processed_add(&new_algo->processed, psrc);
265 0 : pqueue_add(&new_algo->pqueue, psrc);
266 0 : new_algo->path = psrc;
267 : }
268 0 : if (dst) {
269 0 : new_algo->pdst = cpath_new(dst->key);
270 0 : processed_add(&new_algo->processed, new_algo->pdst);
271 : }
272 :
273 0 : memcpy(&new_algo->csts, csts, sizeof(struct constraints));
274 :
275 0 : return new_algo;
276 : }
277 :
278 0 : 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)
281 : {
282 0 : struct ls_vertex *vsrc;
283 0 : struct ls_vertex *vdst;
284 0 : struct cspf *new_algo;
285 :
286 : /* Sanity Check */
287 0 : if (!ted)
288 : return algo;
289 :
290 0 : if (!algo)
291 0 : new_algo = cspf_new();
292 : else
293 : new_algo = algo;
294 :
295 : /* Got Source and Destination Vertex from TED */
296 0 : vsrc = get_vertex_by_ipv4(ted, src);
297 0 : vdst = get_vertex_by_ipv4(ted, dst);
298 0 : csts->family = AF_INET;
299 :
300 0 : return cspf_init(new_algo, vsrc, vdst, csts);
301 : }
302 :
303 0 : 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)
306 : {
307 0 : struct ls_vertex *vsrc;
308 0 : struct ls_vertex *vdst;
309 0 : struct cspf *new_algo;
310 :
311 : /* Sanity Check */
312 0 : if (!ted)
313 : return algo;
314 :
315 0 : if (!algo)
316 0 : new_algo = cspf_new();
317 : else
318 : new_algo = algo;
319 :
320 : /* Got Source and Destination Vertex from TED */
321 0 : vsrc = get_vertex_by_ipv6(ted, src);
322 0 : vdst = get_vertex_by_ipv6(ted, dst);
323 0 : csts->family = AF_INET6;
324 :
325 0 : return cspf_init(new_algo, vsrc, vdst, csts);
326 : }
327 :
328 0 : void cspf_clean(struct cspf *algo)
329 : {
330 0 : struct c_path *path;
331 0 : struct v_node *vnode;
332 :
333 0 : if (!algo)
334 : return;
335 :
336 : /* Normally, Priority Queue is empty. Clean it in case of. */
337 0 : if (pqueue_count(&algo->pqueue)) {
338 0 : frr_each_safe (pqueue, &algo->pqueue, path) {
339 0 : pqueue_del(&algo->pqueue, path);
340 : }
341 : }
342 :
343 : /* Empty Processed Path tree and associated Path */
344 0 : if (processed_count(&algo->processed)) {
345 0 : frr_each_safe (processed, &algo->processed, path) {
346 0 : processed_del(&algo->processed, path);
347 0 : cpath_del(path);
348 : }
349 : }
350 :
351 : /* Empty visited Vertex tree and associated Node */
352 0 : if (visited_count(&algo->visited)) {
353 0 : frr_each_safe (visited, &algo->visited, vnode) {
354 0 : visited_del(&algo->visited, vnode);
355 0 : vnode_del(vnode);
356 : }
357 : }
358 :
359 0 : memset(&algo->csts, 0, sizeof(struct constraints));
360 0 : algo->path = NULL;
361 0 : algo->pdst = NULL;
362 : }
363 :
364 0 : void cspf_del(struct cspf *algo)
365 : {
366 0 : if (!algo)
367 : return;
368 :
369 : /* Empty Priority Queue and Processes Path */
370 0 : cspf_clean(algo);
371 :
372 : /* Then, reset Priority Queue, Processed Path and Visited RB-Tree */
373 0 : pqueue_fini(&algo->pqueue);
374 0 : processed_fini(&algo->processed);
375 0 : visited_fini(&algo->visited);
376 :
377 0 : XFREE(MTYPE_PCA, algo);
378 0 : algo = NULL;
379 : }
380 :
381 : /**
382 : * Prune Edge if constraints are not met by testing Edge Attributes against
383 : * given constraints and cumulative cost of the given constrained path.
384 : *
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
388 : *
389 : * @return True if Edge should be prune, false if Edge is valid
390 : */
391 0 : static bool prune_edge(const struct c_path *path, const struct ls_edge *edge,
392 : const struct constraints *csts)
393 : {
394 0 : struct ls_vertex *dst;
395 0 : struct ls_attributes *attr;
396 :
397 : /* Check that Path, Edge and Constraints are valid */
398 0 : if (!path || !edge || !csts)
399 : return true;
400 :
401 : /* Check that Edge has a valid destination */
402 0 : if (!edge->destination)
403 : return true;
404 0 : dst = edge->destination;
405 :
406 : /* Check that Edge has valid attributes */
407 0 : if (!edge->attributes)
408 : return true;
409 0 : attr = edge->attributes;
410 :
411 : /* Check that Edge belongs to the requested Address Family and type */
412 0 : if (csts->family == AF_INET) {
413 0 : if (IPV4_NET0(attr->standard.local.s_addr))
414 : return true;
415 0 : if (csts->type == SR_TE)
416 0 : if (!CHECK_FLAG(attr->flags, LS_ATTR_ADJ_SID) ||
417 0 : !CHECK_FLAG(dst->node->flags, LS_NODE_SR))
418 : return true;
419 : }
420 0 : if (csts->family == AF_INET6) {
421 0 : if (IN6_IS_ADDR_UNSPECIFIED(&attr->standard.local6))
422 : return true;
423 0 : if (csts->type == SR_TE)
424 0 : if (!CHECK_FLAG(attr->flags, LS_ATTR_ADJ_SID6) ||
425 0 : !CHECK_FLAG(dst->node->flags, LS_NODE_SR))
426 : return true;
427 : }
428 :
429 : /*
430 : * Check that total cost, up to this edge, respects the initial
431 : * constraints
432 : */
433 0 : switch (csts->ctype) {
434 0 : case CSPF_METRIC:
435 0 : if (!CHECK_FLAG(attr->flags, LS_ATTR_METRIC))
436 : return true;
437 0 : if ((attr->metric + path->weight) > csts->cost)
438 : return true;
439 : break;
440 :
441 0 : case CSPF_TE_METRIC:
442 0 : if (!CHECK_FLAG(attr->flags, LS_ATTR_TE_METRIC))
443 : return true;
444 0 : if ((attr->standard.te_metric + path->weight) > csts->cost)
445 : return true;
446 : break;
447 :
448 0 : case CSPF_DELAY:
449 0 : if (!CHECK_FLAG(attr->flags, LS_ATTR_DELAY))
450 : return true;
451 0 : if ((attr->extended.delay + path->weight) > csts->cost)
452 : return true;
453 : break;
454 : }
455 :
456 : /* If specified, check that Edge meet Bandwidth constraint */
457 0 : if (csts->bw > 0.0) {
458 0 : if (attr->standard.max_bw < csts->bw ||
459 0 : attr->standard.max_rsv_bw < csts->bw ||
460 0 : attr->standard.unrsv_bw[csts->cos] < csts->bw)
461 0 : return true;
462 : }
463 :
464 : /* All is fine. We can consider this Edge valid, so not to be prune */
465 : return false;
466 : }
467 :
468 : /**
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.
475 : *
476 : * @param algo CSPF structure
477 : * @param edge Next Edge to be added to the current computed path
478 : *
479 : * @return True if current path reach destination, false otherwise
480 : */
481 0 : static bool relax_constraints(struct cspf *algo, struct ls_edge *edge)
482 : {
483 :
484 0 : struct c_path pkey = {};
485 0 : struct c_path *next_path;
486 0 : struct v_node vnode = {};
487 0 : uint32_t total_cost = MAX_COST;
488 :
489 : /* Verify that we have a current computed path */
490 0 : if (!algo->path)
491 : return false;
492 :
493 : /* Verify if we have not visited the next Vertex to avoid loop */
494 0 : vnode.key = edge->destination->key;
495 0 : if (visited_member(&algo->visited, &vnode)) {
496 : return false;
497 : }
498 :
499 : /*
500 : * Get Next Computed Path from next vertex key
501 : * or create a new one if it has not yet computed.
502 : */
503 0 : pkey.dst = edge->destination->key;
504 0 : next_path = processed_find(&algo->processed, &pkey);
505 0 : if (!next_path) {
506 0 : next_path = cpath_new(pkey.dst);
507 0 : processed_add(&algo->processed, next_path);
508 : }
509 :
510 : /*
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.
515 : */
516 0 : switch (algo->csts.ctype) {
517 0 : case CSPF_METRIC:
518 0 : total_cost = edge->attributes->metric + algo->path->weight;
519 0 : break;
520 0 : case CSPF_TE_METRIC:
521 0 : total_cost = edge->attributes->standard.te_metric +
522 0 : algo->path->weight;
523 0 : break;
524 0 : case CSPF_DELAY:
525 0 : total_cost =
526 0 : edge->attributes->extended.delay + algo->path->weight;
527 0 : break;
528 : default:
529 : break;
530 : }
531 0 : if (total_cost < next_path->weight) {
532 : /*
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.
539 : */
540 0 : struct c_path *path;
541 0 : frr_each_safe (pqueue, &algo->pqueue, path) {
542 0 : if (path->dst == pkey.dst) {
543 0 : pqueue_del(&algo->pqueue, path);
544 : break;
545 : }
546 : }
547 0 : next_path->weight = total_cost;
548 0 : cpath_replace(next_path, algo->path);
549 0 : listnode_add(next_path->edges, edge);
550 0 : pqueue_add(&algo->pqueue, next_path);
551 : }
552 :
553 : /* Return True if we reach the destination */
554 0 : return (next_path->dst == algo->pdst->dst);
555 : }
556 :
557 0 : struct c_path *compute_p2p_path(struct cspf *algo, struct ls_ted *ted)
558 : {
559 0 : struct listnode *node;
560 0 : struct ls_vertex *vertex;
561 0 : struct ls_edge *edge;
562 0 : struct c_path *optim_path;
563 0 : struct v_node *vnode;
564 0 : uint32_t cur_cost;
565 :
566 0 : optim_path = cpath_new(0xFFFFFFFFFFFFFFFF);
567 0 : optim_path->status = FAILED;
568 :
569 : /* Check that all is correctly initialized */
570 0 : if (!algo)
571 : return optim_path;
572 :
573 0 : if (!algo->csts.ctype)
574 : return optim_path;
575 :
576 0 : if (!algo->pdst) {
577 0 : optim_path->status = NO_DESTINATION;
578 0 : return optim_path;
579 : }
580 :
581 0 : if (!algo->path) {
582 0 : optim_path->status = NO_SOURCE;
583 0 : return optim_path;
584 : }
585 :
586 0 : if (algo->pdst->dst == algo->path->dst) {
587 0 : optim_path->status = SAME_SRC_DST;
588 0 : return optim_path;
589 : }
590 :
591 0 : optim_path->dst = algo->pdst->dst;
592 0 : optim_path->status = IN_PROGRESS;
593 :
594 : /*
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()
598 : */
599 0 : cur_cost = MAX_COST;
600 0 : while (pqueue_count(&algo->pqueue) != 0) {
601 : /* Got shortest current Path from the Priority Queue */
602 0 : algo->path = pqueue_pop(&algo->pqueue);
603 :
604 : /* Add destination Vertex of this path to the visited RB Tree */
605 0 : vertex = ls_find_vertex_by_key(ted, algo->path->dst);
606 0 : if (!vertex)
607 0 : continue;
608 0 : vnode = vnode_new(vertex);
609 0 : visited_add(&algo->visited, vnode);
610 :
611 : /* Process all outgoing links from this Vertex */
612 0 : for (ALL_LIST_ELEMENTS_RO(vertex->outgoing_edges, node, edge)) {
613 : /*
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.
617 : */
618 0 : if (prune_edge(algo->path, edge, &algo->csts))
619 0 : continue;
620 :
621 : /*
622 : * Relax constraints and check if we got a shorter
623 : * candidate path
624 : */
625 0 : if (relax_constraints(algo, edge) &&
626 0 : algo->pdst->weight < cur_cost) {
627 0 : cur_cost = algo->pdst->weight;
628 0 : cpath_copy(optim_path, algo->pdst);
629 0 : optim_path->status = SUCCESS;
630 : }
631 : }
632 : }
633 :
634 : /*
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
638 : * returned.
639 : */
640 0 : if (optim_path->status == IN_PROGRESS ||
641 0 : listcount(optim_path->edges) == 0)
642 0 : optim_path->status = FAILED;
643 0 : cspf_clean(algo);
644 :
645 0 : return optim_path;
646 : }
|
