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;
11 import edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath;
12 import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
13 import java.util.ArrayList;
14 import java.util.HashMap;
15 import java.util.Iterator;
16 import java.util.List;
18 import org.apache.commons.collections15.Transformer;
19 import org.opendaylight.transportpce.common.ResponseCodes;
20 import org.opendaylight.transportpce.pce.PceResult.LocalCause;
21 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev150608.NodeId;
22 //import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev150608.network.Node;
23 import org.slf4j.Logger;
24 import org.slf4j.LoggerFactory;
27 public class PceGraph {
29 private static final Logger LOG = LoggerFactory.getLogger(PceCalculation.class);
31 ////////////////////////// for Graph ///////////////////////////
32 private DirectedSparseMultigraph<PceNode, PceLink> nwGraph = new DirectedSparseMultigraph<PceNode, PceLink>();
33 private DijkstraShortestPath<PceNode, PceLink> shortestPath = null;
36 private Map<NodeId, PceNode> allPceNodes = new HashMap<NodeId, PceNode>();
37 private PceNode apceNode = null;
38 private PceNode zpceNode = null;
40 PceConstraints pceHardConstraints;
41 PceConstraints pceSoftConstraints;
44 private PceResult pceResult = null;
45 private List<PceLink> shortestPathAtoZ = null;
48 private static final int MAX_WAWELENGTH = 96;
50 // for path calculation
51 private List<PceLink> pathAtoZ = null;
52 private int minFoundDistance;
53 private int tmpAtozDistance = 0;
54 private int tmpAtozLatency = 0;
55 private int bestDistance;
56 private boolean noPathExists = false;
58 private boolean foundButTooHighLatency = false;
60 private List<ListOfNodes> listOfNodesPerWL = new ArrayList<ListOfNodes>();
62 public PceGraph(PceNode aendNode, PceNode zendNode, Map<NodeId, PceNode> allPceNodes,
63 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;
72 // TODO - fix the assumption that wavelengths are from 1 to 96 and can be used
74 this.listOfNodesPerWL.add(new ListOfNodes());
75 for (int i = 1; i <= MAX_WAWELENGTH; i++) {
76 // create list of nodes per wavelength
77 ListOfNodes wls = new ListOfNodes();
78 this.listOfNodesPerWL.add(wls);
81 LOG.debug("In GraphCalculator: A and Z = {} / {}", aendNode.toString(), zendNode.toString());
82 LOG.debug("In GraphCalculator: allPceNodes = {}", allPceNodes.toString());
85 public boolean calcPath() {
87 LOG.info("In calcPath: metric {} is used ", this.pceHardConstraints.getPceMetrics());
89 populateGraph(this.allPceNodes);
91 LOG.info(" In PCE GRAPH : QUICK algorithm ");
96 this.bestDistance = this.tmpAtozDistance;
98 if (chooseWavelength()) {
99 this.pceResult.setRC(ResponseCodes.RESPONSE_OK);
100 this.shortestPathAtoZ = this.pathAtoZ;
101 LOG.info("In GraphCalculator QUICK CalcPath: AtoZ {}", this.pathAtoZ.toString());
102 LOG.info("In GraphCalculator QUICK CalcPath: pceResult {}", this.pceResult.toString());
106 // continue work per wavelength
107 LOG.warn(" In PCE GRAPH : QUICK algorithm didn't find shared wavelength over the shortest path");
111 LOG.warn(" In PCE GRAPH : QUICK algorithm didn't find shortest path with single wavelength");
112 if (this.noPathExists) {
113 // quick algo looks for path independently on wavelength. therefore no path
114 // means fatal problem
115 LOG.warn(" In PCE GRAPH : QUICK algorithm didn't find any path");
116 this.pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
120 // rearrange all nodes per the relevant wavelength indexes
121 extractWLs(this.allPceNodes);
123 this.pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
124 boolean firstPath = true;
126 for (int i = 1; i <= MAX_WAWELENGTH; i++) {
127 LOG.info(" In PCE GRAPH : FUll algorithm for WL {}", i);
128 List<PceNode> nodes = this.listOfNodesPerWL.get(i).getNodes();
129 populateGraph(nodes);
136 // set minFoundDistance for the first time
141 if (this.tmpAtozDistance < this.minFoundDistance) {
145 if (this.tmpAtozDistance == this.bestDistance) {
146 // optimization: stop on the first WL with result == the best
151 // return codes can come in different orders. this method fixes it a bit
152 // TODO build it better
155 LOG.info("In GraphCalculator FUll CalcPath: pceResult {}", this.pceResult.toString());
156 return (this.pceResult.getStatus());
159 private boolean populateGraph(Map<NodeId, PceNode> allNodes) {
163 Iterator<Map.Entry<NodeId, PceNode>> nodes = allNodes.entrySet().iterator();
164 while (nodes.hasNext()) {
166 Map.Entry<NodeId, PceNode> node = nodes.next();
168 PceNode pcenode = node.getValue();
169 List<PceLink> links = pcenode.getOutgoingLinks();
171 LOG.debug("In populateGraph: use node for graph {}", pcenode.toString());
173 for (PceLink link : links) {
174 LOG.debug("In populateGraph: add edge to graph {}", link.toString());
175 addLinkToGraph(link);
184 private boolean populateGraph(List<PceNode> allNodes) {
188 for (PceNode node : allNodes) {
189 List<PceLink> links = node.getOutgoingLinks();
191 LOG.debug("In populateGraph: use node for graph {}", node.toString());
193 for (PceLink link : links) {
194 LOG.debug("In populateGraph: add edge to graph {}", link.toString());
195 addLinkToGraph(link);
204 private boolean runGraph() {
205 LOG.info("In runGraph Vertices: {}; Eges: {} ", this.nwGraph.getVertexCount(), this.nwGraph.getEdgeCount());
207 this.pathAtoZ = null;
210 this.shortestPath = calcAlgo();
212 if (this.shortestPath == null) {
213 this.noPathExists = true;
214 LOG.error("In runGraph: shortest path alg is null ");// ,
218 this.pathAtoZ = this.shortestPath.getPath(this.apceNode, this.zpceNode);
220 if ((this.pathAtoZ == null) || (this.pathAtoZ.size() == 0)) {
221 LOG.info("In runGraph: AtoZ path is empty");
222 this.pceResult.setLocalCause(LocalCause.NO_PATH_EXISTS);
226 pathMetricsToCompare();
228 return compareMaxLatency();
230 } catch (IllegalArgumentException e) {
231 LOG.error("In runGraph: can't calculate the path. A or Z node don't have any links {}", e);
232 this.noPathExists = true;
238 private DijkstraShortestPath<PceNode, PceLink> calcAlgo() {
240 Transformer<PceLink, Double> wtTransformer = new Transformer<PceLink, Double>() {
242 public Double transform(PceLink link) {
243 return link.getLatency();
247 this.shortestPath = null;
249 switch (this.pceHardConstraints.getPceMetrics()) {
250 case PropagationDelay:
251 this.shortestPath = new DijkstraShortestPath<>(this.nwGraph, wtTransformer);
252 LOG.debug("In calcShortestPath: PropagationDelay method run ");
255 this.shortestPath = new DijkstraShortestPath<>(this.nwGraph);
256 LOG.debug("In calcShortestPath: HopCount method run ");
260 this.shortestPath = new DijkstraShortestPath<>(this.nwGraph);
261 LOG.warn("In calcShortestPath: instead IGPMetric/TEMetric method Hop-Count runs as a default ");
265 return this.shortestPath;
269 private void addLinkToGraph(PceLink pcelink) {
271 PceNode source = this.allPceNodes.get(pcelink.getSourceId());
272 PceNode dest = this.allPceNodes.get(pcelink.getDestId());
274 if (source == null) {
275 LOG.error("In addLinkToGraph link source node is null : {}", pcelink.toString());
279 LOG.error("In addLinkToGraph link dest node is null : {}", pcelink.toString());
283 LOG.debug("In addLinkToGraph link and nodes : {} ; {} / {}", pcelink.toString(), source.toString(),
285 this.nwGraph.addEdge(pcelink, source, dest);
290 * "QUICK" approach build shortest path. and then look for a single wavelength
293 private boolean chooseWavelength() {
294 for (long i = 1; i <= MAX_WAWELENGTH; i++) {
295 boolean completed = true;
296 for (PceLink link : this.pathAtoZ) {
297 PceNode pceNode = this.allPceNodes.get(link.getSourceId());
298 if (!pceNode.checkWL(i)) {
304 this.pceResult.setResultWavelength(i);
308 return (this.pceResult.getResultWavelength() > 0);
311 public List<PceLink> getPathAtoZ() {
312 return this.shortestPathAtoZ;
315 public PceResult getReturnStructure() {
316 return this.pceResult;
319 // TODO build ordered set ordered per the index. Current assumption is that
320 // wavelenght serves as an index
321 private class ListOfNodes {
322 private List<PceNode> listOfNodes = new ArrayList<PceNode>();
324 private void addNodetoWL(PceNode node) {
325 this.listOfNodes.add(node);
328 private List<PceNode> getNodes() {
329 return this.listOfNodes;
334 private boolean extractWLs(Map<NodeId, PceNode> allNodes) {
336 Iterator<Map.Entry<NodeId, PceNode>> nodes = allNodes.entrySet().iterator();
337 while (nodes.hasNext()) {
339 Map.Entry<NodeId, PceNode> node = nodes.next();
341 PceNode pcenode = node.getValue();
342 List<Long> wls = pcenode.getAvailableWLs();
344 LOG.debug("In extractWLs wls in node : {} {}", pcenode.toString(), wls.size());
345 LOG.debug("In extractWLs listOfWLs total : {}", this.listOfNodesPerWL.size());
347 LOG.debug("In extractWLs i in wls : {}", i);
348 ListOfNodes lwl = this.listOfNodesPerWL.get(i.intValue());
349 lwl.addNodetoWL(pcenode);
356 private void cleanupGraph() {
357 LOG.debug("In cleanupGraph remove {} nodes ", this.nwGraph.getEdgeCount());
358 Iterable<PceNode> toRemove = new ArrayList<PceNode>(this.nwGraph.getVertices());
359 for (PceNode node : toRemove) {
360 this.nwGraph.removeVertex(node);
362 LOG.debug("In cleanupGraph after {} removed ", this.nwGraph.getEdgeCount());
365 private void analyzeResult() {
366 // very simple for the start
368 if (this.pceResult.getStatus()) {
372 // if request is rejected but at least once there was path found, try to save
373 // the real reason of reject
374 if (this.foundButTooHighLatency) {
375 this.pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
376 this.pceResult.setLocalCause(LocalCause.TOO_HIGH_LATENCY);
377 this.pceResult.setCalcMessage("No path available due to constraint Hard/Latency");
382 private boolean compareMaxLatency() {
384 Long latencyConstraint = this.pceHardConstraints.getMaxLatency();
386 if (latencyConstraint > 0) {
387 if (this.tmpAtozLatency > latencyConstraint) {
388 this.foundButTooHighLatency = true;
389 this.pceResult.setLocalCause(LocalCause.TOO_HIGH_LATENCY);
390 LOG.info("In validateLatency: AtoZ path has too high LATENCY {} > {}", this.tmpAtozLatency,
395 LOG.info("In validateLatency: AtoZ path is {}", this.pathAtoZ.toString());
399 private void pathMetricsToCompare() {
401 this.tmpAtozDistance = this.shortestPath.getDistance(this.apceNode, this.zpceNode).intValue();
403 // TODO this code is for HopCount. excluded from switch for not implemented
404 // IGPMetric and TEMetric
405 this.tmpAtozLatency = 0;
406 for (PceLink pcelink : this.pathAtoZ) {
407 this.tmpAtozLatency = this.tmpAtozLatency + pcelink.getLatency().intValue();
410 switch (this.pceHardConstraints.getPceMetrics()) {
412 // TODO implement IGPMetric - low priority
413 LOG.error("In PceGraph not implemented IGPMetric. HopCount works as a default");
417 // TODO implement TEMetric - low priority
418 LOG.error("In PceGraph not implemented TEMetric. HopCount works as a default");
424 case PropagationDelay:
425 this.tmpAtozLatency = this.tmpAtozDistance;
429 LOG.error("In PceGraph {}: unknown metric. ", this.pceHardConstraints.getPceMetrics());
433 LOG.info("In runGraph: AtoZ size {}, distance {}, latency {} ", this.pathAtoZ.size(), this.tmpAtozDistance,
434 this.tmpAtozLatency);
435 LOG.debug("In runGraph: AtoZ {}", this.pathAtoZ.toString());
440 private void rememberPath(int index) {
441 this.minFoundDistance = this.tmpAtozDistance;
442 this.shortestPathAtoZ = this.pathAtoZ;
443 this.pceResult.setResultWavelength(Long.valueOf(index));
444 this.pceResult.setRC(ResponseCodes.RESPONSE_OK);
445 LOG.info("In GraphCalculator FUll CalcPath for wl [{}]: found AtoZ {}", index, this.pathAtoZ.toString());
449 public void setConstrains(PceConstraints pceHardCons, PceConstraints pceSoftCons) {
450 this.pceHardConstraints = pceHardCons;
451 this.pceSoftConstraints = pceSoftCons;