2 * Copyright © 2017 AT&T, Inc. and others. 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
9 package org.opendaylight.transportpce.pce.graph;
11 import java.util.ArrayList;
12 import java.util.HashMap;
13 import java.util.Iterator;
14 import java.util.List;
17 import org.jgrapht.GraphPath;
18 import org.jgrapht.alg.shortestpath.KShortestSimplePaths;
19 import org.jgrapht.alg.shortestpath.PathValidator;
20 import org.jgrapht.graph.DefaultDirectedWeightedGraph;
21 import org.opendaylight.transportpce.common.ResponseCodes;
22 import org.opendaylight.transportpce.pce.constraints.PceConstraints;
23 import org.opendaylight.transportpce.pce.networkanalyzer.PceLink;
24 import org.opendaylight.transportpce.pce.networkanalyzer.PceNode;
25 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult;
26 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult.LocalCause;
27 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.NodeId;
29 import org.slf4j.Logger;
30 import org.slf4j.LoggerFactory;
32 public class PceGraph {
34 private static final Logger LOG = LoggerFactory.getLogger(PceGraph.class);
36 ////////////////////////// for Graph ///////////////////////////
37 // how many paths to bring
38 int kpathsToBring = 10;
40 int mhopsPerPath = 50;
43 private Map<NodeId, PceNode> allPceNodes = new HashMap<NodeId, PceNode>();
44 private PceNode apceNode = null;
45 private PceNode zpceNode = null;
47 PceConstraints pceHardConstraints;
48 PceConstraints pceSoftConstraints;
51 private PceResult pceResult = null;
52 private List<PceLink> shortestPathAtoZ = null;
54 // for path calculation
55 List<GraphPath<String, PceGraphEdge>> allWPaths = null;
57 private List<PceLink> pathAtoZ = new ArrayList<PceLink>();
59 public PceGraph(PceNode aendNode, PceNode zendNode, Map<NodeId, PceNode> allPceNodes,
60 PceConstraints pceHardConstraints, PceConstraints pceSoftConstraints, PceResult pceResult) {
62 this.apceNode = aendNode;
63 this.zpceNode = zendNode;
64 this.allPceNodes = allPceNodes;
65 this.pceResult = pceResult;
66 this.pceHardConstraints = pceHardConstraints;
67 this.pceSoftConstraints = pceSoftConstraints;
69 LOG.info("In GraphCalculator: A and Z = {} / {} ", aendNode.toString(), zendNode.toString());
70 LOG.debug("In GraphCalculator: allPceNodes size {}, nodes {} ", allPceNodes.size(), allPceNodes.toString());
74 public boolean calcPath() {
76 LOG.info(" In PCE GRAPH calcPath : K SHORT PATHS algorithm ");
78 DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph =
79 new DefaultDirectedWeightedGraph<String, PceGraphEdge>(PceGraphEdge.class);
80 populateWithNodes(weightedGraph);
81 populateWithLinks(weightedGraph);
83 if (!runKgraphs(weightedGraph)) {
84 LOG.info("In calcPath : pceResult {}", pceResult.toString());
88 // validate found paths
89 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
90 for (GraphPath<String, PceGraphEdge> path : allWPaths) {
92 PostAlgoPathValidator papv = new PostAlgoPathValidator();
93 pceResult = papv.checkPath(path, allPceNodes, pceResult);
94 LOG.info("In calcPath after PostAlgoPathValidator {} {}",
95 pceResult.getResponseCode(), ResponseCodes.RESPONSE_OK);
97 if (!pceResult.getResponseCode().equals(ResponseCodes.RESPONSE_OK)) {
98 LOG.info("In calcPath: post algo validations DROPPED the path {}", path.toString());
104 for (PceGraphEdge edge : path.getEdgeList()) {
105 pathAtoZ.add(edge.link());
108 shortestPathAtoZ = new ArrayList<>(pathAtoZ);
109 LOG.info("In calcPath Path FOUND path for wl [{}], hops {}, distance per metrics {}, path AtoZ {}",
110 pceResult.getResultWavelength(), pathAtoZ.size(), path.getWeight(), pathAtoZ.toString());
114 if (shortestPathAtoZ != null) {
115 LOG.info("In calcPath CHOOSEN PATH for wl [{}], hops {}, path AtoZ {}",
116 pceResult.getResultWavelength(), shortestPathAtoZ.size(), shortestPathAtoZ.toString());
118 LOG.info("In calcPath : pceResult {}", pceResult.toString());
119 return (pceResult.getStatus());
122 private boolean runKgraphs(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
124 if (weightedGraph.edgeSet().isEmpty() || weightedGraph.vertexSet().isEmpty()) {
128 PathValidator<String, PceGraphEdge> wpv = new InAlgoPathValidator(pceHardConstraints, zpceNode);
130 // local optimization. if 'include' constraint exists then increase amount of paths to return.
131 // it's because this constraint is checked at the last step when part of good paths
132 // are dropped by other constraints
133 if (!pceHardConstraints.getListToInclude().isEmpty()) {
134 kpathsToBring = kpathsToBring * 10;
135 LOG.info("k = {}",kpathsToBring);
138 // KShortestPaths on weightedGraph
139 KShortestSimplePaths<String, PceGraphEdge> swp =
140 new KShortestSimplePaths<String, PceGraphEdge>(weightedGraph, mhopsPerPath, wpv);
142 allWPaths = swp.getPaths(apceNode.getNodeId().getValue(), zpceNode.getNodeId().getValue(), kpathsToBring);
144 if (allWPaths.isEmpty()) {
145 LOG.info(" In runKgraphs : algorithm didn't find any path");
146 pceResult.setLocalCause(LocalCause.NO_PATH_EXISTS);
147 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
152 for (GraphPath<String, PceGraphEdge> path : allWPaths) {
153 LOG.info("path Weight: {} : {}", path.getWeight(), path.getVertexList().toString());
160 private boolean validateLinkforGraph(PceLink pcelink) {
162 PceNode source = allPceNodes.get(pcelink.getSourceId());
163 PceNode dest = allPceNodes.get(pcelink.getDestId());
165 if (source == null) {
166 LOG.error("In addLinkToGraph link source node is null : {}", pcelink.toString());
170 LOG.error("In addLinkToGraph link dest node is null : {}", pcelink.toString());
174 LOG.debug("In addLinkToGraph link to nodes : {}{} {}", pcelink.toString(), source.toString(), dest.toString());
179 private void populateWithNodes(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
180 Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
181 while (nodes.hasNext()) {
182 Map.Entry<NodeId, PceNode> node = nodes.next();
183 weightedGraph.addVertex(node.getValue().getNodeId().getValue());
184 LOG.debug("In populateWithNodes in node : {}", node.getValue().toString());
188 private boolean populateWithLinks(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
190 Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
191 while (nodes.hasNext()) {
193 Map.Entry<NodeId, PceNode> node = nodes.next();
195 PceNode pcenode = node.getValue();
196 List<PceLink> links = pcenode.getOutgoingLinks();
198 LOG.debug("In populateGraph: use node for graph {}", pcenode.toString());
200 for (PceLink link : links) {
201 LOG.debug("In populateGraph node {} : add edge to graph {}", pcenode.toString(), link.toString());
203 if (!validateLinkforGraph(link)) {
207 PceGraphEdge graphLink = new PceGraphEdge(link);
208 weightedGraph.addEdge(link.getSourceId().getValue(), link.getDestId().getValue(), graphLink);
210 weightedGraph.setEdgeWeight(graphLink, chooseWeight(link));
216 private double chooseWeight(PceLink link) {
218 // HopCount is default
220 switch (pceHardConstraints.getPceMetrics()) {
222 // TODO implement IGPMetric - low priority.
223 LOG.warn("In PceGraph not implemented IGPMetric. HopCount works as a default");
227 // TODO implement TEMetric - low priority
228 LOG.warn("In PceGraph not implemented TEMetric. HopCount works as a default");
233 LOG.debug("In PceGraph HopCount is used as a metrics. {}", link.toString());
236 case PropagationDelay :
237 weight = link.getLatency();
238 LOG.debug("In PceGraph PropagationDelay is used as a metrics. {}", link.toString());
248 ////////////////////////////////////////////////////////////////////////////////////////////////////////////
249 public List<PceLink> getPathAtoZ() {
250 return shortestPathAtoZ;
253 public PceResult getReturnStructure() {
257 public void setConstrains(PceConstraints pceHardConstraintsInput, PceConstraints pceSoftConstraintsInput) {
258 this.pceHardConstraints = pceHardConstraintsInput;
259 this.pceSoftConstraints = pceSoftConstraintsInput;