lib/cspf.h

   1 /*
   2  * Constraints Shortest Path First algorithms definition - cspf.h
   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 #ifndef _FRR_CSPF_H_
  26 #define _FRR_CSPF_H_
  27
  28 #include "typesafe.h"
  29
  30 #ifdef __cplusplus
  31 extern "C" {
  32 #endif
  33
  34 /**
  35  * This file defines the different structure used for Path Computation with
  36  * various constrained. Up to now, standard metric, TE metric, delay and
  37  * bandwidth constraints are supported.
  38  * All proposed algorithms used the same principle:
  39  *  - A pruning function that keeps only links that meet constraints
  40  *  - A priority Queue that keeps the shortest on-going computed path
  41  *  - A main loop over all vertices to find the shortest path
  42  */
  43
  44 #define MAX_COST        0xFFFFFFFF
  45
  46 /* Status of the path */
  47 enum path_status {
  48         FAILED = 0,
  49         NO_SOURCE,
  50         NO_DESTINATION,
  51         SAME_SRC_DST,
  52         IN_PROGRESS,
  53         SUCCESS
  54 };
  55 enum path_type {RSVP_TE = 1, SR_TE, SRV6_TE};
  56 enum metric_type {CSPF_METRIC = 1, CSPF_TE_METRIC, CSPF_DELAY};
  57
  58 /* Constrained metrics structure */
  59 struct constraints {
  60         uint32_t cost;          /* total cost (metric) of the path */
  61         enum metric_type ctype; /* Metric Type: standard, TE or Delay */
  62         float bw;               /* bandwidth of the path */
  63         uint8_t cos;            /* Class of Service of the path */
  64         enum path_type type;    /* RSVP-TE or SR-TE path */
  65         uint8_t family;         /* AF_INET or AF_INET6 address family */
  66 };
  67
  68 /* Priority Queue for Constrained Path Computation */
  69 PREDECL_RBTREE_NONUNIQ(pqueue);
  70
  71 /* Processed Path for Constrained Path Computation */
  72 PREDECL_RBTREE_UNIQ(processed);
  73
  74 /* Constrained Path structure */
  75 struct c_path {
  76         struct pqueue_item q_itm;    /* entry in the Priority Queue */
  77         uint32_t weight;             /* Weight to sort path in Priority Queue */
  78         struct processed_item p_itm; /* entry in the Processed RB Tree */
  79         uint64_t dst;                /* Destination vertex key of this path */
  80         struct list *edges;          /* List of Edges that compose this path */
  81         enum path_status status;     /* status of the computed path */
  82 };
  83
  84 macro_inline int q_cmp(const struct c_path *p1, const struct c_path *p2)
  85 {
  86         return numcmp(p1->weight, p2->weight);
  87 }
  88 DECLARE_RBTREE_NONUNIQ(pqueue, struct c_path, q_itm, q_cmp);
  89
  90 macro_inline int p_cmp(const struct c_path *p1, const struct c_path *p2)
  91 {
  92         return numcmp(p1->dst, p2->dst);
  93 }
  94 DECLARE_RBTREE_UNIQ(processed, struct c_path, p_itm, p_cmp);
  95
  96 /* List of visited node */
  97 PREDECL_RBTREE_UNIQ(visited);
  98 struct v_node {
  99         struct visited_item item; /* entry in the Processed RB Tree */
 100         uint64_t key;
 101         struct ls_vertex *vertex;
 102 };
 103
 104 macro_inline int v_cmp(const struct v_node *p1, const struct v_node *p2)
 105 {
 106         return numcmp(p1->key, p2->key);
 107 }
 108 DECLARE_RBTREE_UNIQ(visited, struct v_node, item, v_cmp);
 109
 110 /* Path Computation algorithms structure */
 111 struct cspf {
 112         struct pqueue_head pqueue;       /* Priority Queue */
 113         struct processed_head processed; /* Paths that have been processed */
 114         struct visited_head visited;     /* Vertices that have been visited */
 115         struct constraints csts;         /* Constraints of the path */
 116         struct c_path *path;             /* Current Computed Path */
 117         struct c_path *pdst;             /* Computed Path to the destination */
 118 };
 119
 120 /**
 121  * Create a new CSPF structure. Memory is dynamically allocated.
 122  *
 123  * @return      pointer to the new cspf structure
 124  */
 125 extern struct cspf *cspf_new(void);
 126
 127 /**
 128  * Initialize CSPF structure prior to compute a constrained path. If CSPF
 129  * structure is NULL, a new CSPF is dynamically allocated prior to the
 130  * configuration itself.
 131  *
 132  * @param algo  CSPF structure, may be null if a new CSPF must be created
 133  * @param src   Source vertex of the requested path
 134  * @param dst   Destination vertex of the requested path
 135  * @param csts  Constraints of the requested path
 136  *
 137  * @return      pointer to the initialized CSPF structure
 138  */
 139 extern struct cspf *cspf_init(struct cspf *algo, const struct ls_vertex *src,
 140                               const struct ls_vertex *dst,
 141                               struct constraints *csts);
 142
 143 /**
 144  * Initialize CSPF structure prior to compute a constrained path. If CSPF
 145  * structure is NULL, a new CSPF is dynamically allocated prior to the
 146  * configuration itself. This function starts by searching source and
 147  * destination vertices from the IPv4 addresses in the provided TED.
 148  *
 149  * @param algo  CSPF structure, may be null if a new CSPF must be created
 150  * @param ted   Traffic Engineering Database
 151  * @param src   Source IPv4 address of the requested path
 152  * @param dst   Destination IPv4 address of the requested path
 153  * @param csts  Constraints of the requested path
 154  *
 155  * @return      pointer to the initialized CSPF structure
 156  */
 157 extern struct cspf *cspf_init_v4(struct cspf *algo, struct ls_ted *ted,
 158                                  const struct in_addr src,
 159                                  const struct in_addr dst,
 160                                  struct constraints *csts);
 161
 162 /**
 163  * Initialize CSPF structure prior to compute a constrained path. If CSPF
 164  * structure is NULL, a new CSPF is dynamically allocated prior to the
 165  * configuration itself. This function starts by searching source and
 166  * destination vertices from the IPv6 addresses in the provided TED.
 167  *
 168  * @param algo  CSPF structure, may be null if a new CSPF must be created
 169  * @param ted   Traffic Engineering Database
 170  * @param src   Source IPv6 address of the requested path
 171  * @param dst   Destination IPv6 address of the requested path
 172  * @param csts  Constraints of the requested path
 173  *
 174  * @return      pointer to the initialized CSPF structure
 175  */
 176 extern struct cspf *cspf_init_v6(struct cspf *algo, struct ls_ted *ted,
 177                                  const struct in6_addr src,
 178                                  const struct in6_addr dst,
 179                                  struct constraints *csts);
 180
 181 /**
 182  * Clean CSPF structure. Reset all internal list and priority queue for latter
 183  * initialization of the CSPF structure and new path computation.
 184  *
 185  * @param algo  CSPF structure
 186  */
 187 extern void cspf_clean(struct cspf *algo);
 188
 189 /**
 190  * Delete CSPF structure, internal list and priority queue.
 191  *
 192  * @param algo  CSPF structure
 193  */
 194 extern void cspf_del(struct cspf *algo);
 195
 196 /**
 197  * Compute point-to-point constrained path. cspf_init() function must be call
 198  * prior to call this function.
 199  *
 200  * @param algo  CSPF structure
 201  * @param ted   Traffic Engineering Database
 202  *
 203  * @return      Constrained Path with status to indicate computation success
 204  */
 205 extern struct c_path *compute_p2p_path(struct cspf *algo, struct ls_ted *ted);
 206
 207 #ifdef __cplusplus
 208 }
 209 #endif
 210
 211 #endif /* _FRR_CSPF_H_ */