001/******************************************************************************* 002 * Copyright (c) 2017 Pablo Pavon Marino and others. 003 * All rights reserved. This program and the accompanying materials 004 * are made available under the terms of the 2-clause BSD License 005 * which accompanies this distribution, and is available at 006 * https://opensource.org/licenses/BSD-2-Clause 007 * 008 * Contributors: 009 * Pablo Pavon Marino and others - initial API and implementation 010 *******************************************************************************/ 011package com.net2plan.examples.general.offline; 012 013 014import cern.colt.list.tdouble.DoubleArrayList; 015import cern.colt.list.tint.IntArrayList; 016import cern.colt.matrix.tdouble.DoubleFactory2D; 017import cern.colt.matrix.tdouble.DoubleMatrix2D; 018import com.jom.DoubleMatrixND; 019import com.jom.OptimizationProblem; 020import com.net2plan.interfaces.networkDesign.*; 021import com.net2plan.libraries.WDMUtils; 022import com.net2plan.utils.Constants.RoutingType; 023import com.net2plan.utils.InputParameter; 024import com.net2plan.utils.IntUtils; 025import com.net2plan.utils.Pair; 026import com.net2plan.utils.Triple; 027 028import java.util.*; 029 030/** 031 * Algorithm based on an ILP solving the Routing, Spectrum, Modulation Assignment (RSMA) problem with regenerator placement, in flexi (elastic) or fixed grid optical WDM networks, with or without fault tolerance, latency and/or lightpath bidirectionality requisites. 032 * 033 * <p>The input design is assumed to have a WDM layer compatible with {@link com.net2plan.libraries.WDMUtils WDMUtils} Net2Plan 034 * library usual assumptions:</p> 035 * <ul> 036 * <li>Each network node is assumed to be an Optical Add/Drop Multiplexer WDM node</li> 037 * <li>Each network link at WDM layer is assumed to be an optical fiber.</li> 038 * <li>The spectrum in the fibers is assumed to be composed of a number of frequency slots. 039 * In fixed-grid network, each frequency slot would correspond to a wavelength channel. 040 * In flexi-grid networks, it is just a frequency slot, and lightpaths can occupy more than one. In any case, 041 * two lightpaths that use overlapping frequency slots cannot traverse the same fiber, since their signals would mix.</li> 042 * <li>Each traffic demand is a need to transmit an amount of Gbps between two nodes. 043 * A demand traffic can be carried using one or more lightpaths.</li> 044 * </ul> 045 * 046 * <p>Each lightpath produced by the design is returned as a {@code Route} object. Protection lightpaths in 1+1 case 047 * are returned as ProtectionSegment objects attached to the {@code Route}. They represent a set of reserved frequency slots in 048 * a set of fibers, to be used to protect other lightpaths.</p> 049 * 050 * <p>Each lightpath starts and ends in a transponder. The user is able to define a set of available transpoder types, so 051 * the design can create lightpaths using any combination of them. The information user-defined per transponder is:</p> 052 * <ul> 053 * <li>Line rate in Gbps (typically 10, 40, 100 in fixed-grid cases, and other multiples in flexi-grid networks).</li> 054 * <li>Cost</li> 055 * <li>Number of frequency slots occupied (for a given line rate, this depends on the modulation the transponder uses)</li> 056 * <li>Optical reach in km: Maximum allowed length in km of the lightpaths with this transponder. 057 * Higher distances can be reached using signal regenerators.</li> 058 * <li>Cost of a regenerator for this transponder. Regenerators can be placed at intermdiate nodes of the lightpath route, 059 * regenerate its optical signal, and then permit extending its reach. We consider that regenerators cannot change the 060 * frequency slots occupied by the lightpath (that is, they are not capable of wavelength conversion)</li> 061 * </ul> 062 * <p> In addition, the user can force the design to use bidirectional transponders (the usual case). This means that (i) in 063 * each transponder we have the transmission and reception side inseparable (so you cannot e.g. buy just the transmission side), 064 * and (ii) a couple of transponders (of course of the same type) being the end points of a lightpath from node 1 to node 2, 065 * also are used for a lightpath from node 2 to node 1, (iii) note however that the two opposite lightpaths can follow arbitrary routes 066 * (they do not have to traverse the reversed sequence of nodes). This bidirectionality constraint is a common requirement if 067 * the lightpath will be used for carrying IP traffic, since IP assumes that its links (the lightpaths) are bidirectional pipes.</p> 068 * 069 * <p>We assume that all the fibers use the same wavelength grid, composed of a user-defined number of frequency slots. 070 * The user can also select a limit in the maximum propagation delay of a lightpath. </p> 071 * <p>The output design consists in the set of lightpaths to establish, in the 1+1 case also with a 1+1 lightpath each. 072 * Each lightpath is characterized by the transponder type used (which sets its line rate and number of occupied slots in the 073 * traversed fibers), the particular set of contiguous frequency slots occupied, and the set of signal regeneration points (if any). 074 * This information is stored in the {@code Route} and {@code ProtectionSegment} object using the regular methods in WDMUTils, 075 * and can be retrieved in the same form (e.g. by a report showing the WDM network information). 076 * If a feasible solution is not found (one where all the demands are satisfied with the given constraints), a message is shown.</p>. 077 * 078 * <h2>Failure tolerance</h2> 079 * <p>The user can choose among three possibilities for designing the network:</p> 080 * <ul> 081 * <li>No failure tolerant: The lightpaths established should be enough to carry the traffic of all the demands when no failure 082 * occurs in the network, but any losses are accepted if the network suffers failures in links or nodes.</li> 083 * <li>Tolerant to single-SRG (Shared Risk Group) failures with static lightpaths: All the traffic demands should be satisfied using 084 * lightpaths, so that under any single-SRG failure (SRGs are taken from the input design), the surviving lightpaths are enough 085 * to carry the 100% of the traffic. Note that lightpaths are static, in the sense that they are not rerouted when affected by a 086 * failure (they just also fail), and the design should just overprovision the number of lightpaths to establish with that in mind.</li> 087 * <li>1+1 SRG-disjoint protection: This is another form to provide single-SRG failure tolerance. Each lightpath is backed up by 088 * a SRG-disjoint lightpath (returned as a {@code ProtectionSegment} object). The backup lightpath uses the same type of transponder 089 * as the primary (and thus the same line rate, an occupies the same number of slots), its path is SRG-disjoint, and the particular 090 * set of slots occupied can be different. </li> 091 * </ul> 092 * <h2>Optimization targets</h2> 093 * <p>The user can choose between two optimization targets:</p> 094 * <ul> 095 * <li>Minimizing the total cost, given by the transponders and regenerators (if any).</li> 096 * <li>Minimizing congestion at the WDM layer. This means looking for the design that maximizes the number of idle slots 097 * in the bottleneck fiber (the one with less idle frequency slots). </li> 098 * </ul> 099 * <h2>Use cases</h2> 100 * <p>This algorithm is quite general, and fits a number of use cases designing WDM networks, for instance:</p> 101 * <ul> 102 * <li>Single line rate, fixed grid networks: Then, one single type of transponder will be available, which occupies one frequency slot</li> 103 * <li>Mixed-Line Rate fixed-grid networks: In this case, several transponders can be available at different line rates and with different optical 104 * reaches. However, all of them occupy one slot (one wavelength channel)</li> 105 * <li>Single line rate, flexi-grid networks using varying-modulation transponders: Several transponders are available (or the same 106 * transponder with varying configurations), all of them with the same line rate, but thanks to the different usable modulations 107 * they can have different optical reaches and/or number of occupied slots.</li> 108 * <li>Multiple line rate, flexi-grid networks using Bandwidth Variable Transponders: Here, it is possible to use different transponders 109 * with different line rates, e.g. to reflect more sophisticated transponders which can have different configurations, varying its line rate, 110 * optical reach, and number of occupied slots.</li> 111 * <li>...</li> 112 * </ul> 113 * <h2>Some details of the algorithm</h2> 114 * <p>The algorithm is based on solving a set of MILPs (Mixed Integer Linear Programs) interfacing from JOM to the user-defined 115 * solver. The algorithm uses a flow-path formulation, where a number of candidate paths are pre-computed for each demand. The 116 * user-defined parameter {@code k} limits the maximum number of paths computed per demand. In the 1+1 case, the usable SRG-disjoint 117 * path pairs for each demand are computed from the candidate paths. Increasing the number of paths {@code k} also increases 118 * the computational complexity of the algorithm, but can produce better solutions. In some occasions, a low {@code k} number is the 119 * reason for the algorithm failing in finding a feasible solution.</p> 120 * <p>The details of the algorithm will be provided in a publication currently under elaboration.</p> 121 * 122 * @net2plan.keywords JOM, WDM 123 * @net2plan.inputParameters 124 * @author Pablo Pavon-Marino 125 */ 126@SuppressWarnings("unchecked") 127public class Offline_ipOverWdm_routingSpectrumAndModulationAssignmentILPNotGrooming implements IAlgorithm 128{ 129 private InputParameter k = new InputParameter ("k", (int) 5 , "Maximum number of admissible paths per input-output node pair" , 1 , Integer.MAX_VALUE); 130 private InputParameter solverName = new InputParameter ("solverName", "#select# glpk ipopt xpress cplex", "The solver name to be used by JOM. GLPK and IPOPT are free, XPRESS and CPLEX commercial. GLPK, XPRESS and CPLEX solve linear problems w/w.o integer contraints. IPOPT is can solve nonlinear problems (if convex, returns global optimum), but cannot handle integer constraints"); 131 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 132 private InputParameter maxSolverTimeInSeconds = new InputParameter ("maxSolverTimeInSeconds", (double) -1 , "Maximum time granted to the solver to solve the problem. If this time expires, the solver returns the best solution found so far (if a feasible solution is found)"); 133 private InputParameter numFrequencySlotsPerFiber = new InputParameter ("numFrequencySlotsPerFiber", (int) 40 , "Number of wavelengths per link" , 1, Integer.MAX_VALUE); 134 private InputParameter transponderTypesInfo = new InputParameter ("transponderTypesInfo", "10 1 1 9600 1" , "Transpoder types separated by \";\" . Each type is characterized by the space-separated values: (i) Line rate in Gbps, (ii) cost of the transponder, (iii) number of slots occupied in each traversed fiber, (iv) optical reach in km (a non-positive number means no reach limit), (v) cost of the optical signal regenerator (regenerators do NOT make wavelength conversion ; if negative, regeneration is not possible)."); 135 private InputParameter ipLayerIndex = new InputParameter ("ipLayerIndex", (int) 1 , "Index of the IP layer (-1 means default layer)"); 136 private InputParameter wdmLayerIndex = new InputParameter ("wdmLayerIndex", (int) 0 , "Index of the WDM layer (-1 means default layer)"); 137 private InputParameter networkRecoveryType = new InputParameter ("networkRecoveryType", "#select# not-fault-tolerant single-srg-tolerant-static-lp 1+1-srg-disjoint-lps" , "Establish if the design should be tolerant or not to single SRG failures (SRGs are as defined in the input NetPlan). First option is that the design should not be fault tolerant, the second means that failed lightpaths are not recovered, but an overprovisioned should be made so enough lightpaths survive to carry all the traffic in every failure. The third means that each lightpath is 1+1 protceted by a SRG-disjoint one, that uses the same transponder"); 138 private InputParameter optimizationTarget = new InputParameter ("optimizationTarget", "#select# min-cost maximin-fiber-number-idle-slots" , "Type of optimization target. Choose among minimize the network cost given by the su mof the transponders cost, and maximize the number of idle frequency slots in the fiber with less idle frequency slot"); 139 private InputParameter maxPropagationDelayMs = new InputParameter ("maxPropagationDelayMs", (double) -1 , "Maximum allowed propagation time of a lighptath in miliseconds. If non-positive, no limit is assumed"); 140 private InputParameter bidirectionalTransponders = new InputParameter ("bidirectionalTransponders", true , "If true, the transponders used are bidirectional. Then, the number of lightpaths of each type from node 1 to node 2, equals the number of lightpahts from 2 to 1 (see that both directions can have different routes and slots)"); 141 private NetworkLayer wdmLayer, ipLayer; 142 private Demand.IntendedRecoveryType recoveryTypeNewLps; 143 144 @Override 145 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 146 { 147 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 148 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 149 150 /* Create a two-layer IP over WDM design if the input is single layer */ 151 if (netPlan.getNumberOfLayers() == 1) 152 { 153 this.wdmLayer = netPlan.getNetworkLayerDefault(); 154 netPlan.setDemandTrafficUnitsName("Gbps"); 155 netPlan.setLinkCapacityUnitsName("Frequency slots"); 156 this.ipLayer = netPlan.addLayer("IP" , "IP layer" , "Gbps" , "Gbps" , null , null); 157 for (Demand wdmDemand : netPlan.getDemands(wdmLayer)) 158 netPlan.addDemand(wdmDemand.getIngressNode(), wdmDemand.getEgressNode() , wdmDemand.getOfferedTraffic() , RoutingType.SOURCE_ROUTING , wdmDemand.getAttributes() , ipLayer); 159 } 160 else 161 { 162 this.wdmLayer = wdmLayerIndex.getInt () == -1? netPlan.getNetworkLayerDefault() : netPlan.getNetworkLayer(wdmLayerIndex.getInt ()); 163 this.ipLayer = ipLayerIndex.getInt () == -1? netPlan.getNetworkLayerDefault() : netPlan.getNetworkLayer(ipLayerIndex.getInt ()); 164 } 165 166 final NetworkLayer wdmLayer = wdmLayerIndex.getInt () == -1? netPlan.getNetworkLayerDefault() : netPlan.getNetworkLayer(wdmLayerIndex.getInt ()); 167 168 /* Basic checks */ 169 final int N = netPlan.getNumberOfNodes(); 170 final int Ewdm = netPlan.getNumberOfLinks(wdmLayer); 171 final int Dip = netPlan.getNumberOfDemands(ipLayer); 172 final int S = numFrequencySlotsPerFiber.getInt(); 173 if (N == 0 || Ewdm == 0 || Dip == 0) throw new Net2PlanException("This algorithm requires a topology with links and a demand set"); 174 175 if (networkRecoveryType.getString().equals("not-fault-tolerant") || networkRecoveryType.getString().equals("single-srg-tolerant-static-lp")) 176 recoveryTypeNewLps = Demand.IntendedRecoveryType.NONE; 177 else if (networkRecoveryType.getString().equals("1+1-srg-disjoint-lps")) 178 recoveryTypeNewLps = Demand.IntendedRecoveryType.PROTECTION_REVERT; 179 else throw new Net2PlanException ("Wrong input parameters"); 180 181 /* Store transpoder info */ 182 WDMUtils.TransponderTypesInfo tpInfo = new WDMUtils.TransponderTypesInfo(transponderTypesInfo.getString()); 183 final int T = tpInfo.getNumTypes(); 184 185 /* Remove all routes in current netPlan object. Initialize link capacities and attributes, and demand offered traffic */ 186 netPlan.removeAllLinks (ipLayer); 187 netPlan.removeAllDemands (wdmLayer); 188 netPlan.removeAllMulticastDemands(wdmLayer); 189 190 /* Compute the candidate path list of possible paths */ 191 final SortedMap<Pair<Node,Node>,List<List<Link>>> cpl = netPlan.computeUnicastCandidatePathList(netPlan.getVectorLinkLengthInKm(wdmLayer) , k.getInt(), tpInfo.getMaxOpticalReachKm() , -1, maxPropagationDelayMs.getDouble(), -1, -1, -1 , null , wdmLayer); 192 final SortedMap<Pair<Node,Node>,List<Pair<List<Link>,List<Link>>>> cpl11 = networkRecoveryType.getString().equals("1+1-srg-disjoint-lps")? NetPlan.computeUnicastCandidate11PathList(cpl,0) : null; 193 194 /* Compute the CPL, adding the routes */ 195 /* 1+1 case: as many routes as 1+1 valid pairs (then, the same sequence of links can be in more than one Route). The route index and segment index are the same (1+1 pair index) */ 196 /* rest of the cases: each sequence of links appears at most once */ 197 Map<Link,Double> linkLengthMap = new HashMap<Link,Double> (); for (Link e : netPlan.getLinks(wdmLayer)) linkLengthMap.put(e , e.getLengthInKm()); 198 final int maximumNumberOfPaths = T*k.getInt()*Dip; 199 List<Integer> transponderType_p = new ArrayList<Integer> (maximumNumberOfPaths); 200 List<Double> cost_p = new ArrayList<Double> (maximumNumberOfPaths); 201 List<Double> lineRate_p = new ArrayList<Double> (maximumNumberOfPaths); 202 List<Integer> numSlots_p = new ArrayList<Integer> (maximumNumberOfPaths); 203 List<List<Link>> seqLinks_p = new ArrayList<List<Link>> (maximumNumberOfPaths); 204 List<List<Link>> seqLinks2_p = cpl11 == null? null : new ArrayList<List<Link>> (maximumNumberOfPaths); 205 List<int []> regPositions_p = new ArrayList<int []> (maximumNumberOfPaths); 206 List<int []> regPositions2_p = new ArrayList<int []> (maximumNumberOfPaths); 207 List<Demand> ipDemand_p = new ArrayList<Demand> (maximumNumberOfPaths); 208 for (Demand ipDemand : netPlan.getDemands(ipLayer)) 209 { 210 ipDemand.setRoutingType(RoutingType.SOURCE_ROUTING); 211 boolean atLeastOnePathOrPathPair = false; 212 for (int t = 0 ; t < T ; t ++) 213 { 214 final Pair<Node,Node> nodePair = Pair.of(ipDemand.getIngressNode() , ipDemand.getEgressNode()); 215 final double regeneratorCost = tpInfo.getRegeneratorCost(t); 216 final boolean isRegenerable = regeneratorCost >= 0; 217 for (Object sp : cpl11 != null? cpl11.get(nodePair) : cpl.get(nodePair)) 218 { 219 List<Link> firstPath = (cpl11 == null)? ((List<Link>) sp) : ((Pair<List<Link>,List<Link>>) sp).getFirst(); 220 List<Link> secondPath = (cpl11 == null)? null : ((Pair<List<Link>,List<Link>>) sp).getSecond (); 221 if (!isRegenerable && (getLengthInKm(firstPath) > tpInfo.getOpticalReachKm(t))) break; 222 if (secondPath != null) if (!isRegenerable && (getLengthInKm(secondPath) > tpInfo.getOpticalReachKm(t))) break; 223 224 final int [] regPositions1 = isRegenerable? WDMUtils.computeRegeneratorPositions(firstPath , tpInfo.getOpticalReachKm(t)) : new int [firstPath.size()]; 225 final int [] regPositions2 = cpl11 == null? null : isRegenerable? WDMUtils.computeRegeneratorPositions(secondPath , tpInfo.getOpticalReachKm(t)) : new int [secondPath.size()]; 226 final int numRegeneratorsNeeded = !isRegenerable? 0 : (int) IntUtils.sum(regPositions1) + (secondPath == null? 0 : (int) IntUtils.sum(regPositions2)) ; 227 final double costOfLightpathOr11Pair = tpInfo.getCost(t) * (cpl11 != null? 2 : 1) + (tpInfo.getRegeneratorCost(t) * numRegeneratorsNeeded); 228 229 cost_p.add (costOfLightpathOr11Pair); 230 transponderType_p.add (t); 231 lineRate_p.add(tpInfo.getLineRateGbps(t)); 232 numSlots_p.add(tpInfo.getNumSlots(t)); 233 ipDemand_p.add(ipDemand); 234 seqLinks_p.add(firstPath); 235 regPositions_p.add(regPositions1); 236 if (cpl11 != null) { seqLinks2_p.add(secondPath); regPositions2_p.add(regPositions2); } 237 atLeastOnePathOrPathPair = true; 238 } 239 } 240 if (!atLeastOnePathOrPathPair) throw new Net2PlanException ("There are no possible routes (or 1+1 pairs) for a demand (" + ipDemand + "). The topology may be not connected enough, or the optical reach may be too small"); 241 } 242 final int P = transponderType_p.size(); // one per potential sequence of links (or 1+1 pairs of sequences) and transponder 243 244 /* Compute some important matrices for the formulation */ 245 DoubleMatrix2D A_dp = DoubleFactory2D.sparse.make(Dip,P); /* 1 is path p is assigned to demand d */ 246 DoubleMatrix2D A_ep = DoubleFactory2D.sparse.make(Ewdm,P); /* 1 if path (or primary path in 1+1) p travserses link e */ 247 DoubleMatrix2D A2_ep = DoubleFactory2D.sparse.make(Ewdm,P); /* 1 if backup path of pair p traverses link e */ 248 DoubleMatrix2D A_psrg = DoubleFactory2D.sparse.make(P,netPlan.getNumberOfSRGs()); /* 1 if path p fails when srg fails */ 249 double [][] feasibleAssignment_ps = new double [P][S]; 250 DoubleMatrix2D [] A_n1Mn2p = new DoubleMatrix2D [T]; 251 if (bidirectionalTransponders.getBoolean()) 252 for (int t = 0 ; t < T ; t ++) A_n1Mn2p [t] = DoubleFactory2D.sparse.make(N*N , P); 253 for (int p = 0 ; p < P ; p ++) 254 { 255 A_dp.set(ipDemand_p.get(p).getIndex() , p , 1.0); 256 for (Link e : seqLinks_p.get(p)) A_ep.set (e.getIndex() , p , 1.0); 257 if (cpl11 != null) for (Link e : seqLinks2_p.get(p)) A2_ep.set (e.getIndex() , p , 1.0); 258 if (networkRecoveryType.getString().equals("single-srg-tolerant-static-lp")) 259 for (Link e : seqLinks_p.get(p)) 260 { 261 for (SharedRiskGroup srg : e.getSRGs()) A_psrg.set(p,srg.getIndex(),1.0); 262 for (SharedRiskGroup srg : e.getOriginNode().getSRGs()) A_psrg.set(p,srg.getIndex(),1.0); 263 for (SharedRiskGroup srg : e.getDestinationNode().getSRGs()) A_psrg.set(p,srg.getIndex(),1.0); 264 } 265 for (int s = 0; s < S + 1 - numSlots_p.get(p) ; s ++) 266 feasibleAssignment_ps [p][s] = 1; 267 if (bidirectionalTransponders.getBoolean()) 268 { 269 final int t = transponderType_p.get(p); 270 final int n1 = ipDemand_p.get(p).getIngressNode().getIndex(); 271 final int n2 = ipDemand_p.get(p).getEgressNode().getIndex(); 272 final int nLower = n1 < n2? n1 : n2; 273 final int nGreater = n1 > n2? n1 : n2; 274 A_n1Mn2p [t].set(nLower + N * nGreater , p , nLower == n1? 1.0 : -1.0); 275 } 276 } 277 278 279 /* Create the optimization problem object (JOM library) */ 280 OptimizationProblem op = new OptimizationProblem(); 281 282 /* Add the decision variables to the problem */ 283 /* p is the route index and s the initial slot. In 1+1, p is the 1+1 pair index (equal to the route and segment indexes), s the initial slot of the primary (route) */ 284 op.addDecisionVariable("x_ps", true, new int[] {P, S}, new DoubleMatrixND (new int [] {P,S}) , new DoubleMatrixND (feasibleAssignment_ps)); /* 1 if lightpath d(p) is routed through path p in wavelength w */ 285 if (cpl11 != null) 286 /* p is the 1+1 pair index (equal to the route and segment indexes), s the initial slot of the backup (segment) */ 287 op.addDecisionVariable("x2_ps", true, new int[] {P, S}, new DoubleMatrixND (new int [] {P,S}) , new DoubleMatrixND (feasibleAssignment_ps)); /* 1 if lightpath d(p) is routed through path p in wavelength w */ 288 289 /* Set some input parameters */ 290 op.setInputParameter("S", S); 291 op.setInputParameter("h_d", netPlan.getVectorDemandOfferedTraffic(ipLayer), "row"); 292 op.setInputParameter("rate_p", lineRate_p , "row"); 293 op.setInputParameter("c_p", cost_p , "row"); 294 op.setInputParameter("A_dp", A_dp); 295 op.setInputParameter("A_ep", A_ep); // in 1+1, only occupation of the primaries (p is the 1+1 pair index, equal to route and segment indexes) 296 if (cpl11 != null) 297 op.setInputParameter("A2_ep", A2_ep); 298 299 /* Sets the objective function */ 300 if (optimizationTarget.getString().equals("min-cost")) 301 op.setObjectiveFunction("minimize", "sum(c_p * x_ps)"); /* sum_ps (c_p ยท x_ps). In 1+1 the cost is multiplied by two */ 302 else if (optimizationTarget.getString().equals("maximin-fiber-number-idle-slots")) 303 { 304 op.addDecisionVariable("u", true, new int[] {1, 1} , 0 , S); /* Number of idle slots in the worst case fiber */ 305 op.setObjectiveFunction("maximize", "u"); 306 op.setInputParameter("numSlots_p", numSlots_p , "row"); 307 if (cpl11 == null) 308 op.addConstraint("sum(A_ep * diag(numSlots_p) * x_ps , 2) <= S - u"); 309 else 310 op.addConstraint("sum(A_ep * diag(numSlots_p) * x_ps + A2_ep * diag(numSlots_p) * x2_ps , 2) <= S - u"); 311 } 312 313 /* Carry enough traffic in each demand to satisfy the minimum traffic to carry (no failure state) */ 314 /* sum_{s , p \in P_d} rate_p x_ps >= h_d, for each d */ 315 op.addConstraint("A_dp * diag (rate_p) * x_ps * ones([S; 1]) >= h_d'"); /* each lightpath d: is carried in exactly one p-w --> sum_{p in P_d, w} x_dp <= 1, for all d */ 316 if (cpl11 != null) 317 op.addConstraint("sum(x_ps,2) == sum(x2_ps,2)"); /* The number of lightpath in primary of 1+1 pair p and inthe backup is the same */ 318 319 /* (no 1+1, but fault tolerant) Carry enough traffic in each demand to satisfy the minimum traffic to carry, in all of the single-SRG failure states */ 320 if (networkRecoveryType.getString().equals("single-srg-tolerant-static-lp")) 321 { 322 /* sum_{s , p \in P_d, p survives} rate_p x_ps >= h_d, for each d, for each srg */ 323 for (int srg = 0 ; srg < A_psrg.columns() ; srg ++) 324 { 325 /* Asrg_pp_ Diagonal pxp matrix, with a one for surviving paths */ 326 DoubleMatrix2D Asrg_pp = DoubleFactory2D.sparse.make(P,P); 327 for (int p = 0; p < P ; p ++) Asrg_pp.set(p,p,1 - A_psrg.get(p , srg)); 328 op.setInputParameter("Asrg_pp" , Asrg_pp); 329 op.addConstraint("A_dp * Asrg_pp * diag (rate_p) * x_ps * ones([S; 1]) >= h_d'"); /* each lightpath d: is carried in exactly one p-w --> sum_{p in P_d, w} x_dp <= 1, for all d */ 330 } 331 } 332 333 /* Frequency-slot clashing */ 334 /* \sum_t \sum_{p \in P_e, sinit {s-numSlots(t),s} x_ps <= 1, for each e, s */ 335 String constraintString = ""; 336 for (int t = 0; t < T ; t ++) 337 { 338 { 339 final String name_At_pp = "A" + Integer.toString(t) + "_pp"; 340 final String name_At_s1s2 = "A" + Integer.toString(t) + "_s1s2"; 341 /* At_pp, diagonal matrix, 1 if path p is associated to a transponder of type t */ 342 DoubleMatrix2D At_pp = DoubleFactory2D.sparse.make(P,P); 343 int p = 0; for (int type : transponderType_p) { if (type == t) At_pp.set(p,p,1.0); p++; } 344 /* At_s1s2, upper triangular matrix, 1 if a transponder of type with initial slot s1, occupied slots s2 (depends on number of slots occupied) */ 345 DoubleMatrix2D At_s1s2 = DoubleFactory2D.sparse.make(S,S); 346 for (int s1 = 0 ; s1 < S ; s1 ++) 347 for (int cont = 0 ; cont < tpInfo.getNumSlots(t) ; cont ++) 348 if (s1 - cont >= 0) At_s1s2.set(s1-cont,s1,1.0); 349 op.setInputParameter(name_At_pp, At_pp); 350 op.setInputParameter(name_At_s1s2, At_s1s2); 351 constraintString += (t == 0? "" : " + ") + "( A_ep * " + name_At_pp + " * x_ps * " + name_At_s1s2 + " ) "; 352 } 353 354 if (cpl11 != null) // sum also the slots occupied by the 355 { 356 final String name_A2t_pp = "A2" + Integer.toString(t) + "_pp"; 357 final String name_A2t_s1s2 = "A2" + Integer.toString(t) + "_s1s2"; 358 /* At_pp, diagonal matrix, 1 if path p is associated to a transponder of type t */ 359 DoubleMatrix2D A2t_pp = DoubleFactory2D.sparse.make(P,P); 360 int p = 0; for (int type : transponderType_p) { if (type == t) A2t_pp.set(p,p,1.0); p++; } 361 /* At_s1s2, upper triangular matrix, 1 if a transponder of type with initial slot s1, occupied slots s2 (depends on number of slots occupied) */ 362 DoubleMatrix2D A2t_s1s2 = DoubleFactory2D.sparse.make(S,S); 363 for (int s1 = 0 ; s1 < S ; s1 ++) 364 for (int cont = 0 ; cont < tpInfo.getNumSlots(t) ; cont ++) 365 if (s1 - cont >= 0) A2t_s1s2.set(s1-cont,s1,1.0); 366 op.setInputParameter(name_A2t_pp, A2t_pp); 367 op.setInputParameter(name_A2t_s1s2, A2t_s1s2); 368 constraintString += " + ( A2_ep * " + name_A2t_pp + " * x2_ps * " + name_A2t_s1s2 + " ) "; 369 } 370 } 371 op.addConstraint(constraintString + " <= 1"); /* wavelength-clashing constraints --> sum_{p in P_e, w} x_pw <= 1, for all e,w */ 372 373 /* Bidirectional constraints */ 374 if (bidirectionalTransponders.getBoolean()) 375 { 376 for (int t = 0 ; t < T ; t ++) 377 { 378 op.setInputParameter("At_n1Mn2p" , A_n1Mn2p [t]); 379 if (cpl11 != null) 380 op.addConstraint("sum (At_n1Mn2p * (x_ps + x2_ps) , 2) == 0"); 381 else 382 op.addConstraint("sum (At_n1Mn2p * x_ps , 2) == 0"); 383 } 384 } 385 386 /* Call the solver to solve the problem */ 387 op.solve(solverName.getString(), "solverLibraryName", solverLibraryName.getString() , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble()); 388 389 /* If a feasible solution was not found, quit (this may also happen if after the maximum solver time no feasible solution is found) */ 390 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 391 392 /* Retrieve the optimum solutions */ 393 DoubleMatrix2D x_ps = op.getPrimalSolution("x_ps").view2D(); 394 DoubleMatrix2D x2_ps = cpl11 == null? null : op.getPrimalSolution("x2_ps").view2D(); 395 396 /* Create the lightpaths according to the solutions given */ 397 WDMUtils.setFibersNumFrequencySlots(netPlan , numFrequencySlotsPerFiber.getInt() , wdmLayer); 398 IntArrayList slots = new IntArrayList (); DoubleArrayList vals = new DoubleArrayList (); 399 IntArrayList slots2 = new IntArrayList (); DoubleArrayList vals2 = new DoubleArrayList (); 400 for (int p = 0; p < P ; p ++) 401 { 402 slots.clear(); vals.clear(); 403 x_ps.viewRow(p).getNonZeros(slots , vals); 404 if (cpl11 != null) 405 { 406 slots2.clear(); vals.clear(); x2_ps.viewRow(p).getNonZeros(slots2 , vals2); 407 if (slots.size() != slots2.size()) throw new RuntimeException ("Bad"); 408 } 409 if (slots.size() == 0) continue; 410 411 final Demand ipDemand = ipDemand_p.get(p); 412 for (int cont = 0 ; cont < slots.size() ; cont ++) 413 { 414 final int s = slots.get (cont); 415 final Demand newWDMDemand = netPlan.addDemand(ipDemand.getIngressNode() , ipDemand.getEgressNode() , 416 lineRate_p.get(p) , RoutingType.SOURCE_ROUTING , null , wdmLayer); 417 final Route r = WDMUtils.addLightpath(newWDMDemand , new WDMUtils.RSA(seqLinks_p.get(p) , s , numSlots_p.get(p) , regPositions_p.get(p)) , lineRate_p.get(p)); 418 final Link ipLink = newWDMDemand.coupleToNewLinkCreated(ipLayer); 419 final double ipTrafficToCarry = Math.min(lineRate_p.get(p) , ipDemand.getBlockedTraffic()); 420 netPlan.addRoute(ipDemand , ipTrafficToCarry , ipTrafficToCarry , Arrays.asList(ipLink), null); 421 if (cpl11 != null) 422 { 423 final int s2 = slots2.get(cont); 424 final Route backupRoute = WDMUtils.addLightpath(newWDMDemand , new WDMUtils.RSA(seqLinks2_p.get(p) , s2 , numSlots_p.get(p) , regPositions2_p.get(p)) , 0); 425 r.addBackupRoute(backupRoute); 426 } 427 } 428 } 429 430 WDMUtils.checkResourceAllocationClashing(netPlan,true,true,wdmLayer); 431 432 return "Ok!"; 433 } 434 435 private static double getLengthInKm (Collection<Link> r) { double res = 0; for (Link e : r) res += e.getLengthInKm(); return res; } 436 437 @Override 438 public String getDescription() 439 { 440 return "Algorithm based on an ILP solving the Routing, Spectrum, Modulation Assignment (RSMA) problem with regenerator placement, in flexi (elastic) or fixed grid optical WDM networks, with or without fault tolerance, latency and/or lightpath bidirectionality requisites (see the Javadoc for details)."; 441 } 442 443 @Override 444 public List<Triple<String, String, String>> getParameters() 445 { 446 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 447 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 448 } 449}