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