Line data Source code
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 : #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 0 : macro_inline int q_cmp(const struct c_path *p1, const struct c_path *p2)
72 : {
73 0 : return numcmp(p1->weight, p2->weight);
74 : }
75 0 : DECLARE_RBTREE_NONUNIQ(pqueue, struct c_path, q_itm, q_cmp);
76 :
77 0 : macro_inline int p_cmp(const struct c_path *p1, const struct c_path *p2)
78 : {
79 0 : return numcmp(p1->dst, p2->dst);
80 : }
81 0 : 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 0 : macro_inline int v_cmp(const struct v_node *p1, const struct v_node *p2)
92 : {
93 0 : return numcmp(p1->key, p2->key);
94 : }
95 0 : 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_ */
|
