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