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