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