package org.opendaylight.transportpce.pce.graph;
import java.util.ArrayList;
+import java.util.BitSet;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
+import java.util.Map.Entry;
+import java.util.function.Function;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
-import org.jgrapht.alg.shortestpath.KShortestSimplePaths;
import org.jgrapht.alg.shortestpath.PathValidator;
+import org.jgrapht.alg.shortestpath.YenKShortestPath;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.opendaylight.transportpce.common.ResponseCodes;
+import org.opendaylight.transportpce.common.StringConstants;
+import org.opendaylight.transportpce.common.network.NetworkTransactionService;
import org.opendaylight.transportpce.pce.constraints.PceConstraints;
import org.opendaylight.transportpce.pce.networkanalyzer.PceLink;
import org.opendaylight.transportpce.pce.networkanalyzer.PceNode;
import org.opendaylight.transportpce.pce.networkanalyzer.PceResult;
import org.opendaylight.transportpce.pce.networkanalyzer.PceResult.LocalCause;
+import org.opendaylight.yang.gen.v1.http.org.opendaylight.transportpce.pce.rev240205.PceConstraintMode;
+import org.opendaylight.yang.gen.v1.http.org.openroadm.common.state.types.rev191129.State;
import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.NodeId;
+import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.topology.rev180226.LinkId;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
////////////////////////// for Graph ///////////////////////////
// how many paths to bring
- private int kpathsToBring = 10;
-
- // max #hops
- private int mhopsPerPath = 50;
+ private int kpathsToBring = 15;
// input
private Map<NodeId, PceNode> allPceNodes = new HashMap<>();
+ private Map<LinkId, PceLink> allPceLinks = new HashMap<>();
private PceNode apceNode = null;
private PceNode zpceNode = null;
private String serviceType = "";
-
+ private Double margin = null;
PceConstraints pceHardConstraints;
- PceConstraints pceSoftConstraints;
+ private PceConstraintMode pceConstraintMode;
+ private BitSet spectrumConstraint;
// results
private PceResult pceResult = null;
private List<PceLink> shortestPathAtoZ = null;
// for path calculation
- List<GraphPath<String, PceGraphEdge>> allWPaths = null;
+ Map<Integer, GraphPath<String, PceGraphEdge>> allWPaths = null;
private List<PceLink> pathAtoZ = new ArrayList<>();
+ private final NetworkTransactionService networkTransactionService;
+
public PceGraph(PceNode aendNode, PceNode zendNode, Map<NodeId, PceNode> allPceNodes,
- PceConstraints pceHardConstraints, PceConstraints pceSoftConstraints, PceResult pceResult,
- String serviceType) {
+ Map<LinkId, PceLink> allPceLinks, PceConstraints pceHardConstraints,PceResult pceResult, String serviceType,
+ NetworkTransactionService networkTransactionService, PceConstraintMode mode, BitSet spectrumConstraint) {
super();
this.apceNode = aendNode;
this.zpceNode = zendNode;
this.allPceNodes = allPceNodes;
+ this.allPceLinks = allPceLinks;
this.pceResult = pceResult;
this.pceHardConstraints = pceHardConstraints;
- this.pceSoftConstraints = pceSoftConstraints;
this.serviceType = serviceType;
+ this.networkTransactionService = networkTransactionService;
+ this.pceConstraintMode = mode;
+ this.spectrumConstraint = spectrumConstraint;
LOG.info("In GraphCalculator: A and Z = {} / {} ", aendNode, zendNode);
LOG.debug("In GraphCalculator: allPceNodes size {}, nodes {} ", allPceNodes.size(), allPceNodes);
LOG.info(" In PCE GRAPH calcPath : K SHORT PATHS algorithm ");
- DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph =
+ Graph<String, PceGraphEdge> weightedGraph =
new DefaultDirectedWeightedGraph<>(PceGraphEdge.class);
populateWithNodes(weightedGraph);
populateWithLinks(weightedGraph);
if (!runKgraphs(weightedGraph)) {
- LOG.info("In calcPath : pceResult {}", pceResult);
+ LOG.error("In calcPath : pceResult {}", pceResult);
return false;
}
-
// validate found paths
pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
- for (GraphPath<String, PceGraphEdge> path : allWPaths) {
- PostAlgoPathValidator papv = new PostAlgoPathValidator();
- pceResult = papv.checkPath(path, allPceNodes, pceResult, pceHardConstraints, serviceType);
- LOG.info("In calcPath after PostAlgoPathValidator {} {}",
- pceResult.getResponseCode(), ResponseCodes.RESPONSE_OK);
-
- if (!pceResult.getResponseCode().equals(ResponseCodes.RESPONSE_OK)) {
- LOG.info("In calcPath: post algo validations DROPPED the path {}", path);
+ for (Entry<Integer, GraphPath<String, PceGraphEdge>> entry : allWPaths.entrySet()) {
+ GraphPath<String, PceGraphEdge> path = entry.getValue();
+ LOG.info("validating path n° {} - {}", entry.getKey(), path.getVertexList());
+ PostAlgoPathValidator papv = new PostAlgoPathValidator(networkTransactionService, spectrumConstraint);
+ pceResult = papv.checkPath(
+ path, allPceNodes, allPceLinks, pceResult, pceHardConstraints, serviceType, pceConstraintMode);
+ this.margin = papv.getTpceCalculatedMargin();
+ if (ResponseCodes.RESPONSE_OK.equals(pceResult.getResponseCode())) {
+ LOG.info("Path is validated");
+ } else {
+ LOG.warn("In calcPath: post algo validations DROPPED the path {}; for following cause: {}",
+ path, pceResult.getLocalCause());
continue;
}
}
shortestPathAtoZ = new ArrayList<>(pathAtoZ);
- if (("100GE".equals(serviceType)) || ("OTU4".equals(serviceType))) {
- LOG.info("In calcPath Path FOUND path for wl [{}], hops {}, distance per metrics {}, path AtoZ {}",
- pceResult.getResultWavelength(), pathAtoZ.size(), path.getWeight(), pathAtoZ);
- break;
- } else {
- // Service is at OTN layer and is relying on a supporting wavelength service
- LOG.info("In calcPath Path FOUND path for hops {}, distance per metrics {}, path AtoZ {}",
+ switch (serviceType) {
+
+ case StringConstants.SERVICE_TYPE_100GE_T:
+ case StringConstants.SERVICE_TYPE_OTUC2:
+ case StringConstants.SERVICE_TYPE_OTUC3:
+ case StringConstants.SERVICE_TYPE_OTUC4:
+ case StringConstants.SERVICE_TYPE_400GE:
+ case StringConstants.SERVICE_TYPE_OTU4:
+ LOG.debug(
+ "In calcPath Path FOUND path for wl [{}], min Freq assignment {}, max Freq assignment {},"
+ + " hops {}, distance per metrics {}, path AtoZ {}",
+ pceResult.getResultWavelength(), pceResult.getMinFreq(), pceResult.getMaxFreq(),
pathAtoZ.size(), path.getWeight(), pathAtoZ);
- break;
+ break;
+
+ default:
+ LOG.debug(
+ "In calcPath Path FOUND path for hops {}, distance per metrics {}, path AtoZ {}",
+ pathAtoZ.size(), path.getWeight(), pathAtoZ);
+ break;
}
+ break;
}
if (shortestPathAtoZ != null) {
- LOG.info("In calcPath CHOOSEN PATH for wl [{}], hops {}, path AtoZ {}",
- pceResult.getResultWavelength(), shortestPathAtoZ.size(), shortestPathAtoZ);
+ LOG.info("In calcPath CHOOSEN PATH for wl [{}], min freq {}, max freq {}, hops {}, path AtoZ {}",
+ pceResult.getResultWavelength(), pceResult.getMinFreq(), pceResult.getMaxFreq(),
+ shortestPathAtoZ.size(), shortestPathAtoZ);
}
LOG.info("In calcPath : pceResult {}", pceResult);
return (pceResult.getStatus());
}
- private boolean runKgraphs(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
+ private boolean runKgraphs(Graph<String, PceGraphEdge> weightedGraph) {
if (weightedGraph.edgeSet().isEmpty() || weightedGraph.vertexSet().isEmpty()) {
return false;
}
PathValidator<String, PceGraphEdge> wpv = new InAlgoPathValidator();
- // KShortestPaths on weightedGraph
- KShortestSimplePaths<String, PceGraphEdge> swp =
- new KShortestSimplePaths<>(weightedGraph, mhopsPerPath, wpv);
- allWPaths = swp.getPaths(apceNode.getNodeId().getValue(), zpceNode.getNodeId().getValue(), kpathsToBring);
+ // YenShortestPath on weightedGraph
+ YenKShortestPath<String, PceGraphEdge> swp = new YenKShortestPath<>(weightedGraph, wpv);
+ List<GraphPath<String, PceGraphEdge>> weightedPathList = swp
+ .getPaths(apceNode.getNodeId().getValue(), zpceNode.getNodeId().getValue(), kpathsToBring);
+ allWPaths = IntStream
+ .range(0, weightedPathList.size())
+ .boxed()
+ .collect(Collectors.toMap(Function.identity(), weightedPathList::get));
if (allWPaths.isEmpty()) {
LOG.info(" In runKgraphs : algorithm didn't find any path");
}
// debug print
- for (GraphPath<String, PceGraphEdge> path : allWPaths) {
- LOG.debug("path Weight: {} : {}", path.getWeight(), path.getVertexList());
- }
-
+ allWPaths
+ .forEach((k, v) -> LOG.info("path n° {} - weight: {} - path: {}", k, v.getWeight(), v.getVertexList()));
return true;
}
return true;
}
- private void populateWithNodes(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
+ private void populateWithNodes(Graph<String, PceGraphEdge> weightedGraph) {
Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
while (nodes.hasNext()) {
Map.Entry<NodeId, PceNode> node = nodes.next();
- weightedGraph.addVertex(node.getValue().getNodeId().getValue());
- LOG.debug("In populateWithNodes in node : {}", node.getValue());
+ if (State.InService.equals(node.getValue().getState())) {
+ weightedGraph.addVertex(node.getValue().getNodeId().getValue());
+ LOG.debug("In populateWithNodes in node : {}", node.getValue());
+ }
}
}
- private boolean populateWithLinks(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
+ private boolean populateWithLinks(Graph<String, PceGraphEdge> weightedGraph) {
Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
while (nodes.hasNext()) {
if (!validateLinkforGraph(link)) {
continue;
}
+ if (State.InService.equals(link.getState())) {
+ PceGraphEdge graphLink = new PceGraphEdge(link);
+ weightedGraph.addEdge(link.getSourceId().getValue(), link.getDestId().getValue(), graphLink);
- PceGraphEdge graphLink = new PceGraphEdge(link);
- weightedGraph.addEdge(link.getSourceId().getValue(), link.getDestId().getValue(), graphLink);
-
- weightedGraph.setEdgeWeight(graphLink, chooseWeight(link));
+ weightedGraph.setEdgeWeight(graphLink, chooseWeight(link));
+ }
}
}
return true;
case PropagationDelay :
weight = link.getLatency();
LOG.debug("In PceGraph PropagationDelay is used as a metrics. {}", link);
- if ((("1GE".equals(serviceType)) || ("10GE".equals(serviceType)) || ("ODU4".equals(serviceType)))
- && (weight == 0)) {
+ if ((weight == 0)
+ && ("1GE".equals(serviceType) || "10GE".equals(serviceType) || "ODU4".equals(serviceType))) {
LOG.warn("PropagationDelay set as metric, but latency is null: is latency set for OTN link {}?",
link);
}
this.kpathsToBring = kpathsToBring;
}
- public void setMhopsPerPath(int mhopsPerPath) {
- this.mhopsPerPath = mhopsPerPath;
- }
-
public List<PceLink> getPathAtoZ() {
return shortestPathAtoZ;
}
return pceResult;
}
- public void setConstrains(PceConstraints pceHardConstraintsInput, PceConstraints pceSoftConstraintsInput) {
+ public Double getmargin() {
+ return margin;
+ }
+
+ public void setConstrains(PceConstraints pceHardConstraintsInput) {
this.pceHardConstraints = pceHardConstraintsInput;
- this.pceSoftConstraints = pceSoftConstraintsInput;
}
}