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