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.model.SpectrumAssignment;
27 import org.opendaylight.transportpce.pce.networkanalyzer.PceNode;
28 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult;
29 import org.opendaylight.yang.gen.v1.http.org.openroadm.network.types.rev200529.OpenroadmLinkType;
30 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.NodeId;
31 import org.opendaylight.yangtools.yang.common.Uint16;
32 import org.slf4j.Logger;
33 import org.slf4j.LoggerFactory;
35 public class PostAlgoPathValidator {
37 private static final Logger LOG = LoggerFactory.getLogger(PostAlgoPathValidator.class);
39 private static final double MIN_OSNR_W100G = 17;
40 private static final double TRX_OSNR = 33;
41 private static final double ADD_OSNR = 30;
42 public static final Long CONST_OSNR = 1L;
43 public static final double SYS_MARGIN = 0;
46 value = "SF_SWITCH_FALLTHROUGH",
47 justification = "intentional fallthrough")
48 public PceResult checkPath(GraphPath<String, PceGraphEdge> path, Map<NodeId, PceNode> allPceNodes,
49 PceResult pceResult, PceConstraints pceHardConstraints, String serviceType) {
51 // check if the path is empty
52 if (path.getEdgeList().isEmpty()) {
53 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
57 int spectralWidthSlotNumber = GridConstant.SPECTRAL_WIDTH_SLOT_NUMBER_MAP
58 .getOrDefault(serviceType, GridConstant.NB_SLOTS_100G);
59 SpectrumAssignment spectrumAssignment = null;
60 //variable to deal with 1GE (Nb=1) and 10GE (Nb=10) cases
61 switch (serviceType) {
62 case StringConstants.SERVICE_TYPE_OTUC4:
63 case StringConstants.SERVICE_TYPE_400GE:
64 spectralWidthSlotNumber = GridConstant.SPECTRAL_WIDTH_SLOT_NUMBER_MAP
65 .getOrDefault(serviceType, GridConstant.NB_SLOTS_400G);
67 case StringConstants.SERVICE_TYPE_100GE_T:
68 case StringConstants.SERVICE_TYPE_OTU4:
69 spectrumAssignment = getSpectrumAssignment(path,
70 allPceNodes, spectralWidthSlotNumber);
71 pceResult.setServiceType(serviceType);
72 if (spectrumAssignment.getBeginIndex() == 0 && spectrumAssignment.getStopIndex() == 0) {
73 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
74 pceResult.setLocalCause(PceResult.LocalCause.NO_PATH_EXISTS);
77 if (spectrumAssignment.isFlexGrid()) {
78 LOG.info("Spectrum assignment flexgrid mode");
79 pceResult.setResultWavelength(GridConstant.IRRELEVANT_WAVELENGTH_NUMBER);
81 LOG.info("Spectrum assignment fixedgrid mode");
82 pceResult.setResultWavelength(
83 GridUtils.getWaveLengthIndexFromSpectrumAssigment(spectrumAssignment.getBeginIndex()));
85 pceResult.setMinFreq(GridUtils.getStartFrequencyFromIndex(spectrumAssignment.getBeginIndex()));
86 pceResult.setMaxFreq(GridUtils.getStopFrequencyFromIndex(spectrumAssignment.getStopIndex()));
87 LOG.info("In PostAlgoPathValidator: spectrum assignment found {} {}", spectrumAssignment, path);
90 if (!checkOSNR(path)) {
91 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
92 pceResult.setLocalCause(PceResult.LocalCause.OUT_OF_SPEC_OSNR);
96 // Check if MaxLatency is defined in the hard constraints
97 if ((pceHardConstraints.getMaxLatency() != -1)
98 && (!checkLatency(pceHardConstraints.getMaxLatency(), path))) {
99 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
100 pceResult.setLocalCause(PceResult.LocalCause.TOO_HIGH_LATENCY);
104 // Check if nodes are included in the hard constraints
105 if (!checkInclude(path, pceHardConstraints)) {
106 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
107 pceResult.setLocalCause(PceResult.LocalCause.HD_NODE_INCLUDE);
111 // TODO here other post algo validations can be added
112 // more data can be sent to PceGraph module via PceResult structure if required
114 pceResult.setRC(ResponseCodes.RESPONSE_OK);
115 pceResult.setLocalCause(PceResult.LocalCause.NONE);
117 case StringConstants.SERVICE_TYPE_100GE_M:
118 case StringConstants.SERVICE_TYPE_10GE:
119 tribSlotNb = StringConstants.SERVICE_TYPE_10GE.equals(serviceType) ? 8 : 20;
121 case StringConstants.SERVICE_TYPE_1GE:
122 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
123 pceResult.setServiceType(serviceType);
124 Map<String, Uint16> tribPort = chooseTribPort(path, allPceNodes);
125 Map<String, List<Uint16>> tribSlot = chooseTribSlot(path, allPceNodes, tribSlotNb);
127 if (tribPort != null && tribSlot != null) {
128 pceResult.setResultTribPort(tribPort);
129 pceResult.setResultTribSlot(tribSlot);
130 pceResult.setResultTribSlotNb(tribSlotNb);
131 pceResult.setRC(ResponseCodes.RESPONSE_OK);
132 LOG.info("In PostAlgoPathValidator: found TribPort {} - tribSlot {} - tribSlotNb {}",
133 tribPort, tribSlot, tribSlotNb);
136 case StringConstants.SERVICE_TYPE_ODU4:
137 case StringConstants.SERVICE_TYPE_ODUC4:
138 pceResult.setRC(ResponseCodes.RESPONSE_OK);
139 LOG.info("In PostAlgoPathValidator: ODU4/ODUC4 path found {}", path);
142 pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
143 LOG.warn("In PostAlgoPathValidator checkPath: unsupported serviceType {} found {}",
151 private boolean checkLatency(Long maxLatency, GraphPath<String, PceGraphEdge> path) {
154 for (PceGraphEdge edge : path.getEdgeList()) {
156 latency += edge.link().getLatency();
157 LOG.debug("- In checkLatency: latency of {} = {} units", edge.link().getLinkId().getValue(), latency);
158 } catch (NullPointerException e) {
159 LOG.warn("- In checkLatency: the link {} does not contain latency field",
160 edge.link().getLinkId().getValue());
163 return (latency < maxLatency);
166 // Check the inclusion if it is defined in the hard constraints
167 private boolean checkInclude(GraphPath<String, PceGraphEdge> path, PceConstraints pceHardConstraintsInput) {
168 List<ResourcePair> listToInclude = pceHardConstraintsInput.getListToInclude();
169 if (listToInclude.isEmpty()) {
173 List<PceGraphEdge> pathEdges = path.getEdgeList();
174 LOG.debug(" in checkInclude vertex list: [{}]", path.getVertexList());
176 List<String> listOfElementsSubNode = new ArrayList<>();
177 listOfElementsSubNode.add(pathEdges.get(0).link().getsourceNetworkSupNodeId());
178 listOfElementsSubNode.addAll(listOfElementsBuild(pathEdges, PceConstraints.ResourceType.NODE,
179 pceHardConstraintsInput));
181 List<String> listOfElementsCLLI = new ArrayList<>();
182 listOfElementsCLLI.add(pathEdges.get(0).link().getsourceCLLI());
183 listOfElementsCLLI.addAll(listOfElementsBuild(pathEdges, PceConstraints.ResourceType.CLLI,
184 pceHardConstraintsInput));
186 List<String> listOfElementsSRLG = new ArrayList<>();
187 // first link is XPONDEROUTPUT, no SRLG for it
188 listOfElementsSRLG.add("NONE");
189 listOfElementsSRLG.addAll(listOfElementsBuild(pathEdges, PceConstraints.ResourceType.SRLG,
190 pceHardConstraintsInput));
192 // validation: check each type for each element
193 for (ResourcePair next : listToInclude) {
195 switch (next.getType()) {
197 if (listOfElementsSubNode.contains(next.getName())) {
198 indx = listOfElementsSubNode.indexOf(next.getName());
202 if (listOfElementsSRLG.contains(next.getName())) {
203 indx = listOfElementsSRLG.indexOf(next.getName());
207 if (listOfElementsCLLI.contains(next.getName())) {
208 indx = listOfElementsCLLI.indexOf(next.getName());
212 LOG.warn(" in checkInclude vertex list unsupported resource type: [{}]", next.getType());
216 LOG.debug(" in checkInclude stopped : {} ", next.getName());
220 LOG.debug(" in checkInclude next found {} in {}", next.getName(), path.getVertexList());
222 listOfElementsSubNode.subList(0, indx).clear();
223 listOfElementsCLLI.subList(0, indx).clear();
224 listOfElementsSRLG.subList(0, indx).clear();
227 LOG.info(" in checkInclude passed : {} ", path.getVertexList());
231 private List<String> listOfElementsBuild(List<PceGraphEdge> pathEdges, PceConstraints.ResourceType type,
232 PceConstraints pceHardConstraints) {
234 List<String> listOfElements = new ArrayList<>();
235 for (PceGraphEdge link : pathEdges) {
238 listOfElements.add(link.link().getdestNetworkSupNodeId());
241 listOfElements.add(link.link().getdestCLLI());
244 if (link.link().getlinkType() != OpenroadmLinkType.ROADMTOROADM) {
245 listOfElements.add("NONE");
248 // srlg of link is List<Long>. But in this algo we need string representation of
250 // this should be any SRLG mentioned in include constraints if any of them if
252 boolean found = false;
253 for (Long srlg : link.link().getsrlgList()) {
254 String srlgStr = String.valueOf(srlg);
255 if (pceHardConstraints.getSRLGnames().contains(srlgStr)) {
256 listOfElements.add(srlgStr);
257 LOG.info("listOfElementsBuild. FOUND SRLG {} in link {}", srlgStr, link.link());
262 // there is no specific srlg to include. thus add to list just the first one
263 listOfElements.add("NONE");
267 LOG.debug("listOfElementsBuild unsupported resource type");
270 return listOfElements;
273 private Map<String, Uint16> chooseTribPort(GraphPath<String,
274 PceGraphEdge> path, Map<NodeId, PceNode> allPceNodes) {
275 LOG.info("In choosetribPort: edgeList = {} ", path.getEdgeList());
276 Map<String, Uint16> tribPortMap = new HashMap<>();
278 for (PceGraphEdge edge : path.getEdgeList()) {
279 NodeId linkSrcNode = edge.link().getSourceId();
280 String linkSrcTp = edge.link().getSourceTP().toString();
281 NodeId linkDestNode = edge.link().getDestId();
282 String linkDestTp = edge.link().getDestTP().toString();
283 PceNode pceOtnNodeSrc = allPceNodes.get(linkSrcNode);
284 PceNode pceOtnNodeDest = allPceNodes.get(linkDestNode);
285 List<Uint16> srcTpnPool = pceOtnNodeSrc.getAvailableTribPorts().get(linkSrcTp);
286 List<Uint16> destTpnPool = pceOtnNodeDest.getAvailableTribPorts().get(linkDestTp);
287 List<Uint16> commonEdgeTpnPool = new ArrayList<>();
288 for (Uint16 integer : srcTpnPool) {
289 if (destTpnPool.contains(integer)) {
290 commonEdgeTpnPool.add(integer);
293 Collections.sort(commonEdgeTpnPool);
294 if (!commonEdgeTpnPool.isEmpty()) {
295 tribPortMap.put(edge.link().getLinkId().getValue(), commonEdgeTpnPool.get(0));
298 tribPortMap.forEach((k,v) -> LOG.info("TribPortMap : k = {}, v = {}", k, v));
302 private Map<String, List<Uint16>> chooseTribSlot(GraphPath<String,
303 PceGraphEdge> path, Map<NodeId, PceNode> allPceNodes, int nbSlot) {
304 LOG.info("In choosetribSlot: edgeList = {} ", path.getEdgeList());
305 Map<String, List<Uint16>> tribSlotMap = new HashMap<>();
307 for (PceGraphEdge edge : path.getEdgeList()) {
308 NodeId linkSrcNode = edge.link().getSourceId();
309 String linkSrcTp = edge.link().getSourceTP().toString();
310 NodeId linkDestNode = edge.link().getDestId();
311 String linkDestTp = edge.link().getDestTP().toString();
312 PceNode pceOtnNodeSrc = allPceNodes.get(linkSrcNode);
313 PceNode pceOtnNodeDest = allPceNodes.get(linkDestNode);
314 List<Uint16> srcTsPool = pceOtnNodeSrc.getAvailableTribSlots().get(linkSrcTp);
315 List<Uint16> destTsPool = pceOtnNodeDest.getAvailableTribSlots().get(linkDestTp);
316 List<Uint16> commonEdgeTsPool = new ArrayList<>();
317 List<Uint16> tribSlotList = new ArrayList<>();
318 for (Uint16 integer : srcTsPool) {
319 if (destTsPool.contains(integer)) {
320 commonEdgeTsPool.add(integer);
323 Collections.sort(commonEdgeTsPool);
324 boolean discontinue = true;
326 while (discontinue && (commonEdgeTsPool.size() - index >= nbSlot)) {
328 Integer val = commonEdgeTsPool.get(index).toJava();
329 for (int i = 0; i < nbSlot; i++) {
330 if (commonEdgeTsPool.get(index + i).equals(Uint16.valueOf(val + i))) {
331 tribSlotList.add(commonEdgeTsPool.get(index + i));
334 tribSlotList.clear();
340 tribSlotMap.put(edge.link().getLinkId().getValue(), tribSlotList);
342 tribSlotMap.forEach((k,v) -> LOG.info("TribSlotMap : k = {}, v = {}", k, v));
346 // Check the path OSNR
347 private boolean checkOSNR(GraphPath<String, PceGraphEdge> path) {
350 LOG.info("- In checkOSNR: OSNR of the transmitter = {} dB", TRX_OSNR);
351 LOG.info("- In checkOSNR: add-path incremental OSNR = {} dB", ADD_OSNR);
352 double inverseLocalOsnr = getInverseOsnrLinkLu(TRX_OSNR) + getInverseOsnrLinkLu(ADD_OSNR);
353 for (PceGraphEdge edge : path.getEdgeList()) {
354 if (edge.link().getlinkType() == OpenroadmLinkType.ROADMTOROADM) {
356 linkOsnrDb = edge.link().getosnr();
357 LOG.info("- In checkOSNR: OSNR of {} = {} dB", edge.link().getLinkId().getValue(), linkOsnrDb);
358 // 1 over the local OSNR, in linear units
359 inverseLocalOsnr += getInverseOsnrLinkLu(linkOsnrDb);
363 osnrDb = getOsnrDb(1 / inverseLocalOsnr);
364 } catch (ArithmeticException e) {
365 LOG.debug("In checkOSNR: OSNR is equal to 0 and the number of links is: {}", path.getEdgeList().size());
368 LOG.info("In checkOSNR: OSNR of the path is {} dB", osnrDb);
369 return ((osnrDb + SYS_MARGIN) > MIN_OSNR_W100G);
372 private double getOsnrDb(double osnrLu) {
374 osnrDb = 10 * Math.log10(osnrLu);
378 private double getInverseOsnrLinkLu(double linkOsnrDb) {
379 // 1 over the link OSNR, in linear units
381 linkOsnrLu = Math.pow(10, (linkOsnrDb / 10.0));
382 LOG.debug("In retrieveosnr: the inverse of link osnr is {} (Linear Unit)", linkOsnrLu);
383 return (CONST_OSNR / linkOsnrLu);
387 * Get spectrum assignment for path.
389 * @param path the path for which we get spectrum assignment.
390 * @param allPceNodes all optical nodes.
391 * @param spectralWidthSlotNumber number of slot for spectral width. Depends on
393 * @return a spectrum assignment object which contains begin and end index. If
394 * no spectrum assignment found, beginIndex = stopIndex = 0
396 private SpectrumAssignment getSpectrumAssignment(GraphPath<String, PceGraphEdge> path,
397 Map<NodeId, PceNode> allPceNodes, int spectralWidthSlotNumber) {
398 byte[] freqMap = new byte[GridConstant.NB_OCTECTS];
399 Arrays.fill(freqMap, (byte) GridConstant.AVAILABLE_SLOT_VALUE);
400 BitSet result = BitSet.valueOf(freqMap);
401 boolean isFlexGrid = true;
402 LOG.info("Processing path {} with length {}", path, path.getLength());
403 BitSet pceNodeFreqMap;
404 for (PceGraphEdge edge : path.getEdgeList()) {
405 LOG.info("Processing source {} ", edge.link().getSourceId());
406 if (allPceNodes.containsKey(edge.link().getSourceId())) {
407 PceNode pceNode = allPceNodes.get(edge.link().getSourceId());
408 LOG.info("Processing PCE node {}", pceNode);
409 if (StringConstants.OPENROADM_DEVICE_VERSION_1_2_1.equals(pceNode.getVersion())) {
410 LOG.info("Node {}: version is {} and slot width granularity is {} -> fixed grid mode",
411 pceNode.getNodeId(), pceNode.getVersion(), pceNode.getSlotWidthGranularity());
414 if ((pceNode.getSlotWidthGranularity().equals(GridConstant.SLOT_WIDTH_50))
415 && (pceNode.getCentralFreqGranularity().equals(GridConstant.SLOT_WIDTH_50))) {
416 LOG.info("Node {}: version is {} with slot width granularity {} and central "
417 + "frequency granularity is {} -> fixed grid mode",
418 pceNode.getNodeId(), pceNode.getVersion(), pceNode.getSlotWidthGranularity(),
419 pceNode.getCentralFreqGranularity());
422 pceNodeFreqMap = pceNode.getBitSetData();
423 LOG.debug("Pce node bitset {}", pceNodeFreqMap);
424 if (pceNodeFreqMap != null) {
425 result.and(pceNodeFreqMap);
426 LOG.debug("intermediate bitset {}", result);
430 LOG.debug("Bitset result {}", result);
431 return computeBestSpectrumAssignment(result, spectralWidthSlotNumber, isFlexGrid);
435 * Compute spectrum assignment from spectrum occupation for spectral width.
437 * @param spectrumOccupation the spectrum occupation BitSet.
438 * @param spectralWidthSlotNumber the nb slots for spectral width.
439 * @param isFlexGrid true if flexible grid, false otherwise.
440 * @return a spectrum assignment object which contains begin and stop index. If
441 * no spectrum assignment found, beginIndex = stopIndex = 0
443 private SpectrumAssignment computeBestSpectrumAssignment(BitSet spectrumOccupation, int spectralWidthSlotNumber,
444 boolean isFlexGrid) {
445 SpectrumAssignment spectrumAssignment = new SpectrumAssignment(0, 0);
446 spectrumAssignment.setFlexGrid(isFlexGrid);
447 BitSet referenceBitSet = new BitSet(spectralWidthSlotNumber);
448 referenceBitSet.set(0, spectralWidthSlotNumber);
451 nbSteps = spectralWidthSlotNumber;
453 //higher is the frequency, smallest is the wavelength number
454 //in operational, the allocation is done through wavelength starting from the smallest
455 //so we have to loop from the last element of the spectrum occupation
456 for (int i = spectrumOccupation.size(); i >= spectralWidthSlotNumber; i -= nbSteps) {
457 if (spectrumOccupation.get(i - spectralWidthSlotNumber, i).equals(referenceBitSet)) {
458 spectrumAssignment.setBeginIndex(i - spectralWidthSlotNumber);
459 spectrumAssignment.setStopIndex(i - 1);
463 return spectrumAssignment;