2 * Copyright (c) 2016 Orange. All rights reserved.
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v1.0 which accompanies this distribution,
6 * and is available at http://www.eclipse.org/legal/epl-v10.html
8 package org.opendaylight.algo.impl;
10 import java.util.HashMap;
11 import java.util.List;
12 import org.opendaylight.graph.ConnectedEdge;
13 import org.opendaylight.graph.ConnectedGraph;
14 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.graph.rev191125.graph.topology.graph.VertexKey;
15 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ComputationStatus;
16 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPath;
17 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.ConstrainedPathBuilder;
18 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.path.computation.rev200120.PathConstraints;
19 import org.opendaylight.yangtools.yang.common.Uint32;
20 import org.slf4j.Logger;
21 import org.slf4j.LoggerFactory;
24 * This Class implements a simple Constrained Shortest Path First path computation algorithm that take into account
25 * Bandwidth and TE Metric as constraints.
27 * @author Olivier Dugeon
28 * @author Philippe Niger
29 * @author Philippe Cadro
31 public class ConstrainedShortestPathFirst extends AbstractPathComputation {
33 private static final Logger LOG = LoggerFactory.getLogger(ConstrainedShortestPathFirst.class);
35 private HashMap<Long, CspfPath> visitedVertices;
37 public ConstrainedShortestPathFirst(ConnectedGraph graph) {
39 visitedVertices = new HashMap<Long, CspfPath>();
42 public ConstrainedPath computeP2pPath(VertexKey src, VertexKey dst, PathConstraints cts) {
43 ConstrainedPathBuilder cpathBuilder;
44 List<ConnectedEdge> edges;
46 int currentCost = Integer.MAX_VALUE;
48 LOG.info("Start CSPF Path Computation from {} to {} with constraints {}", src, dst, cts);
50 /* Initialize algorithm */
51 this.constraints = cts;
52 cpathBuilder = initializePathComputation(src, dst);
53 if (cpathBuilder.getStatus() == ComputationStatus.Failed) {
54 return cpathBuilder.build();
57 cpathBuilder.setBandwidth(cts.getBandwidth()).setClassType(cts.getClassType());
59 visitedVertices.clear();
61 /* Process all Connected Vertex until priority queue becomes empty. Connected Vertices are added into the
62 * priority queue when processing the next Connected Vertex: see relaxMC() method */
63 while (priorityQueue.size() != 0) {
64 currentPath = priorityQueue.poll();
65 visitedVertices.put(currentPath.getVertexKey(), currentPath);
66 LOG.debug("Got path to Vertex {} from Priority Queue", currentPath.getVertex().toString());
67 edges = currentPath.getVertex().getOutputConnectedEdges();
69 for (ConnectedEdge edge : edges) {
70 /* Skip Connected Edges that must be prune i.e. Edges that not satisfy the given constraints,
71 * in particular the Bandwidth, TE Metric and Delay. */
72 if (pruneEdge(edge, currentPath)) {
73 LOG.trace(" Prune Edge {}", edge.toString());
76 if ((relaxMultiConstraints(edge, currentPath)) && (pathDestination.getCost() < currentCost)) {
77 currentCost = pathDestination.getCost();
78 cpathBuilder.setPathDescription(getPathDescription(pathDestination.getPath()))
79 .setMetric(Uint32.valueOf(pathDestination.getCost()))
80 .setStatus(ComputationStatus.Active);
81 LOG.debug(" Found a valid path up to destination {}", cpathBuilder.getPathDescription());
85 /* The priority queue is empty => all the possible (vertex, path) elements have been explored
86 * The "ConstrainedPathBuilder" object contains the optimal path if it exists
87 * Otherwise an empty path with status failed is returned
89 if ((cpathBuilder.getStatus() == ComputationStatus.InProgress)
90 || (cpathBuilder.getPathDescription().size() == 0)) {
91 cpathBuilder.setStatus(ComputationStatus.Failed);
93 cpathBuilder.setStatus(ComputationStatus.Completed);
95 return cpathBuilder.build();
98 private boolean relaxMultiConstraints(ConnectedEdge edge, CspfPath currentPath) {
99 LOG.debug(" Start relaxing Multi Constraints on Edge {} to Vertex {}",
100 edge.toString(), edge.getDestination().toString());
101 final Long nextVertexKey = edge.getDestination().getKey();
103 /* Verify if we have not visited this Vertex to avoid loop */
104 if (visitedVertices.containsKey(nextVertexKey)) {
108 /* Get Next Vertex from processedPath or create a new one if it has not yet processed */
109 CspfPath nextPath = processedPath.get(nextVertexKey);
110 if (nextPath == null) {
111 nextPath = new CspfPath(edge.getDestination());
112 processedPath.put(nextPath.getVertexKey(), nextPath);
115 /* Add or update the CspfPath in the Priority Queue if total path Cost is lower than cost associated
116 * to this next Vertex. This could occurs if we process a Vertex that as not yet been visited in the Graph
117 * or if we found a shortest path up to this Vertex. */
118 int totalCost = edge.getEdge().getEdgeAttributes().getTeMetric().intValue() + currentPath.getCost();
119 if (totalCost < nextPath.getCost()) {
120 nextPath.setCost(totalCost)
121 .replacePath(currentPath.getPath())
122 .addConnectedEdge(edge);
123 /* It is not possible to directly update the CspfPath in the Priority Queue. Indeed, if we modify the path
124 * weight, the Priority Queue must be re-ordered. So, we need fist to remove the CspfPath if it is present
125 * in the Priority Queue, then, update the Path Weight, and finally (re-)insert it in the Priority Queue.
127 priorityQueue.removeIf((path) -> path.getVertexKey().equals(nextVertexKey));
128 nextPath.setKey(totalCost);
129 priorityQueue.add(nextPath);
130 LOG.debug(" Added path to Vertex {} in the Priority Queue", nextPath.getVertex().toString());
132 /* Return True if we reach the destination, false otherwise */
133 return pathDestination.equals(nextPath);