pce/src/main/java/org/opendaylight/transportpce/pce/graph/PostAlgoPathValidator.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 edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
  12 import java.util.ArrayList;
  13 import java.util.Arrays;
  14 import java.util.BitSet;
  15 import java.util.Collections;
  16 import java.util.HashMap;
  17 import java.util.List;
  18 import java.util.Map;
  19 import org.jgrapht.GraphPath;
  20 import org.opendaylight.transportpce.common.ResponseCodes;
  21 import org.opendaylight.transportpce.common.StringConstants;
  22 import org.opendaylight.transportpce.common.fixedflex.GridConstant;
  23 import org.opendaylight.transportpce.common.fixedflex.GridUtils;
  24 import org.opendaylight.transportpce.pce.constraints.PceConstraints;
  25 import org.opendaylight.transportpce.pce.constraints.PceConstraints.ResourcePair;
  26 import org.opendaylight.transportpce.pce.model.SpectrumAssignment;
  27 import org.opendaylight.transportpce.pce.networkanalyzer.PceNode;
  28 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult;
  29 import org.opendaylight.yang.gen.v1.http.org.openroadm.network.types.rev200529.OpenroadmLinkType;
  30 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.NodeId;
  31 import org.opendaylight.yangtools.yang.common.Uint16;
  32 import org.slf4j.Logger;
  33 import org.slf4j.LoggerFactory;
  34
  35 public class PostAlgoPathValidator {
  36     /* Logging. */
  37     private static final Logger LOG = LoggerFactory.getLogger(PostAlgoPathValidator.class);
  38
  39     private static final double MIN_OSNR_W100G = 17;
  40     private static final double TRX_OSNR = 33;
  41     private static final double ADD_OSNR = 30;
  42     public static final Long CONST_OSNR = 1L;
  43     public static final double SYS_MARGIN = 0;
  44
  45     @SuppressFBWarnings(
  46         value = "SF_SWITCH_FALLTHROUGH",
  47         justification = "intentional fallthrough")
  48     public PceResult checkPath(GraphPath<String, PceGraphEdge> path, Map<NodeId, PceNode> allPceNodes,
  49         PceResult pceResult, PceConstraints pceHardConstraints, String serviceType) {
  50
  51         // check if the path is empty
  52         if (path.getEdgeList().isEmpty()) {
  53             pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
  54             return pceResult;
  55         }
  56         int tribSlotNb = 1;
  57         //variable to deal with 1GE (Nb=1) and 10GE (Nb=10) cases
  58         switch (serviceType) {
  59
  60             case StringConstants.SERVICE_TYPE_100GE:
  61             case StringConstants.SERVICE_TYPE_OTU4:
  62                 int spectralWidthSlotNumber = GridConstant.SPECTRAL_WIDTH_SLOT_NUMBER_MAP
  63                     .getOrDefault(serviceType, GridConstant.NB_SLOTS_100G);
  64                 SpectrumAssignment spectrumAssignment = getSpectrumAssignment(path,
  65                         allPceNodes, spectralWidthSlotNumber);
  66                 pceResult.setServiceType(serviceType);
  67                 if (spectrumAssignment.getBeginIndex() == 0 && spectrumAssignment.getStopIndex() == 0) {
  68                     pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
  69                     pceResult.setLocalCause(PceResult.LocalCause.NO_PATH_EXISTS);
  70                     return pceResult;
  71                 }
  72                 if (spectrumAssignment.isFlexGrid()) {
  73                     LOG.info("Spectrum assignment flexgrid mode");
  74                     pceResult.setResultWavelength(GridConstant.IRRELEVANT_WAVELENGTH_NUMBER);
  75                 } else {
  76                     LOG.info("Spectrum assignment fixedgrid mode");
  77                     pceResult.setResultWavelength(
  78                             GridUtils.getWaveLengthIndexFromSpectrumAssigment(spectrumAssignment.getBeginIndex()));
  79                 }
  80                 pceResult.setMinFreq(GridUtils.getStartFrequencyFromIndex(spectrumAssignment.getBeginIndex()));
  81                 pceResult.setMaxFreq(GridUtils.getStopFrequencyFromIndex(spectrumAssignment.getStopIndex()));
  82                 LOG.info("In PostAlgoPathValidator: spectrum assignment found {} {}", spectrumAssignment, path);
  83
  84                 // Check the OSNR
  85                 if (!checkOSNR(path)) {
  86                     pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
  87                     pceResult.setLocalCause(PceResult.LocalCause.OUT_OF_SPEC_OSNR);
  88                     return pceResult;
  89                 }
  90
  91                 // Check if MaxLatency is defined in the hard constraints
  92                 if ((pceHardConstraints.getMaxLatency() != -1)
  93                         && (!checkLatency(pceHardConstraints.getMaxLatency(), path))) {
  94                     pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
  95                     pceResult.setLocalCause(PceResult.LocalCause.TOO_HIGH_LATENCY);
  96                     return pceResult;
  97                 }
  98
  99                 // Check if nodes are included in the hard constraints
 100                 if (!checkInclude(path, pceHardConstraints)) {
 101                     pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
 102                     pceResult.setLocalCause(PceResult.LocalCause.HD_NODE_INCLUDE);
 103                     return pceResult;
 104                 }
 105
 106                 // TODO here other post algo validations can be added
 107                 // more data can be sent to PceGraph module via PceResult structure if required
 108
 109                 pceResult.setRC(ResponseCodes.RESPONSE_OK);
 110                 pceResult.setLocalCause(PceResult.LocalCause.NONE);
 111
 112                 break;
 113
 114             case StringConstants.SERVICE_TYPE_10GE:
 115                 tribSlotNb = 8;
 116             //fallthrough
 117             case StringConstants.SERVICE_TYPE_1GE:
 118                 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
 119                 pceResult.setServiceType(serviceType);
 120                 Map<String, Uint16> tribPort = chooseTribPort(path, allPceNodes);
 121                 Map<String, List<Uint16>> tribSlot = chooseTribSlot(path, allPceNodes, tribSlotNb);
 122
 123                 if (tribPort != null && tribSlot != null) {
 124                     pceResult.setResultTribPort(tribPort);
 125                     pceResult.setResultTribSlot(tribSlot);
 126                     pceResult.setResultTribSlotNb(tribSlotNb);
 127                     pceResult.setRC(ResponseCodes.RESPONSE_OK);
 128                     LOG.info("In PostAlgoPathValidator: found TribPort {} - tribSlot {} - tribSlotNb {}",
 129                         tribPort, tribSlot, tribSlotNb);
 130                 }
 131                 break;
 132
 133             case StringConstants.SERVICE_TYPE_ODU4:
 134                 pceResult.setRC(ResponseCodes.RESPONSE_OK);
 135                 LOG.info("In PostAlgoPathValidator: ODU4 path found {}", path);
 136                 break;
 137
 138             default:
 139                 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
 140                 LOG.warn("In PostAlgoPathValidator checkPath: unsupported serviceType {} found {}",
 141                     serviceType, path);
 142                 break;
 143         }
 144
 145         return pceResult;
 146     }
 147
 148     // Check the latency
 149     private boolean checkLatency(Long maxLatency, GraphPath<String, PceGraphEdge> path) {
 150         double latency = 0;
 151
 152         for (PceGraphEdge edge : path.getEdgeList()) {
 153             try {
 154                 latency += edge.link().getLatency();
 155                 LOG.debug("- In checkLatency: latency of {} = {} units", edge.link().getLinkId().getValue(), latency);
 156             } catch (NullPointerException e) {
 157                 LOG.warn("- In checkLatency: the link {} does not contain latency field",
 158                     edge.link().getLinkId().getValue());
 159             }
 160         }
 161         return (latency < maxLatency);
 162     }
 163
 164     // Check the inclusion if it is defined in the hard constraints
 165     private boolean checkInclude(GraphPath<String, PceGraphEdge> path, PceConstraints pceHardConstraintsInput) {
 166         List<ResourcePair> listToInclude = pceHardConstraintsInput.getListToInclude();
 167         if (listToInclude.isEmpty()) {
 168             return true;
 169         }
 170
 171         List<PceGraphEdge> pathEdges = path.getEdgeList();
 172         LOG.debug(" in checkInclude vertex list: [{}]", path.getVertexList());
 173
 174         List<String> listOfElementsSubNode = new ArrayList<>();
 175         listOfElementsSubNode.add(pathEdges.get(0).link().getsourceNetworkSupNodeId());
 176         listOfElementsSubNode.addAll(listOfElementsBuild(pathEdges, PceConstraints.ResourceType.NODE,
 177             pceHardConstraintsInput));
 178
 179         List<String> listOfElementsCLLI = new ArrayList<>();
 180         listOfElementsCLLI.add(pathEdges.get(0).link().getsourceCLLI());
 181         listOfElementsCLLI.addAll(listOfElementsBuild(pathEdges, PceConstraints.ResourceType.CLLI,
 182             pceHardConstraintsInput));
 183
 184         List<String> listOfElementsSRLG = new ArrayList<>();
 185         // first link is XPONDEROUTPUT, no SRLG for it
 186         listOfElementsSRLG.add("NONE");
 187         listOfElementsSRLG.addAll(listOfElementsBuild(pathEdges, PceConstraints.ResourceType.SRLG,
 188             pceHardConstraintsInput));
 189
 190         // validation: check each type for each element
 191         for (ResourcePair next : listToInclude) {
 192             int indx = -1;
 193             switch (next.getType()) {
 194                 case NODE:
 195                     if (listOfElementsSubNode.contains(next.getName())) {
 196                         indx = listOfElementsSubNode.indexOf(next.getName());
 197                     }
 198                     break;
 199                 case SRLG:
 200                     if (listOfElementsSRLG.contains(next.getName())) {
 201                         indx = listOfElementsSRLG.indexOf(next.getName());
 202                     }
 203                     break;
 204                 case CLLI:
 205                     if (listOfElementsCLLI.contains(next.getName())) {
 206                         indx = listOfElementsCLLI.indexOf(next.getName());
 207                     }
 208                     break;
 209                 default:
 210                     LOG.warn(" in checkInclude vertex list unsupported resource type: [{}]", next.getType());
 211             }
 212
 213             if (indx < 0) {
 214                 LOG.debug(" in checkInclude stopped : {} ", next.getName());
 215                 return false;
 216             }
 217
 218             LOG.debug(" in checkInclude next found {} in {}", next.getName(), path.getVertexList());
 219
 220             listOfElementsSubNode.subList(0, indx).clear();
 221             listOfElementsCLLI.subList(0, indx).clear();
 222             listOfElementsSRLG.subList(0, indx).clear();
 223         }
 224
 225         LOG.info(" in checkInclude passed : {} ", path.getVertexList());
 226         return true;
 227     }
 228
 229     private List<String> listOfElementsBuild(List<PceGraphEdge> pathEdges, PceConstraints.ResourceType type,
 230         PceConstraints pceHardConstraints) {
 231
 232         List<String> listOfElements = new ArrayList<>();
 233         for (PceGraphEdge link : pathEdges) {
 234             switch (type) {
 235                 case NODE:
 236                     listOfElements.add(link.link().getdestNetworkSupNodeId());
 237                     break;
 238                 case CLLI:
 239                     listOfElements.add(link.link().getdestCLLI());
 240                     break;
 241                 case SRLG:
 242                     if (link.link().getlinkType() != OpenroadmLinkType.ROADMTOROADM) {
 243                         listOfElements.add("NONE");
 244                         break;
 245                     }
 246                     // srlg of link is List<Long>. But in this algo we need string representation of
 247                     // one SRLG
 248                     // this should be any SRLG mentioned in include constraints if any of them if
 249                     // mentioned
 250                     boolean found = false;
 251                     for (Long srlg : link.link().getsrlgList()) {
 252                         String srlgStr = String.valueOf(srlg);
 253                         if (pceHardConstraints.getSRLGnames().contains(srlgStr)) {
 254                             listOfElements.add(srlgStr);
 255                             LOG.info("listOfElementsBuild. FOUND SRLG {} in link {}", srlgStr, link.link());
 256                             found = true;
 257                         }
 258                     }
 259                     if (!found) {
 260                         // there is no specific srlg to include. thus add to list just the first one
 261                         listOfElements.add("NONE");
 262                     }
 263                     break;
 264                 default:
 265                     LOG.debug("listOfElementsBuild unsupported resource type");
 266             }
 267         }
 268         return listOfElements;
 269     }
 270
 271     private Map<String, Uint16> chooseTribPort(GraphPath<String,
 272         PceGraphEdge> path, Map<NodeId, PceNode> allPceNodes) {
 273         LOG.info("In choosetribPort: edgeList = {} ", path.getEdgeList());
 274         Map<String, Uint16> tribPortMap = new HashMap<>();
 275
 276         for (PceGraphEdge edge : path.getEdgeList()) {
 277             NodeId linkSrcNode = edge.link().getSourceId();
 278             String linkSrcTp = edge.link().getSourceTP().toString();
 279             NodeId linkDestNode = edge.link().getDestId();
 280             String linkDestTp = edge.link().getDestTP().toString();
 281             PceNode pceOtnNodeSrc = allPceNodes.get(linkSrcNode);
 282             PceNode pceOtnNodeDest = allPceNodes.get(linkDestNode);
 283             List<Uint16> srcTpnPool = pceOtnNodeSrc.getAvailableTribPorts().get(linkSrcTp);
 284             List<Uint16> destTpnPool = pceOtnNodeDest.getAvailableTribPorts().get(linkDestTp);
 285             List<Uint16> commonEdgeTpnPool = new ArrayList<>();
 286             for (Uint16 integer : srcTpnPool) {
 287                 if (destTpnPool.contains(integer)) {
 288                     commonEdgeTpnPool.add(integer);
 289                 }
 290             }
 291             Collections.sort(commonEdgeTpnPool);
 292             if (!commonEdgeTpnPool.isEmpty()) {
 293                 tribPortMap.put(edge.link().getLinkId().getValue(), commonEdgeTpnPool.get(0));
 294             }
 295         }
 296         tribPortMap.forEach((k,v) -> LOG.info("TribPortMap : k = {}, v = {}", k, v));
 297         return tribPortMap;
 298     }
 299
 300     private Map<String, List<Uint16>> chooseTribSlot(GraphPath<String,
 301         PceGraphEdge> path, Map<NodeId, PceNode> allPceNodes, int nbSlot) {
 302         LOG.info("In choosetribSlot: edgeList = {} ", path.getEdgeList());
 303         Map<String, List<Uint16>> tribSlotMap = new HashMap<>();
 304
 305         for (PceGraphEdge edge : path.getEdgeList()) {
 306             NodeId linkSrcNode = edge.link().getSourceId();
 307             String linkSrcTp = edge.link().getSourceTP().toString();
 308             NodeId linkDestNode = edge.link().getDestId();
 309             String linkDestTp = edge.link().getDestTP().toString();
 310             PceNode pceOtnNodeSrc = allPceNodes.get(linkSrcNode);
 311             PceNode pceOtnNodeDest = allPceNodes.get(linkDestNode);
 312             List<Uint16> srcTsPool = pceOtnNodeSrc.getAvailableTribSlots().get(linkSrcTp);
 313             List<Uint16> destTsPool = pceOtnNodeDest.getAvailableTribSlots().get(linkDestTp);
 314             List<Uint16> commonEdgeTsPool = new ArrayList<>();
 315             List<Uint16> tribSlotList = new ArrayList<>();
 316             for (Uint16 integer : srcTsPool) {
 317                 if (destTsPool.contains(integer)) {
 318                     commonEdgeTsPool.add(integer);
 319                 }
 320             }
 321             Collections.sort(commonEdgeTsPool);
 322             boolean discontinue = true;
 323             int index = 0;
 324             while (discontinue && (commonEdgeTsPool.size() - index >= nbSlot)) {
 325                 discontinue = false;
 326                 Integer val = commonEdgeTsPool.get(index).toJava();
 327                 for (int i = 0; i < nbSlot; i++) {
 328                     if (commonEdgeTsPool.get(index + i).equals(Uint16.valueOf(val + i))) {
 329                         tribSlotList.add(commonEdgeTsPool.get(index + i));
 330                     } else {
 331                         discontinue = true;
 332                         tribSlotList.clear();
 333                         index += i;
 334                         break;
 335                     }
 336                 }
 337             }
 338             tribSlotMap.put(edge.link().getLinkId().getValue(), tribSlotList);
 339         }
 340         tribSlotMap.forEach((k,v) -> LOG.info("TribSlotMap : k = {}, v = {}", k, v));
 341         return tribSlotMap;
 342     }
 343
 344     // Check the path OSNR
 345     private boolean checkOSNR(GraphPath<String, PceGraphEdge> path) {
 346         double linkOsnrDb;
 347         double osnrDb = 0;
 348         LOG.info("- In checkOSNR: OSNR of the transmitter = {} dB", TRX_OSNR);
 349         LOG.info("- In checkOSNR: add-path incremental OSNR = {} dB", ADD_OSNR);
 350         double inverseLocalOsnr = getInverseOsnrLinkLu(TRX_OSNR) + getInverseOsnrLinkLu(ADD_OSNR);
 351         for (PceGraphEdge edge : path.getEdgeList()) {
 352             if (edge.link().getlinkType() == OpenroadmLinkType.ROADMTOROADM) {
 353                 // link OSNR in dB
 354                 linkOsnrDb = edge.link().getosnr();
 355                 LOG.info("- In checkOSNR: OSNR of {} = {} dB", edge.link().getLinkId().getValue(), linkOsnrDb);
 356                 // 1 over the local OSNR, in linear units
 357                 inverseLocalOsnr += getInverseOsnrLinkLu(linkOsnrDb);
 358             }
 359         }
 360         try {
 361             osnrDb = getOsnrDb(1 / inverseLocalOsnr);
 362         } catch (ArithmeticException e) {
 363             LOG.debug("In checkOSNR: OSNR is equal to 0 and the number of links is: {}", path.getEdgeList().size());
 364             return false;
 365         }
 366         LOG.info("In checkOSNR: OSNR of the path is {} dB", osnrDb);
 367         return ((osnrDb + SYS_MARGIN) > MIN_OSNR_W100G);
 368     }
 369
 370     private double getOsnrDb(double osnrLu) {
 371         double osnrDb;
 372         osnrDb = 10 * Math.log10(osnrLu);
 373         return osnrDb;
 374     }
 375
 376     private double getInverseOsnrLinkLu(double linkOsnrDb) {
 377         // 1 over the link OSNR, in linear units
 378         double linkOsnrLu;
 379         linkOsnrLu = Math.pow(10, (linkOsnrDb / 10.0));
 380         LOG.debug("In retrieveosnr: the inverse of link osnr is {} (Linear Unit)", linkOsnrLu);
 381         return (CONST_OSNR / linkOsnrLu);
 382     }
 383
 384     /**
 385      * Get spectrum assignment for path.
 386      *
 387      * @param path                    the path for which we get spectrum assignment.
 388      * @param allPceNodes             all optical nodes.
 389      * @param spectralWidthSlotNumber number of slot for spectral width. Depends on
 390      *                                service type.
 391      * @return a spectrum assignment object which contains begin and end index. If
 392      *         no spectrum assignment found, beginIndex = stopIndex = 0
 393      */
 394     private SpectrumAssignment getSpectrumAssignment(GraphPath<String, PceGraphEdge> path,
 395             Map<NodeId, PceNode> allPceNodes, int spectralWidthSlotNumber) {
 396         byte[] freqMap = new byte[GridConstant.NB_OCTECTS];
 397         Arrays.fill(freqMap, (byte) GridConstant.AVAILABLE_SLOT_VALUE);
 398         BitSet result = BitSet.valueOf(freqMap);
 399         boolean isFlexGrid = true;
 400         LOG.info("Processing path {} with length {}", path, path.getLength());
 401         BitSet pceNodeFreqMap;
 402         for (PceGraphEdge edge : path.getEdgeList()) {
 403             LOG.info("Processing source {} ", edge.link().getSourceId());
 404             if (allPceNodes.containsKey(edge.link().getSourceId())) {
 405                 PceNode pceNode = allPceNodes.get(edge.link().getSourceId());
 406                 LOG.info("Processing PCE node {}", pceNode);
 407                 if (StringConstants.OPENROADM_DEVICE_VERSION_1_2_1.equals(pceNode.getVersion())
 408                         || pceNode.getSlotWidthGranularity().compareTo(GridConstant.SLOT_WIDTH_50) == 0) {
 409                     LOG.info("Node {}: version is {} and slot width granularity is {} -> fixed grid mode",
 410                             pceNode.getNodeId(), pceNode.getVersion(), pceNode.getSlotWidthGranularity());
 411                     isFlexGrid = false;
 412                 }
 413                 pceNodeFreqMap = pceNode.getBitSetData();
 414                 LOG.debug("Pce node bitset {}", pceNodeFreqMap);
 415                 if (pceNodeFreqMap != null) {
 416                     result.and(pceNodeFreqMap);
 417                     LOG.debug("intermediate bitset {}", result);
 418                 }
 419             }
 420         }
 421         LOG.debug("Bitset result {}", result);
 422         return computeBestSpectrumAssignment(result, spectralWidthSlotNumber, isFlexGrid);
 423     }
 424
 425     /**
 426      * Compute spectrum assignment from spectrum occupation for spectral width.
 427      *
 428      * @param spectrumOccupation      the spectrum occupation BitSet.
 429      * @param spectralWidthSlotNumber the nb slots for spectral width.
 430      * @param isFlexGrid              true if flexible grid, false otherwise.
 431      * @return a spectrum assignment object which contains begin and stop index. If
 432      *         no spectrum assignment found, beginIndex = stopIndex = 0
 433      */
 434     private SpectrumAssignment computeBestSpectrumAssignment(BitSet spectrumOccupation, int spectralWidthSlotNumber,
 435             boolean isFlexGrid) {
 436         SpectrumAssignment spectrumAssignment = new SpectrumAssignment(0, 0);
 437         spectrumAssignment.setFlexGrid(isFlexGrid);
 438         BitSet referenceBitSet = new BitSet(spectralWidthSlotNumber);
 439         referenceBitSet.set(0, spectralWidthSlotNumber);
 440         int nbSteps = 1;
 441         if (isFlexGrid) {
 442             nbSteps = spectralWidthSlotNumber;
 443         }
 444         //higher is the frequency, smallest is the wavelength number
 445         //in operational, the allocation is done through wavelength starting from the smallest
 446         //so we have to loop from the last element of the spectrum occupation
 447         for (int i = spectrumOccupation.size(); i >= spectralWidthSlotNumber; i -= nbSteps) {
 448             if (spectrumOccupation.get(i - spectralWidthSlotNumber, i).equals(referenceBitSet)) {
 449                 spectrumAssignment.setBeginIndex(i - spectralWidthSlotNumber);
 450                 spectrumAssignment.setStopIndex(i - 1);
 451                 break;
 452             }
 453         }
 454         return spectrumAssignment;
 455     }
 456
 457 }