Line data Source code
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 0 : macro_inline int q_cmp(const struct c_path *p1, const struct c_path *p2)
85 : {
86 0 : return numcmp(p1->weight, p2->weight);
87 : }
88 0 : DECLARE_RBTREE_NONUNIQ(pqueue, struct c_path, q_itm, q_cmp);
89 :
90 0 : macro_inline int p_cmp(const struct c_path *p1, const struct c_path *p2)
91 : {
92 0 : return numcmp(p1->dst, p2->dst);
93 : }
94 0 : 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 0 : macro_inline int v_cmp(const struct v_node *p1, const struct v_node *p2)
105 : {
106 0 : return numcmp(p1->key, p2->key);
107 : }
108 0 : 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_ */
|
