lib/cspf.c

   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 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 static struct c_path *cpath_new(uint64_t key)
  50 {
  51         struct c_path *path;
  52
  53         /* Sanity Check */
  54         if (key == 0)
  55                 return NULL;
  56
  57         path = XCALLOC(MTYPE_PCA, sizeof(struct c_path));
  58         path->dst = key;
  59         path->status = IN_PROGRESS;
  60         path->edges = list_new();
  61         path->weight = MAX_COST;
  62
  63         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 static struct c_path *cpath_copy(struct c_path *dest, const struct c_path *src)
  77 {
  78         struct c_path *new_path;
  79
  80         if (!src)
  81                 return dest;
  82
  83         if (!dest) {
  84                 new_path = XCALLOC(MTYPE_PCA, sizeof(struct c_path));
  85         } else {
  86                 new_path = dest;
  87                 if (dest->edges)
  88                         list_delete(&new_path->edges);
  89         }
  90
  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;
  95
  96         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 static void cpath_del(struct c_path *path)
 105 {
 106         if (!path)
 107                 return;
 108
 109         if (path->edges)
 110                 list_delete(&path->edges);
 111
 112         XFREE(MTYPE_PCA, path);
 113         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 static void cpath_replace(struct c_path *next_path, struct c_path *cur_path)
 124 {
 125
 126         if (next_path->edges)
 127                 list_delete(&next_path->edges);
 128
 129         next_path->edges = list_dup(cur_path->edges);
 130 }
 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 static struct v_node *vnode_new(struct ls_vertex *vertex)
 141 {
 142         struct v_node *vnode;
 143
 144         if (!vertex)
 145                 return NULL;
 146
 147         vnode = XCALLOC(MTYPE_PCA, sizeof(struct v_node));
 148         vnode->vertex = vertex;
 149         vnode->key = vertex->key;
 150
 151         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 static void vnode_del(struct v_node *vnode)
 160 {
 161         if (!vnode)
 162                 return;
 163
 164         XFREE(MTYPE_PCA, vnode);
 165         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 static struct ls_vertex *get_vertex_by_ipv4(struct ls_ted *ted,
 179                                             struct in_addr ipv4)
 180 {
 181         struct ls_subnet *subnet;
 182         struct prefix p;
 183
 184         p.family = AF_INET;
 185         p.u.prefix4 = ipv4;
 186
 187         frr_each (subnets, &ted->subnets, subnet) {
 188                 if (subnet->key.family != AF_INET)
 189                         continue;
 190                 p.prefixlen = subnet->key.prefixlen;
 191                 if (prefix_same(&subnet->key, &p))
 192                         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 static struct ls_vertex *get_vertex_by_ipv6(struct ls_ted *ted,
 209                                             struct in6_addr ipv6)
 210 {
 211         struct ls_subnet *subnet;
 212         struct prefix p;
 213
 214         p.family = AF_INET6;
 215         p.u.prefix6 = ipv6;
 216
 217         frr_each (subnets, &ted->subnets, subnet) {
 218                 if (subnet->key.family != AF_INET6)
 219                         continue;
 220                 p.prefixlen = subnet->key.prefixlen;
 221                 if (prefix_cmp(&subnet->key, &p) == 0)
 222                         return subnet->vertex;
 223         }
 224
 225         return NULL;
 226 }
 227
 228 struct cspf *cspf_new(void)
 229 {
 230         struct cspf *algo;
 231
 232         /* Allocate New CSPF structure */
 233         algo = XCALLOC(MTYPE_PCA, sizeof(struct cspf));
 234
 235         /* Initialize RB-Trees */
 236         processed_init(&algo->processed);
 237         visited_init(&algo->visited);
 238         pqueue_init(&algo->pqueue);
 239
 240         algo->path = NULL;
 241         algo->pdst = NULL;
 242
 243         return algo;
 244 }
 245
 246 struct cspf *cspf_init(struct cspf *algo, const struct ls_vertex *src,
 247                        const struct ls_vertex *dst, struct constraints *csts)
 248 {
 249         struct cspf *new_algo;
 250         struct c_path *psrc;
 251
 252         if (!csts)
 253                 return NULL;
 254
 255         if (!algo)
 256                 new_algo = cspf_new();
 257         else
 258                 new_algo = algo;
 259
 260         /* Initialize Processed Path and Priority Queue with Src & Dst */
 261         if (src) {
 262                 psrc = cpath_new(src->key);
 263                 psrc->weight = 0;
 264                 processed_add(&new_algo->processed, psrc);
 265                 pqueue_add(&new_algo->pqueue, psrc);
 266                 new_algo->path = psrc;
 267         }
 268         if (dst) {
 269                 new_algo->pdst = cpath_new(dst->key);
 270                 processed_add(&new_algo->processed, new_algo->pdst);
 271         }
 272
 273         memcpy(&new_algo->csts, csts, sizeof(struct constraints));
 274
 275         return new_algo;
 276 }
 277
 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)
 281 {
 282         struct ls_vertex *vsrc;
 283         struct ls_vertex *vdst;
 284         struct cspf *new_algo;
 285
 286         /* Sanity Check */
 287         if (!ted)
 288                 return algo;
 289
 290         if (!algo)
 291                 new_algo = cspf_new();
 292         else
 293                 new_algo = algo;
 294
 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;
 299
 300         return cspf_init(new_algo, vsrc, vdst, csts);
 301 }
 302
 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)
 306 {
 307         struct ls_vertex *vsrc;
 308         struct ls_vertex *vdst;
 309         struct cspf *new_algo;
 310
 311         /* Sanity Check */
 312         if (!ted)
 313                 return algo;
 314
 315         if (!algo)
 316                 new_algo = cspf_new();
 317         else
 318                 new_algo = algo;
 319
 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;
 324
 325         return cspf_init(new_algo, vsrc, vdst, csts);
 326 }
 327
 328 void cspf_clean(struct cspf *algo)
 329 {
 330         struct c_path *path;
 331         struct v_node *vnode;
 332
 333         if (!algo)
 334                 return;
 335
 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);
 340                 }
 341         }
 342
 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);
 347                         cpath_del(path);
 348                 }
 349         }
 350
 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);
 355                         vnode_del(vnode);
 356                 }
 357         }
 358
 359         memset(&algo->csts, 0, sizeof(struct constraints));
 360         algo->path = NULL;
 361         algo->pdst = NULL;
 362 }
 363
 364 void cspf_del(struct cspf *algo)
 365 {
 366         if (!algo)
 367                 return;
 368
 369         /* Empty Priority Queue and Processes Path */
 370         cspf_clean(algo);
 371
 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);
 376
 377         XFREE(MTYPE_PCA, algo);
 378         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 static bool prune_edge(const struct c_path *path, const struct ls_edge *edge,
 392                        const struct constraints *csts)
 393 {
 394         struct ls_vertex *dst;
 395         struct ls_attributes *attr;
 396
 397         /* Check that Path, Edge and Constraints are valid */
 398         if (!path || !edge || !csts)
 399                 return true;
 400
 401         /* Check that Edge has a valid destination */
 402         if (!edge->destination)
 403                 return true;
 404         dst = edge->destination;
 405
 406         /* Check that Edge has valid attributes */
 407         if (!edge->attributes)
 408                 return true;
 409         attr = edge->attributes;
 410
 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))
 414                         return true;
 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))
 418                                 return true;
 419         }
 420         if (csts->family == AF_INET6) {
 421                 if (IN6_IS_ADDR_UNSPECIFIED(&attr->standard.local6))
 422                         return true;
 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))
 426                                 return true;
 427         }
 428
 429         /*
 430          * Check that total cost, up to this edge, respects the initial
 431          * constraints
 432          */
 433         switch (csts->ctype) {
 434         case CSPF_METRIC:
 435                 if (!CHECK_FLAG(attr->flags, LS_ATTR_METRIC))
 436                         return true;
 437                 if ((attr->metric + path->weight) > csts->cost)
 438                         return true;
 439                 break;
 440
 441         case CSPF_TE_METRIC:
 442                 if (!CHECK_FLAG(attr->flags, LS_ATTR_TE_METRIC))
 443                         return true;
 444                 if ((attr->standard.te_metric + path->weight) > csts->cost)
 445                         return true;
 446                 break;
 447
 448         case CSPF_DELAY:
 449                 if (!CHECK_FLAG(attr->flags, LS_ATTR_DELAY))
 450                         return true;
 451                 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         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)
 461                         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 static bool relax_constraints(struct cspf *algo, struct ls_edge *edge)
 482 {
 483
 484         struct c_path pkey = {};
 485         struct c_path *next_path;
 486         struct v_node vnode = {};
 487         uint32_t total_cost = MAX_COST;
 488
 489         /* Verify that we have a current computed path */
 490         if (!algo->path)
 491                 return false;
 492
 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)) {
 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         pkey.dst = edge->destination->key;
 504         next_path = processed_find(&algo->processed, &pkey);
 505         if (!next_path) {
 506                 next_path = cpath_new(pkey.dst);
 507                 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         switch (algo->csts.ctype) {
 517         case CSPF_METRIC:
 518                 total_cost = edge->attributes->metric + algo->path->weight;
 519                 break;
 520         case CSPF_TE_METRIC:
 521                 total_cost = edge->attributes->standard.te_metric +
 522                              algo->path->weight;
 523                 break;
 524         case CSPF_DELAY:
 525                 total_cost =
 526                         edge->attributes->extended.delay + algo->path->weight;
 527                 break;
 528         default:
 529                 break;
 530         }
 531         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                 struct c_path *path;
 541                 frr_each_safe (pqueue, &algo->pqueue, path) {
 542                         if (path->dst == pkey.dst) {
 543                                 pqueue_del(&algo->pqueue, path);
 544                                 break;
 545                         }
 546                 }
 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);
 551         }
 552
 553         /* Return True if we reach the destination */
 554         return (next_path->dst == algo->pdst->dst);
 555 }
 556
 557 struct c_path *compute_p2p_path(struct cspf *algo, struct ls_ted *ted)
 558 {
 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;
 564         uint32_t cur_cost;
 565
 566         optim_path = cpath_new(0xFFFFFFFFFFFFFFFF);
 567         optim_path->status = FAILED;
 568
 569         /* Check that all is correctly initialized */
 570         if (!algo)
 571                 return optim_path;
 572
 573         if (!algo->csts.ctype)
 574                 return optim_path;
 575
 576         if (!algo->pdst) {
 577                 optim_path->status = NO_DESTINATION;
 578                 return optim_path;
 579         }
 580
 581         if (!algo->path) {
 582                 optim_path->status = NO_SOURCE;
 583                 return optim_path;
 584         }
 585
 586         if (algo->pdst->dst == algo->path->dst) {
 587                 optim_path->status = SAME_SRC_DST;
 588                 return optim_path;
 589         }
 590
 591         optim_path->dst = algo->pdst->dst;
 592         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         cur_cost = MAX_COST;
 600         while (pqueue_count(&algo->pqueue) != 0) {
 601                 /* Got shortest current Path from the Priority Queue */
 602                 algo->path = pqueue_pop(&algo->pqueue);
 603
 604                 /* Add destination Vertex of this path to the visited RB Tree */
 605                 vertex = ls_find_vertex_by_key(ted, algo->path->dst);
 606                 if (!vertex)
 607                         continue;
 608                 vnode = vnode_new(vertex);
 609                 visited_add(&algo->visited, vnode);
 610
 611                 /* Process all outgoing links from this Vertex */
 612                 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                         if (prune_edge(algo->path, edge, &algo->csts))
 619                                 continue;
 620
 621                         /*
 622                          * Relax constraints and check if we got a shorter
 623                          * candidate path
 624                          */
 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;
 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         if (optim_path->status == IN_PROGRESS ||
 641             listcount(optim_path->edges) == 0)
 642                 optim_path->status = FAILED;
 643         cspf_clean(algo);
 644
 645         return optim_path;
 646 }