2 * Copyright © 2017 AT&T, Inc. and others. All rights reserved.
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
9 package org.opendaylight.transportpce.pce.graph;
11 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
12 import java.util.ArrayList;
13 import java.util.Arrays;
14 import java.util.BitSet;
15 import java.util.Collections;
16 import java.util.HashMap;
17 import java.util.List;
19 import org.jgrapht.GraphPath;
20 import org.opendaylight.transportpce.common.ResponseCodes;
21 import org.opendaylight.transportpce.common.StringConstants;
22 import org.opendaylight.transportpce.common.fixedflex.GridConstant;
23 import org.opendaylight.transportpce.common.fixedflex.GridUtils;
24 import org.opendaylight.transportpce.pce.constraints.PceConstraints;
25 import org.opendaylight.transportpce.pce.constraints.PceConstraints.ResourcePair;
26 import org.opendaylight.transportpce.pce.networkanalyzer.PceNode;
27 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult;
28 import org.opendaylight.yang.gen.v1.http.org.opendaylight.transportpce.pce.rev210701.SpectrumAssignment;
29 import org.opendaylight.yang.gen.v1.http.org.opendaylight.transportpce.pce.rev210701.SpectrumAssignmentBuilder;
30 import org.opendaylight.yang.gen.v1.http.org.openroadm.network.types.rev200529.OpenroadmLinkType;
31 import org.opendaylight.yang.gen.v1.http.org.openroadm.otn.common.types.rev181130.OpucnTribSlotDef;
32 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.NodeId;
33 import org.opendaylight.yangtools.yang.common.Uint16;
34 import org.slf4j.Logger;
35 import org.slf4j.LoggerFactory;
37 public class PostAlgoPathValidator {
39 private static final Logger LOG = LoggerFactory.getLogger(PostAlgoPathValidator.class);
41 private static final double MIN_OSNR_W100G = 17;
42 private static final double TRX_OSNR = 33;
43 private static final double ADD_OSNR = 30;
44 public static final Long CONST_OSNR = 1L;
45 public static final double SYS_MARGIN = 0;
48 value = "SF_SWITCH_FALLTHROUGH",
49 justification = "intentional fallthrough")
50 public PceResult checkPath(GraphPath<String, PceGraphEdge> path, Map<NodeId, PceNode> allPceNodes,
51 PceResult pceResult, PceConstraints pceHardConstraints, String serviceType) {
53 // check if the path is empty
54 if (path.getEdgeList().isEmpty()) {
55 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
59 int spectralWidthSlotNumber = GridConstant.SPECTRAL_WIDTH_SLOT_NUMBER_MAP
60 .getOrDefault(serviceType, GridConstant.NB_SLOTS_100G);
61 SpectrumAssignment spectrumAssignment = null;
62 //variable to deal with 1GE (Nb=1) and 10GE (Nb=10) cases
63 switch (serviceType) {
64 case StringConstants.SERVICE_TYPE_OTUC4:
65 case StringConstants.SERVICE_TYPE_400GE:
66 spectralWidthSlotNumber = GridConstant.SPECTRAL_WIDTH_SLOT_NUMBER_MAP
67 .getOrDefault(serviceType, GridConstant.NB_SLOTS_400G);
69 case StringConstants.SERVICE_TYPE_100GE_T:
70 case StringConstants.SERVICE_TYPE_OTU4:
71 spectrumAssignment = getSpectrumAssignment(path, allPceNodes, spectralWidthSlotNumber);
72 pceResult.setServiceType(serviceType);
73 if (spectrumAssignment.getBeginIndex().equals(Uint16.valueOf(0))
74 && spectrumAssignment.getStopIndex().equals(Uint16.valueOf(0))) {
75 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
76 pceResult.setLocalCause(PceResult.LocalCause.NO_PATH_EXISTS);
79 if (spectrumAssignment.getFlexGrid()) {
80 LOG.info("Spectrum assignment flexgrid mode");
81 pceResult.setResultWavelength(GridConstant.IRRELEVANT_WAVELENGTH_NUMBER);
83 LOG.info("Spectrum assignment fixedgrid mode");
84 pceResult.setResultWavelength(
85 GridUtils.getWaveLengthIndexFromSpectrumAssigment(spectrumAssignment.getBeginIndex()
88 pceResult.setMinFreq(GridUtils.getStartFrequencyFromIndex(spectrumAssignment.getBeginIndex().toJava()));
89 pceResult.setMaxFreq(GridUtils.getStopFrequencyFromIndex(spectrumAssignment.getStopIndex().toJava()));
90 LOG.info("In PostAlgoPathValidator: spectrum assignment found {} {}", spectrumAssignment, path);
93 if (!checkOSNR(path)) {
94 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
95 pceResult.setLocalCause(PceResult.LocalCause.OUT_OF_SPEC_OSNR);
99 // Check if MaxLatency is defined in the hard constraints
100 if ((pceHardConstraints.getMaxLatency() != -1)
101 && (!checkLatency(pceHardConstraints.getMaxLatency(), path))) {
102 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
103 pceResult.setLocalCause(PceResult.LocalCause.TOO_HIGH_LATENCY);
107 // Check if nodes are included in the hard constraints
108 if (!checkInclude(path, pceHardConstraints)) {
109 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
110 pceResult.setLocalCause(PceResult.LocalCause.HD_NODE_INCLUDE);
114 // TODO here other post algo validations can be added
115 // more data can be sent to PceGraph module via PceResult structure if required
117 pceResult.setRC(ResponseCodes.RESPONSE_OK);
118 pceResult.setLocalCause(PceResult.LocalCause.NONE);
120 case StringConstants.SERVICE_TYPE_100GE_M:
121 case StringConstants.SERVICE_TYPE_10GE:
122 case StringConstants.SERVICE_TYPE_1GE:
123 if (StringConstants.SERVICE_TYPE_100GE_M.equals(serviceType)) {
125 } else if (StringConstants.SERVICE_TYPE_10GE.equals(serviceType)) {
127 } else if (StringConstants.SERVICE_TYPE_1GE.equals(serviceType)) {
130 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
131 LOG.warn("In PostAlgoPathValidator checkPath: unsupported serviceType {} found {}",
135 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
136 pceResult.setServiceType(serviceType);
137 Map<String, List<Uint16>> tribSlot = chooseTribSlot(path, allPceNodes, tribSlotNb);
138 Map<String, Uint16> tribPort = chooseTribPort(path, allPceNodes, tribSlot, tribSlotNb);
139 List<OpucnTribSlotDef> resultTribPortTribSlot = getMinMaxTpTs(tribPort, tribSlot);
141 if (resultTribPortTribSlot.get(0) != null && resultTribPortTribSlot.get(1) != null) {
142 pceResult.setResultTribPortTribSlot(resultTribPortTribSlot);
143 pceResult.setRC(ResponseCodes.RESPONSE_OK);
144 LOG.info("In PostAlgoPathValidator: found TribPort {} - tribSlot {} - tribSlotNb {}",
145 tribPort, tribSlot, tribSlotNb);
148 case StringConstants.SERVICE_TYPE_ODU4:
149 case StringConstants.SERVICE_TYPE_ODUC4:
150 pceResult.setRC(ResponseCodes.RESPONSE_OK);
151 LOG.info("In PostAlgoPathValidator: ODU4/ODUC4 path found {}", path);
154 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
155 LOG.warn("In PostAlgoPathValidator checkPath: unsupported serviceType {} found {}",
163 private boolean checkLatency(Long maxLatency, GraphPath<String, PceGraphEdge> path) {
166 for (PceGraphEdge edge : path.getEdgeList()) {
168 latency += edge.link().getLatency();
169 LOG.debug("- In checkLatency: latency of {} = {} units", edge.link().getLinkId().getValue(), latency);
170 } catch (NullPointerException e) {
171 LOG.warn("- In checkLatency: the link {} does not contain latency field",
172 edge.link().getLinkId().getValue());
175 return (latency < maxLatency);
178 // Check the inclusion if it is defined in the hard constraints
179 private boolean checkInclude(GraphPath<String, PceGraphEdge> path, PceConstraints pceHardConstraintsInput) {
180 List<ResourcePair> listToInclude = pceHardConstraintsInput.getListToInclude();
181 if (listToInclude.isEmpty()) {
185 List<PceGraphEdge> pathEdges = path.getEdgeList();
186 LOG.debug(" in checkInclude vertex list: [{}]", path.getVertexList());
188 List<String> listOfElementsSubNode = new ArrayList<>();
189 listOfElementsSubNode.add(pathEdges.get(0).link().getsourceNetworkSupNodeId());
190 listOfElementsSubNode.addAll(listOfElementsBuild(pathEdges, PceConstraints.ResourceType.NODE,
191 pceHardConstraintsInput));
193 List<String> listOfElementsCLLI = new ArrayList<>();
194 listOfElementsCLLI.add(pathEdges.get(0).link().getsourceCLLI());
195 listOfElementsCLLI.addAll(listOfElementsBuild(pathEdges, PceConstraints.ResourceType.CLLI,
196 pceHardConstraintsInput));
198 List<String> listOfElementsSRLG = new ArrayList<>();
199 // first link is XPONDEROUTPUT, no SRLG for it
200 listOfElementsSRLG.add("NONE");
201 listOfElementsSRLG.addAll(listOfElementsBuild(pathEdges, PceConstraints.ResourceType.SRLG,
202 pceHardConstraintsInput));
204 // validation: check each type for each element
205 for (ResourcePair next : listToInclude) {
207 switch (next.getType()) {
209 if (listOfElementsSubNode.contains(next.getName())) {
210 indx = listOfElementsSubNode.indexOf(next.getName());
214 if (listOfElementsSRLG.contains(next.getName())) {
215 indx = listOfElementsSRLG.indexOf(next.getName());
219 if (listOfElementsCLLI.contains(next.getName())) {
220 indx = listOfElementsCLLI.indexOf(next.getName());
224 LOG.warn(" in checkInclude vertex list unsupported resource type: [{}]", next.getType());
228 LOG.debug(" in checkInclude stopped : {} ", next.getName());
232 LOG.debug(" in checkInclude next found {} in {}", next.getName(), path.getVertexList());
234 listOfElementsSubNode.subList(0, indx).clear();
235 listOfElementsCLLI.subList(0, indx).clear();
236 listOfElementsSRLG.subList(0, indx).clear();
239 LOG.info(" in checkInclude passed : {} ", path.getVertexList());
243 private List<String> listOfElementsBuild(List<PceGraphEdge> pathEdges, PceConstraints.ResourceType type,
244 PceConstraints pceHardConstraints) {
246 List<String> listOfElements = new ArrayList<>();
247 for (PceGraphEdge link : pathEdges) {
250 listOfElements.add(link.link().getdestNetworkSupNodeId());
253 listOfElements.add(link.link().getdestCLLI());
256 if (link.link().getlinkType() != OpenroadmLinkType.ROADMTOROADM) {
257 listOfElements.add("NONE");
260 // srlg of link is List<Long>. But in this algo we need string representation of
262 // this should be any SRLG mentioned in include constraints if any of them if
264 boolean found = false;
265 for (Long srlg : link.link().getsrlgList()) {
266 String srlgStr = String.valueOf(srlg);
267 if (pceHardConstraints.getSRLGnames().contains(srlgStr)) {
268 listOfElements.add(srlgStr);
269 LOG.info("listOfElementsBuild. FOUND SRLG {} in link {}", srlgStr, link.link());
274 // there is no specific srlg to include. thus add to list just the first one
275 listOfElements.add("NONE");
279 LOG.debug("listOfElementsBuild unsupported resource type");
282 return listOfElements;
285 private Map<String, Uint16> chooseTribPort(GraphPath<String,
286 PceGraphEdge> path, Map<NodeId, PceNode> allPceNodes, Map<String, List<Uint16>> tribSlotMap, int nbSlot) {
287 LOG.info("In choosetribPort: edgeList = {} ", path.getEdgeList());
288 Map<String, Uint16> tribPortMap = new HashMap<>();
290 for (PceGraphEdge edge : path.getEdgeList()) {
291 NodeId linkSrcNode = edge.link().getSourceId();
292 String linkSrcTp = edge.link().getSourceTP().toString();
293 NodeId linkDestNode = edge.link().getDestId();
294 String linkDestTp = edge.link().getDestTP().toString();
295 PceNode pceOtnNodeSrc = allPceNodes.get(linkSrcNode);
296 PceNode pceOtnNodeDest = allPceNodes.get(linkDestNode);
297 List<Uint16> srcTpnPool = pceOtnNodeSrc.getAvailableTribPorts().get(linkSrcTp);
298 List<Uint16> destTpnPool = pceOtnNodeDest.getAvailableTribPorts().get(linkDestTp);
299 List<Uint16> commonEdgeTpnPool = new ArrayList<>();
300 for (Uint16 srcTpn : srcTpnPool) {
301 if (destTpnPool.contains(srcTpn)) {
302 commonEdgeTpnPool.add(srcTpn);
305 Collections.sort(commonEdgeTpnPool);
306 if (!commonEdgeTpnPool.isEmpty()) {
307 Integer startTribSlot = tribSlotMap.values().stream().findFirst().get().get(0).toJava();
308 Integer tribPort = (int) Math.ceil((double)startTribSlot / nbSlot);
309 for (Uint16 commonTribPort : commonEdgeTpnPool) {
310 if (tribPort.equals(commonTribPort.toJava())) {
311 tribPortMap.put(edge.link().getLinkId().getValue(), commonTribPort);
316 tribPortMap.forEach((k,v) -> LOG.info("TribPortMap : k = {}, v = {}", k, v));
320 private Map<String, List<Uint16>> chooseTribSlot(GraphPath<String,
321 PceGraphEdge> path, Map<NodeId, PceNode> allPceNodes, int nbSlot) {
322 LOG.info("In choosetribSlot: edgeList = {} ", path.getEdgeList());
323 Map<String, List<Uint16>> tribSlotMap = new HashMap<>();
325 for (PceGraphEdge edge : path.getEdgeList()) {
326 NodeId linkSrcNode = edge.link().getSourceId();
327 String linkSrcTp = edge.link().getSourceTP().toString();
328 NodeId linkDestNode = edge.link().getDestId();
329 String linkDestTp = edge.link().getDestTP().toString();
330 PceNode pceOtnNodeSrc = allPceNodes.get(linkSrcNode);
331 PceNode pceOtnNodeDest = allPceNodes.get(linkDestNode);
332 List<Uint16> srcTsPool = pceOtnNodeSrc.getAvailableTribSlots().get(linkSrcTp);
333 List<Uint16> destTsPool = pceOtnNodeDest.getAvailableTribSlots().get(linkDestTp);
334 List<Uint16> commonEdgeTsPoolList = new ArrayList<>();
335 List<Uint16> tribSlotList = new ArrayList<>();
336 for (Uint16 integer : srcTsPool) {
337 if (destTsPool.contains(integer)) {
338 commonEdgeTsPoolList.add(integer);
341 Collections.sort(commonEdgeTsPoolList);
342 List<Uint16> commonGoodStartEdgeTsPoolList = new ArrayList<>();
343 for (Uint16 startEdgeTsPool : commonEdgeTsPoolList) {
344 if (Integer.valueOf(1).equals(startEdgeTsPool.toJava() % nbSlot)) {
345 commonGoodStartEdgeTsPoolList.add(startEdgeTsPool);
346 } else if (nbSlot == 1) {
347 commonGoodStartEdgeTsPoolList.add(startEdgeTsPool);
350 Collections.sort(commonGoodStartEdgeTsPoolList);
351 boolean goodTsList = false;
352 for (Uint16 goodStartTsPool : commonGoodStartEdgeTsPoolList) {
353 int goodStartIndex = commonEdgeTsPoolList.indexOf(Uint16.valueOf(goodStartTsPool.intValue()));
354 if (!goodTsList && commonEdgeTsPoolList.size() - goodStartIndex >= nbSlot) {
355 for (int i = 0; i < nbSlot; i++) {
356 if (commonEdgeTsPoolList.get(goodStartIndex + i)
357 .equals(Uint16.valueOf(goodStartTsPool.toJava() + i))) {
358 tribSlotList.add(commonEdgeTsPoolList.get(goodStartIndex + i));
362 tribSlotList.clear();
368 tribSlotMap.put(edge.link().getLinkId().getValue(), tribSlotList);
370 tribSlotMap.forEach((k,v) -> LOG.info("TribSlotMap : k = {}, v = {}", k, v));
374 private List<OpucnTribSlotDef> getMinMaxTpTs(Map<String, Uint16> tribPort, Map<String, List<Uint16>> tribSlot) {
375 String tribport = tribPort.values().toArray()[0].toString();
376 @SuppressWarnings("unchecked")
377 List<Uint16> tsList = (List<Uint16>) tribSlot.values().toArray()[0];
378 OpucnTribSlotDef minOpucnTs = OpucnTribSlotDef
379 .getDefaultInstance(String.join(".", tribport, tsList.get(0).toString()));
380 OpucnTribSlotDef maxOpucnTs = OpucnTribSlotDef
381 .getDefaultInstance(String.join(".", tribport, tsList.get(tsList.size() - 1).toString()));
382 List<OpucnTribSlotDef> minmaxTpTsList = new ArrayList<>();
383 minmaxTpTsList.add(minOpucnTs);
384 minmaxTpTsList.add(maxOpucnTs);
385 return minmaxTpTsList;
388 // Check the path OSNR
389 private boolean checkOSNR(GraphPath<String, PceGraphEdge> path) {
392 LOG.info("- In checkOSNR: OSNR of the transmitter = {} dB", TRX_OSNR);
393 LOG.info("- In checkOSNR: add-path incremental OSNR = {} dB", ADD_OSNR);
394 double inverseLocalOsnr = getInverseOsnrLinkLu(TRX_OSNR) + getInverseOsnrLinkLu(ADD_OSNR);
395 for (PceGraphEdge edge : path.getEdgeList()) {
396 if (edge.link().getlinkType() == OpenroadmLinkType.ROADMTOROADM) {
398 linkOsnrDb = edge.link().getosnr();
399 LOG.info("- In checkOSNR: OSNR of {} = {} dB", edge.link().getLinkId().getValue(), linkOsnrDb);
400 // 1 over the local OSNR, in linear units
401 inverseLocalOsnr += getInverseOsnrLinkLu(linkOsnrDb);
405 osnrDb = getOsnrDb(1 / inverseLocalOsnr);
406 } catch (ArithmeticException e) {
407 LOG.debug("In checkOSNR: OSNR is equal to 0 and the number of links is: {}", path.getEdgeList().size());
410 LOG.info("In checkOSNR: OSNR of the path is {} dB", osnrDb);
411 return ((osnrDb + SYS_MARGIN) > MIN_OSNR_W100G);
414 private double getOsnrDb(double osnrLu) {
416 osnrDb = 10 * Math.log10(osnrLu);
420 private double getInverseOsnrLinkLu(double linkOsnrDb) {
421 // 1 over the link OSNR, in linear units
423 linkOsnrLu = Math.pow(10, (linkOsnrDb / 10.0));
424 LOG.debug("In retrieveosnr: the inverse of link osnr is {} (Linear Unit)", linkOsnrLu);
425 return (CONST_OSNR / linkOsnrLu);
429 * Get spectrum assignment for path.
431 * @param path the path for which we get spectrum assignment.
432 * @param allPceNodes all optical nodes.
433 * @param spectralWidthSlotNumber number of slot for spectral width. Depends on
435 * @return a spectrum assignment object which contains begin and end index. If
436 * no spectrum assignment found, beginIndex = stopIndex = 0
438 private SpectrumAssignment getSpectrumAssignment(GraphPath<String, PceGraphEdge> path,
439 Map<NodeId, PceNode> allPceNodes, int spectralWidthSlotNumber) {
440 byte[] freqMap = new byte[GridConstant.NB_OCTECTS];
441 Arrays.fill(freqMap, (byte) GridConstant.AVAILABLE_SLOT_VALUE);
442 BitSet result = BitSet.valueOf(freqMap);
443 boolean isFlexGrid = true;
444 LOG.info("Processing path {} with length {}", path, path.getLength());
445 BitSet pceNodeFreqMap;
446 for (PceGraphEdge edge : path.getEdgeList()) {
447 LOG.info("Processing source {} ", edge.link().getSourceId());
448 if (allPceNodes.containsKey(edge.link().getSourceId())) {
449 PceNode pceNode = allPceNodes.get(edge.link().getSourceId());
450 LOG.info("Processing PCE node {}", pceNode);
451 if (StringConstants.OPENROADM_DEVICE_VERSION_1_2_1.equals(pceNode.getVersion())) {
452 LOG.info("Node {}: version is {} and slot width granularity is {} -> fixed grid mode",
453 pceNode.getNodeId(), pceNode.getVersion(), pceNode.getSlotWidthGranularity());
456 if ((pceNode.getSlotWidthGranularity().equals(GridConstant.SLOT_WIDTH_50))
457 && (pceNode.getCentralFreqGranularity().equals(GridConstant.SLOT_WIDTH_50))) {
458 LOG.info("Node {}: version is {} with slot width granularity {} and central "
459 + "frequency granularity is {} -> fixed grid mode",
460 pceNode.getNodeId(), pceNode.getVersion(), pceNode.getSlotWidthGranularity(),
461 pceNode.getCentralFreqGranularity());
464 pceNodeFreqMap = pceNode.getBitSetData();
465 LOG.debug("Pce node bitset {}", pceNodeFreqMap);
466 if (pceNodeFreqMap != null) {
467 result.and(pceNodeFreqMap);
468 LOG.debug("intermediate bitset {}", result);
472 LOG.debug("Bitset result {}", result);
473 return computeBestSpectrumAssignment(result, spectralWidthSlotNumber, isFlexGrid);
477 * Compute spectrum assignment from spectrum occupation for spectral width.
479 * @param spectrumOccupation the spectrum occupation BitSet.
480 * @param spectralWidthSlotNumber the nb slots for spectral width.
481 * @param isFlexGrid true if flexible grid, false otherwise.
482 * @return a spectrum assignment object which contains begin and stop index. If
483 * no spectrum assignment found, beginIndex = stopIndex = 0
485 private SpectrumAssignment computeBestSpectrumAssignment(BitSet spectrumOccupation, int spectralWidthSlotNumber,
486 boolean isFlexGrid) {
487 SpectrumAssignmentBuilder spectrumAssignmentBldr = new SpectrumAssignmentBuilder()
488 .setBeginIndex(Uint16.valueOf(0))
489 .setStopIndex(Uint16.valueOf(0))
490 .setFlexGrid(isFlexGrid);
491 BitSet referenceBitSet = new BitSet(spectralWidthSlotNumber);
492 referenceBitSet.set(0, spectralWidthSlotNumber);
495 nbSteps = spectralWidthSlotNumber;
497 //higher is the frequency, smallest is the wavelength number
498 //in operational, the allocation is done through wavelength starting from the smallest
499 //so we have to loop from the last element of the spectrum occupation
500 for (int i = spectrumOccupation.size(); i >= spectralWidthSlotNumber; i -= nbSteps) {
501 if (spectrumOccupation.get(i - spectralWidthSlotNumber, i).equals(referenceBitSet)) {
502 spectrumAssignmentBldr.setBeginIndex(Uint16.valueOf(i - spectralWidthSlotNumber));
503 spectrumAssignmentBldr.setStopIndex(Uint16.valueOf(i - 1));
507 return spectrumAssignmentBldr.build();