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;
16 import org.jgrapht.GraphPath;
17 import org.jgrapht.alg.shortestpath.KShortestSimplePaths;
18 import org.jgrapht.alg.shortestpath.PathValidator;
19 import org.jgrapht.graph.DefaultDirectedWeightedGraph;
20 import org.opendaylight.transportpce.common.ResponseCodes;
21 import org.opendaylight.transportpce.common.StringConstants;
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.http.org.openroadm.common.state.types.rev191129.State;
28 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 private int kpathsToBring = 10;
41 private int mhopsPerPath = 50;
44 private Map<NodeId, PceNode> allPceNodes = new HashMap<>();
45 private PceNode apceNode = null;
46 private PceNode zpceNode = null;
47 private String serviceType = "";
49 PceConstraints pceHardConstraints;
50 PceConstraints pceSoftConstraints;
53 private PceResult pceResult = null;
54 private List<PceLink> shortestPathAtoZ = null;
56 // for path calculation
57 List<GraphPath<String, PceGraphEdge>> allWPaths = null;
59 private List<PceLink> pathAtoZ = new ArrayList<>();
61 public PceGraph(PceNode aendNode, PceNode zendNode, Map<NodeId, PceNode> allPceNodes,
62 PceConstraints pceHardConstraints, PceConstraints pceSoftConstraints, PceResult pceResult,
65 this.apceNode = aendNode;
66 this.zpceNode = zendNode;
67 this.allPceNodes = allPceNodes;
68 this.pceResult = pceResult;
69 this.pceHardConstraints = pceHardConstraints;
70 this.pceSoftConstraints = pceSoftConstraints;
71 this.serviceType = serviceType;
73 LOG.info("In GraphCalculator: A and Z = {} / {} ", aendNode, zendNode);
74 LOG.debug("In GraphCalculator: allPceNodes size {}, nodes {} ", allPceNodes.size(), allPceNodes);
77 public boolean calcPath() {
79 LOG.info(" In PCE GRAPH calcPath : K SHORT PATHS algorithm ");
81 DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph =
82 new DefaultDirectedWeightedGraph<>(PceGraphEdge.class);
83 populateWithNodes(weightedGraph);
84 populateWithLinks(weightedGraph);
86 if (!runKgraphs(weightedGraph)) {
87 LOG.info("In calcPath : pceResult {}", pceResult);
91 // validate found paths
92 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
93 for (GraphPath<String, PceGraphEdge> path : allWPaths) {
94 PostAlgoPathValidator papv = new PostAlgoPathValidator();
95 pceResult = papv.checkPath(path, allPceNodes, pceResult, pceHardConstraints, serviceType);
96 LOG.info("In calcPath after PostAlgoPathValidator {} {}",
97 pceResult.getResponseCode(), ResponseCodes.RESPONSE_OK);
99 if (!pceResult.getResponseCode().equals(ResponseCodes.RESPONSE_OK)) {
100 LOG.info("In calcPath: post algo validations DROPPED the path {}", path);
106 for (PceGraphEdge edge : path.getEdgeList()) {
107 pathAtoZ.add(edge.link());
110 shortestPathAtoZ = new ArrayList<>(pathAtoZ);
111 if ((StringConstants.SERVICE_TYPE_100GE.equals(serviceType))
112 || (StringConstants.SERVICE_TYPE_OTU4.equals(serviceType))) {
113 LOG.info("In calcPath Path FOUND path for wl [{}], min Freq assignment {}, max Freq assignment {},"
114 + " hops {}, distance per metrics {}, path AtoZ {}",
115 pceResult.getResultWavelength(), pceResult.getMinFreq(), pceResult.getMaxFreq(),
116 pathAtoZ.size(), path.getWeight(), pathAtoZ);
119 // Service is at OTN layer and is relying on a supporting wavelength service
120 LOG.info("In calcPath Path FOUND path for hops {}, distance per metrics {}, path AtoZ {}",
121 pathAtoZ.size(), path.getWeight(), pathAtoZ);
127 if (shortestPathAtoZ != null) {
128 LOG.info("In calcPath CHOOSEN PATH for wl [{}], min freq {}, max freq {}, hops {}, path AtoZ {}",
129 pceResult.getResultWavelength(), pceResult.getMinFreq(), pceResult.getMaxFreq(),
130 shortestPathAtoZ.size(), shortestPathAtoZ);
132 LOG.info("In calcPath : pceResult {}", pceResult);
133 return (pceResult.getStatus());
136 private boolean runKgraphs(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
138 if (weightedGraph.edgeSet().isEmpty() || weightedGraph.vertexSet().isEmpty()) {
141 PathValidator<String, PceGraphEdge> wpv = new InAlgoPathValidator();
143 // KShortestPaths on weightedGraph
144 KShortestSimplePaths<String, PceGraphEdge> swp =
145 new KShortestSimplePaths<>(weightedGraph, mhopsPerPath, wpv);
146 allWPaths = swp.getPaths(apceNode.getNodeId().getValue(), zpceNode.getNodeId().getValue(), kpathsToBring);
148 if (allWPaths.isEmpty()) {
149 LOG.info(" In runKgraphs : algorithm didn't find any path");
150 pceResult.setLocalCause(LocalCause.NO_PATH_EXISTS);
151 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
156 for (GraphPath<String, PceGraphEdge> path : allWPaths) {
157 LOG.debug("path Weight: {} : {}", path.getWeight(), path.getVertexList());
163 private boolean validateLinkforGraph(PceLink pcelink) {
165 PceNode source = allPceNodes.get(pcelink.getSourceId());
166 PceNode dest = allPceNodes.get(pcelink.getDestId());
168 if (source == null) {
169 LOG.error("In addLinkToGraph link source node is null : {}", pcelink);
173 LOG.error("In addLinkToGraph link dest node is null : {}", pcelink);
176 LOG.debug("In addLinkToGraph link to nodes : {}{} {}", pcelink, source, dest);
180 private void populateWithNodes(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
181 Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
182 while (nodes.hasNext()) {
183 Map.Entry<NodeId, PceNode> node = nodes.next();
184 if (State.InService.equals(node.getValue().getState())) {
185 weightedGraph.addVertex(node.getValue().getNodeId().getValue());
186 LOG.debug("In populateWithNodes in node : {}", node.getValue());
191 private boolean populateWithLinks(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
193 Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
194 while (nodes.hasNext()) {
196 Map.Entry<NodeId, PceNode> node = nodes.next();
198 PceNode pcenode = node.getValue();
199 List<PceLink> links = pcenode.getOutgoingLinks();
201 LOG.debug("In populateGraph: use node for graph {}", pcenode);
203 for (PceLink link : links) {
204 LOG.debug("In populateGraph node {} : add edge to graph {}", pcenode, link);
206 if (!validateLinkforGraph(link)) {
209 if (State.InService.equals(link.getState())) {
210 PceGraphEdge graphLink = new PceGraphEdge(link);
211 weightedGraph.addEdge(link.getSourceId().getValue(), link.getDestId().getValue(), graphLink);
213 weightedGraph.setEdgeWeight(graphLink, chooseWeight(link));
220 private double chooseWeight(PceLink link) {
221 // HopCount is default
223 switch (pceHardConstraints.getPceMetrics()) {
226 LOG.debug("In PceGraph HopCount is used as a metrics. {}", link);
228 case PropagationDelay :
229 weight = link.getLatency();
230 LOG.debug("In PceGraph PropagationDelay is used as a metrics. {}", link);
231 if ((("1GE".equals(serviceType)) || ("10GE".equals(serviceType)) || ("ODU4".equals(serviceType)))
233 LOG.warn("PropagationDelay set as metric, but latency is null: is latency set for OTN link {}?",
237 // TODO implement IGPMetric and TEMetric - low priority.
241 LOG.warn("In PceGraph {} not implemented. HopCount works as a default",
242 pceHardConstraints.getPceMetrics());
248 public int getKpathsToBring() {
249 return kpathsToBring;
252 public void setKpathsToBring(int kpathsToBring) {
253 this.kpathsToBring = kpathsToBring;
256 public void setMhopsPerPath(int mhopsPerPath) {
257 this.mhopsPerPath = mhopsPerPath;
260 public List<PceLink> getPathAtoZ() {
261 return shortestPathAtoZ;
264 public PceResult getReturnStructure() {
268 public void setConstrains(PceConstraints pceHardConstraintsInput, PceConstraints pceSoftConstraintsInput) {
269 this.pceHardConstraints = pceHardConstraintsInput;
270 this.pceSoftConstraints = pceSoftConstraintsInput;