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.common.StringConstants;
  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 import org.slf4j.Logger;
  29 import org.slf4j.LoggerFactory;
  30
  31 public class PceGraph {
  32     /* Logging. */
  33     private static final Logger LOG = LoggerFactory.getLogger(PceGraph.class);
  34
  35     ////////////////////////// for Graph ///////////////////////////
  36     // how many paths to bring
  37     private int kpathsToBring = 10;
  38
  39     // max #hops
  40     private int mhopsPerPath = 50;
  41
  42     // input
  43     private Map<NodeId, PceNode> allPceNodes = new HashMap<>();
  44     private PceNode apceNode = null;
  45     private PceNode zpceNode = null;
  46     private String serviceType = "";
  47
  48     PceConstraints pceHardConstraints;
  49     PceConstraints pceSoftConstraints;
  50
  51     // results
  52     private PceResult pceResult = null;
  53     private List<PceLink> shortestPathAtoZ = null;
  54
  55     // for path calculation
  56     List<GraphPath<String, PceGraphEdge>> allWPaths = null;
  57
  58     private List<PceLink> pathAtoZ = new ArrayList<>();
  59
  60     public PceGraph(PceNode aendNode, PceNode zendNode, Map<NodeId, PceNode> allPceNodes,
  61             PceConstraints pceHardConstraints, PceConstraints pceSoftConstraints, PceResult pceResult,
  62             String serviceType) {
  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         this.serviceType = serviceType;
  71
  72         LOG.info("In GraphCalculator: A and Z = {} / {} ", aendNode, zendNode);
  73         LOG.debug("In GraphCalculator: allPceNodes size {}, nodes {} ", allPceNodes.size(), allPceNodes);
  74     }
  75
  76     public boolean calcPath() {
  77
  78         LOG.info(" In PCE GRAPH calcPath : K SHORT PATHS algorithm ");
  79
  80         DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph =
  81                 new DefaultDirectedWeightedGraph<>(PceGraphEdge.class);
  82         populateWithNodes(weightedGraph);
  83         populateWithLinks(weightedGraph);
  84
  85         if (!runKgraphs(weightedGraph)) {
  86             LOG.info("In calcPath : pceResult {}", pceResult);
  87             return false;
  88         }
  89
  90         // validate found paths
  91         pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
  92         for (GraphPath<String, PceGraphEdge> path : allWPaths) {
  93             PostAlgoPathValidator papv = new PostAlgoPathValidator();
  94             pceResult = papv.checkPath(path, allPceNodes, pceResult, pceHardConstraints, serviceType);
  95             LOG.info("In calcPath after PostAlgoPathValidator {} {}",
  96                     pceResult.getResponseCode(), ResponseCodes.RESPONSE_OK);
  97
  98             if (!pceResult.getResponseCode().equals(ResponseCodes.RESPONSE_OK)) {
  99                 LOG.info("In calcPath: post algo validations DROPPED the path {}", path);
 100                 continue;
 101             }
 102
 103             // build pathAtoZ
 104             pathAtoZ.clear();
 105             for (PceGraphEdge edge : path.getEdgeList()) {
 106                 pathAtoZ.add(edge.link());
 107             }
 108
 109             shortestPathAtoZ = new ArrayList<>(pathAtoZ);
 110             if ((StringConstants.SERVICE_TYPE_100GE.equals(serviceType))
 111                     || (StringConstants.SERVICE_TYPE_OTU4.equals(serviceType))) {
 112                 LOG.info("In calcPath Path FOUND path for wl [{}], min Freq assignment {}, max Freq assignment {},"
 113                         + " hops {}, distance per metrics {}, path AtoZ {}",
 114                         pceResult.getResultWavelength(), pceResult.getMinFreq(), pceResult.getMaxFreq(),
 115                         pathAtoZ.size(), path.getWeight(), pathAtoZ);
 116                 break;
 117             } else {
 118                 // Service is at OTN layer and is relying on a supporting wavelength service
 119                 LOG.info("In calcPath Path FOUND path for hops {}, distance per metrics {}, path AtoZ {}",
 120                         pathAtoZ.size(), path.getWeight(), pathAtoZ);
 121                 break;
 122             }
 123
 124         }
 125
 126         if (shortestPathAtoZ != null) {
 127             LOG.info("In calcPath CHOOSEN PATH for wl [{}], min freq {}, max freq {}, hops {}, path AtoZ {}",
 128                     pceResult.getResultWavelength(), pceResult.getMinFreq(), pceResult.getMaxFreq(),
 129                     shortestPathAtoZ.size(), shortestPathAtoZ);
 130         }
 131         LOG.info("In calcPath : pceResult {}", pceResult);
 132         return (pceResult.getStatus());
 133     }
 134
 135     private boolean runKgraphs(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
 136
 137         if (weightedGraph.edgeSet().isEmpty() || weightedGraph.vertexSet().isEmpty()) {
 138             return false;
 139         }
 140         PathValidator<String, PceGraphEdge> wpv = new InAlgoPathValidator();
 141
 142         // KShortestPaths on weightedGraph
 143         KShortestSimplePaths<String, PceGraphEdge> swp =
 144             new KShortestSimplePaths<>(weightedGraph, mhopsPerPath, wpv);
 145         allWPaths = swp.getPaths(apceNode.getNodeId().getValue(), zpceNode.getNodeId().getValue(), kpathsToBring);
 146
 147         if (allWPaths.isEmpty()) {
 148             LOG.info(" In runKgraphs : algorithm didn't find any path");
 149             pceResult.setLocalCause(LocalCause.NO_PATH_EXISTS);
 150             pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
 151             return false;
 152         }
 153
 154         // debug print
 155         for (GraphPath<String, PceGraphEdge> path : allWPaths) {
 156             LOG.debug("path Weight: {} : {}", path.getWeight(), path.getVertexList());
 157         }
 158
 159         return true;
 160     }
 161
 162     private boolean validateLinkforGraph(PceLink pcelink) {
 163
 164         PceNode source = allPceNodes.get(pcelink.getSourceId());
 165         PceNode dest = allPceNodes.get(pcelink.getDestId());
 166
 167         if (source == null) {
 168             LOG.error("In addLinkToGraph link source node is null : {}", pcelink);
 169             return false;
 170         }
 171         if (dest == null) {
 172             LOG.error("In addLinkToGraph link dest node is null : {}", pcelink);
 173             return false;
 174         }
 175         LOG.debug("In addLinkToGraph link to nodes : {}{} {}", pcelink, source, dest);
 176         return true;
 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());
 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);
 199
 200             for (PceLink link : links) {
 201                 LOG.debug("In populateGraph node {} : add edge to graph {}", pcenode, link);
 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         // HopCount is default
 218         double weight = 1;
 219         switch (pceHardConstraints.getPceMetrics()) {
 220             case HopCount :
 221                 weight = 1;
 222                 LOG.debug("In PceGraph HopCount is used as a metrics. {}", link);
 223                 break;
 224             case PropagationDelay :
 225                 weight = link.getLatency();
 226                 LOG.debug("In PceGraph PropagationDelay is used as a metrics. {}", link);
 227                 if ((("1GE".equals(serviceType)) || ("10GE".equals(serviceType)) || ("ODU4".equals(serviceType)))
 228                         && (weight == 0)) {
 229                     LOG.warn("PropagationDelay set as metric, but latency is null: is latency set for OTN link {}?",
 230                         link);
 231                 }
 232                 break;
 233             // TODO implement IGPMetric and TEMetric - low priority.
 234             case IGPMetric :
 235             case TEMetric :
 236             default:
 237                 LOG.warn("In PceGraph {} not implemented. HopCount works as a default",
 238                     pceHardConstraints.getPceMetrics());
 239                 break;
 240         }
 241         return weight;
 242     }
 243
 244     public int getKpathsToBring() {
 245         return kpathsToBring;
 246     }
 247
 248     public void setKpathsToBring(int kpathsToBring) {
 249         this.kpathsToBring = kpathsToBring;
 250     }
 251
 252     public void setMhopsPerPath(int mhopsPerPath) {
 253         this.mhopsPerPath = mhopsPerPath;
 254     }
 255
 256     public List<PceLink> getPathAtoZ() {
 257         return shortestPathAtoZ;
 258     }
 259
 260     public PceResult getReturnStructure() {
 261         return pceResult;
 262     }
 263
 264     public void setConstrains(PceConstraints pceHardConstraintsInput, PceConstraints pceSoftConstraintsInput) {
 265         this.pceHardConstraints = pceHardConstraintsInput;
 266         this.pceSoftConstraints = pceSoftConstraintsInput;
 267     }
 268 }