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