9f876f471d34a2a92b1cf48b05a97d56c99375d8
[transportpce.git] / pce / src / main / java / org / opendaylight / transportpce / pce / graph / PceGraph.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 java.util.ArrayList;
12 import java.util.HashMap;
13 import java.util.Iterator;
14 import java.util.List;
15 import java.util.Map;
16 import org.jgrapht.GraphPath;
17 import org.jgrapht.alg.shortestpath.KShortestSimplePaths;
18 import org.jgrapht.alg.shortestpath.PathValidator;
19 import org.jgrapht.graph.DefaultDirectedWeightedGraph;
20 import org.opendaylight.transportpce.common.ResponseCodes;
21 import org.opendaylight.transportpce.common.StringConstants;
22 import org.opendaylight.transportpce.pce.constraints.PceConstraints;
23 import org.opendaylight.transportpce.pce.networkanalyzer.PceLink;
24 import org.opendaylight.transportpce.pce.networkanalyzer.PceNode;
25 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult;
26 import org.opendaylight.transportpce.pce.networkanalyzer.PceResult.LocalCause;
27 import org.opendaylight.yang.gen.v1.http.org.openroadm.common.state.types.rev191129.State;
28 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.network.rev180226.NodeId;
29 import org.slf4j.Logger;
30 import org.slf4j.LoggerFactory;
31
32 public class PceGraph {
33     /* Logging. */
34     private static final Logger LOG = LoggerFactory.getLogger(PceGraph.class);
35
36     ////////////////////////// for Graph ///////////////////////////
37     // how many paths to bring
38     private int kpathsToBring = 10;
39
40     // max #hops
41     private int mhopsPerPath = 50;
42
43     // input
44     private Map<NodeId, PceNode> allPceNodes = new HashMap<>();
45     private PceNode apceNode = null;
46     private PceNode zpceNode = null;
47     private String serviceType = "";
48
49     PceConstraints pceHardConstraints;
50     PceConstraints pceSoftConstraints;
51
52     // results
53     private PceResult pceResult = null;
54     private List<PceLink> shortestPathAtoZ = null;
55
56     // for path calculation
57     List<GraphPath<String, PceGraphEdge>> allWPaths = null;
58
59     private List<PceLink> pathAtoZ = new ArrayList<>();
60
61     public PceGraph(PceNode aendNode, PceNode zendNode, Map<NodeId, PceNode> allPceNodes,
62             PceConstraints pceHardConstraints, PceConstraints pceSoftConstraints, PceResult pceResult,
63             String serviceType) {
64         super();
65         this.apceNode = aendNode;
66         this.zpceNode = zendNode;
67         this.allPceNodes = allPceNodes;
68         this.pceResult = pceResult;
69         this.pceHardConstraints = pceHardConstraints;
70         this.pceSoftConstraints = pceSoftConstraints;
71         this.serviceType = serviceType;
72
73         LOG.info("In GraphCalculator: A and Z = {} / {} ", aendNode, zendNode);
74         LOG.debug("In GraphCalculator: allPceNodes size {}, nodes {} ", allPceNodes.size(), allPceNodes);
75     }
76
77     public boolean calcPath() {
78
79         LOG.info(" In PCE GRAPH calcPath : K SHORT PATHS algorithm ");
80
81         DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph =
82                 new DefaultDirectedWeightedGraph<>(PceGraphEdge.class);
83         populateWithNodes(weightedGraph);
84         populateWithLinks(weightedGraph);
85
86         if (!runKgraphs(weightedGraph)) {
87             LOG.info("In calcPath : pceResult {}", pceResult);
88             return false;
89         }
90
91         // validate found paths
92         pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
93         for (GraphPath<String, PceGraphEdge> path : allWPaths) {
94             PostAlgoPathValidator papv = new PostAlgoPathValidator();
95             pceResult = papv.checkPath(path, allPceNodes, pceResult, pceHardConstraints, serviceType);
96             LOG.info("In calcPath after PostAlgoPathValidator {} {}",
97                     pceResult.getResponseCode(), ResponseCodes.RESPONSE_OK);
98
99             if (!pceResult.getResponseCode().equals(ResponseCodes.RESPONSE_OK)) {
100                 LOG.info("In calcPath: post algo validations DROPPED the path {}", path);
101                 continue;
102             }
103
104             // build pathAtoZ
105             pathAtoZ.clear();
106             for (PceGraphEdge edge : path.getEdgeList()) {
107                 pathAtoZ.add(edge.link());
108             }
109
110             shortestPathAtoZ = new ArrayList<>(pathAtoZ);
111             if ((StringConstants.SERVICE_TYPE_100GE.equals(serviceType))
112                     || (StringConstants.SERVICE_TYPE_OTU4.equals(serviceType))) {
113                 LOG.info("In calcPath Path FOUND path for wl [{}], min Freq assignment {}, max Freq assignment {},"
114                         + " hops {}, distance per metrics {}, path AtoZ {}",
115                         pceResult.getResultWavelength(), pceResult.getMinFreq(), pceResult.getMaxFreq(),
116                         pathAtoZ.size(), path.getWeight(), pathAtoZ);
117                 break;
118             } else {
119                 // Service is at OTN layer and is relying on a supporting wavelength service
120                 LOG.info("In calcPath Path FOUND path for hops {}, distance per metrics {}, path AtoZ {}",
121                         pathAtoZ.size(), path.getWeight(), pathAtoZ);
122                 break;
123             }
124
125         }
126
127         if (shortestPathAtoZ != null) {
128             LOG.info("In calcPath CHOOSEN PATH for wl [{}], min freq {}, max freq {}, hops {}, path AtoZ {}",
129                     pceResult.getResultWavelength(), pceResult.getMinFreq(), pceResult.getMaxFreq(),
130                     shortestPathAtoZ.size(), shortestPathAtoZ);
131         }
132         LOG.info("In calcPath : pceResult {}", pceResult);
133         return (pceResult.getStatus());
134     }
135
136     private boolean runKgraphs(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
137
138         if (weightedGraph.edgeSet().isEmpty() || weightedGraph.vertexSet().isEmpty()) {
139             return false;
140         }
141         PathValidator<String, PceGraphEdge> wpv = new InAlgoPathValidator();
142
143         // KShortestPaths on weightedGraph
144         KShortestSimplePaths<String, PceGraphEdge> swp =
145             new KShortestSimplePaths<>(weightedGraph, mhopsPerPath, wpv);
146         allWPaths = swp.getPaths(apceNode.getNodeId().getValue(), zpceNode.getNodeId().getValue(), kpathsToBring);
147
148         if (allWPaths.isEmpty()) {
149             LOG.info(" In runKgraphs : algorithm didn't find any path");
150             pceResult.setLocalCause(LocalCause.NO_PATH_EXISTS);
151             pceResult.setRC(ResponseCodes.RESPONSE_FAILED);
152             return false;
153         }
154
155         // debug print
156         for (GraphPath<String, PceGraphEdge> path : allWPaths) {
157             LOG.debug("path Weight: {} : {}", path.getWeight(), path.getVertexList());
158         }
159
160         return true;
161     }
162
163     private boolean validateLinkforGraph(PceLink pcelink) {
164
165         PceNode source = allPceNodes.get(pcelink.getSourceId());
166         PceNode dest = allPceNodes.get(pcelink.getDestId());
167
168         if (source == null) {
169             LOG.error("In addLinkToGraph link source node is null : {}", pcelink);
170             return false;
171         }
172         if (dest == null) {
173             LOG.error("In addLinkToGraph link dest node is null : {}", pcelink);
174             return false;
175         }
176         LOG.debug("In addLinkToGraph link to nodes : {}{} {}", pcelink, source, dest);
177         return true;
178     }
179
180     private void populateWithNodes(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
181         Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
182         while (nodes.hasNext()) {
183             Map.Entry<NodeId, PceNode> node = nodes.next();
184             if (State.InService.equals(node.getValue().getState())) {
185                 weightedGraph.addVertex(node.getValue().getNodeId().getValue());
186                 LOG.debug("In populateWithNodes in node :  {}", node.getValue());
187             }
188         }
189     }
190
191     private boolean populateWithLinks(DefaultDirectedWeightedGraph<String, PceGraphEdge> weightedGraph) {
192
193         Iterator<Map.Entry<NodeId, PceNode>> nodes = allPceNodes.entrySet().iterator();
194         while (nodes.hasNext()) {
195
196             Map.Entry<NodeId, PceNode> node = nodes.next();
197
198             PceNode pcenode = node.getValue();
199             List<PceLink> links = pcenode.getOutgoingLinks();
200
201             LOG.debug("In populateGraph: use node for graph {}", pcenode);
202
203             for (PceLink link : links) {
204                 LOG.debug("In populateGraph node {} : add edge to graph {}", pcenode, link);
205
206                 if (!validateLinkforGraph(link)) {
207                     continue;
208                 }
209                 if (State.InService.equals(link.getState())) {
210                     PceGraphEdge graphLink = new PceGraphEdge(link);
211                     weightedGraph.addEdge(link.getSourceId().getValue(), link.getDestId().getValue(), graphLink);
212
213                     weightedGraph.setEdgeWeight(graphLink, chooseWeight(link));
214                 }
215             }
216         }
217         return true;
218     }
219
220     private double chooseWeight(PceLink link) {
221         // HopCount is default
222         double weight = 1;
223         switch (pceHardConstraints.getPceMetrics()) {
224             case HopCount :
225                 weight = 1;
226                 LOG.debug("In PceGraph HopCount is used as a metrics. {}", link);
227                 break;
228             case PropagationDelay :
229                 weight = link.getLatency();
230                 LOG.debug("In PceGraph PropagationDelay is used as a metrics. {}", link);
231                 if ((("1GE".equals(serviceType)) || ("10GE".equals(serviceType)) || ("ODU4".equals(serviceType)))
232                         && (weight == 0)) {
233                     LOG.warn("PropagationDelay set as metric, but latency is null: is latency set for OTN link {}?",
234                         link);
235                 }
236                 break;
237             // TODO implement IGPMetric and TEMetric - low priority.
238             case IGPMetric :
239             case TEMetric :
240             default:
241                 LOG.warn("In PceGraph {} not implemented. HopCount works as a default",
242                     pceHardConstraints.getPceMetrics());
243                 break;
244         }
245         return weight;
246     }
247
248     public int getKpathsToBring() {
249         return kpathsToBring;
250     }
251
252     public void setKpathsToBring(int kpathsToBring) {
253         this.kpathsToBring = kpathsToBring;
254     }
255
256     public void setMhopsPerPath(int mhopsPerPath) {
257         this.mhopsPerPath = mhopsPerPath;
258     }
259
260     public List<PceLink> getPathAtoZ() {
261         return shortestPathAtoZ;
262     }
263
264     public PceResult getReturnStructure() {
265         return pceResult;
266     }
267
268     public void setConstrains(PceConstraints pceHardConstraintsInput, PceConstraints pceSoftConstraintsInput) {
269         this.pceHardConstraints = pceHardConstraintsInput;
270         this.pceSoftConstraints = pceSoftConstraintsInput;
271     }
272 }