pce/src/main/java/org/opendaylight/transportpce/pce/graph/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.graph;
  10
  11 import java.util.ArrayList;
  12 import java.util.HashMap;
  13 import java.util.Iterator;
  14 import java.util.List;
  15 import java.util.Map;
  16
  17 import org.jgrapht.GraphPath;
  18 import org.jgrapht.alg.shortestpath.KShortestSimplePaths;
  19 import org.jgrapht.alg.shortestpath.PathValidator;
  20 import org.jgrapht.graph.DefaultDirectedWeightedGraph;
  21 import org.opendaylight.transportpce.common.ResponseCodes;
  22 import org.opendaylight.transportpce.pce.constraints.PceConstraints;
  23 import org.opendaylight.transportpce.pce.networkanalyzer.PceLink;
  24 import org.opendaylight.transportpce.pce.networkanalyzer.PceNode;
  25 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult;
  26 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult.LocalCause;
  27 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.NodeId;
  28
  29 import org.slf4j.Logger;
  30 import org.slf4j.LoggerFactory;
  31
  32 public class PceGraph {
  33     /* Logging. */
  34     private static final Logger LOG = LoggerFactory.getLogger(PceGraph.class);
  35
  36     ////////////////////////// for Graph ///////////////////////////
  37     // how many paths to bring
  38     int kpathsToBring = 10;
  39     // max #hops
  40     int mhopsPerPath = 50;
  41
  42     // input
  43     private Map<NodeId, PceNode> allPceNodes = new HashMap<NodeId, PceNode>();
  44     private PceNode apceNode = null;
  45     private PceNode zpceNode = null;
  46
  47     PceConstraints pceHardConstraints;
  48     PceConstraints pceSoftConstraints;
  49
  50     // results
  51     private PceResult pceResult = null;
  52     private List<PceLink> shortestPathAtoZ = null;
  53
  54     // for path calculation
  55     List<GraphPath<String, PceGraphEdge>> allWPaths = null;
  56
  57     private List<PceLink> pathAtoZ = new ArrayList<PceLink>();
  58
  59     public PceGraph(PceNode aendNode, PceNode zendNode, Map<NodeId, PceNode> allPceNodes,
  60             PceConstraints pceHardConstraints, PceConstraints pceSoftConstraints, PceResult pceResult) {
  61         super();
  62         this.apceNode = aendNode;
  63         this.zpceNode = zendNode;
  64         this.allPceNodes = allPceNodes;
  65         this.pceResult = pceResult;
  66         this.pceHardConstraints = pceHardConstraints;
  67         this.pceSoftConstraints = pceSoftConstraints;
  68
  69         LOG.info("In GraphCalculator: A and Z = {} / {} ", aendNode.toString(), zendNode.toString());
  70         LOG.debug("In GraphCalculator: allPceNodes size {}, nodes {} ", allPceNodes.size(), allPceNodes.toString());
  71
  72     }
  73
  74     public boolean calcPath() {
  75
  76         LOG.info(" In PCE GRAPH calcPath : K SHORT PATHS algorithm ");
  77
  78         DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph =
  79                 new DefaultDirectedWeightedGraph<String, PceGraphEdge>(PceGraphEdge.class);
  80         populateWithNodes(weightedGraph);
  81         populateWithLinks(weightedGraph);
  82
  83         if (!runKgraphs(weightedGraph)) {
  84             LOG.info("In calcPath : pceResult {}", pceResult.toString());
  85             return false;
  86         }
  87
  88         // validate found paths
  89         pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
  90         for (GraphPath<String, PceGraphEdge> path : allWPaths) {
  91
  92             PostAlgoPathValidator papv = new PostAlgoPathValidator();
  93             pceResult = papv.checkPath(path, allPceNodes, pceResult);
  94             LOG.info("In calcPath after PostAlgoPathValidator {} {}",
  95                     pceResult.getResponseCode(), ResponseCodes.RESPONSE_OK);
  96
  97             if (!pceResult.getResponseCode().equals(ResponseCodes.RESPONSE_OK)) {
  98                 LOG.info("In calcPath: post algo validations DROPPED the path {}", path.toString());
  99                 continue;
 100             }
 101
 102             // build pathAtoZ
 103             pathAtoZ.clear();
 104             for (PceGraphEdge edge : path.getEdgeList()) {
 105                 pathAtoZ.add(edge.link());
 106             }
 107
 108             shortestPathAtoZ = new ArrayList<>(pathAtoZ);
 109             LOG.info("In calcPath Path FOUND path for wl [{}], hops {}, distance per metrics {}, path AtoZ {}",
 110                     pceResult.getResultWavelength(), pathAtoZ.size(), path.getWeight(), pathAtoZ.toString());
 111             break;
 112         }
 113
 114         if (shortestPathAtoZ != null) {
 115             LOG.info("In calcPath CHOOSEN PATH for wl [{}], hops {}, path AtoZ {}",
 116                     pceResult.getResultWavelength(), shortestPathAtoZ.size(), shortestPathAtoZ.toString());
 117         }
 118         LOG.info("In calcPath : pceResult {}", pceResult.toString());
 119         return (pceResult.getStatus());
 120     }
 121
 122     private boolean runKgraphs(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
 123
 124         if (weightedGraph.edgeSet().isEmpty() || weightedGraph.vertexSet().isEmpty()) {
 125             return false;
 126         }
 127
 128         PathValidator<String, PceGraphEdge> wpv = new InAlgoPathValidator(pceHardConstraints, zpceNode);
 129
 130         // local optimization. if 'include' constraint exists then increase amount of paths to return.
 131         // it's because this constraint is checked at the last step when part of good paths
 132         // are dropped by other constraints
 133         if (!pceHardConstraints.getListToInclude().isEmpty()) {
 134             kpathsToBring = kpathsToBring * 10;
 135             LOG.info("k = {}",kpathsToBring);
 136         }
 137
 138         // KShortestPaths on weightedGraph
 139         KShortestSimplePaths<String, PceGraphEdge> swp =
 140             new KShortestSimplePaths<String, PceGraphEdge>(weightedGraph, mhopsPerPath, wpv);
 141
 142         allWPaths = swp.getPaths(apceNode.getNodeId().getValue(), zpceNode.getNodeId().getValue(), kpathsToBring);
 143
 144         if (allWPaths.isEmpty()) {
 145             LOG.info(" In runKgraphs : algorithm didn't find any path");
 146             pceResult.setLocalCause(LocalCause.NO_PATH_EXISTS);
 147             pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
 148             return false;
 149         }
 150
 151         // debug print
 152         for (GraphPath<String, PceGraphEdge> path : allWPaths) {
 153             LOG.info("path Weight: {} : {}", path.getWeight(), path.getVertexList().toString());
 154         }
 155         // debug print
 156
 157         return true;
 158     }
 159
 160     private boolean validateLinkforGraph(PceLink pcelink) {
 161
 162         PceNode source = allPceNodes.get(pcelink.getSourceId());
 163         PceNode dest = allPceNodes.get(pcelink.getDestId());
 164
 165         if (source == null) {
 166             LOG.error("In addLinkToGraph link source node is null : {}", pcelink.toString());
 167             return false;
 168         }
 169         if (dest == null) {
 170             LOG.error("In addLinkToGraph link dest node is null : {}", pcelink.toString());
 171             return false;
 172         }
 173
 174         LOG.debug("In addLinkToGraph link to nodes : {}{} {}", pcelink.toString(), source.toString(), dest.toString());
 175         return true;
 176
 177     }
 178
 179     private void populateWithNodes(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
 180         Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
 181         while (nodes.hasNext()) {
 182             Map.Entry<NodeId, PceNode> node = nodes.next();
 183             weightedGraph.addVertex(node.getValue().getNodeId().getValue());
 184             LOG.debug("In populateWithNodes in node :  {}", node.getValue().toString());
 185         }
 186     }
 187
 188     private boolean populateWithLinks(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
 189
 190         Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
 191         while (nodes.hasNext()) {
 192
 193             Map.Entry<NodeId, PceNode> node = nodes.next();
 194
 195             PceNode pcenode = node.getValue();
 196             List<PceLink> links = pcenode.getOutgoingLinks();
 197
 198             LOG.debug("In populateGraph: use node for graph {}", pcenode.toString());
 199
 200             for (PceLink link : links) {
 201                 LOG.debug("In populateGraph node {} : add edge to graph {}", pcenode.toString(), link.toString());
 202
 203                 if (!validateLinkforGraph(link)) {
 204                     continue;
 205                 }
 206
 207                 PceGraphEdge graphLink = new PceGraphEdge(link);
 208                 weightedGraph.addEdge(link.getSourceId().getValue(), link.getDestId().getValue(), graphLink);
 209
 210                 weightedGraph.setEdgeWeight(graphLink, chooseWeight(link));
 211             }
 212         }
 213         return true;
 214     }
 215
 216     private double chooseWeight(PceLink link) {
 217
 218         // HopCount is default
 219         double weight = 1;
 220         switch (pceHardConstraints.getPceMetrics()) {
 221             case IGPMetric :
 222                 // TODO implement IGPMetric - low priority.
 223                 LOG.warn("In PceGraph not implemented IGPMetric. HopCount works as a default");
 224                 break;
 225
 226             case TEMetric :
 227                 // TODO implement TEMetric - low priority
 228                 LOG.warn("In PceGraph not implemented TEMetric. HopCount works as a default");
 229                 break;
 230
 231             case HopCount :
 232                 weight = 1;
 233                 LOG.debug("In PceGraph HopCount is used as a metrics. {}", link.toString());
 234                 break;
 235
 236             case PropagationDelay :
 237                 weight = link.getLatency();
 238                 LOG.debug("In PceGraph PropagationDelay is used as a metrics. {}", link.toString());
 239                 break;
 240
 241             default:
 242                 break;
 243         }
 244
 245         return weight;
 246     }
 247
 248     ////////////////////////////////////////////////////////////////////////////////////////////////////////////
 249     public List<PceLink> getPathAtoZ() {
 250         return shortestPathAtoZ;
 251     }
 252
 253     public PceResult getReturnStructure() {
 254         return pceResult;
 255     }
 256
 257     public void setConstrains(PceConstraints pceHardConstraintsInput, PceConstraints pceSoftConstraintsInput) {
 258         this.pceHardConstraints = pceHardConstraintsInput;
 259         this.pceSoftConstraints = pceSoftConstraintsInput;
 260     }
 261
 262 }