pce/src/main/java/org/opendaylight/transportpce/pce/PceGraph.java

   1 /*
   2  * Copyright © 2017 AT&T, Inc. and others.  All rights reserved.
   3  *
   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
   7  */
   8
   9 package org.opendaylight.transportpce.pce;
  10
  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;
  17 import java.util.Map;
  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;
  25
  26
  27 public class PceGraph {
  28     /* Logging. */
  29     private static final Logger LOG = LoggerFactory.getLogger(PceCalculation.class);
  30
  31     ////////////////////////// for Graph ///////////////////////////
  32     private DirectedSparseMultigraph<PceNode, PceLink> nwGraph = new DirectedSparseMultigraph<PceNode, PceLink>();
  33     private DijkstraShortestPath<PceNode, PceLink> shortestPath = null;
  34
  35     // input
  36     private Map<NodeId, PceNode> allPceNodes = new HashMap<NodeId, PceNode>();
  37     private PceNode apceNode = null;
  38     private PceNode zpceNode = null;
  39
  40     PceConstraints pceHardConstraints;
  41     PceConstraints pceSoftConstraints;
  42
  43     // results
  44     private PceResult pceResult = null;
  45     private List<PceLink> shortestPathAtoZ = null;
  46
  47     // TODO hard-coded 96
  48     private static final int MAX_WAWELENGTH = 96;
  49
  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;
  57
  58     private boolean foundButTooHighLatency = false;
  59
  60     private List<ListOfNodes> listOfNodesPerWL = new ArrayList<ListOfNodes>();
  61
  62     public PceGraph(PceNode aendNode, PceNode zendNode, Map<NodeId, PceNode> allPceNodes,
  63             PceConstraints pceHardConstraints, PceConstraints pceSoftConstraints, PceResult pceResult) {
  64         super();
  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
  72         // TODO - fix the assumption that wavelengths are from 1 to 96 and can be used
  73         // as index
  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);
  79         }
  80
  81         LOG.debug("In GraphCalculator: A and Z = {} / {}", aendNode.toString(), zendNode.toString());
  82         LOG.debug("In GraphCalculator: allPceNodes = {}", allPceNodes.toString());
  83     }
  84
  85     public boolean calcPath() {
  86
  87         LOG.info("In calcPath: metric {} is used ", this.pceHardConstraints.getPceMetrics());
  88
  89         populateGraph(this.allPceNodes);
  90
  91         LOG.info(" In PCE GRAPH : QUICK algorithm ");
  92
  93         // quick algorithm
  94         if (runGraph()) {
  95
  96             this.bestDistance = this.tmpAtozDistance;
  97
  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());
 103                 return true;
 104             }
 105
 106             // continue work per wavelength
 107             LOG.warn(" In PCE GRAPH : QUICK algorithm didn't find shared wavelength over the shortest path");
 108
 109         }
 110
 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);
 117             return false;
 118         }
 119
 120         // rearrange all nodes per the relevant wavelength indexes
 121         extractWLs(this.allPceNodes);
 122
 123         this.pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
 124         boolean firstPath = true;
 125
 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);
 130
 131             if (!runGraph()) {
 132                 continue;
 133             }
 134
 135             if (firstPath) {
 136                 // set minFoundDistance for the first time
 137                 rememberPath(i);
 138                 firstPath = false;
 139             }
 140
 141             if (this.tmpAtozDistance < this.minFoundDistance) {
 142                 rememberPath(i);
 143             }
 144
 145             if (this.tmpAtozDistance == this.bestDistance) {
 146                 // optimization: stop on the first WL with result == the best
 147                 break;
 148             }
 149         }
 150
 151         // return codes can come in different orders. this method fixes it a bit
 152         // TODO build it better
 153         analyzeResult();
 154
 155         LOG.info("In GraphCalculator FUll CalcPath: pceResult {}", this.pceResult.toString());
 156         return (this.pceResult.getStatus());
 157     }
 158
 159     private boolean populateGraph(Map<NodeId, PceNode> allNodes) {
 160
 161         cleanupGraph();
 162
 163         Iterator<Map.Entry<NodeId, PceNode>> nodes = allNodes.entrySet().iterator();
 164         while (nodes.hasNext()) {
 165
 166             Map.Entry<NodeId, PceNode> node = nodes.next();
 167
 168             PceNode pcenode = node.getValue();
 169             List<PceLink> links = pcenode.getOutgoingLinks();
 170
 171             LOG.debug("In populateGraph: use node for graph {}", pcenode.toString());
 172
 173             for (PceLink link : links) {
 174                 LOG.debug("In populateGraph: add edge to graph {}", link.toString());
 175                 addLinkToGraph(link);
 176
 177             }
 178
 179         }
 180
 181         return true;
 182     }
 183
 184     private boolean populateGraph(List<PceNode> allNodes) {
 185
 186         cleanupGraph();
 187
 188         for (PceNode node : allNodes) {
 189             List<PceLink> links = node.getOutgoingLinks();
 190
 191             LOG.debug("In populateGraph: use node for graph {}", node.toString());
 192
 193             for (PceLink link : links) {
 194                 LOG.debug("In populateGraph: add edge to graph {}", link.toString());
 195                 addLinkToGraph(link);
 196
 197             }
 198
 199         }
 200
 201         return true;
 202     }
 203
 204     private boolean runGraph() {
 205         LOG.info("In runGraph Vertices: {}; Eges: {} ", this.nwGraph.getVertexCount(), this.nwGraph.getEdgeCount());
 206
 207         this.pathAtoZ = null;
 208
 209         try {
 210             this.shortestPath = calcAlgo();
 211
 212             if (this.shortestPath == null) {
 213                 this.noPathExists = true;
 214                 LOG.error("In runGraph: shortest path alg is null ");// ,
 215                 return false;
 216             }
 217
 218             this.pathAtoZ = this.shortestPath.getPath(this.apceNode, this.zpceNode);
 219
 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);
 223                 return false;
 224             }
 225
 226             pathMetricsToCompare();
 227
 228             return compareMaxLatency();
 229
 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;
 233             return false;
 234
 235         }
 236     }
 237
 238     private DijkstraShortestPath<PceNode, PceLink> calcAlgo() {
 239
 240         Transformer<PceLink, Double> wtTransformer = new Transformer<PceLink, Double>() {
 241             @Override
 242             public Double transform(PceLink link) {
 243                 return link.getLatency();
 244             }
 245         };
 246
 247         this.shortestPath = null;
 248
 249         switch (this.pceHardConstraints.getPceMetrics()) {
 250             case PropagationDelay:
 251                 this.shortestPath = new DijkstraShortestPath<>(this.nwGraph, wtTransformer);
 252                 LOG.debug("In calcShortestPath: PropagationDelay method run ");
 253                 break;
 254             case HopCount:
 255                 this.shortestPath = new DijkstraShortestPath<>(this.nwGraph);
 256                 LOG.debug("In calcShortestPath: HopCount method run ");
 257                 break;
 258
 259             default:
 260                 this.shortestPath = new DijkstraShortestPath<>(this.nwGraph);
 261                 LOG.warn("In calcShortestPath: instead IGPMetric/TEMetric method Hop-Count runs as a default ");
 262                 break;
 263         }
 264
 265         return this.shortestPath;
 266
 267     }
 268
 269     private void addLinkToGraph(PceLink pcelink) {
 270
 271         PceNode source = this.allPceNodes.get(pcelink.getSourceId());
 272         PceNode dest = this.allPceNodes.get(pcelink.getDestId());
 273
 274         if (source == null) {
 275             LOG.error("In addLinkToGraph link source node is null  :   {}", pcelink.toString());
 276             return;
 277         }
 278         if (dest == null) {
 279             LOG.error("In addLinkToGraph link dest node is null  :   {}", pcelink.toString());
 280             return;
 281         }
 282
 283         LOG.debug("In addLinkToGraph link and nodes :  {} ; {} / {}", pcelink.toString(), source.toString(),
 284                 dest.toString());
 285         this.nwGraph.addEdge(pcelink, source, dest);
 286
 287     }
 288
 289     /*
 290      * "QUICK" approach build shortest path. and then look for a single wavelength
 291      * on it
 292      */
 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)) {
 299                     completed = false;
 300                     break;
 301                 }
 302             }
 303             if (completed) {
 304                 this.pceResult.setResultWavelength(i);
 305                 break;
 306             }
 307         }
 308         return (this.pceResult.getResultWavelength() > 0);
 309     }
 310
 311     public List<PceLink> getPathAtoZ() {
 312         return this.shortestPathAtoZ;
 313     }
 314
 315     public PceResult getReturnStructure() {
 316         return this.pceResult;
 317     }
 318
 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>();
 323
 324         private void addNodetoWL(PceNode node) {
 325             this.listOfNodes.add(node);
 326         }
 327
 328         private List<PceNode> getNodes() {
 329             return this.listOfNodes;
 330         }
 331
 332     }
 333
 334     private boolean extractWLs(Map<NodeId, PceNode> allNodes) {
 335
 336         Iterator<Map.Entry<NodeId, PceNode>> nodes = allNodes.entrySet().iterator();
 337         while (nodes.hasNext()) {
 338
 339             Map.Entry<NodeId, PceNode> node = nodes.next();
 340
 341             PceNode pcenode = node.getValue();
 342             List<Long> wls = pcenode.getAvailableWLs();
 343
 344             LOG.debug("In extractWLs wls in node : {} {}", pcenode.toString(), wls.size());
 345             LOG.debug("In extractWLs listOfWLs total :   {}", this.listOfNodesPerWL.size());
 346             for (Long i : wls) {
 347                 LOG.debug("In extractWLs i in wls :  {}", i);
 348                 ListOfNodes lwl = this.listOfNodesPerWL.get(i.intValue());
 349                 lwl.addNodetoWL(pcenode);
 350             }
 351         }
 352
 353         return true;
 354     }
 355
 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);
 361         }
 362         LOG.debug("In cleanupGraph after {} removed ", this.nwGraph.getEdgeCount());
 363     }
 364
 365     private void analyzeResult() {
 366         // very simple for the start
 367
 368         if (this.pceResult.getStatus()) {
 369             return;
 370         }
 371
 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");
 378         }
 379         return;
 380     }
 381
 382     private boolean compareMaxLatency() {
 383
 384         Long latencyConstraint = this.pceHardConstraints.getMaxLatency();
 385
 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,
 391                         latencyConstraint);
 392                 return false;
 393             }
 394         }
 395         LOG.info("In validateLatency: AtoZ path  is {}", this.pathAtoZ.toString());
 396         return true;
 397     }
 398
 399     private void pathMetricsToCompare() {
 400
 401         this.tmpAtozDistance = this.shortestPath.getDistance(this.apceNode, this.zpceNode).intValue();
 402
 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();
 408         }
 409
 410         switch (this.pceHardConstraints.getPceMetrics()) {
 411             case IGPMetric:
 412                 // TODO implement IGPMetric - low priority
 413                 LOG.error("In PceGraph not implemented IGPMetric. HopCount works as a default");
 414                 break;
 415
 416             case TEMetric:
 417                 // TODO implement TEMetric - low priority
 418                 LOG.error("In PceGraph not implemented TEMetric. HopCount works as a default");
 419                 break;
 420
 421             case HopCount:
 422                 break;
 423
 424             case PropagationDelay:
 425                 this.tmpAtozLatency = this.tmpAtozDistance;
 426                 break;
 427
 428             default:
 429                 LOG.error("In PceGraph {}: unknown metric. ", this.pceHardConstraints.getPceMetrics());
 430                 break;
 431         }
 432
 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());
 436
 437         return;
 438     }
 439
 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());
 446
 447     }
 448
 449     public void setConstrains(PceConstraints pceHardCons, PceConstraints pceSoftCons) {
 450         this.pceHardConstraints = pceHardCons;
 451         this.pceSoftConstraints = pceSoftCons;
 452     }
 453
 454 }