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