pce/src/main/java/org/opendaylight/transportpce/pce/networkanalyzer/PceCalculation.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.networkanalyzer;
  10
  11 import java.util.ArrayList;
  12 import java.util.HashMap;
  13 import java.util.HashSet;
  14 import java.util.Iterator;
  15 import java.util.List;
  16 import java.util.Map;
  17 import java.util.Optional;
  18 import java.util.Set;
  19 import java.util.concurrent.ExecutionException;
  20 import java.util.stream.Collectors;
  21
  22 import org.opendaylight.mdsal.common.api.LogicalDatastoreType;
  23 import org.opendaylight.transportpce.common.NetworkUtils;
  24 import org.opendaylight.transportpce.common.ResponseCodes;
  25 import org.opendaylight.transportpce.common.network.NetworkTransactionService;
  26 import org.opendaylight.transportpce.pce.constraints.PceConstraints;
  27 import org.opendaylight.yang.gen.v1.http.org.opendaylight.transportpce.pce.rev190624.PathComputationRequestInput;
  28 import org.opendaylight.yang.gen.v1.http.org.openroadm.common.network.rev181130.Node1;
  29 import org.opendaylight.yang.gen.v1.http.org.openroadm.network.types.rev181130.OpenroadmLinkType;
  30 import org.opendaylight.yang.gen.v1.http.org.openroadm.network.types.rev181130.OpenroadmNodeType;
  31 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.NetworkId;
  32 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.Networks;
  33 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.NodeId;
  34 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.networks.Network;
  35 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.networks.NetworkKey;
  36 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.networks.network.Node;
  37 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.topology.rev180226.LinkId;
  38 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.topology.rev180226.Network1;
  39 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.topology.rev180226.networks.network.Link;
  40 import org.opendaylight.yangtools.yang.binding.InstanceIdentifier;
  41 import org.slf4j.Logger;
  42 import org.slf4j.LoggerFactory;
  43
  44 public class PceCalculation {
  45     /* Logging. */
  46     private static final Logger LOG = LoggerFactory.getLogger(PceCalculation.class);
  47     private NetworkTransactionService networkTransactionService = null;
  48
  49     ///////////// data parsed from Input/////////////////
  50     private PathComputationRequestInput input;
  51     private String anodeId = "";
  52     private String znodeId = "";
  53
  54     private PceConstraints pceHardConstraints;
  55
  56     ///////////// Intermediate data/////////////////
  57     private List<PceLink> addLinks = new ArrayList<PceLink>();
  58     private List<PceLink> dropLinks = new ArrayList<PceLink>();
  59     private HashSet<NodeId> azSrgs = new HashSet<NodeId>();
  60
  61     private PceNode aendPceNode = null;
  62     private PceNode zendPceNode = null;
  63
  64     private List<Link> allLinks = null;
  65     private List<Node> allNodes = null;
  66
  67     // this List serves graph calculation
  68     private Map<NodeId, PceNode> allPceNodes = new HashMap<NodeId, PceNode>();
  69     // this List serves calculation of ZtoA path description
  70     // TODO maybe better solution is possible
  71     private Map<LinkId, PceLink> allPceLinks = new HashMap<LinkId, PceLink>();
  72     private Set<LinkId> linksToExclude = new HashSet<LinkId>();
  73     private PceResult returnStructure;
  74
  75     private enum ConstraintTypes {
  76         NONE, HARD_EXCLUDE, HARD_INCLUDE, HARD_DIVERSITY, SOFT_EXCLUDE, SOFT_INCLUDE, SOFT_DIVERSITY;
  77     }
  78
  79     public PceCalculation(PathComputationRequestInput input, NetworkTransactionService networkTransactionService,
  80             PceConstraints pceHardConstraints, PceConstraints pceSoftConstraints, PceResult rc) {
  81         this.input = input;
  82         this.networkTransactionService = networkTransactionService;
  83         this.returnStructure = rc;
  84
  85         this.pceHardConstraints = pceHardConstraints;
  86         parseInput();
  87     }
  88
  89     public void calcPath() {
  90
  91         LOG.info("In PceCalculation calcPath: ");
  92
  93         if (!readMdSal()) {
  94             returnStructure.setRC(ResponseCodes.RESPONSE_FAILED);
  95             return;
  96         }
  97         MapUtils.mapDiversityConstraints(allNodes, allLinks, pceHardConstraints);
  98
  99         if (!analyzeNw()) {
 100             returnStructure.setRC(ResponseCodes.RESPONSE_FAILED);
 101             return;
 102         }
 103         printNodesInfo(allPceNodes);
 104
 105         returnStructure.setRC(ResponseCodes.RESPONSE_OK);
 106         return;
 107     }
 108
 109     private boolean parseInput() {
 110         anodeId = input.getServiceAEnd().getNodeId();
 111         znodeId = input.getServiceZEnd().getNodeId();
 112         LOG.info("parseInput: A and Z :[{}] and [{}]", anodeId, znodeId);
 113         returnStructure.setRate(input.getServiceAEnd().getServiceRate());
 114         return true;
 115     }
 116
 117     private boolean readMdSal() {
 118         LOG.info("readMdSal: network {}", NetworkUtils.OVERLAY_NETWORK_ID);
 119         InstanceIdentifier<Network> nwInstanceIdentifier = InstanceIdentifier.builder(Networks.class)
 120             .child(Network.class, new NetworkKey(new NetworkId(NetworkUtils.OVERLAY_NETWORK_ID))).build();
 121         Network nw = null;
 122         try {
 123             Optional<Network> nwOptional =
 124                 networkTransactionService.read(LogicalDatastoreType.CONFIGURATION, nwInstanceIdentifier).get();
 125             if (nwOptional.isPresent()) {
 126                 nw = nwOptional.get();
 127                 LOG.debug("readMdSal: network nodes: nwOptional.isPresent = true {}", nw.toString());
 128             }
 129         } catch (InterruptedException | ExecutionException e) {
 130             LOG.error("readMdSal: Error reading topology {}", nwInstanceIdentifier);
 131             networkTransactionService.close();
 132             returnStructure.setRC(ResponseCodes.RESPONSE_FAILED);
 133             throw new RuntimeException(
 134                     "readMdSal: Error reading from operational store, topology : " + nwInstanceIdentifier + " :" + e);
 135         }
 136         networkTransactionService.close();
 137
 138         if (nw == null) {
 139             LOG.error("readMdSal: network is null: {}", nwInstanceIdentifier);
 140             return false;
 141         }
 142         allNodes = nw.getNode().stream().sorted((n1, n2) -> n1.getNodeId().getValue().compareTo(n2.getNodeId()
 143             .getValue())).collect(Collectors.toList());
 144         Network1 nw1 = nw.augmentation(Network1.class);
 145
 146         allLinks = nw1.getLink().stream().sorted((l1, l2) -> l1.getSource().getSourceTp().toString().compareTo(l2
 147             .getSource().getSourceTp().toString())).collect(Collectors.toList());
 148         if (allNodes == null || allNodes.isEmpty()) {
 149             LOG.error("readMdSal: no nodes ");
 150             return false;
 151         }
 152         LOG.info("readMdSal: network nodes: {} nodes added", allNodes.size());
 153         LOG.debug("readMdSal: network nodes: {} nodes added", allNodes.toString());
 154
 155         if (allLinks == null || allLinks.isEmpty()) {
 156             LOG.error("readMdSal: no links ");
 157             return false;
 158         }
 159         LOG.info("readMdSal: network links: {} links added", allLinks.size());
 160         LOG.debug("readMdSal: network links: {} links added", allLinks.toString());
 161
 162         return true;
 163     }
 164
 165     private boolean analyzeNw() {
 166
 167         LOG.debug("analyzeNw: allNodes size {}, allLinks size {}", allNodes.size(), allLinks.size());
 168
 169         for (Node node : allNodes) {
 170             validateNode(node);
 171         }
 172         LOG.debug("analyzeNw: allPceNodes size {}", allPceNodes.size());
 173
 174         if (aendPceNode == null || zendPceNode == null) {
 175             LOG.error("analyzeNw: Error in reading nodes: A or Z do not present in the network");
 176             return false;
 177         }
 178
 179         for (Link link : allLinks) {
 180             validateLink(link);
 181         }
 182
 183         LOG.debug("analyzeNw: addLinks size {}, dropLinks size {}", addLinks.size(), dropLinks.size());
 184
 185         // debug prints
 186         LOG.debug("analyzeNw: azSrgs size = {}", azSrgs.size());
 187         for (NodeId srg : azSrgs) {
 188             LOG.debug("analyzeNw: A/Z Srgs SRG = {}", srg.getValue());
 189         }
 190         // debug prints
 191
 192         for (PceLink link : addLinks) {
 193             filteraddLinks(link);
 194         }
 195         for (PceLink link : dropLinks) {
 196             filterdropLinks(link);
 197         }
 198
 199         LOG.info("analyzeNw: allPceNodes size {}, allPceLinks size {}", allPceNodes.size(), allPceLinks.size());
 200
 201         if ((allPceNodes.size() == 0) || (allPceLinks.size() == 0)) {
 202             return false;
 203         }
 204
 205         LOG.debug("analyzeNw: allPceNodes {}", allPceNodes.toString());
 206         LOG.debug("analyzeNw: allPceLinks {}", allPceLinks.toString());
 207
 208         return true;
 209     }
 210
 211     private boolean filteraddLinks(PceLink pcelink) {
 212
 213         NodeId nodeId = pcelink.getSourceId();
 214
 215         if (azSrgs.contains(nodeId)) {
 216             allPceLinks.put(pcelink.getLinkId(), pcelink);
 217             allPceNodes.get(nodeId).addOutgoingLink(pcelink);
 218             LOG.debug("analyzeNw: Add_LINK added to source and to allPceLinks {}", pcelink.getLinkId().toString());
 219             return true;
 220         }
 221
 222         // remove the SRG from PceNodes, as it is not directly connected to A/Z
 223         allPceNodes.remove(nodeId);
 224         LOG.debug("analyzeNw: SRG removed {}", nodeId.getValue());
 225
 226         return false;
 227     }
 228
 229     private boolean filterdropLinks(PceLink pcelink) {
 230
 231         NodeId nodeId = pcelink.getDestId();
 232
 233         if (azSrgs.contains(nodeId)) {
 234             allPceLinks.put(pcelink.getLinkId(), pcelink);
 235             allPceNodes.get(nodeId).addOutgoingLink(pcelink);
 236             LOG.debug("analyzeNw: Drop_LINK added to dest and to allPceLinks {}", pcelink.getLinkId().toString());
 237             return true;
 238         }
 239
 240         // remove the SRG from PceNodes, as it is not directly connected to A/Z
 241         allPceNodes.remove(pcelink.getDestId());
 242         LOG.debug("analyzeNw: SRG removed {}", nodeId.getValue());
 243
 244         return false;
 245     }
 246
 247     private boolean validateLink(Link link) {
 248
 249         LOG.debug("validateLink: link {} ", link.toString());
 250
 251         if (linksToExclude.contains(link.getLinkId())) {
 252             LOG.info("validateLink: Link is ignored due opposite link problem - {}", link.getLinkId().getValue());
 253             return false;
 254         }
 255
 256         NodeId sourceId = link.getSource().getSourceNode();
 257         NodeId destId = link.getDestination().getDestNode();
 258         PceNode source = allPceNodes.get(sourceId);
 259         PceNode dest = allPceNodes.get(destId);
 260
 261         if (source == null) {
 262             LOG.debug("validateLink: Link is ignored due source node is rejected by node validation - {}",
 263                     link.getSource().getSourceNode().getValue());
 264             return false;
 265         }
 266         if (dest == null) {
 267             LOG.debug("validateLink: Link is ignored due dest node is rejected by node validation - {}",
 268                     link.getDestination().getDestNode().getValue());
 269             return false;
 270         }
 271
 272         PceLink pcelink = new PceLink(link, source, dest);
 273         if (!pcelink.isValid()) {
 274             dropOppositeLink(link);
 275             LOG.error(" validateLink: Link is ignored due errors in network data or in opposite link");
 276             return false;
 277         }
 278
 279         LinkId linkId = pcelink.getLinkId();
 280
 281         switch (validateLinkConstraints(pcelink)) {
 282             case HARD_EXCLUDE :
 283                 dropOppositeLink(link);
 284                 LOG.debug("validateLink: constraints : link is ignored == {}", linkId.getValue());
 285                 return false;
 286             default:
 287                 break;
 288         }
 289
 290         switch (pcelink.getlinkType()) {
 291             case ROADMTOROADM :
 292                 allPceLinks.put(linkId, pcelink);
 293                 source.addOutgoingLink(pcelink);
 294                 LOG.debug("validateLink: ROADMTOROADM-LINK added to allPceLinks {}", pcelink.toString());
 295                 break;
 296             case EXPRESSLINK :
 297                 allPceLinks.put(linkId, pcelink);
 298                 source.addOutgoingLink(pcelink);
 299                 LOG.debug("validateLink: EXPRESS-LINK added to allPceLinks {}", pcelink.toString());
 300                 break;
 301             case ADDLINK :
 302                 pcelink.setClient(source.getRdmSrgClient(pcelink.getSourceTP().toString(), true));
 303                 addLinks.add(pcelink);
 304                 LOG.debug("validateLink: ADD-LINK saved  {}", pcelink.toString());
 305                 break;
 306             case DROPLINK :
 307                 pcelink.setClient(dest.getRdmSrgClient(pcelink.getDestTP().toString(), false));
 308                 dropLinks.add(pcelink);
 309                 LOG.debug("validateLink: DROP-LINK saved  {}", pcelink.toString());
 310                 break;
 311             case XPONDERINPUT :
 312                 // store separately all SRG links directly
 313                 azSrgs.add(sourceId);
 314                 // connected to A/Z
 315                 if (!dest.checkTP(pcelink.getDestTP().toString())) {
 316                     LOG.debug("validateLink: XPONDER-INPUT is rejected as NW port is busy - {} ", pcelink.toString());
 317                     return false;
 318                 }
 319                 pcelink.setClient(dest.getClient(pcelink.getDestTP().toString()));
 320                 allPceLinks.put(linkId, pcelink);
 321                 source.addOutgoingLink(pcelink);
 322                 LOG.debug("validateLink: XPONDER-INPUT link added to allPceLinks {}", pcelink.toString());
 323                 break;
 324             // does it mean XPONDER==>>SRG ?
 325             case XPONDEROUTPUT :
 326                 // store separately all SRG links directly
 327                 azSrgs.add(destId);
 328                 // connected to A/Z
 329                 if (!source.checkTP(pcelink.getSourceTP().toString())) {
 330                     LOG.debug("validateLink: XPONDER-OUTPUT is rejected as NW port is busy - {} ", pcelink.toString());
 331                     return false;
 332                 }
 333                 pcelink.setClient(source.getClient(pcelink.getSourceTP().toString()));
 334                 allPceLinks.put(linkId, pcelink);
 335                 source.addOutgoingLink(pcelink);
 336                 LOG.debug("validateLink: XPONDER-OUTPUT link added to allPceLinks {}", pcelink.toString());
 337                 break;
 338             default:
 339                 LOG.warn("validateLink: link type is not supported {}", pcelink.toString());
 340
 341         }
 342
 343         return true;
 344     }
 345
 346     private boolean validateNode(Node node) {
 347         LOG.debug("validateNode: node {} ", node.toString());
 348
 349         // PceNode will be used in Graph algorithm
 350         Node1 node1 = node.augmentation(Node1.class);
 351         if (node1 == null) {
 352             LOG.error("getNodeType: no Node1 (type) Augmentation for node: [{}]. Node is ignored", node.getNodeId());
 353         }
 354         OpenroadmNodeType nodeType = node1.getNodeType();
 355
 356         PceNode pceNode = new PceNode(node,nodeType,node.getNodeId());
 357         pceNode.validateAZxponder(anodeId, znodeId);
 358         pceNode.initWLlist();
 359
 360         if (!pceNode.isValid()) {
 361             LOG.warn(" validateNode: Node is ignored");
 362             return false;
 363         }
 364
 365         switch (validateNodeConstraints(pceNode)) {
 366             case HARD_EXCLUDE :
 367                 return false;
 368
 369             default :
 370                 break;
 371         }
 372
 373         if (pceNode.getSupNodeIdPceNode().equals(this.anodeId)) {
 374             if (this.aendPceNode != null) {
 375                 LOG.debug("aendPceNode already gets: {}", this.aendPceNode);
 376             } else if (endPceNode(nodeType,pceNode.getNodeId(), pceNode)) {
 377                 this.aendPceNode = pceNode;
 378             }
 379             // returning false otherwise would break E2E test
 380         }
 381         if (pceNode.getSupNodeIdPceNode().equals(this.znodeId)) {
 382             if (this.zendPceNode != null) {
 383                 LOG.debug("zendPceNode already gets: {}", this.zendPceNode);
 384             } else if (endPceNode(nodeType,pceNode.getNodeId(), pceNode)) {
 385                 this.zendPceNode = pceNode;
 386             }
 387             // returning false otherwise would break E2E test
 388         }
 389
 390         allPceNodes.put(pceNode.getNodeId(), pceNode);
 391         LOG.debug("validateNode: node is saved {}", pceNode.getNodeId().getValue());
 392         return true;
 393     }
 394
 395     private ConstraintTypes validateNodeConstraints(PceNode pcenode) {
 396
 397         if (pceHardConstraints.getExcludeSupNodes().isEmpty() && pceHardConstraints.getExcludeCLLI().isEmpty()) {
 398             return ConstraintTypes.NONE;
 399         }
 400
 401         if (pceHardConstraints.getExcludeSupNodes().contains(pcenode.getSupNodeIdPceNode())) {
 402             LOG.info("validateNodeConstraints: {}", pcenode.getNodeId().getValue());
 403             return ConstraintTypes.HARD_EXCLUDE;
 404         }
 405         if (pceHardConstraints.getExcludeCLLI().contains(pcenode.getCLLI())) {
 406             LOG.info("validateNodeConstraints: {}", pcenode.getNodeId().getValue());
 407             return ConstraintTypes.HARD_EXCLUDE;
 408         }
 409
 410         return ConstraintTypes.NONE;
 411     }
 412
 413     private ConstraintTypes validateLinkConstraints(PceLink link) {
 414         if (pceHardConstraints.getExcludeSRLG().isEmpty()) {
 415             return ConstraintTypes.NONE;
 416         }
 417
 418         // for now SRLG is the only constraint for link
 419         if (link.getlinkType() != OpenroadmLinkType.ROADMTOROADM) {
 420             return ConstraintTypes.NONE;
 421         }
 422
 423         List<Long> constraints = new ArrayList<Long>(pceHardConstraints.getExcludeSRLG());
 424         constraints.retainAll(link.getsrlgList());
 425         if (!constraints.isEmpty()) {
 426             LOG.info("validateLinkConstraints: {}", link.getLinkId().getValue());
 427             return ConstraintTypes.HARD_EXCLUDE;
 428         }
 429
 430         return ConstraintTypes.NONE;
 431     }
 432
 433     private void dropOppositeLink(Link link) {
 434         LinkId opplink = MapUtils.extractOppositeLink(link);
 435
 436         PceLink oppPceLink = allPceLinks.get(opplink);
 437         if (oppPceLink != null) {
 438             allPceLinks.remove(oppPceLink);
 439         } else {
 440             linksToExclude.add(opplink);
 441         }
 442     }
 443
 444     private Boolean endPceNode(OpenroadmNodeType openroadmNodeType, NodeId nodeId, PceNode pceNode) {
 445         switch (openroadmNodeType) {
 446             case SRG :
 447                 pceNode.initSrgTps();
 448                 this.azSrgs.add(nodeId);
 449                 break;
 450             case XPONDER :
 451                 pceNode.initXndrTps();
 452                 break;
 453             default:
 454                 LOG.warn("endPceNode: Node {} is not SRG or XPONDER !", nodeId);
 455                 return false;
 456         }
 457
 458         if (!pceNode.isValid()) {
 459             LOG.error("validateNode : there are no availaible wavelengths in node {}", pceNode.getNodeId().getValue());
 460             return false;
 461         }
 462         return true;
 463     }
 464
 465     public PceNode getaendPceNode() {
 466         return aendPceNode;
 467     }
 468
 469     public PceNode getzendPceNode() {
 470         return zendPceNode;
 471     }
 472
 473     public Map<NodeId, PceNode> getAllPceNodes() {
 474         return this.allPceNodes;
 475     }
 476
 477     public Map<LinkId, PceLink> getAllPceLinks() {
 478         return this.allPceLinks;
 479     }
 480
 481     public PceResult getReturnStructure() {
 482         return returnStructure;
 483     }
 484
 485     private static void printNodesInfo(Map<NodeId, PceNode> allpcenodes) {
 486         Iterator<Map.Entry<NodeId, PceNode>> nodes = allpcenodes.entrySet().iterator();
 487         while (nodes.hasNext()) {
 488             PceNode pcenode = nodes.next().getValue();
 489             List<PceLink> links = pcenode.getOutgoingLinks();
 490             LOG.info("In printNodes in node {} : outgoing links {} ", pcenode.getNodeId().getValue(), links.toString());
 491         }
 492     }
 493
 494     /*private static void printLinksInfo(Map<LinkId, PceLink> allpcelinks) {
 495         Iterator<Map.Entry<LinkId, PceLink>> links = allpcelinks.entrySet().iterator();
 496         while (links.hasNext()) {
 497             LOG.info("In printLinksInfo link {} : ", links.next().getValue().toString());
 498         }
 499     }*/
 500
 501 }