pce/src/main/java/org/opendaylight/transportpce/pce/graph/InAlgoPathValidator.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.List;
  13
  14 import org.jgrapht.GraphPath;
  15 import org.jgrapht.alg.shortestpath.PathValidator;
  16 import org.opendaylight.transportpce.pce.constraints.PceConstraints;
  17 import org.opendaylight.transportpce.pce.constraints.PceConstraints.ResourcePair;
  18 import org.opendaylight.transportpce.pce.networkanalyzer.PceNode;
  19 import org.opendaylight.yang.gen.v1.http.org.openroadm.network.types.rev181130.OpenroadmLinkType;
  20 import org.slf4j.Logger;
  21 import org.slf4j.LoggerFactory;
  22
  23 public class InAlgoPathValidator implements PathValidator<String, PceGraphEdge> {
  24     /* Logging. */
  25     private static final Logger LOG = LoggerFactory.getLogger(PceGraph.class);
  26
  27     private PceConstraints pceHardConstraints = null;
  28     private PceNode zendNode = null;
  29
  30     public InAlgoPathValidator(PceConstraints pceHardConstraints, PceNode zendNode) {
  31         super();
  32         this.pceHardConstraints = pceHardConstraints;
  33         this.zendNode = zendNode;
  34     }
  35
  36     @Override
  37     public boolean isValidPath(GraphPath<String, PceGraphEdge> partialPath, PceGraphEdge edge) {
  38         int size = partialPath.getEdgeList().size();
  39         if (size == 0) {
  40             return true;
  41         }
  42         LOG.debug("InAlgoPathValidator: partialPath size: {} prev edge {} new edge {}",
  43             size, edge.link().getlinkType(), partialPath.getEdgeList().get(size - 1).link().getlinkType());
  44
  45         if (!checkTurn(partialPath.getEdgeList().get(size - 1).link().getlinkType(), edge.link().getlinkType())) {
  46             return false;
  47         }
  48         if (!checkLimits(partialPath, edge, pceHardConstraints)) {
  49             return false;
  50         }
  51         if (!checkInclude(partialPath, edge, zendNode, pceHardConstraints)) {
  52             return false;
  53         }
  54
  55         return true;
  56     }
  57
  58     private boolean checkTurn(OpenroadmLinkType prevType, OpenroadmLinkType nextType) {
  59
  60         if (nextType == OpenroadmLinkType.ADDLINK && prevType != OpenroadmLinkType.XPONDEROUTPUT) {
  61             LOG.debug("in checkPath dropped {} {} ", prevType, nextType);
  62             return false;
  63         }
  64
  65         if (nextType == OpenroadmLinkType.EXPRESSLINK && prevType != OpenroadmLinkType.ROADMTOROADM) {
  66             LOG.debug("in checkPath dropped {} {} ", prevType, nextType);
  67             return false;
  68         }
  69
  70         if (nextType == OpenroadmLinkType.DROPLINK && prevType != OpenroadmLinkType.ROADMTOROADM) {
  71             LOG.debug("in checkPath dropped {} {} ", prevType, nextType);
  72             return false;
  73         }
  74
  75         if (nextType == OpenroadmLinkType.XPONDERINPUT && prevType != OpenroadmLinkType.DROPLINK) {
  76             LOG.debug("in checkPath dropped {} {} ", prevType, nextType);
  77             return false;
  78         }
  79
  80         if (prevType == OpenroadmLinkType.EXPRESSLINK && nextType != OpenroadmLinkType.ROADMTOROADM) {
  81             LOG.debug("in checkPath dropped {} {} ", prevType, nextType);
  82             return false;
  83         }
  84
  85         if (prevType == OpenroadmLinkType.ADDLINK && nextType != OpenroadmLinkType.ROADMTOROADM) {
  86             LOG.debug("in checkPath dropped {} {} ", prevType, nextType);
  87             return false;
  88         }
  89
  90         return true;
  91     }
  92
  93     /*
  94      * this method should be added to JgraphT as accumulated values inside path
  95      * (RankingPathElementList)
  96      */
  97     private boolean checkLimits(GraphPath<String, PceGraphEdge> partialPath,
  98                                 PceGraphEdge edge, PceConstraints pceHardConstraintsInput) {
  99
 100         Long latencyConstraint = pceHardConstraintsInput.getMaxLatency();
 101         if (latencyConstraint > 0) {
 102             long newLatency = Math.round(calcLatency(partialPath) + edge.link().getLatency());
 103             if (newLatency > latencyConstraint) {
 104                 LOG.warn("In validateLatency: AtoZ path is dropped because of MAX LATENCY {} > {}",
 105                     newLatency, latencyConstraint);
 106                 return false;
 107             }
 108         }
 109
 110         return true;
 111     }
 112
 113     private double calcLatency(GraphPath<String, PceGraphEdge> path) {
 114         double latency = 0;
 115         for (PceGraphEdge edge : path.getEdgeList()) {
 116             latency = latency + edge.link().getLatency();
 117         }
 118         return latency;
 119     }
 120
 121     /*
 122      * checkInclude this method ensures the path is going over path elements
 123      * to be included, alway check target node in the new edge
 124      *
 125      */
 126     private boolean checkInclude(GraphPath<String, PceGraphEdge> partialPath,
 127                                  PceGraphEdge edge, PceNode zendNodeInput,
 128                                  PceConstraints pceHardConstraintsInput) {
 129
 130         List<ResourcePair> listToInclude = pceHardConstraintsInput.getListToInclude();
 131         if (listToInclude.isEmpty()) {
 132             return true;
 133         }
 134
 135         // run this check only for the last edge of path
 136         if (!edge.link().getDestId().getValue().equals(zendNodeInput.getNodeId().getValue())) {
 137             return true;
 138         }
 139         List<PceGraphEdge> pathEdges = partialPath.getEdgeList();
 140         pathEdges.add(edge);
 141         LOG.info(" in checkInclude vertex list: [{}]", partialPath.getVertexList());
 142
 143         List<String> listOfElementsSubNode = new ArrayList<String>();
 144         listOfElementsSubNode.add(pathEdges.get(0).link().getsourceSupNodeId());
 145         listOfElementsSubNode.addAll(listOfElementsBuild(pathEdges, PceConstraints.ResourceType.NODE));
 146
 147         List<String> listOfElementsCLLI = new ArrayList<String>();
 148         listOfElementsCLLI.add(pathEdges.get(0).link().getsourceCLLI());
 149         listOfElementsCLLI.addAll(listOfElementsBuild(pathEdges, PceConstraints.ResourceType.CLLI));
 150
 151         List<String> listOfElementsSRLG = new ArrayList<String>();
 152         listOfElementsSRLG.add("NONE"); // first link is XPONDEROUTPUT, no SRLG for it
 153         listOfElementsSRLG.addAll(listOfElementsBuild(pathEdges, PceConstraints.ResourceType.SRLG));
 154
 155         // validation: check each type for each element
 156         for (ResourcePair next : listToInclude) {
 157             int indx = -1;
 158             switch (next.type) {
 159                 case NODE:
 160                     if (listOfElementsSubNode.contains(next.name)) {
 161                         indx = listOfElementsSubNode.indexOf(next.name);
 162                     }
 163                     break;
 164                 case SRLG:
 165                     if (listOfElementsSRLG.contains(next.name)) {
 166                         indx = listOfElementsSRLG.indexOf(next.name);
 167                     }
 168                     break;
 169                 case CLLI:
 170                     if (listOfElementsCLLI.contains(next.name)) {
 171                         indx = listOfElementsCLLI.indexOf(next.name);
 172                     }
 173                     break;
 174                 default:
 175                     LOG.warn(" in checkInclude vertex list unsupported resource type: [{}]", next.type);
 176             }
 177
 178             if (indx < 0) {
 179                 LOG.debug(" in checkInclude stopped : {} ", next.name);
 180                 return false;
 181             }
 182
 183             LOG.debug(" in checkInclude next found {} in {}", next.name, partialPath.getVertexList());
 184
 185             listOfElementsSubNode.subList(0, indx).clear();
 186             listOfElementsCLLI.subList(0, indx).clear();
 187             listOfElementsSRLG.subList(0, indx).clear();
 188         }
 189
 190         LOG.info(" in checkInclude passed : {} ", partialPath.getVertexList());
 191         return true;
 192     }
 193
 194     private List<String> listOfElementsBuild(List<PceGraphEdge> pathEdges, PceConstraints.ResourceType type) {
 195         List<String> listOfElements = new ArrayList<String>();
 196
 197         for (PceGraphEdge link: pathEdges) {
 198             switch (type) {
 199                 case NODE:
 200                     listOfElements.add(link.link().getdestSupNodeId());
 201                     break;
 202                 case CLLI:
 203                     listOfElements.add(link.link().getdestCLLI());
 204                     break;
 205                 case SRLG:
 206                     if (link.link().getlinkType() != OpenroadmLinkType.ROADMTOROADM) {
 207                         listOfElements.add("NONE");
 208                         break;
 209                     }
 210
 211                     // srlg of link is List<Long>. But in this algo we need string representation of one SRLG
 212                     // this should be any SRLG mentioned in include constraints if any of them if mentioned
 213                     boolean found = false;
 214                     for (Long srlg : link.link().getsrlgList()) {
 215                         String srlgStr = String.valueOf(srlg);
 216                         if (pceHardConstraints.getSRLGnames().contains(srlgStr)) {
 217                             listOfElements.add(srlgStr);
 218                             LOG.info("listOfElementsBuild. FOUND SRLG {} in link {}", srlgStr, link.link().toString());
 219                             found = true;
 220                             continue;
 221                         }
 222                     }
 223                     if (found == false) {
 224                         // there is no specific srlg to include. thus add to list just the first one
 225                         listOfElements.add("NONE");
 226                     }
 227                     break;
 228                 default:
 229                     LOG.debug("listOfElementsBuild unsupported resource type");
 230             }
 231         }
 232
 233         return listOfElements;
 234     }
 235 }