/src/frr/lib/cspf.h

Source
// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Constraints Shortest Path First algorithms definition - cspf.h
 *
 * Author: Olivier Dugeon <olivier.dugeon@orange.com>
 *
 * Copyright (C) 2022 Orange http://www.orange.com
 *
 * This file is part of Free Range Routing (FRR).
 */

#ifndef _FRR_CSPF_H_
#define _FRR_CSPF_H_

#include "typesafe.h"

#ifdef __cplusplus
extern "C" {
#endif

/**
 * This file defines the different structure used for Path Computation with
 * various constrained. Up to now, standard metric, TE metric, delay and
 * bandwidth constraints are supported.
 * All proposed algorithms used the same principle:
 *  - A pruning function that keeps only links that meet constraints
 *  - A priority Queue that keeps the shortest on-going computed path
 *  - A main loop over all vertices to find the shortest path
 */

#define MAX_COST  0xFFFFFFFF

/* Status of the path */
enum path_status {
  FAILED = 0,
  NO_SOURCE,
  NO_DESTINATION,
  SAME_SRC_DST,
  IN_PROGRESS,
  SUCCESS
};
enum path_type {RSVP_TE = 1, SR_TE, SRV6_TE};
enum metric_type {CSPF_METRIC = 1, CSPF_TE_METRIC, CSPF_DELAY};

/* Constrained metrics structure */
struct constraints {
  uint32_t cost;    /* total cost (metric) of the path */
  enum metric_type ctype; /* Metric Type: standard, TE or Delay */
  float bw;   /* bandwidth of the path */
  uint8_t cos;    /* Class of Service of the path */
  enum path_type type;  /* RSVP-TE or SR-TE path */
  uint8_t family;   /* AF_INET or AF_INET6 address family */
};

/* Priority Queue for Constrained Path Computation */
PREDECL_RBTREE_NONUNIQ(pqueue);

/* Processed Path for Constrained Path Computation */
PREDECL_RBTREE_UNIQ(processed);

/* Constrained Path structure */
struct c_path {
  struct pqueue_item q_itm;    /* entry in the Priority Queue */
  uint32_t weight;             /* Weight to sort path in Priority Queue */
  struct processed_item p_itm; /* entry in the Processed RB Tree */
  uint64_t dst;                /* Destination vertex key of this path */
  struct list *edges;          /* List of Edges that compose this path */
  enum path_status status;     /* status of the computed path */
};

macro_inline int q_cmp(const struct c_path *p1, const struct c_path *p2)
{
  return numcmp(p1->weight, p2->weight);
}
DECLARE_RBTREE_NONUNIQ(pqueue, struct c_path, q_itm, q_cmp);

macro_inline int p_cmp(const struct c_path *p1, const struct c_path *p2)
{
  return numcmp(p1->dst, p2->dst);
}
DECLARE_RBTREE_UNIQ(processed, struct c_path, p_itm, p_cmp);

/* List of visited node */
PREDECL_RBTREE_UNIQ(visited);
struct v_node {
  struct visited_item item; /* entry in the Processed RB Tree */
  uint64_t key;
  struct ls_vertex *vertex;
};

macro_inline int v_cmp(const struct v_node *p1, const struct v_node *p2)
{
  return numcmp(p1->key, p2->key);
}
DECLARE_RBTREE_UNIQ(visited, struct v_node, item, v_cmp);

/* Path Computation algorithms structure */
struct cspf {
  struct pqueue_head pqueue;       /* Priority Queue */
  struct processed_head processed; /* Paths that have been processed */
  struct visited_head visited;     /* Vertices that have been visited */
  struct constraints csts;         /* Constraints of the path */
  struct c_path *path;             /* Current Computed Path */
  struct c_path *pdst;             /* Computed Path to the destination */
};

/**
 * Create a new CSPF structure. Memory is dynamically allocated.
 *
 * @return  pointer to the new cspf structure
 */
extern struct cspf *cspf_new(void);

/**
 * Initialize CSPF structure prior to compute a constrained path. If CSPF
 * structure is NULL, a new CSPF is dynamically allocated prior to the
 * configuration itself.
 *
 * @param algo  CSPF structure, may be null if a new CSPF must be created
 * @param src Source vertex of the requested path
 * @param dst Destination vertex of the requested path
 * @param csts  Constraints of the requested path
 *
 * @return  pointer to the initialized CSPF structure
 */
extern struct cspf *cspf_init(struct cspf *algo, const struct ls_vertex *src,
            const struct ls_vertex *dst,
            struct constraints *csts);

/**
 * Initialize CSPF structure prior to compute a constrained path. If CSPF
 * structure is NULL, a new CSPF is dynamically allocated prior to the
 * configuration itself. This function starts by searching source and
 * destination vertices from the IPv4 addresses in the provided TED.
 *
 * @param algo  CSPF structure, may be null if a new CSPF must be created
 * @param ted Traffic Engineering Database
 * @param src Source IPv4 address of the requested path
 * @param dst Destination IPv4 address of the requested path
 * @param csts  Constraints of the requested path
 *
 * @return  pointer to the initialized CSPF structure
 */
extern struct cspf *cspf_init_v4(struct cspf *algo, struct ls_ted *ted,
         const struct in_addr src,
         const struct in_addr dst,
         struct constraints *csts);

/**
 * Initialize CSPF structure prior to compute a constrained path. If CSPF
 * structure is NULL, a new CSPF is dynamically allocated prior to the
 * configuration itself. This function starts by searching source and
 * destination vertices from the IPv6 addresses in the provided TED.
 *
 * @param algo  CSPF structure, may be null if a new CSPF must be created
 * @param ted Traffic Engineering Database
 * @param src Source IPv6 address of the requested path
 * @param dst Destination IPv6 address of the requested path
 * @param csts  Constraints of the requested path
 *
 * @return  pointer to the initialized CSPF structure
 */
extern struct cspf *cspf_init_v6(struct cspf *algo, struct ls_ted *ted,
         const struct in6_addr src,
         const struct in6_addr dst,
         struct constraints *csts);

/**
 * Clean CSPF structure. Reset all internal list and priority queue for latter
 * initialization of the CSPF structure and new path computation.
 *
 * @param algo  CSPF structure
 */
extern void cspf_clean(struct cspf *algo);

/**
 * Delete CSPF structure, internal list and priority queue.
 *
 * @param algo  CSPF structure
 */
extern void cspf_del(struct cspf *algo);

/**
 * Compute point-to-point constrained path. cspf_init() function must be call
 * prior to call this function.
 *
 * @param algo  CSPF structure
 * @param ted Traffic Engineering Database
 *
 * @return  Constrained Path with status to indicate computation success
 */
extern struct c_path *compute_p2p_path(struct cspf *algo, struct ls_ted *ted);

extern void cpath_del(struct c_path *path);

#ifdef __cplusplus
}
#endif

#endif /* _FRR_CSPF_H_ */

Coverage Report

Created: 2025-11-09 06:11

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