1 Path Computation Algorithms
2 ===========================
7 Both RSVP-TE and Segment Routing Flex Algo need to compute end to end path
8 with other constraints as the standard IGP metric. Based on Shortest Path First
9 (SPF) algorithms, a new class of Constrained SPF (CSPF) is provided by the FRR
12 Supported constraints are as follow:
13 - Standard IGP metric (here, CSPF provides the same result as a normal SPF)
14 - Traffic Engineering (TE) IGP metric
15 - Delay from the IGP Extended Metrics
16 - Bandwidth for a given Class of Service (CoS) for bandwidth reservation
21 The CSPF algorithm is based on a Priority Queue which store the on-going
22 possible path sorted by their respective weights. This weight corresponds
23 to the cost of the cuurent path from the source up to the current node.
25 The algorithm is as followed:
29 Priority_Queue.empty();
31 Processed_Path.empty();
32 src = new_path(source_address);
34 dst = new_destinatio(destination_address);
36 Processed_Path.add(src);
37 Processed_Path.add(dst);
38 while (Priority_Queue.count != 0) {
39 current_path = Priority_Queue.pop();
40 current_node = next_path.destination;
41 Visited_Node.add(current_node);
42 for (current_node.edges: edge) {
43 if (prune_edge(current_path, edge)
45 if (relax(current_path) && cost > current_path.cost) {
46 optim_path = current_path;
47 cost = current_path.cost;
52 prune_edge(path, edge) {
53 // check that path + edge meet constraints e.g.
54 if (current_path.cost + edge.cost > constrained_cost)
60 relax_edge(current_path, edge) {
61 next_node = edge.destination;
62 if (Visited_Node.get(next_node))
64 next_path = Processed_Path.get(edge.destination);
66 next_path = new path(edge.destination);
67 Processed_Path.add(next_path);
69 total_cost = current_path.cost + edge.cost;
70 if (total_cost < next_path.cost) {
71 next_path = current_path;
72 next_path.add_edge(edge);
73 next_path.cost = total_cost;
74 Priority_Queue.add(next_path);
76 return (next_path.destination == destination);
84 .. c:struct:: constraints
86 This is the constraints structure that contains:
88 - cost: the total cost that the path must respect
89 - ctype: type of constraints:
91 - CSPF_METRIC for standard metric
92 - CSPF_TE_METRIC for TE metric
93 - CSPF_DELAY for delay metric
95 - bw: bandwidth that the path must respect
96 - cos: Class of Service (COS) for the bandwidth
97 - family: AF_INET or AF_INET6
98 - type: RSVP_TE, SR_TE or SRV6_TE
102 This is the Constraint Path structure that contains:
104 - edges: List of Edges that compose the path
105 - status: FAILED, IN_PROGRESS, SUCCESS, NO_SOURCE, NO_DESTINATION, SAME_SRC_DST
106 - weight: the cost from source to the destination of the path
107 - dst: key of the destination vertex
111 This is the main structure for path computation. Even if it is public, you
112 don't need to set manually the internal field of the structure. Instead, use
113 the following functions:
115 .. c:function:: struct cspf *cspf_new(void);
117 Function to create an empty cspf for future call of path computation
119 .. c:function:: struct cspf *cspf_init(struct cspf *algo, const struct ls_vertex *src, const struct ls_vertex *dst, struct constraints *csts);
121 This function initialize the cspf with source and destination vertex and
122 constraints and return pointer to the cspf structure. If input cspf structure
123 is NULL, a new cspf structure is allocated and initialize.
125 .. c:function:: 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);
127 Same as cspf_init, but here, source and destination vertex are extract from
128 the TED data base based on respective IPv4 source and destination addresses.
130 .. c:function:: 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);
132 Same as cspf_init_v4 but with IPv6 source and destination addresses.
134 .. c:function:: void cspf_clean(struct cspf *algo);
136 Clean internal structure of cspf in order to reuse it for another path
139 .. c:function:: void cspf_del(struct cspf *algo);
141 Delete cspf structure. A call to cspf_clean() function is perform prior to
142 free allocated memeory.
144 .. c:function:: struct c_path *compute_p2p_path(struct ls_ted *ted, struct cspf *algo);
146 Compute point to point path from the ted and cspf.
147 The function always return a constraints path. The status of the path gives
148 indication about the success or failure of the algorithm. If cspf structure has
149 not been initialize with a call to `cspf_init() or cspf_init_XX()`, the
150 algorithm returns a constraints path with status set to FAILED.
151 Note that a call to `cspf_clean()` is performed at the end of this function,
152 thus it is mandatory to initialize the cspf structure again prior to call again
153 the path computation algorithm.
159 Of course, CSPF algorithm needs a network topology that contains the
160 various metrics. Link State provides such Traffic Engineering Database.
162 To perform a Path Computation with given constraints, proceed as follow:
169 struct constraints csts;
172 // Create a new CSPF structure
175 // Initialize constraints
177 csts.ctype = CSPF_TE_METRIC;
178 csts.family = AF_INET;
183 // Then, initialise th CSPF with source, destination and constraints
184 cspf_init_v4(algo, ted, src, dst, &csts);
186 // Finally, got the Computed Path;
187 path = compute_p2p_path(ted, algo);
189 if (path.status == SUCCESS)
190 zlog_info("Got a valid constraints path");
192 zlog_info("Unable to compute constraints path. Got %d status", path->status);
195 If you would compute another path, you must call `cspf_init()` prior to
196 `compute_p2p_path()` to change source, destination and/or constraints.