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