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.Graph;
  21 import org.jgrapht.GraphPath;
  22 import org.jgrapht.alg.shortestpath.PathValidator;
  23 import org.jgrapht.alg.shortestpath.YenKShortestPath;
  24 import org.jgrapht.graph.DefaultDirectedWeightedGraph;
  25 import org.opendaylight.transportpce.common.ResponseCodes;
  26 import org.opendaylight.transportpce.common.StringConstants;
  27 import org.opendaylight.transportpce.common.network.NetworkTransactionService;
  28 import org.opendaylight.transportpce.pce.constraints.PceConstraints;
  29 import org.opendaylight.transportpce.pce.networkanalyzer.PceLink;
  30 import org.opendaylight.transportpce.pce.networkanalyzer.PceNode;
  31 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult;
  32 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult.LocalCause;
  33 import org.opendaylight.yang.gen.v1.http.org.opendaylight.transportpce.pce.rev230925.PceConstraintMode;
  34 import org.opendaylight.yang.gen.v1.http.org.openroadm.common.state.types.rev191129.State;
  35 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.NodeId;
  36 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.topology.rev180226.LinkId;
  37 import org.slf4j.Logger;
  38 import org.slf4j.LoggerFactory;
  39
  40 public class PceGraph {
  41     /* Logging. */
  42     private static final Logger LOG = LoggerFactory.getLogger(PceGraph.class);
  43
  44     ////////////////////////// for Graph ///////////////////////////
  45     // how many paths to bring
  46     private int kpathsToBring = 15;
  47
  48     // input
  49     private Map<NodeId, PceNode> allPceNodes = new HashMap<>();
  50     private Map<LinkId, PceLink> allPceLinks = new HashMap<>();
  51     private PceNode apceNode = null;
  52     private PceNode zpceNode = null;
  53     private String serviceType = "";
  54     private Double margin = null;
  55     PceConstraints pceHardConstraints;
  56     private PceConstraintMode pceConstraintMode;
  57
  58     // results
  59     private PceResult pceResult = null;
  60     private List<PceLink> shortestPathAtoZ = null;
  61
  62     // for path calculation
  63     Map<Integer, GraphPath<String, PceGraphEdge>> allWPaths = null;
  64
  65     private List<PceLink> pathAtoZ = new ArrayList<>();
  66
  67     private final NetworkTransactionService networkTransactionService;
  68
  69     public PceGraph(PceNode aendNode, PceNode zendNode, Map<NodeId, PceNode> allPceNodes,
  70             Map<LinkId, PceLink> allPceLinks, PceConstraints pceHardConstraints,PceResult pceResult, String serviceType,
  71             NetworkTransactionService networkTransactionService, PceConstraintMode mode) {
  72         super();
  73         this.apceNode = aendNode;
  74         this.zpceNode = zendNode;
  75         this.allPceNodes = allPceNodes;
  76         this.allPceLinks = allPceLinks;
  77         this.pceResult = pceResult;
  78         this.pceHardConstraints = pceHardConstraints;
  79         this.serviceType = serviceType;
  80         this.networkTransactionService = networkTransactionService;
  81         this.pceConstraintMode = mode;
  82
  83         LOG.info("In GraphCalculator: A and Z = {} / {} ", aendNode, zendNode);
  84         LOG.debug("In GraphCalculator: allPceNodes size {}, nodes {} ", allPceNodes.size(), allPceNodes);
  85     }
  86
  87     public boolean calcPath() {
  88
  89         LOG.info(" In PCE GRAPH calcPath : K SHORT PATHS algorithm ");
  90
  91         Graph<String, PceGraphEdge> weightedGraph =
  92                 new DefaultDirectedWeightedGraph<>(PceGraphEdge.class);
  93         populateWithNodes(weightedGraph);
  94         populateWithLinks(weightedGraph);
  95
  96         if (!runKgraphs(weightedGraph)) {
  97             LOG.error("In calcPath : pceResult {}", pceResult);
  98             return false;
  99         }
 100         // validate found paths
 101         pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
 102         for (Entry<Integer, GraphPath<String, PceGraphEdge>> entry : allWPaths.entrySet()) {
 103             GraphPath<String, PceGraphEdge> path = entry.getValue();
 104             LOG.info("validating path n° {} - {}", entry.getKey(), path.getVertexList());
 105             PostAlgoPathValidator papv = new PostAlgoPathValidator(networkTransactionService);
 106             pceResult = papv.checkPath(
 107                     path, allPceNodes, allPceLinks, pceResult, pceHardConstraints, serviceType, pceConstraintMode);
 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(Graph<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         // YenShortestPath on weightedGraph
 166         YenKShortestPath<String, PceGraphEdge> swp = new YenKShortestPath<>(weightedGraph, wpv);
 167         List<GraphPath<String, PceGraphEdge>> weightedPathList = swp
 168             .getPaths(apceNode.getNodeId().getValue(), zpceNode.getNodeId().getValue(), kpathsToBring);
 169         allWPaths = IntStream
 170             .range(0, weightedPathList.size())
 171             .boxed()
 172             .collect(Collectors.toMap(Function.identity(), weightedPathList::get));
 173
 174         if (allWPaths.isEmpty()) {
 175             LOG.info(" In runKgraphs : algorithm didn't find any path");
 176             pceResult.setLocalCause(LocalCause.NO_PATH_EXISTS);
 177             pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
 178             return false;
 179         }
 180
 181         // debug print
 182         allWPaths
 183             .forEach((k, v) -> LOG.info("path n° {} - weight: {} - path: {}", k, v.getWeight(), v.getVertexList()));
 184         return true;
 185     }
 186
 187     private boolean validateLinkforGraph(PceLink pcelink) {
 188
 189         PceNode source = allPceNodes.get(pcelink.getSourceId());
 190         PceNode dest = allPceNodes.get(pcelink.getDestId());
 191
 192         if (source == null) {
 193             LOG.error("In addLinkToGraph link source node is null : {}", pcelink);
 194             return false;
 195         }
 196         if (dest == null) {
 197             LOG.error("In addLinkToGraph link dest node is null : {}", pcelink);
 198             return false;
 199         }
 200         LOG.debug("In addLinkToGraph link to nodes : {}{} {}", pcelink, source, dest);
 201         return true;
 202     }
 203
 204     private void populateWithNodes(Graph<String, PceGraphEdge> weightedGraph) {
 205         Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
 206         while (nodes.hasNext()) {
 207             Map.Entry<NodeId, PceNode> node = nodes.next();
 208             if (State.InService.equals(node.getValue().getState())) {
 209                 weightedGraph.addVertex(node.getValue().getNodeId().getValue());
 210                 LOG.debug("In populateWithNodes in node :  {}", node.getValue());
 211             }
 212         }
 213     }
 214
 215     private boolean populateWithLinks(Graph<String, PceGraphEdge> weightedGraph) {
 216
 217         Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
 218         while (nodes.hasNext()) {
 219
 220             Map.Entry<NodeId, PceNode> node = nodes.next();
 221
 222             PceNode pcenode = node.getValue();
 223             List<PceLink> links = pcenode.getOutgoingLinks();
 224
 225             LOG.debug("In populateGraph: use node for graph {}", pcenode);
 226
 227             for (PceLink link : links) {
 228                 LOG.debug("In populateGraph node {} : add edge to graph {}", pcenode, link);
 229
 230                 if (!validateLinkforGraph(link)) {
 231                     continue;
 232                 }
 233                 if (State.InService.equals(link.getState())) {
 234                     PceGraphEdge graphLink = new PceGraphEdge(link);
 235                     weightedGraph.addEdge(link.getSourceId().getValue(), link.getDestId().getValue(), graphLink);
 236
 237                     weightedGraph.setEdgeWeight(graphLink, chooseWeight(link));
 238                 }
 239             }
 240         }
 241         return true;
 242     }
 243
 244     private double chooseWeight(PceLink link) {
 245         // HopCount is default
 246         double weight = 1;
 247         switch (pceHardConstraints.getPceMetrics()) {
 248             case HopCount :
 249                 weight = 1;
 250                 LOG.debug("In PceGraph HopCount is used as a metrics. {}", link);
 251                 break;
 252             case PropagationDelay :
 253                 weight = link.getLatency();
 254                 LOG.debug("In PceGraph PropagationDelay is used as a metrics. {}", link);
 255                 if ((weight == 0)
 256                         && ("1GE".equals(serviceType) || "10GE".equals(serviceType) || "ODU4".equals(serviceType))) {
 257                     LOG.warn("PropagationDelay set as metric, but latency is null: is latency set for OTN link {}?",
 258                         link);
 259                 }
 260                 break;
 261             // TODO implement IGPMetric and TEMetric - low priority.
 262             case IGPMetric :
 263             case TEMetric :
 264             default:
 265                 LOG.warn("In PceGraph {} not implemented. HopCount works as a default",
 266                     pceHardConstraints.getPceMetrics());
 267                 break;
 268         }
 269         return weight;
 270     }
 271
 272     public int getKpathsToBring() {
 273         return kpathsToBring;
 274     }
 275
 276     public void setKpathsToBring(int kpathsToBring) {
 277         this.kpathsToBring = kpathsToBring;
 278     }
 279
 280     public List<PceLink> getPathAtoZ() {
 281         return shortestPathAtoZ;
 282     }
 283
 284     public PceResult getReturnStructure() {
 285         return pceResult;
 286     }
 287
 288     public Double getmargin() {
 289         return margin;
 290     }
 291
 292     public void setConstrains(PceConstraints pceHardConstraintsInput) {
 293         this.pceHardConstraints = pceHardConstraintsInput;
 294     }
 295 }