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