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