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.rev180226.NodeId;
  22 import org.slf4j.Logger;
  23 import org.slf4j.LoggerFactory;
  24
  25
  26 public class PceGraph {
  27     /* Logging. */
  28     private static final Logger LOG = LoggerFactory.getLogger(PceCalculation.class);
  29
  30     ////////////////////////// for Graph ///////////////////////////
  31     private DirectedSparseMultigraph<PceNode, PceLink> nwGraph = new DirectedSparseMultigraph<PceNode, PceLink>();
  32     private DijkstraShortestPath<PceNode, PceLink> shortestPath = null;
  33
  34     // input
  35     private Map<NodeId, PceNode> allPceNodes = new HashMap<NodeId, PceNode>();
  36     private PceNode apceNode = null;
  37     private PceNode zpceNode = null;
  38
  39     PceConstraints pceHardConstraints;
  40     PceConstraints pceSoftConstraints;
  41
  42     // results
  43     private PceResult pceResult = null;
  44     private List<PceLink> shortestPathAtoZ = null;
  45
  46     // TODO hard-coded 96
  47     private static final int MAX_WAWELENGTH = 96;
  48
  49     // for path calculation
  50     private List<PceLink> pathAtoZ = null;
  51     private int minFoundDistance;
  52     private int tmpAtozDistance = 0;
  53     private int tmpAtozLatency = 0;
  54     private int bestDistance;
  55     private boolean noPathExists = false;
  56
  57     private boolean foundButTooHighLatency = false;
  58
  59     private List<ListOfNodes> listOfNodesPerWL = new ArrayList<ListOfNodes>();
  60
  61     public PceGraph(PceNode aendNode, PceNode zendNode, Map<NodeId, PceNode> allPceNodes,
  62             PceConstraints pceHardConstraints, PceConstraints pceSoftConstraints, PceResult pceResult) {
  63         super();
  64         this.apceNode = aendNode;
  65         this.zpceNode = zendNode;
  66         this.allPceNodes = allPceNodes;
  67         this.pceResult = pceResult;
  68         this.pceHardConstraints = pceHardConstraints;
  69         this.pceSoftConstraints = pceSoftConstraints;
  70
  71         // TODO - fix the assumption that wavelengths are from 1 to 96 and can be used
  72         // as index
  73         this.listOfNodesPerWL.add(new ListOfNodes());
  74         for (int i = 1; i <= MAX_WAWELENGTH; i++) {
  75             // create list of nodes per wavelength
  76             ListOfNodes wls = new ListOfNodes();
  77             this.listOfNodesPerWL.add(wls);
  78         }
  79
  80         LOG.debug("In GraphCalculator: A and Z = {} / {}", aendNode.toString(), zendNode.toString());
  81         LOG.debug("In GraphCalculator: allPceNodes = {}", allPceNodes.toString());
  82     }
  83
  84     public boolean calcPath() {
  85
  86         LOG.info("In calcPath: metric {} is used ", this.pceHardConstraints.getPceMetrics());
  87
  88         populateGraph(this.allPceNodes);
  89
  90         LOG.info(" In PCE GRAPH : QUICK algorithm ");
  91
  92         // quick algorithm
  93         if (runGraph()) {
  94
  95             this.bestDistance = this.tmpAtozDistance;
  96
  97             if (chooseWavelength()) {
  98                 this.pceResult.setRC(ResponseCodes.RESPONSE_OK);
  99                 this.shortestPathAtoZ = this.pathAtoZ;
 100                 LOG.info("In GraphCalculator QUICK CalcPath: AtoZ {}", this.pathAtoZ.toString());
 101                 LOG.info("In GraphCalculator QUICK CalcPath: pceResult {}", this.pceResult.toString());
 102                 return true;
 103             }
 104
 105             // continue work per wavelength
 106             LOG.warn(" In PCE GRAPH : QUICK algorithm didn't find shared wavelength over the shortest path");
 107
 108         }
 109
 110         LOG.warn(" In PCE GRAPH : QUICK algorithm didn't find shortest path with single wavelength");
 111         if (this.noPathExists) {
 112             // quick algo looks for path independently on wavelength. therefore no path
 113             // means fatal problem
 114             LOG.warn(" In PCE GRAPH : QUICK algorithm didn't find any path");
 115             this.pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
 116             return false;
 117         }
 118
 119         // rearrange all nodes per the relevant wavelength indexes
 120         extractWLs(this.allPceNodes);
 121
 122         this.pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
 123         boolean firstPath = true;
 124
 125         for (int i = 1; i <= MAX_WAWELENGTH; i++) {
 126             LOG.info(" In PCE GRAPH : FUll algorithm for WL {}", i);
 127             List<PceNode> nodes = this.listOfNodesPerWL.get(i).getNodes();
 128             populateGraph(nodes);
 129
 130             if (!runGraph()) {
 131                 continue;
 132             }
 133
 134             if (firstPath) {
 135                 // set minFoundDistance for the first time
 136                 rememberPath(i);
 137                 firstPath = false;
 138             }
 139
 140             if (this.tmpAtozDistance < this.minFoundDistance) {
 141                 rememberPath(i);
 142             }
 143
 144             if (this.tmpAtozDistance == this.bestDistance) {
 145                 // optimization: stop on the first WL with result == the best
 146                 break;
 147             }
 148         }
 149
 150         // return codes can come in different orders. this method fixes it a bit
 151         // TODO build it better
 152         analyzeResult();
 153
 154         LOG.info("In GraphCalculator FUll CalcPath: pceResult {}", this.pceResult.toString());
 155         return (this.pceResult.getStatus());
 156     }
 157
 158     private boolean populateGraph(Map<NodeId, PceNode> allNodes) {
 159
 160         cleanupGraph();
 161
 162         Iterator<Map.Entry<NodeId, PceNode>> nodes = allNodes.entrySet().iterator();
 163         while (nodes.hasNext()) {
 164
 165             Map.Entry<NodeId, PceNode> node = nodes.next();
 166
 167             PceNode pcenode = node.getValue();
 168             List<PceLink> links = pcenode.getOutgoingLinks();
 169
 170             LOG.info("In populateGraph: use node for graph {}", pcenode.toString());
 171
 172             for (PceLink link : links) {
 173                 LOG.info("In populateGraph: add edge to graph {}", link.toString());
 174                 addLinkToGraph(link);
 175
 176             }
 177
 178         }
 179
 180         return true;
 181     }
 182
 183     private boolean populateGraph(List<PceNode> allNodes) {
 184
 185         cleanupGraph();
 186
 187         for (PceNode node : allNodes) {
 188             List<PceLink> links = node.getOutgoingLinks();
 189
 190             LOG.debug("In populateGraph: use node for graph {}", node.toString());
 191
 192             for (PceLink link : links) {
 193                 LOG.debug("In populateGraph: add edge to graph {}", link.toString());
 194                 addLinkToGraph(link);
 195
 196             }
 197
 198         }
 199
 200         return true;
 201     }
 202
 203     private boolean runGraph() {
 204         LOG.info("In runGraph Vertices: {}; Eges: {} ", this.nwGraph.getVertexCount(), this.nwGraph.getEdgeCount());
 205
 206         this.pathAtoZ = null;
 207
 208         try {
 209             this.shortestPath = calcAlgo();
 210
 211             if (this.shortestPath == null) {
 212                 this.noPathExists = true;
 213                 LOG.error("In runGraph: shortest path alg is null ");// ,
 214                 return false;
 215             }
 216
 217             this.pathAtoZ = this.shortestPath.getPath(this.apceNode, this.zpceNode);
 218
 219             if ((this.pathAtoZ == null) || (this.pathAtoZ.size() == 0)) {
 220                 LOG.info("In runGraph: AtoZ path is empty");
 221                 this.pceResult.setLocalCause(LocalCause.NO_PATH_EXISTS);
 222                 return false;
 223             }
 224
 225             pathMetricsToCompare();
 226
 227             return compareMaxLatency();
 228
 229         } catch (IllegalArgumentException e) {
 230             LOG.error("In runGraph: can't calculate the path. A or Z node don't have any links {}", e);
 231             this.noPathExists = true;
 232             return false;
 233
 234         }
 235     }
 236
 237     private DijkstraShortestPath<PceNode, PceLink> calcAlgo() {
 238
 239         Transformer<PceLink, Double> wtTransformer = new Transformer<PceLink, Double>() {
 240             @Override
 241             public Double transform(PceLink link) {
 242                 return link.getLatency();
 243             }
 244         };
 245
 246         this.shortestPath = null;
 247
 248         switch (this.pceHardConstraints.getPceMetrics()) {
 249             case PropagationDelay:
 250                 this.shortestPath = new DijkstraShortestPath<>(this.nwGraph, wtTransformer);
 251                 LOG.debug("In calcShortestPath: PropagationDelay method run ");
 252                 break;
 253             case HopCount:
 254                 this.shortestPath = new DijkstraShortestPath<>(this.nwGraph);
 255                 LOG.debug("In calcShortestPath: HopCount method run ");
 256                 break;
 257
 258             default:
 259                 this.shortestPath = new DijkstraShortestPath<>(this.nwGraph);
 260                 LOG.warn("In calcShortestPath: instead IGPMetric/TEMetric method Hop-Count runs as a default ");
 261                 break;
 262         }
 263
 264         return this.shortestPath;
 265
 266     }
 267
 268     private void addLinkToGraph(PceLink pcelink) {
 269
 270         PceNode source = this.allPceNodes.get(pcelink.getSourceId());
 271         PceNode dest = this.allPceNodes.get(pcelink.getDestId());
 272
 273         if (source == null) {
 274             LOG.error("In addLinkToGraph link source node is null  :   {}", pcelink.toString());
 275             return;
 276         }
 277         if (dest == null) {
 278             LOG.error("In addLinkToGraph link dest node is null  :   {}", pcelink.toString());
 279             return;
 280         }
 281
 282         LOG.debug("In addLinkToGraph link and nodes :  {} ; {} / {}", pcelink.toString(), source.toString(),
 283                 dest.toString());
 284         this.nwGraph.addEdge(pcelink, source, dest);
 285
 286     }
 287
 288     /*
 289      * "QUICK" approach build shortest path. and then look for a single wavelength
 290      * on it
 291      */
 292     private boolean chooseWavelength() {
 293         for (long i = 1; i <= MAX_WAWELENGTH; i++) {
 294             boolean completed = true;
 295             for (PceLink link : this.pathAtoZ) {
 296                 PceNode pceNode = this.allPceNodes.get(link.getSourceId());
 297                 if (!pceNode.checkWL(i)) {
 298                     completed = false;
 299                     break;
 300                 }
 301             }
 302             if (completed) {
 303                 this.pceResult.setResultWavelength(i);
 304                 break;
 305             }
 306         }
 307         return (this.pceResult.getResultWavelength() > 0);
 308     }
 309
 310     public List<PceLink> getPathAtoZ() {
 311         return this.shortestPathAtoZ;
 312     }
 313
 314     public PceResult getReturnStructure() {
 315         return this.pceResult;
 316     }
 317
 318     // TODO build ordered set ordered per the index. Current assumption is that
 319     // wavelenght serves as an index
 320     private class ListOfNodes {
 321         private List<PceNode> listOfNodes = new ArrayList<PceNode>();
 322
 323         private void addNodetoWL(PceNode node) {
 324             this.listOfNodes.add(node);
 325         }
 326
 327         private List<PceNode> getNodes() {
 328             return this.listOfNodes;
 329         }
 330
 331     }
 332
 333     private boolean extractWLs(Map<NodeId, PceNode> allNodes) {
 334
 335         Iterator<Map.Entry<NodeId, PceNode>> nodes = allNodes.entrySet().iterator();
 336         while (nodes.hasNext()) {
 337
 338             Map.Entry<NodeId, PceNode> node = nodes.next();
 339
 340             PceNode pcenode = node.getValue();
 341             List<Long> wls = pcenode.getAvailableWLs();
 342
 343             LOG.debug("In extractWLs wls in node : {} {}", pcenode.toString(), wls.size());
 344             LOG.debug("In extractWLs listOfWLs total :   {}", this.listOfNodesPerWL.size());
 345             for (Long i : wls) {
 346                 LOG.debug("In extractWLs i in wls :  {}", i);
 347                 ListOfNodes lwl = this.listOfNodesPerWL.get(i.intValue());
 348                 lwl.addNodetoWL(pcenode);
 349             }
 350         }
 351
 352         return true;
 353     }
 354
 355     private void cleanupGraph() {
 356         LOG.debug("In cleanupGraph remove {} nodes ", this.nwGraph.getEdgeCount());
 357         Iterable<PceNode> toRemove = new ArrayList<PceNode>(this.nwGraph.getVertices());
 358         for (PceNode node : toRemove) {
 359             this.nwGraph.removeVertex(node);
 360         }
 361         LOG.debug("In cleanupGraph after {} removed ", this.nwGraph.getEdgeCount());
 362     }
 363
 364     private void analyzeResult() {
 365         // very simple for the start
 366
 367         if (this.pceResult.getStatus()) {
 368             return;
 369         }
 370
 371         // if request is rejected but at least once there was path found, try to save
 372         // the real reason of reject
 373         if (this.foundButTooHighLatency) {
 374             this.pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
 375             this.pceResult.setLocalCause(LocalCause.TOO_HIGH_LATENCY);
 376             this.pceResult.setCalcMessage("No path available due to constraint Hard/Latency");
 377         }
 378         return;
 379     }
 380
 381     private boolean compareMaxLatency() {
 382
 383         Long latencyConstraint = this.pceHardConstraints.getMaxLatency();
 384
 385         if (latencyConstraint > 0) {
 386             if (this.tmpAtozLatency > latencyConstraint) {
 387                 this.foundButTooHighLatency = true;
 388                 this.pceResult.setLocalCause(LocalCause.TOO_HIGH_LATENCY);
 389                 LOG.info("In validateLatency: AtoZ path has too high LATENCY {} > {}", this.tmpAtozLatency,
 390                         latencyConstraint);
 391                 return false;
 392             }
 393         }
 394         LOG.info("In validateLatency: AtoZ path  is {}", this.pathAtoZ.toString());
 395         return true;
 396     }
 397
 398     private void pathMetricsToCompare() {
 399
 400         this.tmpAtozDistance = this.shortestPath.getDistance(this.apceNode, this.zpceNode).intValue();
 401
 402         // TODO this code is for HopCount. excluded from switch for not implemented
 403         // IGPMetric and TEMetric
 404         this.tmpAtozLatency = 0;
 405         for (PceLink pcelink : this.pathAtoZ) {
 406             this.tmpAtozLatency = this.tmpAtozLatency + pcelink.getLatency().intValue();
 407         }
 408
 409         switch (this.pceHardConstraints.getPceMetrics()) {
 410             case IGPMetric:
 411                 // TODO implement IGPMetric - low priority
 412                 LOG.error("In PceGraph not implemented IGPMetric. HopCount works as a default");
 413                 break;
 414
 415             case TEMetric:
 416                 // TODO implement TEMetric - low priority
 417                 LOG.error("In PceGraph not implemented TEMetric. HopCount works as a default");
 418                 break;
 419
 420             case HopCount:
 421                 break;
 422
 423             case PropagationDelay:
 424                 this.tmpAtozLatency = this.tmpAtozDistance;
 425                 break;
 426
 427             default:
 428                 LOG.error("In PceGraph {}: unknown metric. ", this.pceHardConstraints.getPceMetrics());
 429                 break;
 430         }
 431
 432         LOG.info("In runGraph: AtoZ size {}, distance {}, latency {} ", this.pathAtoZ.size(), this.tmpAtozDistance,
 433                 this.tmpAtozLatency);
 434         LOG.debug("In runGraph: AtoZ {}", this.pathAtoZ.toString());
 435
 436         return;
 437     }
 438
 439     private void rememberPath(int index) {
 440         this.minFoundDistance = this.tmpAtozDistance;
 441         this.shortestPathAtoZ = this.pathAtoZ;
 442         this.pceResult.setResultWavelength(Long.valueOf(index));
 443         this.pceResult.setRC(ResponseCodes.RESPONSE_OK);
 444         LOG.info("In GraphCalculator FUll CalcPath for wl [{}]: found AtoZ {}", index, this.pathAtoZ.toString());
 445
 446     }
 447
 448     public void setConstrains(PceConstraints pceHardConstraintsIn, PceConstraints pceSoftConstraintsIn) {
 449         this.pceHardConstraints = pceHardConstraintsIn;
 450         this.pceSoftConstraints = pceSoftConstraintsIn;
 451     }
 452
 453 }