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