]>
Commit | Line | Data |
---|---|---|
fd8e262a OD |
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_ */ |