]>
Commit | Line | Data |
---|---|---|
acddc0ed | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
fd8e262a OD |
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). | |
fd8e262a OD |
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 | macro_inline int q_cmp(const struct c_path *p1, const struct c_path *p2) | |
72 | { | |
73 | return numcmp(p1->weight, p2->weight); | |
74 | } | |
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 | { | |
79 | return numcmp(p1->dst, p2->dst); | |
80 | } | |
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 | { | |
93 | return numcmp(p1->key, p2->key); | |
94 | } | |
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 | ||
5aa36ff7 K |
194 | extern void cpath_del(struct c_path *path); |
195 | ||
fd8e262a OD |
196 | #ifdef __cplusplus |
197 | } | |
198 | #endif | |
199 | ||
200 | #endif /* _FRR_CSPF_H_ */ |