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