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 java.util.Map.Entry;
  17 import java.util.function.Function;
  18 import java.util.stream.Collectors;
  19 import java.util.stream.IntStream;
  20 import org.jgrapht.GraphPath;
  21 import org.jgrapht.alg.shortestpath.KShortestSimplePaths;
  22 import org.jgrapht.alg.shortestpath.PathValidator;
  23 import org.jgrapht.graph.DefaultDirectedWeightedGraph;
  24 import org.opendaylight.transportpce.common.ResponseCodes;
  25 import org.opendaylight.transportpce.common.StringConstants;
  26 import org.opendaylight.transportpce.pce.constraints.PceConstraints;
  27 import org.opendaylight.transportpce.pce.networkanalyzer.PceLink;
  28 import org.opendaylight.transportpce.pce.networkanalyzer.PceNode;
  29 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult;
  30 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult.LocalCause;
  31 import org.opendaylight.yang.gen.v1.http.org.openroadm.common.state.types.rev191129.State;
  32 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.NodeId;
  33 import org.slf4j.Logger;
  34 import org.slf4j.LoggerFactory;
  35
  36 public class PceGraph {
  37     /* Logging. */
  38     private static final Logger LOG = LoggerFactory.getLogger(PceGraph.class);
  39
  40     ////////////////////////// for Graph ///////////////////////////
  41     // how many paths to bring
  42     private int kpathsToBring = 10;
  43
  44     // max #hops
  45     private int mhopsPerPath = 50;
  46
  47     // input
  48     private Map<NodeId, PceNode> allPceNodes = new HashMap<>();
  49     private PceNode apceNode = null;
  50     private PceNode zpceNode = null;
  51     private String serviceType = "";
  52
  53     PceConstraints pceHardConstraints;
  54     PceConstraints pceSoftConstraints;
  55
  56     // results
  57     private PceResult pceResult = null;
  58     private List<PceLink> shortestPathAtoZ = null;
  59
  60     // for path calculation
  61     Map<Integer, GraphPath<String, PceGraphEdge>> allWPaths = null;
  62
  63     private List<PceLink> pathAtoZ = new ArrayList<>();
  64
  65     public PceGraph(PceNode aendNode, PceNode zendNode, Map<NodeId, PceNode> allPceNodes,
  66             PceConstraints pceHardConstraints, PceConstraints pceSoftConstraints, PceResult pceResult,
  67             String serviceType) {
  68         super();
  69         this.apceNode = aendNode;
  70         this.zpceNode = zendNode;
  71         this.allPceNodes = allPceNodes;
  72         this.pceResult = pceResult;
  73         this.pceHardConstraints = pceHardConstraints;
  74         this.pceSoftConstraints = pceSoftConstraints;
  75         this.serviceType = serviceType;
  76
  77         LOG.info("In GraphCalculator: A and Z = {} / {} ", aendNode, zendNode);
  78         LOG.debug("In GraphCalculator: allPceNodes size {}, nodes {} ", allPceNodes.size(), allPceNodes);
  79     }
  80
  81     public boolean calcPath() {
  82
  83         LOG.info(" In PCE GRAPH calcPath : K SHORT PATHS algorithm ");
  84
  85         DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph =
  86                 new DefaultDirectedWeightedGraph<>(PceGraphEdge.class);
  87         populateWithNodes(weightedGraph);
  88         populateWithLinks(weightedGraph);
  89
  90         if (!runKgraphs(weightedGraph)) {
  91             LOG.error("In calcPath : pceResult {}", pceResult);
  92             return false;
  93         }
  94         // validate found paths
  95         pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
  96         for (Entry<Integer, GraphPath<String, PceGraphEdge>> entry : allWPaths.entrySet()) {
  97             GraphPath<String, PceGraphEdge> path = entry.getValue();
  98             LOG.info("validating path n° {} - {}", entry.getKey(), path.getVertexList());
  99             PostAlgoPathValidator papv = new PostAlgoPathValidator();
 100             pceResult = papv.checkPath(path, allPceNodes, pceResult, pceHardConstraints, serviceType);
 101             if (ResponseCodes.RESPONSE_OK.equals(pceResult.getResponseCode())) {
 102                 LOG.info("Path is validated");
 103             } else {
 104                 LOG.warn("Path not validated - cause: {}", pceResult.getLocalCause());
 105             }
 106
 107             if (!pceResult.getResponseCode().equals(ResponseCodes.RESPONSE_OK)) {
 108                 LOG.warn("In calcPath: post algo validations DROPPED the path {}", path);
 109                 continue;
 110             }
 111
 112             // build pathAtoZ
 113             pathAtoZ.clear();
 114             for (PceGraphEdge edge : path.getEdgeList()) {
 115                 pathAtoZ.add(edge.link());
 116             }
 117
 118             shortestPathAtoZ = new ArrayList<>(pathAtoZ);
 119             switch (serviceType) {
 120
 121                 case StringConstants.SERVICE_TYPE_100GE_T:
 122                 case StringConstants.SERVICE_TYPE_OTUC2:
 123                 case StringConstants.SERVICE_TYPE_OTUC3:
 124                 case StringConstants.SERVICE_TYPE_OTUC4:
 125                 case StringConstants.SERVICE_TYPE_400GE:
 126                 case StringConstants.SERVICE_TYPE_OTU4:
 127                     LOG.debug(
 128                         "In calcPath Path FOUND path for wl [{}], min Freq assignment {}, max Freq assignment {},"
 129                         + " hops {}, distance per metrics {}, path AtoZ {}",
 130                         pceResult.getResultWavelength(), pceResult.getMinFreq(), pceResult.getMaxFreq(),
 131                         pathAtoZ.size(), path.getWeight(), pathAtoZ);
 132                     break;
 133
 134                 default:
 135                     LOG.debug(
 136                         "In calcPath Path FOUND path for hops {}, distance per metrics {}, path AtoZ {}",
 137                         pathAtoZ.size(), path.getWeight(), pathAtoZ);
 138                     break;
 139             }
 140             break;
 141
 142         }
 143
 144         if (shortestPathAtoZ != null) {
 145             LOG.info("In calcPath CHOOSEN PATH for wl [{}], min freq {}, max freq {}, hops {}, path AtoZ {}",
 146                     pceResult.getResultWavelength(), pceResult.getMinFreq(), pceResult.getMaxFreq(),
 147                     shortestPathAtoZ.size(), shortestPathAtoZ);
 148         }
 149         LOG.info("In calcPath : pceResult {}", pceResult);
 150         return (pceResult.getStatus());
 151     }
 152
 153     private boolean runKgraphs(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
 154
 155         if (weightedGraph.edgeSet().isEmpty() || weightedGraph.vertexSet().isEmpty()) {
 156             return false;
 157         }
 158         PathValidator<String, PceGraphEdge> wpv = new InAlgoPathValidator();
 159
 160         // KShortestPaths on weightedGraph
 161         KShortestSimplePaths<String, PceGraphEdge> swp =
 162             new KShortestSimplePaths<>(weightedGraph, mhopsPerPath, wpv);
 163         List<GraphPath<String, PceGraphEdge>> weightedPathList = swp
 164             .getPaths(apceNode.getNodeId().getValue(), zpceNode.getNodeId().getValue(), kpathsToBring);
 165         allWPaths = IntStream
 166             .range(0, weightedPathList.size())
 167             .boxed()
 168             .collect(Collectors.toMap(Function.identity(), weightedPathList::get));
 169
 170         if (allWPaths.isEmpty()) {
 171             LOG.info(" In runKgraphs : algorithm didn't find any path");
 172             pceResult.setLocalCause(LocalCause.NO_PATH_EXISTS);
 173             pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
 174             return false;
 175         }
 176
 177         // debug print
 178         allWPaths
 179             .forEach((k, v) -> LOG.info("path n° {} - weight: {} - path: {}", k, v.getWeight(), v.getVertexList()));
 180         return true;
 181     }
 182
 183     private boolean validateLinkforGraph(PceLink pcelink) {
 184
 185         PceNode source = allPceNodes.get(pcelink.getSourceId());
 186         PceNode dest = allPceNodes.get(pcelink.getDestId());
 187
 188         if (source == null) {
 189             LOG.error("In addLinkToGraph link source node is null : {}", pcelink);
 190             return false;
 191         }
 192         if (dest == null) {
 193             LOG.error("In addLinkToGraph link dest node is null : {}", pcelink);
 194             return false;
 195         }
 196         LOG.debug("In addLinkToGraph link to nodes : {}{} {}", pcelink, source, dest);
 197         return true;
 198     }
 199
 200     private void populateWithNodes(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
 201         Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
 202         while (nodes.hasNext()) {
 203             Map.Entry<NodeId, PceNode> node = nodes.next();
 204             if (State.InService.equals(node.getValue().getState())) {
 205                 weightedGraph.addVertex(node.getValue().getNodeId().getValue());
 206                 LOG.debug("In populateWithNodes in node :  {}", node.getValue());
 207             }
 208         }
 209     }
 210
 211     private boolean populateWithLinks(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
 212
 213         Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
 214         while (nodes.hasNext()) {
 215
 216             Map.Entry<NodeId, PceNode> node = nodes.next();
 217
 218             PceNode pcenode = node.getValue();
 219             List<PceLink> links = pcenode.getOutgoingLinks();
 220
 221             LOG.debug("In populateGraph: use node for graph {}", pcenode);
 222
 223             for (PceLink link : links) {
 224                 LOG.debug("In populateGraph node {} : add edge to graph {}", pcenode, link);
 225
 226                 if (!validateLinkforGraph(link)) {
 227                     continue;
 228                 }
 229                 if (State.InService.equals(link.getState())) {
 230                     PceGraphEdge graphLink = new PceGraphEdge(link);
 231                     weightedGraph.addEdge(link.getSourceId().getValue(), link.getDestId().getValue(), graphLink);
 232
 233                     weightedGraph.setEdgeWeight(graphLink, chooseWeight(link));
 234                 }
 235             }
 236         }
 237         return true;
 238     }
 239
 240     private double chooseWeight(PceLink link) {
 241         // HopCount is default
 242         double weight = 1;
 243         switch (pceHardConstraints.getPceMetrics()) {
 244             case HopCount :
 245                 weight = 1;
 246                 LOG.debug("In PceGraph HopCount is used as a metrics. {}", link);
 247                 break;
 248             case PropagationDelay :
 249                 weight = link.getLatency();
 250                 LOG.debug("In PceGraph PropagationDelay is used as a metrics. {}", link);
 251                 if ((weight == 0)
 252                         && ("1GE".equals(serviceType) || "10GE".equals(serviceType) || "ODU4".equals(serviceType))) {
 253                     LOG.warn("PropagationDelay set as metric, but latency is null: is latency set for OTN link {}?",
 254                         link);
 255                 }
 256                 break;
 257             // TODO implement IGPMetric and TEMetric - low priority.
 258             case IGPMetric :
 259             case TEMetric :
 260             default:
 261                 LOG.warn("In PceGraph {} not implemented. HopCount works as a default",
 262                     pceHardConstraints.getPceMetrics());
 263                 break;
 264         }
 265         return weight;
 266     }
 267
 268     public int getKpathsToBring() {
 269         return kpathsToBring;
 270     }
 271
 272     public void setKpathsToBring(int kpathsToBring) {
 273         this.kpathsToBring = kpathsToBring;
 274     }
 275
 276     public void setMhopsPerPath(int mhopsPerPath) {
 277         this.mhopsPerPath = mhopsPerPath;
 278     }
 279
 280     public List<PceLink> getPathAtoZ() {
 281         return shortestPathAtoZ;
 282     }
 283
 284     public PceResult getReturnStructure() {
 285         return pceResult;
 286     }
 287
 288     public void setConstrains(PceConstraints pceHardConstraintsInput, PceConstraints pceSoftConstraintsInput) {
 289         this.pceHardConstraints = pceHardConstraintsInput;
 290         this.pceSoftConstraints = pceSoftConstraintsInput;
 291     }
 292 }